Improvements to meta allocator.

1 files changed, 40 insertions, 42 deletions

diff --git a/src/zisp/gc/meta_alloc.zig b/src/zisp/gc/meta_alloc.zig
index a600f3f..da9074a 100644
--- a/src/zisp/gc/meta_alloc.zig
+++ b/src/zisp/gc/meta_alloc.zig
@@ -33,19 +33,23 @@
 // directly store a chunk of indexes.  Concretely, nodes of this linked list
 // have the following format:
 //
-//     { next_head_idx: u32, idx_count: u32, idx_array: [idx_count]u32 }
-//
-// But with some padding to make idx_array 128-bit aligned for SIMD.
+//     {
+//       next_head_idx: u32,
+//       idx_count:     u32,
+//       _padding:      u64,
+//       idx_1:         u32,
+//       idx_2:         u32,
+//       ...
+//     }
 //
 // So, it's not a typical free-list where each node simply points to the next
 // entry; rather, each node is the first of a chunk of N entries, where the
-// remaining entries of the chunk are inlined as an array into the first.
+// indexes of the remaining N-1 entries are inlined into this head node.
 //
 // Each thread also has a small static thread-local array of indexes of most
 // recently freed slots.  This makes alloc/free extremely efficient in common
-// cases.  We fill or empty half of this array from the global free-list when
-// it's empty or full, respectively.  This forms the above mentioned chunks in
-// the global free-list.
+// cases.  We fill/empty half of this array from/to the global free-list when
+// it's empty/full; this is how the chunks in the global free-list are formed.
 //
 // == Monomorphization (or lack thereof) over size class values ==
 //
@@ -65,8 +69,8 @@ const std = @import("std");
 /// Size classes.
 const SIZES: [16]comptime_int = .{
     // Important: Ensure the smallest size class is inherently immune to false
-    // sharing, and no smaller than: 16 + RESERVE_MAX / 2 * @sizeOf(u32) bytes.
-    // That's 80 bytes assuming RESERVE_MAX = 32.
+    // sharing, and no smaller than: 16 + 4 * ( RESERVE_MAX / 2 ) many bytes.
+    // That's 80 bytes assuming RESERVE_MAX = 32 (see below).
     128,
     256,
     512,
@@ -129,7 +133,7 @@ const RESERVE_MAX = 32;
 /// thread-local reserved slots for smaller size classes.  So, for example, the
 /// size classes from 128 to 1K will use 32 thread-local reserved slots, while
 /// classes 512K to 4M will use only 4 reserved slots.
-inline fn reserveCountForSizeClassIndex(sci: u8) u8 {
+inline fn reserveCountForSizeClassIndex(sci: u8) u32 {
     return @as(u8, RESERVE_MAX) >> @intCast(sci / 4);
 }
 
@@ -143,7 +147,7 @@ const TlSlabInfo = struct {
     wm_hi: u32 = 0,
     /// Current count of entries in free slot cache.
     fc_count: u32 = 0,
-    /// Free slot cache; aligned to 16 bytes for SIMD.
+    /// Free slot cache; align to 16 for potential SIMD benefits.
     fc: [RESERVE_MAX]u32 align(16) = undefined,
 };
 
@@ -243,9 +247,7 @@ fn alloc_from_fl(
         tl.fc_count = arr[1];
         // We can safely copy more than needed since we set fc_count; this way
         // it should compile neatly into SIMD instructions.
-        const arr_u128: [*]u128 = @ptrCast(@alignCast(arr + 4));
-        const fc_u128: [*]u128 = @ptrCast(&tl.fc);
-        for (0..RESERVE_MAX / 2 / 4) |i| fc_u128[i] = arr_u128[i];
+        for (0..RESERVE_MAX / 2) |i| tl.fc[i] = arr[4 + i];
 
         return ptr;
     }
@@ -295,40 +297,38 @@ fn free_size_class(sci: u8, slot: []u8) void {
 
     const tl = &tl_slab_infos[sci];
     const slab = slabs + sci * SLAB_SIZE;
-    const res_n = reserveCountForSizeClassIndex(sci);
+    const idx: u32 = @intCast((slot.ptr - slab) / 8);
 
-    tl.fc[tl.fc_count] = @intCast((slot.ptr - slab) / 8);
-    tl.fc_count += 1;
+    const res_n = reserveCountForSizeClassIndex(sci);
 
-    // Is the local free slot cache saturated?
-    if (tl.fc_count == res_n) {
-        const info = &slab_infos[sci];
-        flush_fc(slab, info, tl);
+    if (tl.fc_count != res_n) {
+        tl.fc[tl.fc_count] = idx;
+        tl.fc_count += 1;
+        return;
     }
+
+    const info = &slab_infos[sci];
+    free_into_fl(info, tl, slot, idx, res_n / 2);
 }
 
-fn flush_fc(slab: [*]u8, info: *SlabInfo, tl: *TlSlabInfo) void {
-    var fl_head = @atomicLoad(FlHead, &info.free_list, .acquire);
-    while (true) {
-        const prev = fl_head.idx;
+fn free_into_fl(
+    info: *SlabInfo,
+    tl: *TlSlabInfo,
+    slot: []u8,
+    idx: u32,
+    n: u32,
+) void {
+    const arr: [*]u32 = @ptrCast(@alignCast(slot.ptr));
 
-        // fc_count is always even here and can be divided in equal halves.
-        const half = tl.fc_count / 2;
+    tl.fc_count = n;
 
-        const idx = tl.fc[half];
-        const ptr = slab + idx * 8;
-        const arr: [*]u32 = @ptrCast(@alignCast(ptr));
+    arr[1] = n;
+    // Safe to copy more than needed; should compile into SIMD.
+    for (0..RESERVE_MAX / 2) |i| arr[4 + i] = tl.fc[n + i];
 
-        @atomicStore(u32, &arr[0], prev, .unordered);
-        @atomicStore(u32, &arr[1], half, .unordered);
-        // Safe to copy more than needed; should compile into SIMD ops if we
-        // treat it as a u128 array.
-        const arr_u128: [*]u128 = @ptrCast(@alignCast(arr + 4));
-        const fc_u128: [*]u128 = @ptrCast(&tl.fc);
-        const start = half / 4;
-        for (0..RESERVE_MAX / 2 / 4) |i| {
-            @atomicStore(u128, &arr_u128[i], fc_u128[start + i], .unordered);
-        }
+    var fl_head = @atomicLoad(FlHead, &info.free_list, .acquire);
+    while (true) {
+        arr[0] = fl_head.idx;
         if (@cmpxchgWeak(
             FlHead,
             &info.free_list,
@@ -341,8 +341,6 @@ fn flush_fc(slab: [*]u8, info: *SlabInfo, tl: *TlSlabInfo) void {
             std.atomic.spinLoopHint();
             continue;
         }
-        tl.fc_count = half;
-
         return;
     }
 }