语义与并行不可分,兼回qiezi的Blog

首先先回一下qiezi的这个blog，http://qiezi.iteye.com/blog/163182
可以写这样一个小小的macro解决问题.




好了,现在你无论执行多少次Score()都能得到值.如果你觉得macro仍然像一个补丁,那么也不要紧.你可以像dcaoyuan的record bird一样自己定义一个语法糖，比如说

record(score,Person)@async.

然后解析Ast Form，用-compile关键字加入这个你自己定义的语法.你真要让Erlang team加上这个也是很小菜的事情,但是我个人觉得这个macros已经够了,毕竟这个macro非常简单才10行,还没有复杂到boost:preprocess那种让人抓狂的程度,加上这个语法糖意义不大,反而会增加语言的复杂性.


在单CPU上我们可以把多线程可以看成并发问题,但是在SMP上则是实实在在的并行问题.虽然从代码层面,一个能够准确无误执行的并发程序，也一定能在SMP上并行的执行。但是从VM模型来说,GC但是对并行的影响相当大.

这不仅仅是取决于你用什么GC策略，还要取决于你采用什么样的VM模型，而使用什么样的VM模型则决定于你采用了什么语义模型.
很多不那么纯粹的FP语言比如OCaml在加入SMP方面举步维艰,比如说这里.
http://caml.inria.fr/pub/ml-archives/caml-list/2002/11/64c14acb90cb14bedb2cacb73338fb15.en.html
根据Xavier说法,为什么Ocaml不支持SMP?这个问题,已经成为了mailinglist上年经贴.
只要引入了side effect,那么必须引入共享堆。有了共享堆那么就必须对共享资源的获取设置lock,这就会带来很大的OverHead.这只是问题的冰山一角，更为致命的是如果这个语言使用Share memory的方案那么就打开了hell gate,各种各样的魔鬼就会一股脑的蹦出来.因为Share memory方案,允许进程间的内存指针互相指引，而GC在清扫过程无法确保这些互相应用的指针不做修改，因此它就必须stop whole world.这对于要求soft-realtime的系统来说就要倒大霉了。要解决这个问题唯一的办法就是concurrent gc.但是这个方案会引入大麻烦。实际上据Xavier说90年代就已经把Caml
concurrent gc做出来过，但是最后上是被放弃掉了。原因很简单，第一concurrent gc虽然有一大堆的机器证明,但是它本身复杂很难除错,第二concurrent gc是要付出代价的，大概是顺序执行效率的30%.比如现在的Dual Core Cpu理论上的speed up是170,用了concurrent gc后只有119%,而对于那些没有使用并行方法优化的遗留代码，这就更变成了灾难，除非caml小组维护两套VM.因此Xavier认为除非有足够的数据说明，multi-core或者hyperthreading的speed up能够抵消concurrent gc的overhead,否则concurrent gc对于VM来说就是一个巨大的包袱。在Xavier看来side-effect和Share momery机制的在并发上的机制是几乎不可能克服的(it is very very unlikely that there will ever be).要想真正的搞并行，还是老老实实的做message passing(better investigate message-passing interfaces).当然现在Ocmal社区出现了Jocaml，其并发效率超过了Erlang.不过Jocaml是基于pi-calculus和join-calculus的并发与现在所有的并发机制都不同，这又是另外一个很大的话题了。

实际上我认为Xavier只说对了一部分,除了使用message passing之外，还要严格杜绝不必要的side-effect以及VM模型中任何可能出现的内存指针互相引用的情况。这两个问题，目前有两种解决方式,第一种是Erlang pure FP+Hybridheap,第二种是Haskell pure FP+STM.对于后者，Haskell是纯Pure FP当然也有可能有一些side-effect,但是至少从理论上来这些side-effect已经降到不能再降。因此Haskell选择VM模型是基于graph reduction的，也就是说Haskell的指令代码是先后顺序是无关的，没有时间关系只有逻辑关系。因此它本身就具有并行性质。在VM层面上对GC对并发影响很小,另外一方面Haskell的并发通信是采用Software transcational Memory.这种技术仍然是一种内存共享机制,但是由于STM本质上是一种采用log页的方式进行数据交换，所以进程之间也不会存在指针互相指引的问题。而且Haskell可以通过它特有的monad机制,把STM上的side-effect严格的限制在某一个区域之内。我个人认为STM(单机多核之间)+Message passing(网络多机之间)应该是目前来说最完美的并行模型.不过目前STM一来虽然研究很热但是仍然很不成熟用Simon Peyton-Jones的话说就是"it's really really hot,but irrelative to developers",二来没有haskell的monad配合，STM就难以驾驭.至于Monad这个东西我也就不多说了用过的都知道是啥德行.....。Channel 9上有一段关于STM的介绍，感兴趣的可以去这里看看很精彩.http://channel9.msdn.com/Showpost.aspx?postid=231495
至于Erlang,已经介绍了很多了这里只是要讲一下一个比较常见的误解:Erlang Pure FP带来的优势是Private Heap，虽然Private Heap可以大大降低的GC的影响但是Private Heap需要进程之间进行message copy.其实Erlang早已经有了Hybird heap.简而言之,Hybird heap就是一个Private heap+shared heap.进程自己的数据存放Private Heap,进程间消息存放在Shared heap。但是这样一来虽然语义上进程之间没有互相指引的指针，但是对于VM模型内部的指针互相指引就不一定能够完全避免.不过幸好，Erlang的Message passing 模型避免了stop whole world的噩梦。因为message passing是send and pray,那么进程和Shared heap之间的指针都是单向的。Erik Johansson在这篇论文里说明的很清楚了。
http://user.it.uu.se/~happi/publications/heap.pdf
单向指针的shared heap,可以采用一种non-moving mark-sweep算法或者reference counting,这两种算法都是可并行化的也就是不需要stop whole world.

所以什么是样风格的并行是可以large scale的并行？这个问题的答案不完全基于语法上的,更重要的是基于语义和VM模型上的.其标准,我觉得Ulf Wiger 的这篇文章，http://erlang-china.org/news/erlang-style_concurrency.html，说的很明白了。虽然IO,Ruby的revactor,Stackless Python这些语言可以在语法上接近甚至超越Erlang,但是只要没有办法解决进程之间彻底独立不共享内存这一条就无法进行large scale的并行，勉强只能算是高性能的并发.

哎咳，看完了，先感叹一下：都是GC的惹得麻烦啊，还是回C++得了，什么麻烦事都没有，效率又足够高。

Programming in the age of large scale parallelism,You should look the big picture.OpenMP is a dancing elephant.

OpenMP或类似的多线程方案我从来不看好。我的意思是说能不能用C++实现一套，Coroutine+MessagePassing+Scheduler(SMP)，我觉得排除了GC这个最大的障碍以后，实现应该会简单很多。这也是我最近的想法，所以比较偏重于看一些支持Coroutine的语言或基于Coroutine的并发库的实现。上次用D语言模拟Erlang的消息机制就发现GC效率影响挺大，当然这还没到SMP调度器，所以最近又有点远离Ｄ语言了。

其实VM模型不单单是内存管理上,还要防止指针异常在整个系统中的弥散,这个在windows下应该有解但是Xnix下就是大麻烦除非修改内核.还有消息的生存期的问题怎么解决呢?这也是头疼的问题,在一个OS thread的地址中或许reference counting可以解决一下，但是两个thread呢?即便在单thread里面使用reference counting，那么就必须强制消息指针必须是单向的.如果为了追求减少copy,而把同一块内存作为不同的消息在两个coroutine里互相传递，那么就会出现cycle reference，这个时候refernce counting就无能为力了，要么引入清扫机制的GC，要么程序员自己手工施放.或许STM能帮你解决一些问题,理想的做法应该是把多核之间的通信和多机之间的通信分开然后用统一的message passing接口。在单机多核上底层用STM实现send/recv,在网络多机之间用纯粹的message passing.但是这个方案也是或许,我虽然看到过有人在C++上实现过Rochester STM,但是在非并行程序或者并行程度较低的情况下仍然好像是不靠谱的样子.
有兴趣的看这里,http://www.cs.rochester.edu/research/synchronization/rstm/.
既要马儿不吃草，又要马儿跑得快，很难啊.
呵呵.

上次看了个ppt，貌似ibm的新的jvm有实现了concurrent gc算法，不知道T1大神对这个有没有了解？做下评价？

如果用C++实现这样一个框架，这种异常本来也不打算处理，C++的传统也是这样嘛。


可以用个简单点的方式，发送方负责分配，接收方负责释放，消息对象我们约定它是只读的。

然后我们再约定在coroutine里面别使用全局变量，一切修改共享对象的操作都把它封装成进程用消息来操作，和Erlang一样。

把和自动GC有关的东西全部排除，呵呵，我感觉挺干净的呀。

Erlang我曾经试过用在项目中，有个负载均恒算法，用c++写了个还没优化就能达到200万次/秒，Erlang版本我花了几小时才从10万次/秒提高到30万次/秒（注），这个应用每秒处理请求超过1万，自然不能在这个算法上浪费太多CPU。自己水平有限写得效率不高是一方面，不过也常听说Erlang不适合计算密集型应用，原因就是效率不高。所以我感觉用C++实现这样的东西还是有点吸引力的。


注：这个有兴趣可以玩下，看看Erlang可以达到什么样的效率。

% 以下表示a的权重是1，b的权重是2，依次类推
Weights = [{a, 1}, {b, 2}, {c, 3} ... {j, 10}]

要求生成一个随机数，按权重选出a-j，要求10000次执行的结果，a-j被选出的几率和它们的权重相近即可。
也可以调整数据结构，但要求能够保证可以随时更新权重值，插入和删除。
实际应用比这个稍复杂一些，数据量多一些，算法部分主要是这个。

IBM的jvm在很早就实现了所谓的concurrent gc的算法，应该说ibm的jvm要hot spot好的多.但是IBM的JVM仍然无法避免stop whole world,只是通过某些算法来降低stop whole world的时间.我记得02年的时候在csnd上发过一篇关于ibmjvm gc的分析文章,有兴趣的可以找来看一下.IBM jvm这几年或许有些其他的改进，但是没有仔细关心过,这里就粗粗的根据当时的印象，简单说一下.
一般Mark-sweep算法分成两个步骤Mark(标记)和Sweep(清扫)(Ibm jvm实际上是三个还有一个是Compaction(内存紧缩)这一部分可以完全并行的执行).Ibm的concurrent gc主要集中于Mark阶段.在Mark阶段主要采用Parallel Mark和Concurrent mark.前者的主要目的是为了在SMP上降低Mark phase的执行时间,在N路SMP上，除了一个main GC thread以外，还可以开启N-1路helper gc thread.main gc的工作主要是扫描C stack以便收集Heap roots,收集完成之后把Heap roots平均分配到N条Helper gc上去.而Concurrent mark的目的则是在于降低stop whole world的时间,即便由N个gc thread进行mark,它也必须打断当前working thread的执行.但是很多working thread工作并不繁忙，因此IBM jvm就想办法让每一个working thread在空闲时自己清扫自己的heap root.当一个working thread没有获取一个global heap lock时,由普通GC或者Parallel Mark清扫.一旦某个working thread要获取global heap lock的时候就代表它自己的heap耗尽.那么这时就启动Concurrent mark,让这个working thread自己清扫自己的stack.
这样做的好处在于GC可以在global heap用尽的同时完成标记工作。此时GC就开始stop whole world,进入清扫阶段。
所以IBM的concurrent gc仍然无法避免stop whole world.因为只要内存模型中允许指针互相引用,stop whole world就无法避免.在这种情况下,GC无法保证Concurrent gc完成以后所有的reachable objects都被mark到,所以必须进行一次stop whole world进行remark.当然分代收集的GC这个pause会比较小，但是这也仅仅是统计意义上的保证,对于一个长时间运行的服务器来说运行时间越长(样本的越大)统计意义的保证就越不可靠(大数定理咯).因此这种concurrent gc一般称为Mostly-Concurrent Collector.

另外对于VM模型上还有一个影响并发/并行的因素忘记说了,就是在分代收集过程中的write barrier.分代收集里根据统计把内存分为yong和old,因为由于指针互相指引的问题,不能总保证内存指针是从yong指向old,如果出现old指向yong的情况，那么就需要从新调整分代。但是从统计上这种情况比较少见，所以进行全局扫描的cost就太高，于是就设计一个write barrier当应用程序把指针从old指向yong的时候就进行自陷然后写入一个卡表.这个自陷的过程也是一个麻烦的根源,也就是说每当你做一次refernce赋值实际上就要进行一次write barrier 检测.这个消耗一般来说在3-5个机器指令左右，当频繁写Heap时造成的消耗也非常可观.而FP语言就没有这种问题了.

至于真正的concurrent gc,据说能做到zero latency不过要付出的代价也不少。这方面我不熟悉,不过Elminster在这方面很有造纸，可以请他来讲一下。

注：这个有兴趣可以玩下，看看Erlang可以达到什么样的效率。 
Java代码 
% 以下表示a的权重是1，b的权重是2，依次类推   
Weights = [{a, 1}, {b, 2}, {c, 3} ... {j, 10}]  

% 以下表示a的权重是1，b的权重是2，依次类推
Weights = [{a, 1}, {b, 2}, {c, 3} ... {j, 10}]

要求生成一个随机数，按权重选出a-j，要求10000次执行的结果，a-j被选出的几率和它们的权重相近即可。 
也可以调整数据结构，但要求能够保证可以随时更新权重值，插入和删除。 
实际应用比这个稍复杂一些，数据量多一些，算法部分主要是这个。 

这里表述有问题吧，a-j出现的概率总是(0-1)怎么可能和weights相近?你到底想求什么?
另外,这个问题个人初步的感觉完全没有必要做10000次循环的啊.
某个weights出现的概率和试验次数没有关系,而是取决于你的随机函数采用什么样的分布,一般的编程语言都是用线性同余法做的其实就是均匀分布,在区间[a,b]上任意x的分布函数是p(x)=(x-a)/(b-a).那么这个问题就很简单了,在[minweights,maxweights]中的某个weights的概率就是p(x)=(x-minweights)/(maxweights-minweights).然后求数列{p(x)*10-x|x∈[minweights,maxweights]}的最小值就ok了。如果为了寻求更大的随机性一般负载均衡的分布大概是γ分布或对数正态分布,具体的记不清了,可查查有关负载均衡的书,简单起见可以考虑二项式分布因为消息队列数据大小的分布差不多是泊松分布,一般的网络状况都是n很大p很小二项式分布近似于泊松分布.

如果说你的意思是把Weights的数值当作Weights本身出现的次数算该Weights出现的概率那个最高.那么每次weights出现都是独立随机事件,于是在10000次试验中出现n次weights的概率就是应该呈n重贝努力分布.

K是出现试验次数,p是某个weights在随机函数分布中的概率.那么带入公式算应该很快的吧.如果不是，其实其他的问题也是一样在这几个分布里面到来到去。如果嫌算阶乘还是慢，可以像概率论教科书后面的正太分布表一样建一张密度函数表，然后直接查就OK了啊,每个weights的概率计算复杂度是O(1).当然每次更新Weights的时候要从新建表.但是这种样本在100以内的表，就算是按正态分布建消耗也是小菜吧.

也就是不考虑转发这种情况?