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:10)
From: Yoann Padioleau <padiolea@i...>
Subject: Re: [Caml-list] OCaml troll on Slashdot
Jon Harrop <> writes:

> 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.

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.

> 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 
> programming.

I do. As much as possible I try to have "persistent" (persistent in the okasaki sense)

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

really ? why ?

> 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 
> up.

Yoann  Padioleau,  INSA de Rennes, France
Opinions expressed here are only mine. Je n'écris qu'à titre personnel.
**____   Get Free. Be Smart.  Simply use Linux and Free Software.   ____**