[erlang-questions] N-Queens

Mikael Pettersson mikpe@REDACTED
Thu Jan 4 13:25:10 CET 2007


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.

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 ==.

/Mikael



More information about the erlang-questions mailing list