控制流漫谈

By guenchi at 2017-12-13 • 0人收藏 • 188人看过

http://www.zenlife.tk/control-flow.md


服务器做高性能时基本上会落在IO模型这一块上面,因为CPU/内存/IO的制约关系,最弱的一环就是最需要注意的一环。

IO模型跟编程模型又是密切相关的,最终都关于控制流管理。基本的常识是,IO阻塞的时候,我们应该把CPU拿去做其它事情,也就是控制流的切换。

callback

回调可以看下图:

注册好回调的函数,在dispatch做主循环,当IO(或者更抽象的概念--事件)可用的时候调用注册好的回调函数。在回调返回的时候,通常还会注册下一次的回调。上下文切换是在回调的返回过程中。状态是保存在一个全局的数据结构中,传递到下一次的回调。

这种控制流的问题是要手动地管理状态,逻辑被打散在callback中了,编程很不友好。开发者的思维必须异步:等到什么样的事件发生后,进行什么样的回调处理,完成之后再做什么样的操作。

coroutine

coroutine相对于callback的好处是解放思维,用户还是按同步的思维去写代码,代码遇到IO阻塞执行不下去时会自动切换,对用户是透明的。

coroutine的状态不需要用户管理,切换时自动保存上下文。不过有一个难点是栈增长的处理。采用固定分配,太大则浪费空间,太小则会栈溢出。动态改变大小的栈很难做,Go语言之前是用分段栈,后面改成连续栈了。我原本想写一个coroutine的库模拟Go的连续栈做法的,后来发现实现不了。因为拷贝栈需要做指针的地址重新解析。Go能做是因为它知道类型信息,而库的形式是做不了的,因为没有类型信息,无法区分一个东西是指针还是一个整数。

continuation

由于C语言系使用的栈模型,控制流是不支持重入的。函数返回之后栈就不可用了,再也没法回到曾经执行到的位置。coroutine其实是一种特殊的控制流,对每个coroutine使用单独的栈,切换时将关键的寄存器保存起来,后面恢复这些寄存器就可以恢复到曾经的的位置。这个做法是比较tricky的。

如果不要局限于C这种过程式语言的范畴,扩展到函数式领域,用continuation可以表示任何的控制流,不限于非局部跳转。

cps

实现continuation最直观的一种方式是利用cps将continuation具体化。每个函数后面都带一个cont的参数,函数永远不会返回。

由于函数永不返回,栈是一直增长的,那么栈上的数据一直可用,于是就可以重入了。但同样是由于栈一直增长,问题也来了:栈会溢出。

trampoline

cps之后,因为不支持尾递归优化会导致栈溢出。trampoline(蹦床)是为了解决这一问题而使用的一种方法。以C代码为例,假设函数A和B相互调用:

void A() {...; B()}
void B() {...; A()}

A()调用之后会将栈耗尽。使用trampoline改写之后,A不会递归调用B,而是返回B的函数地址,B也不会递归调用A,而是返回A的函数地址。将函数地址返回后让trampoline去调用:

void A() {...; return B;}
void B() {...; return A;}
void trampoline {
    f = A();
    while(true) {
        f = f();
    }
}

由于中间有函数返回过程,栈就不会无限增长了。

后记

又是一篇"漫谈",写得没什么主题性,思维走到哪就写到哪。起初是思考一个好的IO模型,callback不好用,coroutine不好实现,于是想到其实问题的核心是控制流管理,continuation那边会有一些启发。

chicken就是这么做的,chicken是一个将scheme编译成c的编译器,核心的编译步骤就是宏展开,cps变换,闭包转换,lambda提升,加一些编译优化的工作之后转换为c。支持continuation的语言特性,又是生成的c代码可以做交互,看起来挺不错的。


登录后方可回帖

登 录
信息栏

Scheme中文社区

推荐实现 ChezScheme / r6rs / r7rs large
theschemer.org
Q群: 724577239

精华导览

社区项目

包管理器:Raven
HTTP服务器:Igropyr (希腊火)
官方插件:vscode-chez

社区目标:

完善足以使Scheme工程化和商业化的库,特别是开发极致速度的Web服务器和ANN模块。

一直以来Scheme缺少一个活跃的中文社区,同时中文资料的稀少,导致大多数因为黑客与画家和SICP而接触Scheme的朋友,在学完SICP后无事可做,不能将Scheme转换为实际的生产力。最后渐渐的放弃。
同时Chicken等实现,却因效率问题无法与其他语言竞争。本社区只有一个目的,传播Scheme的文明之火,在最快的编译器实现上,集众人之力发展出足够与其他语言竞争的社区和库。


友情链接:

Clojure 中文论坛
函数式·China


Loading...