Merge PR #13506: Micro-optimizations of the tight loop in Hashset.

Reviewed-by: SkySkimmer

1 files changed, 21 insertions, 17 deletions

diff --git a/clib/hashset.ml b/clib/hashset.ml
index 89136e7870..ae43e7db92 100644
--- a/clib/hashset.ml
+++ b/clib/hashset.ml
@@ -52,7 +52,7 @@ module Make (E : EqType) =
     mutable rover : int;               (* for internal bookkeeping *)
   }
 
-  let get_index t h = (h land max_int) mod (Array.length t.table)
+  let get_index t h = (h land max_int) mod (Array.length t)
 
   let limit = 7
   let over_limit = 2
@@ -135,7 +135,7 @@ module Make (E : EqType) =
       let add_weak ob oh oi =
         let setter nb ni _ = Weak.blit ob oi nb ni 1 in
         let h = oh.(oi) in
-        add_aux newt setter None h (get_index newt h);
+        add_aux newt setter None h (get_index newt.table h);
       in
       iter_weak add_weak t;
       t.table <- newt.table;
@@ -178,24 +178,28 @@ module Make (E : EqType) =
     in
     loop 0
 
-  let find_or h t d ifnotfound =
-    let index = get_index t h in
-    let bucket = t.table.(index) in
+  let repr h d t =
+    let table = t.table in
+    let index = get_index table h in
+    let bucket = table.(index) in
     let hashes = t.hashes.(index) in
     let sz = Weak.length bucket in
-    let rec loop i =
-      if i >= sz then ifnotfound index
-      else if Int.equal h hashes.(i) then begin
+    let pos = ref 0 in
+    let ans = ref None in
+    while !pos < sz && !ans == None do
+      let i = !pos in
+      if Int.equal h hashes.(i) then begin
         match Weak.get bucket i with
-        | Some v when E.eq v d -> v
-        | _ -> loop (i + 1)
-      end else loop (i + 1)
-    in
-    loop 0
-
-  let repr h d t =
-    let ifnotfound index = add_aux t Weak.set (Some d) h index; d in
-    find_or h t d ifnotfound
+        | Some v as res when E.eq v d -> ans := res
+        | _ -> incr pos
+      end else incr pos
+    done;
+    if !pos >= sz then
+      let () = add_aux t Weak.set (Some d) h index in
+      d
+    else match !ans with
+    | None -> assert false
+    | Some v -> v
 
   let stats t =
     let fold accu bucket = max (count_bucket 0 bucket 0) accu in