[Caml-list] Hashtbl: find and find_rec

[Arlen Cuss <celtic@sairyx.org>]

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