What is a match statement translated into?

What is a match statement translated into?

[Joel Reymont]

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?

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.

	Thanks, Joel

--
http://wagerlabs.com

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

[Jacques GARRIGUE]

From: Joel Reymont <joelr1@gmail.com>

> 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)?

I do not understand your description of C compilation: this certainly
depends a lot on the compiler and the optimization level.
OCaml does different things according to the data matched, using a
table when it is compact enough, or branches otherwise. So there is
no uniform answer, just that it is rather optimized.

> How do I find out?
> 
> 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.

No need to disassemble: you can just dump the assembler with the -S
flag. And this is probably the most instructive approach, as the
compiler itself is quite involved.

Jacques Garrigue

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

[Jon Harrop]

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