Re: [Caml-list] What is a match statement translated into?

[Jon Harrop <jon@ffconsultancy.com>]

On Saturday 18 August 2007 07:55:24 Joel Reymont wrote:
> Folks,
>
> Is pattern-matching code in OCaml expanded into threaded code (pre-
> computed branch table) or something analogous to the C switch
> statement (lots of branching)?
>
> How do I find out?

Use:

  ocamlopt -S test.ml

and look at the generated assembler.

> I suspect this should be quite optimized but I haven't tried dumping
> disassembling native-compiled OCaml yet and I wonder if there's a
> simpler approach.

Depends what type you are matching over. Pattern matches over variant types 
(including nesting) are compiled extremely efficiently (dispatch table). 
Polymorphic variants, ints and floats are efficient (balanced trees of 
comparisons). Strings are very inefficient (sequence of string compares).

For example, finding a Java keyword:

let kwd = function
  |"abstract" |"continue" |"for" |"new" |"switch"
  |"assert" |"default" |"goto" |"package" |"synchronized"
  |"boolean" |"do" |"if" |"private" |"this"
  |"break" |"double" |"implements" |"protected" |"throw"
  |"byte" |"else" |"import" |"public" |"throws"
  |"case" |"enum" |"instanceof" |"return" |"transient" 
  |"catch" |"extends" |"int" |"short" |"try"
  |"char" |"final" |"interface" |"static" |"void"
  |"class" |"finally" |"long" |"strictfp" |"volatile"
  |"const" |"float" |"native" |"super" |"while" -> true
  | _ -> false

let () = match Sys.argv with
  | [|_|] ->
      for i=1 to 1000000 do
	ignore(kwd "while")
      done
  | _ ->
      let kwds = Hashtbl.create 1 in
      List.iter (fun kwd -> Hashtbl.add kwds kwd ())
	["abstract" ;"continue" ;"for" ;"new" ;"switch"
	;"assert" ;"default" ;"goto" ;"package" ;"synchronized"
	;"boolean" ;"do" ;"if" ;"private" ;"this"
	;"break" ;"double" ;"implements" ;"protected" ;"throw"
	;"byte" ;"else" ;"import" ;"public" ;"throws"
	;"case" ;"enum" ;"instanceof" ;"return" ;"transient" 
	;"catch" ;"extends" ;"int" ;"short" ;"try"
	;"char" ;"final" ;"interface" ;"static" ;"void"
	;"class" ;"finally" ;"long" ;"strictfp" ;"volatile"
	;"const" ;"float" ;"native" ;"super" ;"while"];
      for i=1 to 1000000 do
	try Hashtbl.find kwds "while" with Not_found -> ()
      done

The pattern match is 4.1x slower that the hash table lookup on my machine.

Contrast this with the worst case for balanced trees, which is probably floats 
because the literals are loaded from memory into registers and the difference 
between fastest and slowest is only 35% and the average improvement over 
string matching is 33x faster.

So pattern matching over strings in performance critical code is a very bad 
idea with the current OCaml implementation. There are ways to work around it, 
of course, but they are non-trivial.

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