Re: [Caml-list] Question on writing efficient Ocaml.

[Serge Aleynikov <serge@hq.idt.net>]

[-- Attachment #1: Type: text/plain, Size: 5316 bytes --]

Here's a slightly modified version of the algorithm that finds all 
solutions for the N-Queens problem implemented in C/C++/OCaml/Erlang.

$ 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
./queens_ml.bcode:      22.55
erl -noshell -run nqueens main 8 1000 -s erlang halt -- :  8.56

Note that Erlang code is natively compiled.  Without the native flag it 
gives about the same time as queens_ml.bcode.  I also have a parallel 
version of Erlang implementation of this algorithm that in SMP mode 
scales linearly with the number of CPUs, but since this "number 
crunching" problem domain is not for meant for Erlang, I haven't 
included it in this email.

If we use optimization (-O3 for C/C++ and -unsafe for OCaml) the timing 
picture is slightly different.

Serge

Jon Harrop wrote:
> On Thursday 28 December 2006 11:42, Ian Oversby wrote:
>> I've written some Ocaml code to solve the problem of placing 8 queens on a
>> board so that none of them attack each-other.
> 
> Your program is very verbose: many times longer than is necessary. Most of 
> this verbosity can be attributed to performing various boxing, unboxing and 
> allocation tasks that are superfluous and simply slow the code down. However, 
> profiling suggests that you're also using a different algorithm in OCaml as 
> the core functions are called many more times in the OCaml than in the C++.
> 
> Contrast your code with a minimal program to solve the n-queens problem in 
> OCaml:
> 
> let rec unthreatened (x1, y1) (x2, y2) =
>   x1 <> x2 && y1 <> y2 && x2 - x1 <> y2 - y1 && x1 - y2 <> x2 - y1;;
> 
> let rec search n f qs ps =
>   if length qs = n then f qs else
>     iter (fun q -> search n f (q::qs) (filter (unthreatened q) ps)) ps;;
> 
> let ps = rev (flatten (init n (fun i -> init n (fun j -> i, j))))
> search n f [] ps
> 
> This program starts with a list of all board positions "ps" and simply filters 
> out threatened positions as queens are added. Performance is poor compared to 
> your C++:
> 
> 0.625s C++ (130 LOC)
> 4.466s OCaml (28 LOC)
> 
> My first solution is written for brevity and not performance so it is still 3x 
> slower than the C++:
> 
> The core of the program is just this:
> 
> open List;;
> 
> let print_board n queens =
>   for y=0 to n-1 do
>     for x=0 to n-1 do
>       print_string (if mem (x, y) queens then "Q" else ".")
>     done;
>     print_newline()
>   done;
>   print_newline();;
> 
> let rec fold_n2 f accu x y n =
>   if y=n then accu else
>     if x=n then fold_n2 f accu 0 (y + 1) n else
>       fold_n2 f (f accu x y) (x + 1) y n;;
> 
> let unthreatened (x1, y1) (x2, y2) =
>   x1 <> x2 && y1 <> y2 && x2 - x1 <> y2 - y1 && x1 - y2 <> x2 - y1;;
> 
> let rec search n f queens () x y =
>   if for_all (unthreatened (x, y)) queens then
>     if length queens = n - 1 then f ((x, y) :: queens) else
>       fold_n2 (search n f ((x, y) :: queens)) () (x + 1) y n;;
> 
> then I wrote this to search once and print and then search a given number of 
> times (for benchmarking):
> 
> exception Queens of (int * int) list;;
> 
> let _ =
>   let n = 8 in
>   let f qs = raise (Queens qs) in
>   (try search n f [] () 0 0 with Queens qs -> print_board n qs);
>   match Sys.argv with
>   | [|_; reps|] ->
>       for rep=2 to int_of_string reps do
> 	try search n (fun _ -> raise Exit) [] () 0 0 with Exit -> ()
>       done
>   | _ -> ()
> 
> The "fold_n2" and "search" functions are both polymorphic folds. The former 
> folds over a square array and the latter folds over all solutions to the 
> n-queens problem. The generality of the "search" function is not used in this 
> case, as I just print the first solution found and bail using an exception.
> 
> On my machine, 1000 solutions takes:
> 
> 0.625s C++ (130 LOC)
> 1.764s OCaml (30 LOC)
> 
> So OCaml is >4x more concise but 2.8x slower than C++.
> 
> Profiling shows that a lot of time is spent in List.for_all. We can roll this 
> ourselves to remove some polymorphism and improve performance:
> 
> let rec unthreatened x1 y1 = function
>   | (x2, y2) :: t ->
>       x1 <> x2 && y1 <> y2 && x2 - x1 <> y2 - y1 && x1 - y2 <> x2 - y1 &&
> 	unthreatened x1 y1 t
>   | [] -> true;;
> 
> let rec search n f queens () x y =
>   if unthreatened x y queens then
>     if length queens = n - 1 then f ((x, y) :: queens) else
>       fold_n2 (search n f ((x, y) :: queens)) () (x + 1) y n;;
> 
> This gets the time down to:
> 
> 1.159s OCaml (33 LOC)
> 
> We can continue optimising by removing some generality. Let's turn the "fold" 
> into an "iter" so that "search" becomes monomorphic:
> 
> let rec iter_n2 f x y n =
>   if y<n then
>     if x=n then iter_n2 f 0 (y + 1) n else
>       (f x y;
>        iter_n2 f (x + 1) y n);;
> 
> let rec search n f queens x y =
>   if unthreatened x y queens then
>     if length queens = n - 1 then f ((x, y) :: queens) else
>       iter_n2 (search n f ((x, y) :: queens)) (x + 1) y n;;
> 
> Performance is improved even more, at the cost of generality.
> 
> 0.827s OCaml (34 LOC)
> 
> So OCaml is now only 30% slower whilst still being ~4x more concise.
> 


[-- Attachment #2: nqueens.tar.gz --]
[-- Type: application/x-gzip, Size: 3321 bytes --]