shootout - nsieve-bits benchmark

[Kostis Sagonas]

Richard Carlsson wrote:
 > Ulf Wiger (AL/EAB) wrote:
 > > I noticed that Erlang HiPE times out on the nsieve-bits benchmark.
 > > That's not very flattering, since the upper limit is 3600 seconds. (:
 > > [...]
 > 
 > > I attach a version that uses an ordered_set ets table for a bit array.
 > > It at least puts Erlang at the level of Tcl/JavaScript, and well before
 > > Ruby (assuming that the Pentium 4 box performs at least as well as my
 > > SunBLADE). It also matches the output of the other implementations (it
 > > also seems to agree with Doug Bagley's old sieve program, found at
 > > http://www.erlang.org/ml-archive/erlang-questions/200009/msg00010.html)
 > > 
 > > I haven't submitted it. Does anyone have a better implementation?
 > 
 > A nice challenge. Try the attached file - it's more than twice as fast
 > as yours. That should put Erlang on the same level as Python and Smalltalk.

I've kept quiet till now, because I did not want to reveal the HiPE
magic to the world, but since I see that all Erlang solutions are
ets-based, I find little reason not to send this post...

Try the program below. Currently, it uses byte arrays rather than bits,
but converting it to use bits should be straightforward. It is about 20
times faster than Yffe's program and about 10 times faster than Richard's.

Oh, it is also about 3 to 5 times smaller...

Kostis.

%%------------------------------------------------------------------
%% HiPE program contributed by Kostis Sagonas

-module(nsievebits).
-export([main/1]).

main([Arg]) ->
  N = list_to_integer(Arg),
  lists:foreach(fun(I) -> nsieve(10000 bsl (N-I)) end, [0,1,2]),
  halt(0).

nsieve(M) ->
  io:format("Primes up to ~8w~8w\n", [M, nsieve(array(M), 2, M-1, 0)]).

nsieve(A, P, Sz, C) when P =< Sz ->
  NC = case hipe_bifs:bytearray_sub(A, P) of
	   0 -> C;
	   _ -> nsieve_sub(A, P+P, Sz, P), C+1
       end,
  nsieve(A, P+1, Sz, NC);
nsieve(_A, _P, _M, C) -> C.

nsieve_sub(A, I, Sz, P) when I =< Sz ->
  hipe_bifs:bytearray_update(A, I, 0), % clear position
  nsieve_sub(A, I+P, Sz, P);
nsieve_sub(_, _, _, _) -> ok.

array(M) -> hipe_bifs:bytearray(M+1, 16#ff). % an Erlang binary