[erlang-questions] N-Queens

[Kostis Sagonas]

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
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: nqueens_ha.erl
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20070104/a05a2ff7/attachment.ksh>