caml-list - the Caml user's mailing list
 help / color / mirror / Atom feed
* [Caml-list] Hashtbl: find and find_rec
@ 2011-03-07  6:39 Arlen Cuss
  2011-03-07 12:00 ` Alexandre Pilkiewicz
  0 siblings, 1 reply; 2+ messages in thread
From: Arlen Cuss @ 2011-03-07  6:39 UTC (permalink / raw)
  To: caml-list

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


^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2011-03-07 12:00 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2011-03-07  6:39 [Caml-list] Hashtbl: find and find_rec Arlen Cuss
2011-03-07 12:00 ` Alexandre Pilkiewicz

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).