IstrSet: Implement cluster-wise copy on resize.

1 files changed, 41 insertions, 19 deletions

diff --git a/src/zisp/gc/IstrSet.zig b/src/zisp/gc/IstrSet.zig
index 005c220..f3212ab 100644
--- a/src/zisp/gc/IstrSet.zig
+++ b/src/zisp/gc/IstrSet.zig
@@ -176,30 +176,52 @@ fn resize(self: *Set, alloc: Alloc) !void {
     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 old_mask = old_bc - 1;
+    const new_mask = new_bc - 1;
 
-    const idx_mask = new_bc - 1;
+    // Find a cluster root by searching backwards.
+    const idx_init = for (old_bs, 0..) |_, i| {
+        // old_mask = highest valid index
+        const idx = old_mask - i;
+        const s0 = sector(old_bs, idx, 0);
+        const s1 = sector(old_bs, idx, 1);
+        // NOTE: Might also end up pointing to an empty bucket
+        if (s0.hash == 0 or s1.hash == 0) break (idx + 1) & old_mask;
+    } else unreachable; // Resize at 80% guarantees empty slots.
 
-    for (old_bs, 0..) |_, idx| {
-        inline for (0..bucket_sectors) |s_idx| {
-            const sec = sector(old_bs, idx, s_idx);
-            if (sec.hash != 0) transfer(sec, new_bs, idx_mask);
+    const idx_last = (idx_init -% 1) & old_mask;
+
+    var idx = idx_init;
+    while (idx != idx_last) : (idx = (idx + 1) & old_mask) {
+        // Make sure we're at the start of a cluster
+        if (sector(old_bs, idx, 0).hash == 0) continue;
+
+        // Have to use sector offsets here
+        var dest_lo = bucket_sectors * idx;
+        var dest_hi = bucket_sectors * (idx + old_bc);
+
+        // Start copying cluster
+        const new_bs_base = @intFromPtr(new_bs.ptr);
+        b: while (idx != idx_last) : (idx = (idx + 1) & old_mask) {
+            inline for (0..bucket_sectors) |s_idx| {
+                const sec = sector(old_bs, idx, s_idx);
+                if (sec.hash == 0) break :b;
+                const new_idx = sec.hash & new_mask;
+                if (new_idx < old_bc) {
+                    const dest_addr = new_bs_base + dest_lo * sector_size;
+                    const dest: SectorPtr = @ptrFromInt(dest_addr);
+                    sec.copy(dest);
+                    dest_lo += 1;
+                } else {
+                    const dest_addr = new_bs_base + dest_hi * sector_size;
+                    const dest: SectorPtr = @ptrFromInt(dest_addr);
+                    sec.copy(dest);
+                    dest_hi += 1;
+                }
+            }
         }
     }
 
     alloc.free(old_bs);
     self.buckets = new_bs;
 }
-
-fn transfer(sec: SectorPtr, new_bs: []Bucket, idx_mask: usize) void {
-    var new_idx = @as(usize, @truncate(sec.hash & idx_mask));
-    while (true) : (new_idx = (new_idx + 1) & idx_mask) {
-        inline for (0..bucket_sectors) |new_s_idx| {
-            const new_sec = sector(new_bs, new_idx, new_s_idx);
-            if (new_sec.hash == 0) return sec.copy(new_sec);
-        }
-    }
-}