lib/gpalloc/src/cache/thread.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const size_class = @import("../root.zig").class;
  3 
  4 pub const capacity: u16 = 960;
  5 pub const extra_bin_capacity: u16 = 1088;
  6 pub const target_bytes: usize = 64 * 1024;
  7 pub const refill_max: usize = 256;
  8 pub const tight_class_size: usize = 80;
  9 pub const tight_class_capacity: u16 = 512;
 10 pub const preload_class_size: usize = 96;
 11 pub const preload_class_refill_max: usize = 512;
 12 pub const extra_class_sizes = [_]usize{ 32, 48 };
 13 pub const extra_class_capacities = [_]u16{ 1088, 405 };
 14 pub const extra_class_count: usize = extra_class_sizes.len;
 15 pub const extra_class_refill_max: usize = 512;
 16 pub const fixed_class_count: usize = 20;
 17 
 18 const class_limits = buildClassLimits();
 19 const extra_class_indices = buildExtraClassIndices();
 20 
 21 pub fn classLimit(class_index: usize) u16 {
 22     return class_limits[class_index];
 23 }
 24 
 25 fn buildClassLimits() [size_class.count]u16 {
 26     var limits: [size_class.count]u16 = undefined;
 27     for (&limits, 0..) |*limit, class_index| {
 28         const class_size = size_class.size(class_index);
 29         const by_bytes = @max(@as(usize, 1), target_bytes / class_size);
 30         const by_slots = slotCapacity(class_index);
 31         limit.* = @intCast(@min(by_slots, by_bytes));
 32     }
 33     return limits;
 34 }
 35 
 36 fn slotCapacity(class_index: usize) usize {
 37     const class_size = size_class.size(class_index);
 38     if (class_size == tight_class_size) return tight_class_capacity;
 39     return @as(usize, capacity) + extraCapacity(class_index);
 40 }
 41 
 42 pub fn extraCapacity(class_index: usize) u16 {
 43     return if (extraClassIndex(class_index)) |extra_index| extra_class_capacities[extra_index] else 0;
 44 }
 45 
 46 pub fn extraClassIndex(class_index: usize) ?usize {
 47     inline for (extra_class_indices, 0..) |extra_class_index, extra_index| {
 48         if (class_index == extra_class_index) return extra_index;
 49     }
 50     return null;
 51 }
 52 
 53 pub fn refillCount(class_index: usize) usize {
 54     const cache_limit = classLimit(class_index);
 55     if (extraClassIndex(class_index) != null) return @min(extra_class_refill_max, cache_limit);
 56     if (size_class.size(class_index) == preload_class_size) return @min(preload_class_refill_max, cache_limit);
 57     return @min(refill_max, cache_limit);
 58 }
 59 
 60 pub fn drainCount(cache_limit: u16) usize {
 61     return @max(@as(usize, 1), @as(usize, cache_limit) / 2);
 62 }
 63 
 64 fn buildExtraClassIndices() [extra_class_count]usize {
 65     var indices: [extra_class_count]usize = undefined;
 66     for (extra_class_sizes, 0..) |extra_class_size, extra_index| {
 67         for (size_class.sizes, 0..) |class_size, class_index| {
 68             if (class_size == extra_class_size) {
 69                 indices[extra_index] = class_index;
 70                 break;
 71             }
 72         } else {
 73             @compileError("missing thread extra size class");
 74         }
 75     }
 76     return indices;
 77 }
 78 
 79 test "thread class limits match byte and slot caps" {
 80     for (size_class.sizes, 0..) |class_size, class_index| {
 81         const by_bytes = @max(@as(usize, 1), target_bytes / class_size);
 82         const by_slots = slotCapacity(class_index);
 83         const expected: u16 = @intCast(@min(by_slots, by_bytes));
 84         try std.testing.expectEqual(expected, classLimit(class_index));
 85     }
 86 }
 87 
 88 test "thread refill counts match class limits" {
 89     for (size_class.sizes, 0..) |_, class_index| {
 90         const cache_limit = classLimit(class_index);
 91         const expected = if (extraClassIndex(class_index) != null)
 92             @min(extra_class_refill_max, cache_limit)
 93         else if (size_class.size(class_index) == preload_class_size)
 94             @min(preload_class_refill_max, cache_limit)
 95         else
 96             @min(refill_max, cache_limit);
 97         try std.testing.expectEqual(expected, refillCount(class_index));
 98     }
 99 }
100 
101 test "preload class uses larger refill batches within the byte cap" {
102     const preload_class = size_class.indexFor(preload_class_size, .@"1").?;
103     try std.testing.expectEqual(@as(usize, preload_class_refill_max), refillCount(preload_class));
104     try std.testing.expect(refillCount(preload_class) < classLimit(preload_class));
105 
106     const following_class = size_class.indexFor(112, .@"1").?;
107     try std.testing.expectEqual(@as(usize, refill_max), refillCount(following_class));
108 }
109 
110 test "extra classes use extra slot capacity and refill batches" {
111     inline for (extra_class_sizes, extra_class_capacities) |extra_class_size, extra_capacity| {
112         const class_index = size_class.indexFor(extra_class_size, .@"1").?;
113         try std.testing.expect(extraClassIndex(class_index) != null);
114         try std.testing.expectEqual(extra_capacity, extraCapacity(class_index));
115         try std.testing.expectEqual(@min(extra_class_refill_max, classLimit(class_index)), refillCount(class_index));
116     }
117 }