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 (03:00)
From: Jon Harrop <jon@f...>
Subject: Re: [Caml-list] OCaml troll on Slashdot

Just for the record, I'd like to dispell a couple of myths:

On Wednesday 16 March 2005 01:05, Yoann Padioleau wrote:
> IMHO the reason it was slow is because it used associative list (instead of
> Map) for associative access,

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.

Also, I think that many people would consider the use of an imperative data 
structure, such as a hash table, for memoizing to be the remit of functional 

On Wednesday 16 March 2005 00:18, Oliver Bandel wrote:
> which does not really looks tail recursive.
> Called more than 2 * 10^6 times...
> And many other examples...

In OCaml, non-tail-recursive functions are often faster than their tail 
recursive equivalents for small inputs (e.g. short lists). I expect that the 
functions you have identified fall into this category, so converting them to 
tail-recursive form is likely to slow the program down rather than speed it 

Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists