On Monday 04 June 2007 15:03:45 Mike Furr wrote:
> I have already started using your suggestion of
> including a 1-element 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 no-op 
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 no-op 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 already-sorted 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 higher-order 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