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

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:  20061229 (02:09) 
From:  Jon Harrop <jon@f...> 
Subject:  Re: [Camllist] 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 eachother. 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 nqueens 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 n1 do for x=0 to n1 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 nqueens 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