Comparison of OCaml and MLton for numerics
 Yuanchen Zhu
[
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:  20070610 (12:17) 
From:  Jon Harrop <jon@f...> 
Subject:  Re: [Camllist] Comparison of OCaml and MLton for numerics 
On Monday 04 June 2007 15:03:45 Mike Furr wrote: > I have already started using your suggestion of > including a 1element constructor for my trees as it does indeed seem to > give a noticeable speedup. I have another suggestion for you: OCaml's exceptions are very fast and can be used to accelerate many noop paths. For example, when inserting an element into a set that already contains that element, the current Set implementation will reallocate every node on the path to the element even though the resulting set is identical. You can improve performance enormously for the noop case, avoiding this allocation, by raising an exception as soon as you realise the element is already present and catching it on the outside of the "insert" function to return the input set as the output. A related optimization is to use physical equality to avoid allocation (copying) when the output will be equivalent to the input. Insertion sort is a good example of this. A naive insertion sort may be written: let rec insertion = function  [] > []  h1::t > match insertion t with  h2::t when h1>h2 > h2::insertion(h1::t)  t > h1::t but this copies alreadysorted tail lists unnecessarily. It can be optimized by returning the original "list" when possible: let rec insertion = function  [] > []  h1::t as list > match insertion t with  h2::t when h1>h2 > h2::insertion(h1::t)  t' > if t==t' then list else h1::t' More generally, applications such as term rewriters can benefit from specialized higherorder functions that incorporate this physical equality based optimization. My term rewriter used an "id_map" function: val id_map : ('a > 'a) > 'a array > 'a array which returns the input when possible. This can avoid a lot of unnecessary allocation during rewriting and doubled the performance of the whole program! My implementation of id_map was as follows: let id_map f a = if a = [] then a else let b = ref a in try for i = 0 to length a  1 do let e = f a.(i) in if e != a.(i) then begin b := Array.copy a; (!b).(i) < e; raise (Start (i+1)) end done; a with Start start > let b = !b in for i = start to length a  1 do let e = f a.(i) in if e != a.(i) then b.(i) < e; done; b Another useful function along similar lines combines a map and a fold_left into one operation: let id_map_fold_left f x a = if a = [] then x, a else let r = ref x in let b = ref a in try for i = 0 to length a  1 do let r', e = f !r a.(i) in r := r'; if e != a.(i) then begin b := Array.copy a; (!b).(i) < e; raise (Start (i+1)) end done; !r, a with Start start > let b = !b in for i = start to length a  1 do let r', e = f !r a.(i) in r := r'; if e != a.(i) then b.(i) < e; done; !r, b I used the "map" to rewrite one expression into another and the "fold_left" to accumulate the state of the interpreter. I'm sure you can think of many combinations along similar lines. I think a new standard library would do very well to work such optimizations into the existing framework (e.g. the Set module) and providing some useful additional functions would be nice too. I'll write articles about these sorts of things for the OCaml Journal.  Dr Jon D Harrop, Flying Frog Consultancy Ltd. OCaml for Scientists http://www.ffconsultancy.com/products/ocaml_for_scientists/?e