又有人投入Erlang的怀抱了:37Signals Campfire loves Erlang

就喜欢看这样的东西...

This is so juicy I couldn’t resist blogging about it. 37Signals sysadmin and my good friend Mark Imbriaco replaced the Campfire chat room handler, originally written in C, with an Erlang version. The results?

283. As in 283 lines of Erlang code in toto.

1500. The Erlang poller handles 1200 - 1500 requests per second.

2.8. Average request time in milliseconds.

240. Number of requests, in millions, served since it went into production last friday.

恩,和我遇到的情况差不多呵呵.
几百行代码,分布式架构,几十K/s请求,没有内存泄漏,系统长久运行...

原文:
http://www.37signals.com/svn/posts/1728-nuts-bolts-campfire-loves-erlang
http://weblog.hypotheticalabs.com/?p=490

评论

41 楼 jigloo 2009-09-22  

因为要做n(n+1)/2次加法，所以按n(n+1)/2p来分配任务。

40 楼 Trustno1 2009-09-03  

<div class="quote_title">night_stalker 写道</div>
<div class="quote_div">
<p>排版好痛苦…… 改了好几遍</p>
<p>这样应该清晰？ 设有 4 个处理器。（p=4）</p>
<p> </p>
<p><span style="font-family: courier new,courier;">1 2 | 3  4 |  5 6  | 7  8     运算次数 / 本轮用到的处理器个数</span></p>
<p><span style="font-family: courier new,courier;"><br>第一步：块内向前和<br>1 <span style="color: #ff0000;">3</span> | 3  <span style="color: #ff0000;">7</span> |  5 <span style="color: #ff0000;">11</span> | 7  <span style="color: #ff0000;">15</span>          1 / 4 </span></p>
<p> </p>
<p>第二步：块外向前和<span style="font-family: courier new,courier;">（结果存于前一块的最后一个元素）<br>1 3                                <br>      3 <span style="color: #ff0000;">10</span>                          1 / 1 (10 = 3+7)<br>              5 <span style="color: #ff0000;">21                  <span style="color: #000000;">1 / 1 (21 = 10+11)</span></span> <br>                     7  <span style="color: #ff0000;">36</span>          1 / 1 (36 = 21+15)<br></span></p>
<p> </p>
<p>第三步：内外向前和相加<span style="font-family: courier new,courier;"><br>1 3 | <span style="color: #ff0000;">6</span> 10 | <span style="color: #ff0000;">15</span> 21 | <span style="color: #ff0000;">28</span> 36          1 / 3</span></p>
<p> </p>
<p>既然处理器数量是小小的常数，O(2n/p + p) = O(n/2) = O(n)，怎么弄都是 O(n) ……</p>
</div>
<p>这个算法串行仍然是O(nLogn)的,很简单每一步都需要n/2,总共需要logn步。</p>
<p>只有当处理器达到log2n时,才可能是O(n)的,即可以在n/2内完成,但是再多的处理器也只能比串行算法快一半.比如你处理100万个元素,需要将近20个处理器才能比串行算法快一半.</p>
<p>其实,这个算法可以在串行时就达到O(n).并行时可以达到O(n/p).</p>
<p> </p>

39 楼 DraculaW 2009-05-19  

根据同学说的 xiaonei现在也转向Erlang了

38 楼 Trustno1 2009-05-19  

其实加速的方法是比较经典的算法.可以往这方面考虑
另外,还可以加一个两个限制条件,就不那么简单了.
1.数组中的某些随机数可能太小,因此我们可以设一个阈值k,使得前向加前的所有元素都大于k
2.再进一步元素的值也不能过大,设一阈值l,使得前向加前的所有元素都在k和l之间.

37 楼 night_stalker 2009-05-19  

<p>假定现在4个处理器<br><br><span style="font-family: courier new,courier;">1  2  3  4 |  5  6  7  8 |  9 10 11 12 | 13 14  15  16    总运算/处理器个数<br></span></p>
<p><span style="font-family: courier new,courier;">1  <span style="color: #ff0000;">3  6 10</span> |  5 <span style="color: #ff0000;">11</span></span><span style="font-family: courier new,courier;"><span style="color: #ff0000;"> 18 26</span> |  9 <span style="color: #ff0000;">19 30 42</span> | 13 <span style="color: #ff0000;">27  42  58       <span style="color: #0000ff;">12/4</span><br></span></span></p>
<p><span style="font-family: courier new,courier;">1  3  6 10 |  5 11</span><span style="font-family: courier new,courier;"> 18 <span style="color: #ff0000;">36</span> |  9 19 30 <span style="color: #ff0000;">78</span> | 13 27  42  <span style="color: #ff0000;">136       <span style="color: #0000ff;">3/1</span><br></span></span></p>
<p><span style="font-family: courier new,courier;">1  3  6 10 | <span style="color: #ff0000;">15 21</span></span><span style="font-family: courier new,courier;"><span style="color: #ff0000;"> 28</span> 36 | <span style="color: #ff0000;">45 55 66</span> 78 | <span style="color: #ff0000;">91 105 120</span> 136       <span style="color: #0000ff;">9/3</span></span></p>
<p> </p>
<p>第二步等价于 大小为4（分块数）的数组向前和问题，既然处理器数量是常数，那么就可以常数时间解决，并不是 bottle neck。</p>

36 楼 Trustno1 2009-05-19  

第一步 n/2p

第二步 n/2-1 (bottle neck)

第三步 (n-1)/2p

n/2p+n/2+(n-1)/2p

按照比单线程算法快的要求，的确已经不错了，不过speed up不可能高于50%.意味着你无论加多少cpu都不会快过单线程算法的一半.

35 楼 night_stalker 2009-05-19  

<p>排版好痛苦…… 改了好几遍</p>
<p>这样应该清晰？ 设有 4 个处理器。（p=4）</p>
<p> </p>
<p><span style="font-family: courier new,courier;">1 2 | 3  4 |  5 6  | 7  8     运算次数 / 本轮用到的处理器个数</span></p>
<p><span style="font-family: courier new,courier;"><br>第一步：块内向前和<br>1 <span style="color: #ff0000;">3</span> | 3  <span style="color: #ff0000;">7</span> |  5 <span style="color: #ff0000;">11</span> | 7  <span style="color: #ff0000;">15</span>          1 / 4 </span></p>
<p> </p>
<p>第二步：块外向前和<span style="font-family: courier new,courier;">（结果存于前一块的最后一个元素）<br>1 3                                <br>      3 <span style="color: #ff0000;">10</span>                          1 / 1 (10 = 3+7)<br>              5 <span style="color: #ff0000;">21                  <span style="color: #000000;">1 / 1 (21 = 10+11)</span></span> <br>                     7  <span style="color: #ff0000;">36</span>          1 / 1 (36 = 21+15)<br></span></p>
<p> </p>
<p>第三步：内外向前和相加<span style="font-family: courier new,courier;"><br>1 3 | <span style="color: #ff0000;">6</span> 10 | <span style="color: #ff0000;">15</span> 21 | <span style="color: #ff0000;">28</span> 36          1 / 3</span></p>
<p> </p>
<p>既然处理器数量是小小的常数，O(2n/p + p) = O(n/2) = O(n)，怎么弄都是 O(n) ……</p>

34 楼 Trustno1 2009-05-19  

night_stalker 写道

Trustno1 写道

引用

p > 1 时
  1.由于 n 很大，先均匀分 p 块，求 块内向前和，耗时 n/p
  2.再求 块外向前和，耗时不超过 p
  3.最后把 块内向前和 与 块外向前和 加起来，耗时 n/p

这个算法若不考虑通讯开销,最快是O(nlogn)的.只会慢不会快.

不是啊，能达到 O(sqrt(n)) 的

并行算法的一个前提条件是假定处理器数量固定.假定你现在4个处理器


1 2 | 3 4 | 5 6 | 7 8|9 10|11 12|13 14| 15 16 

1 3 | 3 7 | 5 11 | 7 15|9 19|11 23|13 27| 15 31    8/4

1 3  6 10 | 5 11  18 26|9 19 30 33|13 27 42 58    8/4

1 3  6 10  15 21  28 36|9 19 30 33 46 60 75 71    8/4

1 3  6 10  15 21  28 36 9 19 30 33 46 60 75 71    8/4


你的算法是这样的？
刚才说错了复杂度应该是O(nlogn/p)
只有当处理器数目和元素数目相等时，才能跑到O(logn)
当然一般的情况下,元素数目远大于处理器数目

33 楼 night_stalker 2009-05-19  

Trustno1 写道

引用

p > 1 时
  1.由于 n 很大，先均匀分 p 块，求 块内向前和，耗时 n/p
  2.再求 块外向前和，耗时不超过 p
  3.最后把 块内向前和 与 块外向前和 加起来，耗时 n/p

这个算法若不考虑通讯开销,最快是O(nlogn)的.只会慢不会快.

不是啊，p == sqrt(2n) 时，能达到 O(sqrt(n)) 的

32 楼 Trustno1 2009-05-19  

引用

p > 1 时
  1.由于 n 很大，先均匀分 p 块，求 块内向前和，耗时 n/p
  2.再求 块外向前和，耗时不超过 p
  3.最后把 块内向前和 与 块外向前和 加起来，耗时 n/p

这个算法若不考虑通讯开销,最快是O(nlogn)的.只会慢不会快.

31 楼 night_stalker 2009-05-19  

p 处理器 求 大小为 n 的数组 的向前和：

p == 1 时
  做 n-1 次加法，耗时 n

p > 1 时
  1.由于 n 很大，先均匀分 p 块，求 块内向前和，耗时 n/p
  2.再求 块外向前和，耗时不超过 p
  3.最后把 块内向前和 与 块外向前和 加起来，耗时 n/p

  最后是 2n/p + p
  处理器数目巨大时，第 2 步耗时可以更少，设为 f(p)，由 f(n) 和 f(p) 的关系列出方程，选择适当的 p 可以求得 f 最小值……
  既然题目说数组巨大，那么相比之下处理器数目不巨大，就不考虑了 ……

-----------------

处理器充分多时，求 n 个数的和，可以用二叉把耗时降低至 log(n)/log(2)，不过“向前和”貌似有点不一样 -_-

30 楼 Trustno1 2009-05-19  

再出一个并行算法的题.
有一个庞大的数组,数组每一个元素都是随机数,现在求这个数组每一个元素的前向和,即p[n]=p[1]+....+p[n-1].要求算法的复杂度小于单线程最快算法的复杂度.

29 楼 everlasting_188 2009-05-18  

night_stalker 写道

比 fib 速度请用 C，循环用 goto。C 写的单线程算法就打翻 VM 语言好多个核了。

不过聊天室的 concurrency 和 parallel 真的没什么联系……
瓶颈不在 cpu，在 io 和锁。所以 C 算得快也没多大帮助。

赞一个，计算机设计就是一个主要的原因就是合理利用IO，从cpu的缓存，到内存，操作系统级别的缓存，应用级别的缓存，硬盘级别的缓存，无一不是用来提高IO的。合理的IO也需要合理的锁设计，要不成单线程了，最坏的就是死锁。

个人感觉： 现在cpu是很快了，除了视频编解码和图像处理外外，其他应用主要是IO处理上跟不上，不在cpu的处理能力上

28 楼 neora 2009-05-17  

Chat Room无疑是ERLANG的强项了。

27 楼 Trustno1 2009-05-16  

night_stalker 写道

单线程矩阵乘 和 并行矩阵乘比。

只要 cpu 的个数有限，仅仅改成并行不能降低算法复杂度。

当幂充分大的时候,这个幂起码可以分成4个通道来做.
从复杂度上来说，可以是1/4的.当然从数量及来说，是不可能降的更低了.

26 楼 ray_linn 2009-05-16  

night_stalker 写道

单线程矩阵乘 和 并行矩阵乘比。

只要 cpu 的个数有限，仅仅改成并行不能降低算法复杂度。

比如Axum理论上的CPU是无限的，因为可以通过网络扩展。

25 楼 night_stalker 2009-05-16  

单线程矩阵乘 和 并行矩阵乘比。

只要 cpu 的个数有限，仅仅改成并行不能降低算法复杂度。

24 楼 Trustno1 2009-05-16  

night_stalker 写道

Trustno1 写道

这不一定，选对了算法javascrpit都会比C快.
首先，单线程的尾递归也好循环也好,最快也是O(n)的，而且无法并行运算.
但是吧fib(n)转换为
0 1
1 1
矩阵的n次幂,那么就可以并行计算,而且不光是并行计算,本身的单线程算法就可以从循环的o(n)下降为o(log(n)).

如果都是矩阵乘，那么 C 的单线程算法还是能打翻很多虚拟机语言的多核算法……

矩阵与矩阵比
矩阵与递归比
矩阵与并行矩阵乘比
你说的是那个?

23 楼 night_stalker 2009-05-16  

Trustno1 写道

这不一定，选对了算法javascrpit都会比C快.
首先，单线程的尾递归也好循环也好,最快也是O(n)的，而且无法并行运算.
但是吧fib(n)转换为
0 1
1 1
矩阵的n次幂,那么就可以并行计算,而且不光是并行计算,本身的单线程算法就可以从循环的o(n)下降为o(log(n)).

如果都是矩阵乘，那么 C 的单线程算法还是能打翻很多虚拟机语言的多核算法……

22 楼 mathgl 2009-05-16  

Trustno1 写道

night_stalker 写道

比 fib 速度请用 C，循环用 goto。C 写的单线程算法就打翻 VM 语言好多个核了。

这不一定，选对了算法javascrpit都会比C快.
首先，单线程的尾递归也好循环也好,最快也是O(n)的，而且无法并行运算.
但是吧fib(n)转换为
0 1
1 1
矩阵的n次幂,那么就可以并行计算,而且不光是并行计算,本身的单线程算法就可以从循环的o(n)下降为o(log(n)).

这个好， 这是我看的一本薄 algorithms 书中第一章章末的一道习题 提到用matrix来算fib。