Python线程的隐晦之处

记几点python多线程使用里需要注意的地方。

thread.stack_size([size])

这是module thread提供的接口,该函数每次调用时都会设置stack size,不加参数就设置stack size为0,也就是使用系统默认值,返回值是之前stack size的“旧值”。不要以为不加参数仅仅是返回stack size。

thread._local, _threading_local, threading.local

thread._local和_threading_local是原始实现, threading提供的只是个alias。mannual page: link.

_local()每次都会产生一个全新的localobject,实现方式是新建一个localobject,内部封装一个dict,然后对localobject的属性查找都在封装的dict里进行,同时dict也以threadid为key存储在PyThreadState/threading.Thread的dict属性里。没啥用。
使用过程中需要由用户持有对localobject的引用,一旦释放localobject也就被析构了,内部存储的数据也会被析构,也就是不能像以下代码里这样用:

1
2
3
4
5
6
7
8
9
10
def func_a():
tss =thread._local()
tss.var = tss.var + 1
def func_b():
tss = thread._local()
print tss.var
def thread_proc():
while True:
func_a()
func_b()

也就是他无法提供一个线程级的__builtins__ namespace空间。thread._local支持的功能用户可以用更加清晰的方式自己实现。

基于linux实现的thread module是detach的。

其他系统有没有detach这个概念不清楚了。

threading的线程安全性。

我竟然在说线程库的线程安全性(囧
每个threading.Thread()是有个thread-name的,如果初始化参数没有提供会使用如下函数进行生成:

1
2
3
4
5
6
# file: threading.py
_counter = 0
def _newname(template="Thread-%d"):
global _counter
_counter = _counter + 1
return template % _counter

threading是python实现的,这段代码也不是线程安全的,生成的thread-name有可能重复。所以还是自己设置thread name吧。
可以执行这个脚本测下,输出的thread name是有重复的,我的测试版本是cpython 2.7.5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import threading
import time
import sys

sys.setcheckinterval(1)

class MyThread(threading.Thread):
def __init__(self, level):
threading.Thread.__init__(self)
self.level = level
def run(self):
print self.getName()
if self.level > 8:
return
thread_a = MyThread(self.level+1)
thread_b = MyThread(self.level+1)
thread_a.start()
thread_b.start()

thread = MyThread(1)
thread.start()

time.sleep(2)

###importing in threaded code
from mannual, link.

Firstly, other than in the main module, an import should not have the side effect of spawning a new thread and then waiting for that thread in any way. Failing to abide by this restriction can lead to a deadlock if the spawned thread directly or indirectly attempts to import a module.

这条说的是import的时候,要导入的module如果另起一个线程并等待该线程做某些事情,同时该线程里又要执行import操作,这样会导致死锁,main thread也不行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// file: import.c
PyObject *
PyImport_ImportModuleLevel(char *name, PyObject *globals, PyObject *locals,
PyObject *fromlist, int level)
{
PyObject *result;
lock_import();
result = import_module_level(name, globals, locals, fromlist, level);
if (unlock_import() < 0) {
Py_XDECREF(result);
PyErr_SetString(PyExc_RuntimeError,
"not holding the import lock");
return NULL;
}
return result;
}

这是cpython的import功能实现代码,虚拟机经过一系列调用到这个函数真正开始import操作。其中的lock_import() & unlock_import()实现了reentrant lock的功能。原因很清楚,虚拟机是字节码级别的中断,该函数是import_name的实现,可以认为是原子的,函数里加的锁不会随着GIL的释放而释放。
死锁模拟代码:link

Secondly, all import attempts must be completed before the interpreter starts shutting itself down. This can be most easily achieved by only performing imports from non-daemon threads created through the threading module. Daemon threads and threads created directly with the thread module will require some other form of synchronization to ensure they do not attempt imports after system shutdown has commenced. Failure to abide by this restriction will lead to intermittent exceptions and crashes during interpreter shutdown (as the late imports attempt to access machinery which is no longer in a valid state).

这个说的比较清楚了。

libchan实现分析

libchan是docker衍生出来的子模块,用来在goroutine间、进程间、机器间提供相同的类似go channel的通信方式,每个channal是单工的,方便程序从多goroutine到多进程再到多机的扩展。使用上跟linux pipe类似。

项目地址: https://github.com/docker/libchan
代码版本:commit 1e141b35ee

这是项目里提到的功能:

  1. Simple message passing
  2. Synchronization for concurrent programming
  3. Nesting: channels can send channels
    1/3是可以理解的,2有一点疑问,可以参考项目issue里的讨论。

使用方法参考项目里的demo: https://github.com/docker/libchan/tree/master/examples/rexec

接口定义

项目里目前提供了基于tcp/spdy和inmem两种实现,每种实现只需实现以下接口即可:

1
2
3
4
5
6
7
8
9
10
11
type Transport interface {
NewSendChannel() (Sender, error)
WaitReceiveChannel() (Receiver, error)
}
type Sender interface {
Send(message interface{}) error
Close() error
}
type Receiver interface {
Receive(message interface{}) error
}

inmem没有提供Transport,是通过Pipe()函数成生的sender & receiver,因此spdy/inmen的实现在channel初始化的时候稍有不同。

可打包传输的数据类型

数据传输使用github.com/dmcgowan/go/codec进行编码,打包格式用的msgpack。
codec默认支持以下数据类型:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// file: https://github.com/dmcgowan/go/blob/master/codec/encode.go
// encDriver abstracts the actual codec (binc vs msgpack, etc)
type encDriver interface {
isBuiltinType(rt uintptr) bool
encodeBuiltin(rt uintptr, v interface{})
encodeNil()
encodeInt(i int64)
encodeUint(i uint64)
encodeBool(b bool)
encodeFloat32(f float32)
encodeFloat64(f float64)
encodeExtPreamble(xtag byte, length int)
encodeArrayPreamble(length int)
encodeMapPreamble(length int)
encodeString(c charEncoding, v string)
encodeSymbol(v string)
encodeStringBytes(c charEncoding, v []byte)
//TODO
//encBignum(f *big.Int)
//encStringRunes(c charEncoding, v []rune)
}

codec支持扩展,可以注册其他数据类型的编解码句柄。libchan扩展支持Sender/Receiver/io.ReadWriteCloser/io.ReadCloser/io.WriteCloser的打包传输。
TCPConn & UDPConn属于io.ReadWriteCloser类型,spdy实现只能传输建立在sender&receiver所在主机之间的连接。

io对象传输的实现流程是:

  • sender端需要打包发送io句柄A
  • 在sender&receiver之间建立通信管道P(P-Sender, P-Receiver),inmem、spdy分别使用net.Pipe和spdy.stream建立。
  • sender起goroutine在A & P-Sender间进行数据拷贝,发送管道P的ID,receiver端对P-receiver进行读写。

操作完成后的情况如下图:

###代码分析

####inmem
每一对sender&receiver都有与之关联的一个session数据结构,用来管理通过该chan传输的sender、receiver、io对象等。

1
2
3
4
5
6
7
8
9
10
11
12
type streamSession struct {
pipeLock sync.Mutex
pipeCount uint64
pipeReaders map[uint64]*io.PipeReader
pipeWriters map[uint64]*io.PipeWriter

handler codec.Handle

referenceLock sync.Mutex
referenceID uint64
byteStreams map[uint64]*byteStream
}

handler是一个codec编解码句柄。
io对象的传输是通过net.Pipe()创建的管道和sender端的proxy实现,IO通道存储在byteStreams字段里,net.Pipe()返回两个句柄,对应两个byteStream对象,分别存储在map[ref_ID] map[ref_ID+1]里,本地使用map[ref_ID]进行读写,传输ref_ID+1给对端,对端使用map[ref_ID+1]的对象读写。
io.ReadClose & io.WriteClose & io.ReadWriteCloser实现方式相同,只是在sender端起的proxy routine不同。byteStream是可读写的,根据存储byteStream对象的字段类型的不同会表现出只读、只写、读写的不同特征。

Sender & Receiver通过io.Pipe()传输数据,返回的通道是单工的,读写两端分别存储在pipeReaders & pipeWriters字段里。S & R传输处理流程类似,比如senderA.send(otherB),如果senderB属于senderA的session,则直接传输对应的map-key,如果不是则新建一个io.Pipe,通过goroutine io.copy实现转发。

接下来分析下io.ReadWriteCloser、Sender对象编码传输、解码使用的流程。

#####临时对象构造
首先对要传输的对象构造出来一个临时的拷贝,其中的io.ReadWriteCloser/Sender转换成内部对应的bytesStream对象和同session的Sender,如有需要,转发的proxy都已启动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (w *pipeSender) copyValue(v interface{}) (interface{}, error) {
switch val := v.(type) {
...
case *pipeSender:
if val.session != w.session {
return w.copySender(val)
}
...
case io.ReadWriteCloser:
return w.copyByteStream(val)
...
}
return v, nil
}

copyByteStream行为是在该session内新建一个net.Pipe,然后启动转发的proxy-routine。newByteStream()创建一对byteStream对象代表net.Pipe的两端,存储在byteStreams字段里,id分别为referenceID和referenceID+1,referenceID+1给对端使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func (w *pipeSender) copyByteStream(stream io.ReadWriteCloser) (io.ReadWriteCloser, error) {
streamCopy, err := w.session.newByteStream()
if err != nil {
return nil, err
}
go func() {
io.Copy(streamCopy, stream)
streamCopy.Close()
}()
go func() {
io.Copy(stream, streamCopy)
stream.Close()
}()
return streamCopy, nil
}

func (s *streamSession) newByteStream() (io.ReadWriteCloser, error) {
c1, c2 := net.Pipe()
bs := &byteStream{
Conn: c1,
referenceID: s.referenceID,
session: s,
}
s.referenceLock.Lock()
s.byteStreams[s.referenceID] = bs
s.byteStreams[s.referenceID+1] = &byteStream{
Conn: c2,
referenceID: s.referenceID + 1,
session: s,
}
s.referenceID = s.referenceID + 2
s.referenceLock.Unlock()

return bs, nil
}

copySender()行为类似:

1
2
3
4
5
6
7
8
9
10
11
func (w *pipeSender) copySender(val Sender) (Sender, error) {
recv, send, err := w.CreateNestedReceiver()
if err != nil {
return nil, err
}
go func() {
Copy(val, recv)
val.Close()
}()
return send, nil
}

#####序列化
byteStream和Sender使用注册的codec扩展句柄编码,byteStream编码函数:

1
2
3
4
5
6
7
8
9
10
func (s *streamSession) encodeStream(v reflect.Value) ([]byte, error) {
bs := v.Interface().(byteStream)
if bs.referenceID == 0 {
return nil, errors.New("bad type")
}
var buf [8]byte
written := binary.PutUvarint(buf[:], uint64(bs.referenceID)^0x01)

return buf[:written], nil
}

byteStream每次都创建一对,并且referenceID从2顺序使用,因此本端对象的referenceID总是偶数,对端使用referenceID+1存储的byteStream,uint64(bs.referenceID)^0x01等价于bs.referenceID+1,这个地方太绕了。
encodeSender()编码Sender对象,行为类似。

#####反序列化
对于一个整数,反序列化后的类型取决于存储他的对象类型,所以收发两端的数据结构不对应就会出错。byteStream反序列化逻辑如下,Sender处理逻辑类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (s *streamSession) decodeStream(v reflect.Value, b []byte) error {
referenceID, readN := binary.Uvarint(b)
if readN == 0 {
return errors.New("bad reference id")
}

bs, ok := s.byteStreams[referenceID]
if !ok {
return errors.New("byte stream does not exist")
}

if bs != nil {
v.Set(reflect.ValueOf(*bs))
}

return nil
}

byteStream结构体嵌入了net.Conn,因此是一个io.ReadWriteClose对象。

1
2
3
4
5
type byteStream struct {
net.Conn
referenceID uint64
session *streamSession
}

####spdy
这是一个基于tcp+spdy作为传输层的实现,每一对sender&receiver或io对象都对应spdy的一个stream。spdy实现了Transport,也使用该数据结构管理在一个chan间传输的sub-chan、io对象的信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
type Transport struct {
conn *spdystream.Connection
handler codec.Handle

receiverChan chan *channel
channelC *sync.Cond
channels map[uint64]*channel

referenceLock sync.Mutex
referenceCounter uint64
byteStreamC *sync.Cond
byteStreams map[uint64]*byteStream

netConnC *sync.Cond
netConns map[byte]map[string]net.Conn
networks map[string]byte
}

type channel struct {
referenceID uint64
parentID uint64
stream *spdystream.Stream
session *Transport
direction direction
}

byteStreams存储io对象转发的通道,使用TCPConn传输,因此是双工的。怎么使用依赖于持有他的对象。
channels存储两机间的chan通道。channel封装了一个byteStream对象和direction字段,因此只能单向使用。

因为Sender&Receiver和io对象都通过spdy的stream实现,所以stream建立的时候就需要进行区分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
func (s *Transport) newStreamHandler(stream *spdystream.Stream) {
referenceIDString := stream.Headers().Get("libchan-ref")
parentIDString := stream.Headers().Get("libchan-parent-ref")

returnHeaders := http.Header{}
finish := false
referenceID, parseErr := strconv.ParseUint(referenceIDString, 10, 64)
if parseErr != nil {
returnHeaders.Set("status", "400")
finish = true
} else {
// parentIDString区分了channel和stream
if parentIDString == "" {
byteStream := &byteStream{
referenceID: referenceID,
stream: stream,
session: s,
}
s.byteStreamC.L.Lock()
s.byteStreams[referenceID] = byteStream
s.byteStreamC.Broadcast()
s.byteStreamC.L.Unlock()

returnHeaders.Set("status", "200")
} else {
parentID, parseErr := strconv.ParseUint(parentIDString, 10, 64)
if parseErr != nil {
returnHeaders.Set("status", "400")
finish = true
} else {
c := &channel{
referenceID: referenceID,
parentID: parentID,
stream: stream,
session: s,
}
s.channelC.L.Lock()
s.channels[referenceID] = c
s.channelC.Broadcast()
s.channelC.L.Unlock()

// subchannel是没有方向概念的
if parentID == 0 {
c.direction = inbound
s.receiverChan <- c
}

returnHeaders.Set("status", "200")
}
}
}

stream.SendReply(returnHeaders, finish)
}

如果parentIDString为空,则是一个byteStream,该stream只读、只写、读写是由持有他的对象决定的。parentIDString非空且不等于0,则是在两机间新建一个管道,创建总是由sender端发起;如果不等于,则是一个subchannel,该chan用来发送还是接收是由持有他的对象决定的。

spdy实现在函数initializeHandler()注册的扩展类型编解码句柄:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func (s *Transport) initializeHandler() *codec.MsgpackHandle {
mh := &codec.MsgpackHandle{WriteExt: true}

...

// Register networks
s.networks["tcp"] = 0x04
s.netConns[0x04] = make(map[string]net.Conn)
err = mh.AddExt(reflect.TypeOf(net.TCPConn{}), 0x04, s.encodeNetConn, s.decodeNetConn)
if err != nil {
panic(err)
}

s.networks["udp"] = 0x05
s.netConns[0x05] = make(map[string]net.Conn)
err = mh.AddExt(reflect.TypeOf(net.UDPConn{}), 0x05, s.encodeNetConn, s.decodeNetConn)
if err != nil {
panic(err)
}

// TODO add unix network as 0x06

return mh
}

相比inmem增加了TCPConn和UDPConn的额外处理。因此这也限制了spdy只能传输在两机间建立的连接,且接收端已经将该conn注册到这个session内。
这是代码中的注释:

// RegisterConn registers a network connection to be used
// by inbound messages referring to the connection
// with the registered connection's local and remote address.
// Note: a connection does not need to be registered before
// being sent in a message, but does need to be registered
// to by the receiver of a message. If registration should be
// automatic, register a listener instead.

注册的连接保存在netConns字段内,使用二维map存储:map[network-type][localaddr<>remoteaddr]。传输时编码的是一个三元组(network-type, local-addr, remote-addr) 。实现函数是encodeNetConn(), decodeNetConn(),注意解码时的字段顺序。

网络连接的传输可以参考这个测试用例:https://github.com/docker/libchan/blob/master/spdy/conn_test.go

###summary
总体来说channel通信方式使用很直观方便,屏蔽了底层的通信建立细节。但是实现方式不容易理解,看了spdy代码也不放心,出了问题debug有困难,比如:

1
2
3
4
5
6
7
8
9
10
func (s *Transport) getByteStream(referenceID uint64) *byteStream {
s.byteStreamC.L.Lock()
bs, ok := s.byteStreams[referenceID]
if !ok {
s.byteStreamC.Wait()
bs, ok = s.byteStreams[referenceID]
}
s.byteStreamC.L.Unlock()
return bs
}

if是不是应该换成while判断。

LeetCode - Sort List

Sort List
Sort a linked list in O(n log n) time using constant space complexity.

排序一个单向链表,要求时间复杂度O(nlgn),空间复杂度O(1)。使用merge sort解该问题,网上的答案用的都是递归的解法,也就是top-down的实现,空间复杂度应该为O(lgn),并不是常数,使用bottom-up的实现可以达到O(1)的空间复杂度。

wikipedia只给出了数组的top-down & bottom-up实现和list的top-down实现。
这里的快慢指针技巧非常有用:link1 link2
链表的实现有带头节点和不带头节点两种形式,不带头节点的实现需要判断head==NULL的情况,带头节点则会浪费一个节点的空间。对于不带头节点的链表,各个操作可以用二级指针实现,把代码书写上的复杂度转移到coder的脑袋里。

Talk is cheap, show you the code:

两个bottom-up的实现,第一个空间复杂度O(n),最多需要存储n/2个链表头指针。

Code 1.

这里的queue使用list会超时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
**/
#include <deque>

using namespace std;

class Solution {
public:
ListNode *sortList(ListNode *head) {
if (head == NULL) {
return NULL;
}

deque<ListNode*> queue;
ListNode* iter = head;
ListNode* next = NULL;
while (iter != NULL) {
queue.push_back(iter);
next = iter->next;
iter->next = NULL;
iter = next;
}
while (queue.size() >= 2) {
iter = queue.front();
queue.pop_front();
next = queue.front();
queue.pop_front();
queue.push_back(mergeList(iter, next));
}
return queue.front();
}

private:
ListNode* mergeList(ListNode* left, ListNode* right) {
ListNode* merged_list = NULL;
ListNode** next_holder = &merged_list;
ListNode* selected_node = NULL;
while(left != NULL && right != NULL) {
if (left->val <= right->val) {
selected_node = left;
left = left->next;
} else {
selected_node = right;
right = right->next;
}
selected_node->next = NULL;
*next_holder = selected_node;
next_holder = &(selected_node->next);
}
*next_holder = left ? left : right;
return merged_list;
}
};

Code 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
class Solution {
public:
ListNode* sortList(ListNode* head) {
//assert(head != NULL);

int step = 1;
int len = length(head);
ListNode* sorted_list = NULL;
ListNode** tail_holder = &sorted_list;
while (step < len) {
ListNode* left_head = NULL;
ListNode* left_tail = NULL;
ListNode* right_head = NULL;
ListNode* right_tail = NULL;

cutList(head, step, &left_head, &left_tail, &head);
left_tail->next = NULL;
if (head == NULL) {
*tail_holder = left_head;
goto NEXT_LOOP;
}

cutList(head, step, &right_head, &right_tail, &head);
right_tail->next = NULL;
*tail_holder = mergeList(left_head, right_head);
//assert( (left_tail->next == NULL && right_tail->next != NULL)
// || (left_tail->next != NULL && right_tail->next == NULL));
if (right_tail->next == NULL) {
tail_holder = &(right_tail->next);
} else {
tail_holder = &(left_tail->next);
}
NEXT_LOOP:
if (head == NULL) {
head = sorted_list;
sorted_list = NULL;
tail_holder = &sorted_list;
step *= 2;
}
}
return head;
}


private:
int length(ListNode* head) {
int len = 0;
while (head != NULL) {
++len;
head = head->next;
}
return len;
}
void cutList(ListNode* head, int len,
ListNode** p_left_head, ListNode** p_left_tail, ListNode** p_right_head) {
//assert(head != NULL);

*p_left_head = head;
*p_left_tail = head;
*p_right_head = head->next;
for (int i = 0; i < len && head != NULL; ++i) {
*p_left_tail = head;
*p_right_head = head->next;
head = head->next;
}
}
ListNode* mergeList(ListNode* left, ListNode* right) {
//assert(left != NULL);
//assert(right != NULL);

ListNode* merged_list = NULL;
ListNode** next_holder = &merged_list;
ListNode* selected_node = NULL;
while(left != NULL && right != NULL) {
if (left->val <= right->val) {
selected_node = left;
left = left->next;
} else {
selected_node = right;
right = right->next;
}
selected_node->next = NULL;
*next_holder = selected_node;
next_holder = &(selected_node->next);
}
*next_holder = left ? left : right;
return merged_list;
}
};

c++ vector和deque的区别

用c++解Min Stack的时候被Memory Limit Exceeded搞的很头痛,自己写过链表、空间可增长的数组,用了stl的vector、deque,最后是deque的实现可以通过,搜了下也有用stack过的。
在这里记录下deque&stack跟其他实现的区别。

这是cplusplus deque页面的讲的vector和deque实现的区别:

Both vectors and deques provide a very similar interface and can be used for similar purposes, but internally both work in quite different ways: While vectors use a single array that needs to be occasionally reallocated for growth, the elements of a deque can be scattered in different chunks of storage, with the container keeping the necessary information internally to provide direct access to any of its elements in constant time and with a uniform sequential interface (through iterators). Therefore, deques are a little more complex internally than vectors, but this allows them to grow more efficiently under certain circumstances, especially with very long sequences, where reallocations become more expensive.

vector用的是一个数组,剩余空间不够时申请一个size-doubled的新数组,然后把原数据拷贝过来。而deque因为是双向的,如果还是像vector这种实现方式空间浪费会比较多,所以使用了多个chunk存储数据,然后用一个T*进行索引,当空间不够时新分配一个chunk,chunk大小也是固定的。

leetcode一组测试数据共插入7w个整数,需要空间28w bytes,大于等于该值的最小的2的幂次方是2^18=524288,使用vector消耗的差不多就是这么大,额外消耗238kb,即使用vector::resize()预分配空间也依赖于内存分配器的行为。
使用deque的话,数据存储空间大约是(28w/512+1)*512 byte,最多浪费512字节;索引的话,28w/512=546, 索引占用1024*sizeof(int*),额外消耗4.5kb(64位8.5kb)。deque里每个chunk大小的计算公式如下:

1
2
item_size = sizeof(T)
(item_size < 512 ? (512 / item_size) : 1) * item_size

stl里的stack是一种container adaptor,底层使用deque实现,因此内存消耗与deque相同。

这篇文章link介绍了deque的实现,图画的很好。
stl的实现原理可以参考侯捷的《STL源码剖析》和stl代码。

min stack实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstddef>
#include <deque>

using namespace std;

class MinStack {
deque<int> stack;
deque<int> min;
public:
void push(int x) {
stack.push_back(x);
if (min.size() <= 0 || x <= min.back()) {
min.push_back(x);
}
}
void pop() {
int stack_last = stack.back();
stack.pop_back();
int min_last = min.back();
if (stack_last == min_last) {
min.pop_back();
}
}
int top() {
return stack.back();
}
int getMin() {
return min.back();
}
};

gorun实现分析

学习golang的时候想写点代码还得到特定的目录结构下,build & run,实在是太罗嗦,好在Programming in Go这本书一开始就提到了把golang当作脚本语言使的工具,但是直到这本书快看完了才受够了这个流程决定使用这两个工具(好强的忍耐力。。。

这篇文章是对gorun代码的分析,项目地址是:https://wiki.ubuntu.com/gorun

使用方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
gorun <source-file> [option...]
```
option是传给source-file的参数

### 处理流程
脚本实现思路是把输入的源文件拷贝到系统TempDir目录下,然后编译执行。大致流程如下:
* 创建工作目录:
rundir = TMPDIR/gorun-hostname-euid[-NUM]/GOOS_GOARCH
* 生成可执行文件的文件名:
runfile = EvalSymlinks(Abs(sourcefile)), Replace("%"->"%%", filepath.Separator->"%")
* 基于ModTime检测源文件相对上次编译是否更新
若不需要重新编译,则touch(runfile) & CleanDir(rundir),请注意touch的原因
* 若需要编译则调用go tool工具编译,这样可以指定产出文件。
如果源文件首行以#!开头,则会生成一个临时的源文件runfile.pid.go并且编译后删除。原因是代码还是用go编译的,#!不符合go的语法,因此源文件除了首行可以以#!开头外,其他地方都要符合go的语法。
* 之后使用系统调用exec执行,如果是因为目标文件不存在导致失败则会有重试。


目前代码里有个小问题:
```go
// CleanDir removes binary files under rundir in case they were not
// accessed for more than CleanFileDelay nanoseconds. A last-cleaned
// marker file is created so that the next verification is only done
// after CleanFileDelay nanoseconds.
func CleanDir(rundir string, now time.Time) error {
cleanedfile := filepath.Join(rundir, "last-cleaned")
cleanLine := now.Add(-CleanFileDelay)
if info, err := os.Stat(cleanedfile); err == nil && info.ModTime().After(cleanLine) {
// It's been cleaned recently.
return nil
}
f, err := os.Create(cleanedfile)
if err != nil {
return err
}
_, err = f.Write([]byte(now.Format(time.RFC3339)))
f.Close()
if err != nil {
return err
}

// Look for expired files.
d, err := os.Open(rundir)
if err != nil {
return err
}
infos, err := d.Readdir(-1)
for _, info := range infos {
atim := sysStat(info).Atim
access := time.Unix(int64(atim.Sec), int64(atim.Nsec))
if access.Before(cleanLine) {
os.Remove(filepath.Join(rundir, info.Name()))
}
}
return nil
}

这里在判断"old compiled files"用的是atime,首先文件系统可以配置不记录atime,这样的话就没法判断bin文件是不是被用过。然后是如果文件已经存在,则Create不会更新atime,这就导致last-cleaned也会被删除,下一次gorun还会调用CleanDir一次。但是都不是大问题,atime本身比较蛋疼需要注意。

还有就是go run可以编译并执行源程序,再用第三方脚本就没必要了。