[Shootout-list] Erlang Crisis! :-)
Nicolas Niclausse
nicolas@niclux.org
Sun, 4 Jul 2004 12:47:39 +0200 (CEST)
------=_20040704124739_83559
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: 8bit
>>>>> Brent A Fulgham <bfulgham@debian.org> writes:
> For some reason, Erlang has absolutely terrible performance on
> heapsort, statistical moments, and interestingly even the
> producer/consumer threads implementation (an area I would have
> expected to be strong).
I've made a patch to use ets instead of tuples for the heapsort benchmark
before:
:~/erlang$ time erl -noinput -s heapsort main 10000
0.9997070759
real 0m50.624s
user 0m49.370s
sys 0m0.306s
after:
:~/erlang$ time erl -noinput -s heapsort main 10000
0.9997070759
real 0m1.630s
user 0m1.549s
sys 0m0.050s
:~/erlang$ time erl -noinput -s heapsort main 80000
0.9999928555
real 0m14.693s
user 0m14.407s
sys 0m0.141s
--
Nicolas Niclausse
------=_20040704124739_83559
Content-Type: text/x-patch; name="heapsort.patch"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment; filename="heapsort.patch"
--- heapsort.erl.orig 2004-06-19 20:01:41.000000000 +0200
+++ heapsort.erl 2004-06-19 21:24:37.000000000 +0200
@@ -7,6 +7,8 @@
%% with +1 adjustment for array indexes.
%% Mercury uses 0..N-1 and Erlang uses 1..N
%%
+%% 20040619: Nicolas Niclausse: use ets instead of tuples
+%%
%% Usage: start from command line with
%% erlc heapsort.erl
%% erl -noinput -s heapsort main 10000
@@ -15,64 +17,66 @@
-export([main/1]).
random_heap(I, Seed, H) ->
- if
- I < size(H) ->
+ case I < ets:info(H,size) of
+ true->
{NextSeed, R} = gen_random(Seed),
random_heap(I+1, NextSeed, up_heap(I, R, H));
- true -> H
+ false -> H
end.
-
up_heap(N, Y, H) ->
HalfN = N div 2,
- X = element(HalfN+1, H), %%%% +1
- Condition = 0 < N andalso X < Y,
- if
- Condition -> up_heap(HalfN, Y, setelement(N+1, H, X)); %%%% +1
- true -> setelement(N+1, H, Y) %%%% +1
+ X = ets:lookup_element(H,HalfN+1, 2), %%%% +1
+ case 0 < N andalso X < Y of
+ true -> up_heap(HalfN, Y, ets_setelement(N+1, H, X)); %%%% +1
+ false -> ets_setelement(N+1, H, Y) %%%% +1
end.
-
heapsort(0, H) -> H;
heapsort(N, H) -> heapsort(N-1, remove_greatest(N, H)).
-
remove_greatest(N, H) ->
- X = element(0+1, H), %%%% +1
- Y = element(N+1, H), %%%% +1
- down_heap(0, N-1, Y, setelement(N+1, H, X)). %%%% +1
-
+ X = ets:lookup_element(H,0+1, 2), %%%% +1
+ Y = ets:lookup_element(H,N+1, 2), %%%% +1
+ down_heap(0, N-1, Y, ets_setelement(N+1, H, X)). %%%% +1
down_heap(I, N, X, H) ->
L = I + I + 1,
R = L + 1,
- if
- N < L ->
- setelement(I+1, H, X); %%%% +1
- true ->
- Condition = R < N andalso element(R+1, H) > element(L+1, H), %%%% +1
- J = if
- Condition -> R;
- true -> L
+ case N < L of
+ true ->
+ ets_setelement(I+1, H, X); %%%% +1
+ false ->
+ J = case R < N andalso ets:lookup_element(H, R+1, 2) > ets:lookup_element(H,L+1, 2) of %%%% +1
+ true -> R;
+ false -> L
end,
- Y = element(J+1, H),
- if
- X > Y -> setelement(I+1, H, X); %%%% +1
- true -> down_heap(J, N, X, setelement(I+1, H, Y)) %%%% +1
+ Y = ets:lookup_element(H, J+1, 2),
+ case X > Y of
+ true -> ets_setelement(I+1, H, X); %%%% +1
+ false -> down_heap(J, N, X, ets_setelement(I+1, H, Y)) %%%% +1
end
end.
+ets_setelement(N,H,X)->
+ ets:insert(H,{N,X}),
+ H.
+
+clear_ets_array(H,0) -> ok;
+clear_ets_array(H,I) ->
+ ets:insert(H, {I,0}),
+ clear_ets_array(H,I - 1).
gen_random(Seed) ->
IM = 139968, IA = 3877, IC = 29573,
S = ((Seed * IA) + IC) rem IM,
{S, S/IM}.
-
main([Arg]) ->
N = list_to_integer(atom_to_list(Arg)),
- Seed = 42,
- RandomHeap = random_heap(0, Seed, erlang:make_tuple(N, 0.0)),
+ ets:new(h, [set, private, named_table]),
+ clear_ets_array(h,N),
+ RandomHeap = random_heap(0, 42, h),
SortedHeap = heapsort(N-1, RandomHeap),
- io:fwrite("~.10f~n", [element(N, SortedHeap)]),
+ io:fwrite("~.10f~n", [ets:lookup_element(SortedHeap,N,2 )]),
halt(0).
------=_20040704124739_83559--