Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
OCaml troll on Slashdot
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2005-03-16 (13:41)
From: Jacques Garrigue <garrigue@m...>
Subject: Re: [Caml-list] OCaml troll on Slashdot
From: Yoann Padioleau <>
> Jon Harrop <> writes:
> > Although Map is asymptotically faster than List.assoc for lookup (O(ln n) vs 
> > O(n)), OCaml's Hashtbl and array-based equivalents are typically several 
> > times faster than Map.
> I agree, I beleived that too but 
> I switched from Map to Hashtbl in the "troll" code and Hashtbl sux. 
> I don't know why.

Because the default hash function doesn't work well on complex
data-structures, where it has lots of collisions, and results in
putting lots of values in the same bucket. It's a bad idea to directly
use complex data structures as key anyway, but particularly bad with
hash tables.

> > In OCaml, non-tail-recursive functions are often faster than their tail 
> > recursive equivalents for small inputs (e.g. short lists). 
> really ? why ?

Because tail-recursive versions do some extra work to ensure
tail-recursiveness. For instance building a list in reverse order, and
converting it back with List.rev at the end. This only pays off for
huge lists.

Jacques Garrigue