shootout - nsieve-bits benchmark

[Serge Aleynikov]

Kostis,

Is there a reason for functions in hipe_bifs to be available on 
Linux/UNIX but not on Windows?

1> os:type().
{win32,nt}
2> hipe_bifs:bytearray(10, 16#99).
** exited: {undef,[{hipe_bifs,bytearray,[10,153]},
                    {erl_eval,do_apply,5},
                    {shell,exprs,6},
                    {shell,eval_loop,3}]} **

Serge

Kostis Sagonas wrote:
> 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