素数求解，兼谈Erlang的性能特性
javaeye 的 dachidahu 同学不久前提了一个关于 Erlang 的问题 —— 《Erlang 求解1到N 素数的效率问题》。我试了一下，这个问题并不复杂，但结果相当有趣。对于初学 Erlang 的朋友而言，这个程序作为一个了解 Erlang 语言性能特性的例子，非常具有典型性。因此，特地整理一番，与众初学者共享。
这是“求素数”的 Java 代码。基本来自 dachidahu 的帖子，为了测试方便，略做修改。
// java Prime 1000000
public class Prime {
public static void main(String[] args){
int n = Integer.parseInt(args[0]);
long start = System.currentTimeMillis();
for(int i=2; i<n; i++){
boolean b = isPrime(i);
// if(b) System.out.println(i);
}
long now = System.currentTimeMillis();
System.out.println("total running time: "+(now - start)+" ms");
}
public static boolean isPrime(int i){
for(int j=2; j<=Math.sqrt(i)+1; j++){
if(i%j == 0) return false;
}
return true;
}
}
这是相应的 Erlang 源代码。顺手写的。实际包含三个分支，略有区别。其中的 a 分支是严格按照 java 版本的逻辑逐行翻译写出来的。 b 和 a 的唯一区别是在递归当中加入了一个列表参数 L 来传递计算结果。c 分支则采用 dachidahu 同学的“优化思路”——用已经求出的素数来作为被除数，以降低运算次数。
%% erlc +native +"{hipe,[o3]}" prime.erl
%% erl -eval "prime:start(a, 1000000)." -s c q -noshell
%% erl -eval "prime:start(b, 1000000)." -s c q -noshell
%% erl -eval "prime:start(c, 1000000)." -s c q -noshell
-module(prime).
-export([start/2]).
start(M, N) ->
statistics(runtime),
_L = findPrime(M, 1, N, []),
{_, T} = statistics(runtime),
io:format("total running time: ~p ms ~n", [T]).
findPrime(_, N, N, L) ->
L;
findPrime(a, X, N, _L) ->
case isPrimeInt(X, 2, trunc(math:sqrt(X)+1)) of
true -> findPrime(a, X+1, N, []);
_ -> findPrime(a, X+1, N, [])
end;
findPrime(b, X, N, L) ->
case isPrimeInt(X, 2, trunc(math:sqrt(X)+1)) of
true -> findPrime(b, X+1, N, L++[X]);
_ -> findPrime(b, X+1, N, L)
end;
findPrime(c, X, N, L) ->
case isPrimeList(X, L, trunc(math:sqrt(X)+1)) of
true -> findPrime(c, X+1, N, L++[X]);
_ -> findPrime(c, X+1, N, L)
end.
isPrimeInt(1, _, _) -> false;
isPrimeInt(2, _, _) -> true;
isPrimeInt(X, N, E) when N =< E ->
case X rem N of
0 -> false;
_ -> isPrimeInt(X, N+1, E)
end;
isPrimeInt(_, _, _) -> true.
isPrimeList(1, _, _) -> false;
isPrimeList(2, _, _) -> true;
isPrimeList(X, [H|T], E) when H =< E ->
case X rem H of
0 -> false;
_ -> isPrimeList(X, T, E)
end;
isPrimeList(_, _, _) -> true.
作为基准，先看 Java 的版本表现如何：
jackyz@ubuntu:~$ java Prime 1000000
total running time: 4323 ms
看看 Erlang 三个分支各自的运算表现：
jackyz@ubuntu:~$ erl -eval "prime:start(a, 1000000)." -s c q -noshell
total running time: 5660 ms
jackyz@ubuntu:~$ erl -eval "prime:start(b, 1000000)." -s c q -noshell
total running time: 69810 ms
jackyz@ubuntu:~$ erl -eval "prime:start(c, 1000000)." -s c q -noshell
total running time: 65510 ms
结果有没有让你吃惊？
分支 a 与 java 代码几乎是严格对应的，执行的性能比 java 略慢一点(慢30%)，但差别很有限，并没有得出象 dachidahu 同学那样离谱的差异。
分支 b 和分支 a 的唯一区别是多加了一个参数用来传递当前已经算出的素数。仅仅多了这么一步，和前面一个分支相比，立刻就有了非常惊人的差别(慢1133%)。
分支 c 则正如我们预料的一样，要比分支 b 快一点点。但也仅仅只是比 b 快了那么一点点而已(快6%)。
通过这个例子，我们能够体会到 Erlang 怎样的性能特性呢？
- Erlang 并不以高效著称(它最为突出的特性应该是可靠性，其次是基于消息的彻底隔离与内置的分布式支持)，虽说 Erlang 团队在虚拟机优化上下了很多功夫，但比起同样经过“业界精英苦心优化”的 Java 来说，可能仍然是各有千秋(具体怎么个各有千秋法，仍需仔细考察)。至少在这个例子中 Erlang byte code 并没有在实际执行中表现出超越 Java byte code 的性能。
- 和上面一条恰好相反，Erlang 的虚拟机也并不像我们所想象的那么糟糕，有文章称 Erlang 虚拟机比 Java 虚拟机要慢上一个数量级，我不知道这样的结论是如何得出的，但至少在上面这个例子中的 rem (整除)操作上，并没有看到这样的差异。
- 虽说列表操作在 Erlang 语法里看起来只是一句超简单的“原子操作”，但实际上它也是有代价的。尤其是，当需要承载大量数据的时候(有文章称超过 1K 数据量就应该考虑其他数据结构)，就不再适合采用 list 来装数据。
- 类似于 list 的例子，在 Erlang 里可能还有不少。具体会怎样，应该靠实际而耐心的测试去发现问题，而不是我们的猜测。要点就是，这是不同的语言，之前的经验或许已经不再适用。
- 不要提前(草率)优化。优化是一个精细活，必须建立在精细设计的 profiling 的基础之上，找出瓶颈，然后再优化之。否则，就会象上面的 c 分支一样，优化了半天，却根本就没有击中要害。
我们以一个 trick 来结尾，在 Erlang 里面是否有超越 Java 执行性能的可能呢？有！比如说，我们可以象这样：
jackyz@ubuntu:~$ erl -eval "prime:start(a, 1000000)." -s c q -noshell
total running time: 3010 ms
不错吧。
不过，这是以 native code 对 byte code 的怪招，胜之不武。哈哈。
-EOF-
不过，这是以 native code 对 byte code 的怪招，胜之不武。哈哈。
——— java 有JIT的.hipe对他来说,没什么胜之不武的
但，为什么是 “L++[X]“，而不是“[X|L]”？
@Jer
哈哈，改成 [X|L]之后，和a方案的时间差距已经在100ms以内。看来b方案绝大部分都耗在list的连接上了。
在Erlang程序设计中，作者指出L++[X]存在性能问题。
@blast
偶尔用用可以,大量使用就不成了
这里写的 L++[X] 肯定远慢于 [X|L]。list是单链表，在头部附加元素远快于在尾部追加元素；且头部附加能zero-copy实现（只需要保留不同表头的指针），尾部追加会导致复制一遍整个链表的数据。
然而，在按照 [X|L] 的降序列表顺序添加新的“优化算法”分支之后，又发现了另外一个有趣的情况：
这是程序：
%% erlc prime.erl
%% erlc +native +"{hipe,[o3]}" prime.erl
%% erl -eval "prime:start(a, 1000000)." -s c q -noshell
%% erl -eval "prime:start(b, 1000000)." -s c q -noshell
%% erl -eval "prime:start(c, 1000000)." -s c q -noshell
%% erl -eval "prime:start(d, 1000000)." -s c q -noshell
%% erl -eval "prime:start(e, 1000000)." -s c q -noshell
-module(prime).
-export([start/2]).
start(M, N) ->
statistics(runtime),
L = findPrime(M, 1, N, []),
{_, T} = statistics(runtime),
io:format("total running time: ~p ms ~n", [T]),
io:format("found primes number:~p~n", [length(L)]).
findPrime(_, N, N, L) ->
L;
findPrime(a, X, N, _L) ->
case isPrimeInt(X, 2, trunc(math:sqrt(X)+1)) of
true -> findPrime(a, X+1, N, []);
_ -> findPrime(a, X+1, N, [])
end;
findPrime(b, X, N, L) ->
case isPrimeInt(X, 2, trunc(math:sqrt(X)+1)) of
true -> findPrime(b, X+1, N, L++[X]);
_ -> findPrime(b, X+1, N, L)
end;
findPrime(c, X, N, L) ->
case isPrimeList(X, L, trunc(math:sqrt(X)+1)) of
true -> findPrime(c, X+1, N, L++[X]);
_ -> findPrime(c, X+1, N, L)
end;
findPrime(d, X, N, L) ->
case isPrimeInt(X, 2, trunc(math:sqrt(X)+1)) of
true -> findPrime(d, X+1, N, [X|L]);
_ -> findPrime(d, X+1, N, L)
end;
findPrime(e, X, N, L) ->
case isPrimeListR(X, L, trunc(math:sqrt(X)+1)) of
true -> findPrime(e, X+1, N, [X|L]);
_ -> findPrime(e, X+1, N, L)
end.
isPrimeInt(1, _, _) -> false;
isPrimeInt(2, _, _) -> true;
isPrimeInt(X, N, E) when N =< E ->
case X rem N of
0 -> false;
_ -> isPrimeInt(X, N+1, E)
end;
isPrimeInt(_, _, _) -> true.
isPrimeList(1, _, _) -> false;
isPrimeList(2, _, _) -> true;
isPrimeList(X, [H|T], E) when H =< E ->
case X rem H of
0 -> false;
_ -> isPrimeList(X, T, E)
end;
isPrimeList(_, _, _) -> true.
isPrimeListR(1, _, _) -> false;
isPrimeListR(2, _, _) -> true;
isPrimeListR(X, [H|T], E) ->
if
H > E ->
isPrimeListR(X, T, E);
true ->
case X rem H of
0 -> false;
_ -> isPrimeListR(X, T, E)
end
end;
isPrimeListR(_, _, _) -> true.
这是结果：
jackyz@ubuntu:~$ erlc +native +"{hipe,[o3]}" prime.erl
jackyz@ubuntu:~$ erl -eval "prime:start(a, 100000)." -s c q -noshell
total running time: 140 ms
found primes number:0
jackyz@ubuntu:~$ erl -eval "prime:start(b, 100000)." -s c q -noshell
total running time: 830 ms
found primes number:9592
jackyz@ubuntu:~$ erl -eval "prime:start(c, 100000)." -s c q -noshell
total running time: 730 ms
found primes number:9592
jackyz@ubuntu:~$ erl -eval "prime:start(d, 100000)." -s c q -noshell
total running time: 140 ms
found primes number:9592
jackyz@ubuntu:~$ erl -eval "prime:start(e, 100000)." -s c q -noshell
total running time: 6370 ms
found primes number:9592
# 采用 hipe 编译
# 使用10万作为测试值是因为分支 e 在100万时实在太慢
# a 分支，0140ms，测试基准，不收集结果
# b 分支，0830ms，用 L++[X] 收集结果，不需对结果进行解析
# c 分支，0730ms，被除数优化算法，用 L++[X] 收集结果，需要对结果进行解析
# d 分支，0140ms，参照 b 分支，改用 [X|L] 收集结果，不需对结果进行解析
# e 分支，6370ms，参照 c 分支，被除数优化算法，改用 [X|L] 收集结果，需要对结果进行解析，结果列表为降序，相比 c 分支，在 isPrimeListR 函数中需要执行的 [H|T]=L 列表解析次数更多
上面的列表操作会导致GC 所以如果你能在命令行上 加上 +h 999999 那么速度会快很多。
@chaoslawful zero copy是list在VM虚拟机的最大的优点，列表是在进程堆和栈里面构造成的 无需任何拷贝。 所以小的数据量用list是很快的。
我是初学者,我想问个问题.这样的测试是不是只能说在顺序编程中的效率呢?
而erlang的面向并发是其主要特点..我觉得如果真要比较的话.
是不是换种方式来写会好点.比如利用并发进程:
创建10个并发进程.而这10个进程分别求各个10W的素数.(1~10W|100..1~`999..|T)
利用顺序编程创建10个并发进程,然后他们自己去求值.最后得到各个进程所花的时间.这样的一个方式在去和java进行比较呢.?是不是更有意思.
当然java代码也要更改.也用同样的创建10个线程去分别求解..
老大能不能这样去计算一下….
初学的想法…大家不要喷我…
这样的简单的数学计算 不符合 small message, big computaion的原则。 所以即使是多进程并行计算 收益也是很小的。
erlang的优势不在于计算，而在于完善的网络和服务器的编程模式， 已经平台和工具支持。 所以定位非常重要。
http://yufeng.info
测试结果没能证明 +h 参数调节 heap size 能带来正面影响。
jackyz@ubuntu:~$ erl -eval "prime:start(c, 100000)." -s c q -noshell
total running time: 730 ms
found primes number:9592
jackyz@ubuntu:~$ erl +h 999999 -eval "prime:start(c, 100000)." -s c q -noshell
total running time: 770 ms
found primes number:9592
jackyz@ubuntu:~$ erl -eval "prime:start(e, 100000)." -s c q -noshell
total running time: 6960 ms
found primes number:9592
jackyz@ubuntu:~$ erl +h 999999 -eval "prime:start(e, 100000)." -s c q -noshell
total running time: 11950 ms
found primes number:9592
可以发现 +h 对分支 C 无明显效果，对分支 E 还会导致其更慢，在这里，可能 GC 并非关键。
例子本身的讨论就到这里，下面来讲一点虚的。
这一句也正是我想引用的，而且还要再引申一下：
从这个意义上说， Erlang 不能只当作一种单纯的计算机语言或技术来对待，它同时也可以意味着一些不同的软件思想，对于我们当中的大多数人来说，工作当中也许不一定用得上，但至少，是一种“有益的补充”。
采用NIF实现素数求解的运行效率和C几乎差不多
http://cryolite.javaeye.com/blog/534368
Awesome !
@jackyz
精彩!鼓掌!
erlang 是为并发而生的。 下面这段并发代码在虚拟机中跑了930ms
erl -eval “make_prime:start(1000000).” -noshell -s c q -smp +S 1
-module(make_prime).
-export([start/1]).
start(Num) ->
statistics(runtime),
Pl = mapreduce(Num),
{_, T} = statistics(runtime),
io:format(“total running time: ~p ms ~n”, [T]),
io:format(“primes total : ~p ~n”, [erlang:length(Pl)]).
mapreduce(Num) ->
Server = self(),
Ref = erlang:make_ref(),
Pids = prime_map(Server, Ref, 1, Num, []),
reduce(Pids, Ref, []).
get_end(Start, Num) when Start == Num ->
Num;
get_end(Start, Num) when Start
End = if
Start =
Start + 5000;
Start =
Start + 500;
Start =
Start + 300;
Start > 500000 ->
Start + 100
end,
if
End = End;
End > Num -> Num
end.
prime_map(Server, Ref, Start, Num, Pids) when Start =
End = get_end(Start, Num),
Pid = spawn( fun() -> do_prime(Server, Ref, Start, End) end ),
prime_map(Server, Ref, End+1, Num, [Pid|Pids]);
prime_map(_Server, _Ref, Start, Num, Pids) when Start > Num ->
Pids.
do_prime(Server, Ref, Start, End) ->
Primes = find_primes(Start, End, []),
Server ! {self(), Ref, Primes}.
find_primes(Start, End, Primes) when Start
case is_prime(Start, trunc(math:sqrt(Start)+1)) of
true ->
find_primes(Start+1, End, [Start|Primes]);
_ ->
find_primes(Start+1, End, Primes)
end;
find_primes(Start, End, Primes) when Start == End ->
case is_prime(Start, trunc(math:sqrt(Start)+1)) of
true ->
lists:reverse([Start|Primes]);
_ ->
lists:reverse(Primes)
end.
is_prime(1, _) -> false;
is_prime(2, _) -> true;
is_prime(Int, Sqrt) ->
is_prime(2, Int, Sqrt).
is_prime(N, Int, Sqrt) when N =
case Int rem N of
0 ->
false;
_ ->
is_prime(N+1, Int, Sqrt)
end;
is_prime(_, _, _) -> true.
reduce([Pid|T], Ref, Primes) ->
receive
{Pid, Ref, Ret} ->
reduce(T, Ref, append_list(Ret, Primes))
end;
reduce([], _, Primes) ->
Primes.
append_list([H|T], List) ->
append_list(T, [H|List]);
append_list([], List) ->
List.
更优雅的实现:
[code]
-module( echo ).
-export( [ test/1] ).
test(N)->
statistics(runtime),
All=run(N),
{_, T} = statistics(runtime),
io:format("Total running time: ~p ms ~n", [T]).
%%io:format("Total:~p running time: ~p ms ~n", [All,T]).
run(1) -> error;
run(2) -> [2];
run(N) when N rem 2 == 0 -> run(N-1);
run(N) -> findPrime(3,N,[2],false). %%直接从3开始,到N为止
findPrime(X, N, L,true) -> findPrime(X,N,[X-2|L],false);
findPrime(N, N, L,_) -> [N|L];
findPrime(X, N, L,false) -> findPrime(X+2,N,L,isPrimeInt(X,3,trunc(math:sqrt(X)+1))).
isPrimeInt(_, S, E) when S >= E -> true;
isPrimeInt(X, S, _) when X rem S == 0 -> false;
isPrimeInt(X, S, E) -> isPrimeInt(X, S+2, E).
[/code]
> echo:test(1000000).
Total: running time: 1859 ms
Hello, blogger, your article very good, looking forward to sharing your latest