From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail4-relais-sop.national.inria.fr (mail4-relais-sop.national.inria.fr [192.134.164.105])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p6RL7T1r030321
	for <caml-list@sympa-roc.inria.fr>; Wed, 27 Jul 2011 23:07:29 +0200
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AssBAPh8ME7RVaE0imdsb2JhbABPAjIBHxwCAxQQFiIYAwIBAgECFBIBBQErDg8BAR+nHAgUAQEBCgkNBxIGIYh+AqFwglIKjCqCUIR8O4htAgMGhjoEknWFB4Emgz+CXjyDXQ
X-IronPort-AV: E=Sophos;i="4.67,278,1309730400"; 
   d="scan'208";a="104053666"
Received: from mail-fx0-f52.google.com ([209.85.161.52])
  by mail4-smtp-sop.national.inria.fr with ESMTP/TLS/RC4-SHA; 27 Jul 2011 23:07:23 +0200
Received: by fxd18 with SMTP id 18so715765fxd.39
        for <caml-list@yquem.inria.fr>; Wed, 27 Jul 2011 14:07:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=gamma;
        h=message-id:date:from:user-agent:mime-version:to:subject
         :content-type:content-transfer-encoding;
        bh=JIwwCev9SiJY8UfvSLijapWijH8QKMGJIYLQwumza3k=;
        b=WX9sMqw/ryLBkaaJtDFkM9NMP8Uir9WDRifZfBX3jv26qjPkD69k4nBJLxBPIELbzF
         +v/TZEfcti2EJf9hdqt5oUt624M3KGuoB0BeZOnYUw93c+I+wLAcRPOPRuHKGRveVcCD
         89uzvyaaJsdiilkYL158PCwCgtwHCg7PbQawc=
Received: by 10.223.64.66 with SMTP id d2mr177040fai.116.1311800841737;
        Wed, 27 Jul 2011 14:07:21 -0700 (PDT)
Received: from [192.168.1.64] (94-193-173-247.zone7.bethere.co.uk [94.193.173.247])
        by mx.google.com with ESMTPS id p17sm75850fak.1.2011.07.27.14.07.19
        (version=TLSv1/SSLv3 cipher=OTHER);
        Wed, 27 Jul 2011 14:07:20 -0700 (PDT)
Message-ID: <4E307DFE.3040502@gmail.com>
Date: Wed, 27 Jul 2011 22:07:10 +0100
From: Toby Kelsey <toby.kelsey@gmail.com>
User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:1.9.2.18) Gecko/20110617 Lightning/1.0b2 Thunderbird/3.1.11
MIME-Version: 1.0
To: caml-list <caml-list@yquem.inria.fr>
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Subject: [Caml-list] Hashtbl performance

I have written two versions of a small program, one using an (int list) data structure and the other an ((int*int) list); and I tested using Hashtbl, Set and (Jean-Christophe Filliatre's) Trie to cache these elements in each version.
The relative run times of the programs turns out to be:

                 Hashtbl  Set  Trie
(int list)         1      2.1  2.0
((int*int) list)  34.7    2.6  2.1


There is a slight inherent speed difference between the 2 versions but the major effect is the cache type (in fact the caching difference must be larger than these ratios due to non-cache computations). I expected Hashtbl might be a bit slower than more specialised data structures, but the large speed difference with different data structures was unexpected. Presumably the slow-down is due to excessive hash collisions.

I had expected that the generic Hashtbl would be written to give adequate speed for all types of data and when I look at OCaml code on the web Hashtbl is usually used, so it seems most OCaml programmers believe the standard Hashtbl is a reasonable choice for most data types as well.

I haven't tested the Batteries or OCaml-Core hash tables so these may be more consistent, but if not, my question is can you predict how well Hashtbl will work for different types of data and so what to use it with, or it is just not reliable enough for general-purpose caching/memoization?

If anyone wants to look at the code, the (int list) Hashtbl version is at <http://rosettacode.org/wiki/Sokoban#OCaml> and the other versions are in <http://pastebin.com/hGn1AL9L> temporarily. Apart from the caching and the int/int pair changes they should be identical.

Toby