IstrSet: Improve resize decision.

1 files changed, 38 insertions, 19 deletions

diff --git a/src/zisp/gc/IstrSet.zig b/src/zisp/gc/IstrSet.zig
index 05a2911..35365d1 100644
--- a/src/zisp/gc/IstrSet.zig
+++ b/src/zisp/gc/IstrSet.zig
@@ -96,6 +96,8 @@ const SectorHead = packed union {
 
 buckets: []Bucket,
 
+used_sectors: usize = 0,
+
 const default_bcount = 512;
 
 pub fn init(alloc: Alloc) !Set {
@@ -103,6 +105,7 @@ pub fn init(alloc: Alloc) !Set {
 }
 
 pub fn initCustom(alloc: Alloc, bcount: usize) !Set {
+    std.debug.assert(@popCount(bcount) == 1); // Must be power of 2.
     return Set{ .buckets = try allocBuckets(alloc, bcount) };
 }
 
@@ -126,46 +129,62 @@ pub fn add(self: *Set, alloc: Alloc, s: []const u8) !IstrPtr {
 
     const idx_mask = self.buckets.len - 1;
 
-    const h0 = std.hash_map.hashString(s);
-    const hash = (h0 << 8) | s.len;
+    const real_hash = std.hash_map.hashString(s);
+    const hash = (real_hash << 8) | s.len;
 
-    // We resize if we had to walk through 50% of the buckets.
-    const probe_limit = self.buckets.len >> 1;
+    const idx_init = @as(usize, @truncate(hash & idx_mask));
 
-    var probes: usize = 0;
-    var idx = @as(usize, @truncate(hash & idx_mask));
+    var idx = idx_init;
     const s_idx = b: while (true) : (idx = (idx + 1) & idx_mask) {
-        inline for (0..1) |i| {
-            const sec = sector(self.buckets, idx, i);
-            if (sec.hash == 0) break :b i;
+        inline for (0..1) |si| {
+            const sec = sector(self.buckets, idx, si);
+            if (sec.hash == 0) break :b si;
             if (sec.match(hash, s)) |istr| return istr;
         }
-        probes += 1;
-        if (probes > probe_limit) {
-            try self.resize(alloc);
-            return self.add(alloc, s);
-        }
     };
 
+    // Check if we walked 64 buckets (4096 bytes)
+    if ((idx -% idx_init) >= 64) {
+        try self.resize(alloc);
+        return self.add(alloc, s);
+    }
+
     const sec = sector(self.buckets, idx, s_idx);
-    return sec.insert(alloc, hash, s);
+    const result = sec.insert(alloc, hash, s);
+
+    self.used_sectors += 1;
+
+    // Remember sector count = 2 * bucket count, so 16/10 is really 8/10.
+    if (self.used_sectors >= (self.buckets.len * 16) / 10) {
+        try self.resize(alloc);
+    }
+
+    return result;
 }
 
 fn resize(self: *Set, alloc: Alloc) !void {
-    const new_bc = self.buckets.len << 1;
+    const old_bc = self.buckets.len;
+    const old_bs = self.buckets;
+
+    const new_bc = old_bc << 1;
     const new_bs = try allocBuckets(alloc, new_bc);
     @memset(new_bs, std.mem.zeroes(Bucket));
 
+    // Find a cluster root
+    // const idx_init = for (old_bs, 0..) |_, idx| {
+    //     if (sector(old_bs, idx, 0).hash == 0) break idx;
+    // }
+
     const idx_mask = new_bc - 1;
 
-    for (self.buckets, 0..) |_, idx| {
+    for (old_bs, 0..) |_, idx| {
         inline for (0..1) |s_idx| {
-            const sec = sector(self.buckets, idx, s_idx);
+            const sec = sector(old_bs, idx, s_idx);
             if (sec.hash != 0) transfer(sec, new_bs, idx_mask);
         }
     }
 
-    alloc.free(self.buckets);
+    alloc.free(old_bs);
     self.buckets = new_bs;
 }