tiny.gpalloc.class

1const std = @import("std");23pub const min_alignment: usize = 16;4pub const page_size: usize = 64 * 1024;5pub const max_small_size: usize = 32 * 1024;67pub const sizes = [_]usize{8    16,    32,    48,    64,    80,    96,    112,   128,9    160,   192,   224,   256,   320,   384,   448,   512,10    640,   768,   896,   1024,  1280,  1536,  1792,  2048,11    2560,  3072,  3584,  4096,  5120,  6144,  7168,  8192,12    10240, 12288, 14336, 16384, 20480, 24576, 28672, 32768,13};1415pub const count = sizes.len;1617const size_lookup_count = max_small_size / min_alignment + 1;18const min_alignment_shift = @ctz(@as(usize, min_alignment));19const lookup = buildLookup();2021pub fn indexFor(len: usize, alignment: std.mem.Alignment) ?usize {22    if (isDefaultAligned(alignment)) return indexForDefaultAlignment(len);23    return indexForOveraligned(len, alignment);24}2526fn isDefaultAligned(alignment: std.mem.Alignment) bool {27    return @backingInt(alignment) <= min_alignment_shift;28}2930fn indexForDefaultAlignment(len: usize) ?usize {31    std.debug.assert(len > 0);32    if (len > max_small_size) return null;3334    return lookup[(len + min_alignment - 1) >> min_alignment_shift];35}3637fn indexForOveraligned(len: usize, alignment: std.mem.Alignment) ?usize {38    std.debug.assert(len > 0);39    if (len > max_small_size) return null;4041    const alignment_bytes = alignment.toByteUnits();42    if (alignment_bytes > max_small_size) return null;43    const aligned_len = std.mem.alignForward(usize, len, alignment_bytes);44    return lookup[(aligned_len + min_alignment - 1) >> min_alignment_shift];45}4647fn indexForByScan(len: usize, alignment: std.mem.Alignment) ?usize {48    const requested_len = @max(len, min_alignment);49    if (requested_len > max_small_size) return null;5051    const requested_alignment = alignment.toByteUnits();52    const effective_alignment = @max(requested_alignment, min_alignment);53    for (sizes, 0..) |class_size, index| {54        if (class_size >= requested_len and class_size % effective_alignment == 0) {55            return index;56        }57    }58    return null;59}6061fn buildLookup() [size_lookup_count]u8 {62    @setEvalBranchQuota(2_000_000);63    var table: [size_lookup_count]u8 = undefined;64    table[0] = 0;65    for (1..size_lookup_count) |size_index| {66        const requested_len = size_index * min_alignment;67        const class_index = indexForByScan(requested_len, .fromByteUnits(min_alignment)) orelse68            @compileError("size class lookup must cover the small range");69        table[size_index] = @intCast(class_index);70    }71    return table;72}7374pub fn size(index: usize) usize {75    return sizes[index];76}7778pub fn blockAlignment(class_size: usize) usize {79    var alignment: usize = min_alignment;80    while (alignment < page_size and alignment * 2 <= class_size and class_size % (alignment * 2) == 0) {81        alignment *= 2;82    }83    return alignment;84}8586test "classes are sorted and cover the small range" {87    var previous: usize = 0;88    for (sizes) |class_size| {89        try std.testing.expect(class_size > previous);90        try std.testing.expectEqual(@as(usize, 0), class_size % min_alignment);91        previous = class_size;92    }93    try std.testing.expectEqual(max_small_size, sizes[sizes.len - 1]);94}9596test "class lookup respects requested alignment" {97    inline for (.{ 1, 2, 4, 8, 16, 32, 64, 256, 4096, 32768 }) |alignment| {98        const index = indexFor(17, .fromByteUnits(alignment)) orelse return error.MissingClass;99        const class_size = size(index);100        try std.testing.expect(class_size >= 17);101        try std.testing.expectEqual(@as(usize, 0), class_size % @max(alignment, min_alignment));102    }103}104105test "oversized or over-aligned requests bypass small classes" {106    try std.testing.expect(indexFor(max_small_size + 1, .@"1") == null);107    try std.testing.expect(indexFor(1, .fromByteUnits(page_size * 2)) == null);108}109110test "class lookup table matches scan" {111    inline for (.{112        1,   2,    4,    8,    16,   32,    64,    128,   256,113        512, 1024, 2048, 4096, 8192, 16384, 32768, 65536,114    }) |alignment| {115        var len: usize = 1;116        while (len <= max_small_size) : (len += 1) {117            try std.testing.expectEqual(118                indexForByScan(len, .fromByteUnits(alignment)),119                indexFor(len, .fromByteUnits(alignment)),120            );121        }122    }123}124125test "default aligned lookup avoids alignment scan" {126    inline for (.{ 1, 2, 4, 8, 16 }) |alignment| {127        var len: usize = 1;128        while (len <= max_small_size) : (len += 1) {129            try std.testing.expectEqual(130                indexForByScan(len, .fromByteUnits(alignment)),131                indexForDefaultAlignment(len),132            );133        }134    }135}

1pub const class = @import("class.zig");