Senlin's Blog


  • 分类

  • 归档

  • 标签

  • 关于

Python 协程的前世今生

发表于 2016-07-30   |   分类于 并发编程   |   阅读次数

生成器与协程

  在Python2.3中,生成器正式被纳入标准。在处理大量数据时,生成器非常有用,例如读取一个几G的文件,你没有必要将文件一次性读取到内存,而是读到一行就将其返回,这样程序不会阻塞在等待读取文件的过程中,也可以大大减少内存的占用。

1
2
3
4
5
6
7
def read_lazy(file_object):
"""Lazy function (generator) to read a file line by line."""
while True:
data = file_object.readline()
if not data:
break
yield data

  生成器执行时候每次遇到yield就会停顿一次并返回一个值,而你可以使用next()让生成器继续执行,直到遇到下一个yield。

1
2
3
4
5
6
7
f = open('data')
while True:
try:
line = next(f)
print(line, end='')
except StopIteration:
break


  后来人们意识到了,既然有办法暂停一个函数的执行,稍后让它从暂停的地方继续执行,这不就满足了协程的概念吗?然而你只能获得生成器的返回值,而不能向生成器传递值。为支持协程,PEP 342提出了你可以使用send()向生成器发送一个值同时重启生成器的执行。

1
2
3
4
5
6
7
8
9
10
11
12
13
def grep(pattern):
try:
while True:
line = (yield)
if pattern in line:
print(line)
except GeneratorExit:
print('See you again!')
g = grep('Python')
g.send(None) # 启动协程
g.send("Python Cookbook")
g.close()

  既然一个协程在执行时候可以通过yield让出当前线程,那么我们就可以在不同的协程之间进行切换从而达到并发的效果,为此你需要编写一个任务调度器,实现基于Cooperative multitasking的任务调度,通过这个调度器管理不同协程的执行。


  下面我们实现一个基于协程的并发Echo Server,这个程序的核心在于任务调度器:

  • 当EchoServer在执行accept, recv和send这类I/O操作之前,会主动让出,这时控制权将移交到调度器手中。
  • 当调度器发现将要执行的I/O操作是accept或recv时,就将任务放到等待读取的队列,若是send则将任务放到等待写入的队列。
  • 调度器会对这两个队列进行I/O轮询,并将就绪的任务放到就绪队列中。
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
from socket import socket, AF_INET, SOCK_STREAM, SOL_SOCKET, SO_REUSEADDR
from collections import deque
from select import select
class Scheduler(object):
def __init__(self):
self.ready = deque() # 就绪队列 deque: coroutine
self.read_waiting = {} # 等待读取的队列 dict: socket -> coroutine
self.write_waiting = {} # 等待写入的队列 dict: socket -> coroutine
def add_ready(self, task):
self.ready.append(task)
def add_read(self, fileno, task):
self.read_waiting[fileno] = task
def add_write(self, fileno, task):
self.write_waiting[fileno] = task
def loop(self):
while any([self.ready, self.read_waiting, self.write_waiting]):
# 如果就绪队列是空的,就进行I/O轮询,等待事件就绪
while not self.ready:
can_read, can_write, _ = select(self.read_waiting,
self.write_waiting,
[])
for fileno in can_read:
self.ready.append(self.read_waiting.pop(fileno))
for fileno in can_write:
self.ready.append(self.write_waiting.pop(fileno))
task = self.ready.popleft()
try:
event, fileno = next(task) # 让协程执行到 yield
if event == 'read':
self.read_waiting[fileno] = task
elif event == 'write':
self.write_waiting[fileno] = task
else:
raise RuntimeError("ERROR!")
except StopIteration:
print('task done')
class AsyncSocket(object):
def __init__(self, sock):
self.sock = sock
def recv(self, maxsize):
yield 'read', self.sock # 主动让出,交给调度器调度
return self.sock.recv(maxsize)
def send(self, data):
yield 'write', self.sock # 主动让出,交给调度器调度
return self.sock.send(data)
def accept(self):
yield 'read', self.sock # 主动让出,交给调度器调度
client, addr = self.sock.accept()
return AsyncSocket(client), addr
def __getattr__(self, name):
return getattr(self.sock, name)
def echo_server(scheduler, address, backlog=5):
sock = AsyncSocket(socket(AF_INET, SOCK_STREAM))
sock.setsockopt(SOL_SOCKET, SO_REUSEADDR, 1)
sock.bind(address)
sock.listen(backlog)
while True:
client_sock, client_addr = yield from sock.accept() # blocking
scheduler.add_ready(echo_handler(client_addr, client_sock))
def echo_handler(address, client_sock):
print('Got connection from {}'.format(address))
while True:
msg = yield from client_sock.recv(8192) # blocking
if not msg:
break
yield from client_sock.send(msg) # blocking
client_sock.close()
if __name__ == '__main__':
scheduler = Scheduler()
server = echo_server(scheduler, ('', 20000))
scheduler.add_ready(server)
scheduler.loop()

  这段代码实现了一个小型的协作式任务调度器。这里你应该意识到协程与线程的不同点了,线程的调度是基于抢占式调度的,在抢占式调度里面,一个线程可能来不及将寄存器变量写入到内存中,或者处理器的缓存来不及同步到主内存中,就被迫切换到另一线程,这就是线程中为什么需要使用各种同步的方式来保证数据的一致性。而协程是主动让出,所以不存在多个协程同时修改同一变量的情况,也就不需要使用互斥锁等同步方式了。
  而协作式调度的一个明显缺点就是,如果某个协程在执行阻塞的调用,或者执行密集的CPU计算,这时协程就无法让出,整个程序就会失去响应了。这就是为什么当今的操作系统放弃协作式调度的原因了。

阅读全文 »

打造 Mac OS 的 C++ IDE(Emacs 篇)

发表于 2016-01-11   |   分类于 开发环境   |   阅读次数

IDE 介绍

  本篇文章将从零开始,介绍如何搭建一个好用的 C++ IDE,主要特性:

  • 支持代码语义跳转。
  • 支持代码自动补全。
  • 支持代码语法检查。
  • 支持 cmake。

通用配置

  下面是一些比较有用的设置,打开~/.emacs文件,写入以下内容:

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
;; 启动时不显示信息
(setq inhibit-startup-message t)
;; 显示行号
(global-linum-mode t)
;; 自动补全括号
(electric-pair-mode 1)
;; 按 Ctl-Enter 开始选中文本
(global-set-key (kbd "C-<return>") 'set-mark-command)
;; 设置代码风格
(c-add-style "my-style"
'("stroustrup"
(indent-tabs-mode . nil) ; 使用空格缩进而不是 Tab
(c-basic-offset . 4) ; 使用四个空格缩进
(c-offsets-alist . ((inline-open . 0)
(brace-list-open . 0)
(statement-case-open . +)))))
(defun my-c++-mode-hook ()
(c-set-style "my-style") ; use my-style defined above
(auto-fill-mode)
(c-toggle-auto-hungry-state 1))
(add-hook 'c++-mode-hook 'my-c++-mode-hook)
(add-hook 'c-mode-hook 'my-c++-mode-hook)

阅读全文 »

如何设计 C++ 的二叉树的迭代器

发表于 2015-08-27   |   分类于 数据结构   |   阅读次数

中序历遍

  我们希望以升序的方式历遍二叉树,这种历遍方式就是中序历遍,好了,那看看中序历遍的非递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template <typename UnaryFuncion>
void inorderTraverse( UnaryFuncion visit ) const
{
auto curr = root_;
std::stack<node_ptr> nodeStack;
while( curr || !nodeStack.empty() )
{
while( curr )
{
nodeStack.push( curr );
curr = curr->left;
}
auto top = nodeStack.top();
nodeStack.pop();
visit( top->value );
curr = top->right;
}
}

  可以想到,将中序历遍分成两部分,初始化阶段,以及迭代阶段。先看看初始化阶段:

1
2
3
4
5
6
auto curr = root;
while( curr )
{
nodeStack.push( curr );
curr = curr->left;
}

  还有,迭代阶段:

1
2
3
4
5
6
7
8
9
auto curr = stack.top();
stack.pop();
curr = curr->right;
while( curr )
{
stack.push( curr );
curr = curr->left;
}

迭代器设计

  二叉树的迭代器是 input iterator,可以这样设计:

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
class const_iterator
{
friend class BinaryTree;
public:
using value_type = T;
using pointer = const T*;
using reference = const T&;
using iterator_category = std::input_iterator_tag;
reference operator*() const;
pointer operator->() const;
const_iterator &operator++();
const const_iterator operator++(int);
bool operator==( const const_iterator &other ) const noexcept;
bool operator!=( const const_iterator &other ) const noexcept;
protected:
const_iterator( const BinaryTree *t, bool end )
: tree( t ), index( 0 )
{
// ...
}
const BinaryTree *tree;
size_type index;
std::stack<node_ptr> stack;
};

阅读全文 »

C++ 实现阻塞队列

发表于 2015-08-24   |   分类于 并发编程   |   阅读次数

队列的异常安全

  考虑一下 STL 中 queue 的接口:

1
2
3
4
5
6
7
8
template <typename T, typename Container = std::deque<T>>
class queue
{
T& front();
void push( const T &elem );
void pop();
bool empty() const; // avoid undefined behaviour before calling front()
};

  我们知道,front()用来获得队列头部元素,而pop()则令头部元素出列。但是为什么不设计成这样呢:

1
2
3
4
5
template <typename T, typename Container = std::deque<T>>
class queue
{
T pop();
};

  其实这是为了保证异常安全(Exception Safe),像下面这个例子:

1
2
3
queue<Widget> q;
// ...
Widget value = q.top();

  设想一下,要是top()将元素出列,并且将这个元素赋值给 value 时,若其拷贝构造函数发生了异常,那么,这个元素就会永远丢失了。

关于实现的细节

  我们将设计一个 ThreadQueue,并且具有以下的特点:

  • 允许多个读者 ( Reader ) 和多个写者 ( Writer ) 并发地访问队列。
  • 元素出列的操作将会阻塞,直到队列不为空。
  • 元素出列时保证异常安全性。
阅读全文 »

谈谈 C++ 的编译期计算

发表于 2015-05-01   |   分类于 编程语言   |   阅读次数

const 变量

  const修饰变量,表示这个变量是不可修改,const变量必须初始化,一经初始化就不可修改:

  • 编译时初始化。
  • 运行时初始化。

  在编译时,可以使用编译时常量来初始化const变量:

1
const int SIZE = 100;

  那么,由于SIZE的值是在编译时就已经确定的,编译器会使用常量 100 来替代程序中出现的SIZE。

  另一方面,const变量也可以运行时才初始化:

1
2
vector<int> v;
const int i = v.size();

constexpr 变量

  const变量的值可以在编译时或运行时确定,与const相比,constexpr的限制更多,因为constexpr变量的值必须在编译时就能确定。
  在一些场合之下,变量的值要求是编译期就必须确定的,constexpr变量正好满足要求:

  • 数组的大小必须是编译期常量。
  • std::array的大小必须是编译期常量。
  • std::bitset的大小必须是编译期常量。
1
2
const auto SIZE = 100;
std::array<int, SIZE> arr;

constexpr 函数

  constexpr函数则与编译期计算有关,要是constexpr函数所使用的变量其值能够在编译时就确定,那么constexpr函数就能在编译时执行计算。另一方面,要是constexpr函数所使用的变量其值只能在运行时确定,那么constexpr就和一般的函数没区别。

  C++11 要求constexpr函数不能多于一条语句,但是碰到 if-else 语句时,但可以巧妙地使用条件操作符来替代:

1
2
3
4
constexpr unsigned long long fib( unsigned n ) noexcept
{
return ( n == 0 || n == 1 ? n : fib( n - 1 ) + fib( n - 2 ) );
}

阅读全文 »
1…10111213

高性能

61 日志
13 分类
14 标签
GitHub 知乎
© 2015 - 2022
由 Hexo 强力驱动
主题 - NexT.Mist
  |   总访问量: