Re: [Caml-list] OCaml troll on Slashdot

[Yoann Padioleau <padiolea@irisa.fr>]

Jacques Garrigue <garrigue@math.nagoya-u.ac.jp> writes:

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

I am happy. I have learned (or re-learned) a few stuff from this thread
so in a way from this "troll"  :)
Perhaps it is not always a waste of time to post in the news :)

It would be cool if some of those insights on optimization would be put
somewhere via a wiki.
http://haskell.org/hawiki/ThingsToAvoid  is a good stard  but it is for haskell
(but many stuff said still apply to ocaml).
I am sure that I am not the only one to ask for a wiki
(and not the only one to do nothing about it :)  )

It seems that this page is no more accessible from the new website
 http://caml.inria.fr/pub/old_caml_site/FAQ/FAQ_EXPERT-eng.html#efficacite

> 
> Jacques Garrigue
> 

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