Re: [Caml-list] OCaml troll on Slashdot

[Oliver Bandel <oliver@first.in-berlin.de>]

On Wed, Mar 16, 2005 at 10:41:08PM +0900, Jacques Garrigue wrote:
> From: Yoann Padioleau <padiolea@irisa.fr>
> > Jon Harrop <jon@ffconsultancy.com> 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.


Can you please provide more details here?!
When to use Hashtbl and when not?

Are there (freely available) papers on this theme/topic?

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

Where/when is the break-even point?

When to decide for the one or the other solution?

Trying?

Or counting the number cycles the resulting machine code will
need to do it in the one or the other way?

Or are there abstract ways of finding the break even point?

Or experience based rules of thumb?


Ciao,
   Oliver