Wide Finder - Erlang实现小结

Tim的WideFinder习题让多核和并行编程实践在一个简单的问题上有了多种语言作一次比较的机会，所以参与者甚多，我觉得也是很有意义的一件事。今天有点时间，作一个小总结。

目前排行榜上列第一、第二、第三的分别是OCaml+JoCaml，Erlang和Python。C/C++的版本理论上应该可以有很好的结果，但现在还没出来，这反倒说明用C/C++来完成这么一个简单的并行任务并不是很顺畅。

就Erlang的实现而言，基本上是一些象我这样的初学者慢慢摸索（Anders和Steve也都是初学者），加上专家们在一些关键地方的适时指点的过程。

现在看来，几个重要的转折在：
1、min_heap_size的设置对Binary性能的影响非常重要，这涉及到Heap的初始分配、GC的性能。好在探询合适的+h参数比较方便，在命令行加+h Size就可以了；
2、遍历Binary时尽量只移动指针，如无必要，就不要分解出子binary。这对Binary的操作性能也是至关重要，因为分解出的binary要在globle heap中分配并被GC回收，这样是要耗时间的。

解决上述问题后，Erlanger们（包括Anders, Pichi和我）立刻不需要再担心binary的性能，而且已经可以轻易击败ruby了。但要和最快的python实现（wf-6.py）相比，还要解决一个问题：搜索算法。python对定长字符串的搜索是2006年时由Fredrik Lundh写了一个Boyer-Moore的算法并加入到Python 2.5中的，因此Fredrik Lundh在实现他的WideFinder时很自然就用了它。Steve注意到了这一点，用Erlang实现了一个类似的，这样Erlang和Python的的比较才算公平。

于是Anders的wfinder8能在T5120上跑到4.42秒，与Fredrik Lundh的wf-6的4.38秒期鼓相当。

但Fredrik Lundh的wf-6.py和Fernandez的JoCaml版本都是利用操作系统的process来跑并行的。Erlang则是用操作系统的thread来调度自己的轻量process，因此Anders就再写了一个wfinder7_2，干脆跑n个node，每个node是一个操作系统的process，利用Node之间的通讯来合并结果，这个实现能跑到3.54秒，超过了Python，只比JoCaml的1.76秒慢。

还应该提到的是，JoCaml和Python都使用到了Memory Mapping，相当于把整个log文件读到和映射到内存中，因为Tim的那台T5120有8个G的内存，所以这个处理不会带来频繁的swap，不过我本人不喜欢这种方式。

我写程序比较喜欢简洁和直接了当，所以我的实现注重的是在简洁、可读和性能之间的平衡，最后的实现是tbray9a.erl，大约115行，最快是5.26秒。

与Python，JoCaml相比，我喜欢Erlang的地方在于，Erlang对并行和并发的支持在语法和机制上是一致的，而且性能也毫不逊色。Python在进程间通讯时使用了管道、JoCaml也基本上是这样，这也无所谓，但遇到并发情景时，Python和JoCaml就难受了，是用操作系统的Process呢还是用Thread？都不是好的方案。而对Erlang而言，并发和并行的处理机制是一致的，不管在是在自己的轻量processes层次，还是在Node层次，甚至，还有一个层次，就是，它同时还是分布的。

评论

4 楼 dcaoyuan 2007-11-13  

OCaml是静态类型语言，编译器可以依类型信息做更多的优化，这样在单核情况下就比Python，Erlang这类动态类型语言快不少，如果再分解成多个操作系统的Process来跑，在多核情况下也不会差。

OCaml还经常击败C/C++，因为是函数式（当然也支持OO），编译器可以判断哪些语句没有副作用，据此还可以进一步优化，因此在很多情况下比C/C++还要快。

Haskell也有同样的特点。

Erlang的优势在于内建对并发／并行／分布的支持，在利用多核方面，代码的构键最简单、最自然和顺畅。在WideFinder实现中Python的wf-6.py有近三分之一的代码是为并行专门写的，在我的tbray9a.erl中，只有十分之一。

OCaml+JoCaml也可以做到很小比例的代码专门为并行，但对于并发和分布，就得用另一套机制了，或者，象Erlang一样，重写一套类似的机制。

3 楼 mryufeng 2007-11-13  

OCaml 为什么能排第一 想的不是很明白

2 楼 dcaoyuan 2007-11-12  

zbird 写道

Stackless Python，可以实现微线程。
不知道用这个来做性能怎么样。

不知道为什么没有人试这个，应该可以让代码更流畅，但性能不会超过Fredrik Lundh的wf-6.py

1 楼 zbird 2007-11-12  

Stackless Python，可以实现微线程。
不知道用这个来做性能怎么样。