Hashtbl find_opt function

hashtbl
#1

I found this code for the Hashtbl.find_opt function while looking at the implementation of Hashtbl in the standard library.

let rec find_rec_opt key = function
  | Empty ->
      None
  | Cons{key=k; data; next} ->
      if compare key k = 0 then Some data else find_rec_opt key next

let find_opt h key =
  match h.data.(key_index h key) with
  | Empty -> None
  | Cons{key=k1; data=d1; next=next1} ->
      if compare key k1 = 0 then Some d1 else
      match next1 with
      | Empty -> None
      | Cons{key=k2; data=d2; next=next2} ->
          if compare key k2 = 0 then Some d2 else
          match next2 with
          | Empty -> None
          | Cons{key=k3; data=d3; next=next3} ->
              if compare key k3 = 0 then Some d3 else find_rec_opt key next3

Does anybody know why they chose to manually perform a pattern matching on the 3 first buckets before calling find_rec_opt ? I suppose it is for performance reasons, but isn’t tail recursion optimised by the compiler ? How does a manual match impact performance on a positive way ?

Thanks for your answers.

0 Likes

#2

This looks like loop unrolling.

0 Likes