From mboxrd@z Thu Jan  1 00:00:00 1970
Received: from mail2-relais-roc.national.inria.fr (mail2-relais-roc.national.inria.fr [192.134.164.83])
	by walapai.inria.fr (8.13.6/8.13.6) with ESMTP id p276e1Ot011805
	for <caml-list@sympa-roc.inria.fr>; Mon, 7 Mar 2011 07:40:01 +0100
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AvgGAFIMdE2t/9A2/2dsb2JhbACEKJQnjX10rgKPfIEng0V2BI9zgiE
X-IronPort-AV: E=Sophos;i="4.62,276,1297033200"; 
   d="scan'208";a="92804233"
Received: from sairyx.org ([173.255.208.54])
  by mail2-smtp-roc.national.inria.fr with ESMTP; 07 Mar 2011 07:39:55 +0100
Received: by sairyx.org (Postfix, from userid 5001)
	id C618F48002; Mon,  7 Mar 2011 06:39:53 +0000 (UTC)
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on sairyx.org
X-Spam-Level: 
Received: from [192.168.200.106] (203-206-182-151.perm.iinet.net.au [203.206.182.151])
	(Authenticated sender: celtic@sairyx.org)
	by sairyx.org (Postfix) with ESMTPSA id 0485348001
	for <caml-list@inria.fr>; Mon,  7 Mar 2011 06:39:52 +0000 (UTC)
From: Arlen Cuss <celtic@sairyx.org>
To: caml-list@inria.fr
Content-Type: text/plain; charset="UTF-8"
Date: Mon, 07 Mar 2011 17:39:50 +1100
Message-ID: <1299479990.22876.15.camel@azayaka>
Mime-Version: 1.0
X-Mailer: Evolution 2.30.3 
Content-Transfer-Encoding: 7bit
Subject: [Caml-list] Hashtbl: find and find_rec

Hi all,

I'm puzzling over the OCaml source, and am trying to work out the reason
for the following definition:

----8<----
let rec find_rec key = function
    Empty ->
      raise Not_found
  | Cons(k, d, rest) ->
      if compare key k = 0 then d else find_rec key rest

let find h key =
  match h.data.((hash key) mod (Array.length h.data)) with
    Empty -> raise Not_found
  | Cons(k1, d1, rest1) ->
      if compare key k1 = 0 then d1 else
      match rest1 with
        Empty -> raise Not_found
      | Cons(k2, d2, rest2) ->
          if compare key k2 = 0 then d2 else
          match rest2 with
            Empty -> raise Not_found
          | Cons(k3, d3, rest3) ->
              if compare key k3 = 0 then d3 else find_rec key rest3
----8<----

My only guess thus far is that it's cheaper if we don't recurse (stack
doesn't grow as much, fewer branches), and thus a few levels of testing
are put in for good measure to speed up the case where it's one of the
first three items.

Is this it? Or am I missing something else?

Cheers,
Arlen