[Caml-list] Hashtbl: find and find_rec

[Caml-list] Hashtbl: find and find_rec

[Arlen Cuss]

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

Re: [Caml-list] Hashtbl: find and find_rec

[Alexandre Pilkiewicz]

Hi

2011/3/7 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:

[snip]

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

I don't think stack is smaller since the find_rec function is tail
recursive. So it is basically loop unrolling (fewer branches).

What I don't really understand is why only do the unrolling on the 3
first iterations. As soon as we have an unrolled version, why not
calling it recursively?