This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Question on writing efficient Ocaml.
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 2006-12-29 (02:09) From: Jon Harrop Subject: Re: [Caml-list] Question on writing efficient Ocaml.
```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

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.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists

```