[erlang-questions] N-Queens

[Serge Aleynikov]

This problem domain is certainly not meant for Erlang.  The purpose of 
this exercise was to compare speed of OCaml's staticly checked bytecode 
and dynamically checked Erlang's.  My initial (wrong) guess also was 
that interpreted OCaml should be faster.  It is pleasant to see that the 
scheduling overhead of Erlang VM is not significant in this problem 
compared to OCaml.  Also I was quite surprised that OCaml could beat C 
performance-wise with standard compilation options (with full 
optimization on, they have about the same performance).

BTW, on this host the nqueens_ha version of the code gives:

nqueens_ha.beam:  6.79s

Regards,

Serge

Kostis Sagonas wrote:
> Mikael Pettersson wrote:
>> Serge Aleynikov writes:
>>  > Greetings!
>>  >  > I wrote an N-Queen problem solver in C/C++/OCaml/Erlang for 
>> conducting a  > benchmarking exercise.  Here are results:
>>  >  > $ wc -l nqueens.{c,cpp,ml,erl}
>>  >    93 nqueens.c
>>  >   109 nqueens.cpp
>>  >    61 nqueens.ml
>>  >    61 nqueens.erl
>>  >  > On my host timing is as follows:
>>  >  > $ make run   # 8 queens, 1000 times
>>  > # Program               Time
>>  > ./queens_c:             0.96
>>  > ./queens_cpp:           1.16
>>  > ./queens_ml:            0.77     # OCaml natively compiled
>>  > ./queens_ml.bcode:      22.55    # OCaml bytecode compiled
>>  > nqueens.beam:           8.56
>>  >  > Note that Erlang code is natively compiled.  Without the native 
>> flag it  > gives about the same time as queens_ml.bcode.
>>  >  > If we use optimization (-O3 for C/C++ and -unsafe for OCaml) the 
>> timing  > picture is slightly different.
>>  >  > I am curious if anyone can suggest any improvement to 
>> nqueens.erl  > (preserving the algorithm) that would increase its 
>> performance (other  > that parallelization).
>>
>> Both the C/C++ and O'Caml versions use mutable arrays and omit
>> runtime safety checks, while the Erlang version is using tuples
>> and runtime type and index checks. Apples and oranges...
>>
>> It's not surprising Erlang is slow here, but I am surprised to
>> see interpreted O'Caml being so much slower.
> 
> I very much second what Mikael wrote.  The comparison is really like 
> comparing apples and oranges.  Erlang is simply not designed for kinds 
> of tasks like nqueens and it is penalized by various restrictions in the 
> kinds of compiler optimizations which are allowed.
> 
>> In any case, the simplest way to speed up nqueens.erl is to
>> convert it to use HiPE arrays. Also lose the higher-order stuff,
>> and use =:= not ==.
> 
> I've only converted Serge's program to use HiPE arrays and =:= instead 
> of ==, but have not removed the higher-order stuff which add a 
> significant overhead. The resulting program (attached) runs about twice 
> as fast.
> 
> Kostis
> 
> 
> ------------------------------------------------------------------------
> 
> %% Purpose: Eight queens problem solver using HiPE arrays
> %% Author:  Kostis Sagonas <kostis@REDACTED>
> %% Date:    4-Jan-2007
> %% Compile: erlc +native nqueens_ha.erl
> %% Run:     erl -noshell -run nqueens_ha main 8 1000 -s erlang halt
> -module(nqueens_ha).
> -export([main/1, queens/3]).
> 
> loop(N, N, F, A) -> F(N, A);
> loop(I, N, F, A) -> A1 = F(I, A), loop(I+1, N, F, A1).
> 
> loop_nl(I, N, F) -> loop(I, N, F, ok), io:nl().
> 
> %% Output solution to console if Display is true. 
> %% Throws 'abort' when counter signals that MaxCount is reached.
> output(_Board, _SolCount, false) -> ok;
> output( Board,  SolCount, _Display) ->
>     io:format("~-8w/", [SolCount]),
>     N = hipe_bifs:array_length(Board) - 1,
>     loop_nl(0, N, fun(I,_) -> io:format("~2w"  , [I]) end),
>     loop_nl(0, N, fun(I,_) -> io:format("~8w: ", [I]), 
>                               QI = hipe_bifs:array_sub(Board, I),
>                               loop_nl(0, N, fun(J,_) when J =:= QI -> io:put_chars("Q "); 
>                                                (_,_)               -> io:put_chars("* ") 
>                                             end) 
>                   end).
>     
> % Is the queen at row I not threatened
> safe(_Brd, N, I, N) -> I =:= N;                                        % last column
> safe( Brd, N, I, J) ->
>     case hipe_bifs:array_sub(Brd, I) - hipe_bifs:array_sub(Brd, J) of
> 	0 -> I =:= J;             % vert/horiz threat
> 	D -> case abs(D) =:= I - J of
> 		 true -> I =:= J;  % diag threat
> 		 false -> safe(Brd, N, I, J+1)
> 	     end
>     end.
> 
> % Main algorithm
> queens(N, Times, MaxSol) 
>   when is_integer(N), is_integer(Times), is_integer(MaxSol), N > 0, Times > 0 ->
>     Board = hipe_bifs:array(N, 0),
>     F = fun(_,_) -> queens1(Board, MaxSol, 0, Times =:= 1, 0) end,
>     TotalSol = (catch loop(0, Times-1, F, 0)),
>     io:format("Total: ~w solutions~n", [TotalSol]).
>         
> queens1(Brd, MaxSol, SolCount, Display, I) ->
>     F = fun(J, Sum) -> hipe_bifs:array_update(Brd, I, J), queens2(Brd, MaxSol, Sum, Display, I) end, 
>     loop(0, hipe_bifs:array_length(Brd) - 1, F, SolCount).
> 
> queens2(Board, MaxSol, SolCount, Display, I) -> 
>     N = hipe_bifs:array_length(Board) - 1,
>     case safe(Board, N, I, 0) of
> 	false             -> SolCount;
> 	true when I =:= N -> SC = SolCount+1,
> 			     output(Board, SC, Display), 
> 			     SC =:= MaxSol andalso throw(MaxSol),
> 			     SC;
> 	_                 -> queens1(Board, MaxSol, SolCount, Display, I+1)
>     end.
> 
> % Main function
> main([Size, Times]) -> main([Size, Times, "0"]);
> main([Size, Times, MaxSol]) when is_list(Size), is_list(Times), is_list(MaxSol) ->
>     queens(list_to_integer(Size), list_to_integer(Times), list_to_integer(MaxSol)).