From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <oliver@first.in-berlin.de>
Delivered-To: caml-list@yquem.inria.fr
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78])
	by yquem.inria.fr (Postfix) with ESMTP id 89ED9BC48
	for <caml-list@yquem.inria.fr>; Thu, 17 Mar 2005 11:20:08 +0100 (CET)
Received: from first.in-berlin.de (dialin-145-254-054-177.arcor-ip.net [145.254.54.177])
	by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j2HAK69c022431
	for <caml-list@yquem.inria.fr>; Thu, 17 Mar 2005 11:20:07 +0100
Received: by first.in-berlin.de (Postfix, from userid 501)
	id 82CCEBC2A0; Thu, 17 Mar 2005 01:14:01 +0100 (CET)
Date: Thu, 17 Mar 2005 01:14:01 +0100
From: Oliver Bandel <oliver@first.in-berlin.de>
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] OCaml troll on Slashdot
Message-ID: <20050317001400.GC439@first.in-berlin.de>
References: <20050316001819.GB347@first.in-berlin.de> <200503160301.11138.jon@ffconsultancy.com> <m31xaf4tzi.fsf@ryxa.irisa.fr> <20050316.224108.35690658.garrigue@math.nagoya-u.ac.jp>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20050316.224108.35690658.garrigue@math.nagoya-u.ac.jp>
User-Agent: Mutt/1.5.6i
X-Miltered: at nez-perce with ID 423959D6.004 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)!
X-Spam: no; 0.00; oliver:01 bandel:01 oliver:01 in-berlin:01 caml-list:01 ocaml:01 irisa:01 ocaml's:01 hashtbl:01 hashtbl:01 hash:01 hash:01 ocaml:01 recursive:01 inputs:01 
X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr
X-Spam-Status: No, score=0.3 required=5.0 tests=DATE_IN_PAST_06_12,
	FORGED_RCVD_HELO autolearn=disabled version=3.0.2
X-Spam-Level: 

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