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层次，甚至，还有一个层次，就是，它同时还是分布的。
Comments
＠dcaoyuan, excellent!
wide finder 是极好的优化 step by step 系列，上次看到你更新了 blog 一直想整一篇后续，苦于不得要领无从下口，现在好了，perfect!
速度真的很快哦
“因此Anders就再写了一个wfinder7_2，干脆跑n个node，每个node是一个操作系统的process，利用Node之间的通讯来合并结果，这个实现能跑到3.54秒，超过了Python，只比JoCaml的1.76秒慢。”
这是不是说明，在多核的系统上，进程级别的分布比线程级别的分布能够更有效率地利用 处理器 ？ 操作系统在调度线程的时候考虑了亲缘性于是只能在几个固定的核上跑？
@louyi，我觉得这恐怕难以很明显的说明什么问题。
优化到了这个份上，性能的差异已在毫厘之间了，在这种情况下，如果A方法比B方法性能高，那有可能只是因为在底层代码中，B方法的某个地方有浪费CPU的代码（又或者是什么其他说不清的原因，而不是“我们编写的代码有问题”）。
也就是说，如果是底层或者其他的原因造成了性能的差异，那么，这种差异应被归类到“trick”里面去（如果差异巨大那就是“trap”）。因为，这些差异已经超出了“问题域的分层”。而保证“易于理解的方式，具有相对较好的性能”，这不是编程者的责任，而是语言／API实现者的责任。
Write a Comment