From 86e77fc35b3a9146a31b872643a85f8f6a486a07 Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Thu, 2 Jul 2026 06:14:48 +0200 Subject: Exciting things are happening. - Vague Posting King --- src/zisp/gc.zig | 39 ++++-- src/zisp/gc/CodePool.zig | 357 ----------------------------------------------- src/zisp/gc/ListPool.zig | 357 +++++++++++++++++++++++++++++++++++++++++++++++ src/zisp/value.zig | 32 ++++- src/zisp/value/array.zig | 137 ++++++++++-------- src/zisp/value/pair.zig | 23 ++- 6 files changed, 503 insertions(+), 442 deletions(-) delete mode 100644 src/zisp/gc/CodePool.zig create mode 100644 src/zisp/gc/ListPool.zig (limited to 'src') diff --git a/src/zisp/gc.zig b/src/zisp/gc.zig index 0e26aa9..b36628f 100644 --- a/src/zisp/gc.zig +++ b/src/zisp/gc.zig @@ -5,25 +5,26 @@ const Alloc = std.mem.Allocator; const value = @import("value.zig"); -pub const CodePool = @import("gc/CodePool.zig"); +pub const ListPool = @import("gc/ListPool.zig"); pub const IstrPool = @import("gc/IstrPool.zig"); const HeapPtr = value.HeapPtr; +const HeapType = value.HeapType; var main_alloc: Alloc = undefined; -var code_heap_start: usize = undefined; +var list_heap_start: usize = undefined; var main_heap_start: usize = undefined; var istr_heap_start: usize = undefined; var main_list_pool: ListPool = undefined; var main_istr_pool: IstrPool = undefined; -pub fn codePtrFromIdx(idx: u32) [*]Value { - return @ptrFromInt(code_heap_start + idx * 8); +pub fn listPtrFromIdx(idx: u32) [*]Value { + return @ptrFromInt(list_heap_start + idx * 8); } -pub fn heapPtrFromIdx(idx: u32) HeapPtr { +pub fn heapPtrFromIdx(comptime typ: HeapType, idx: u32) typ.PtrType() { return @ptrFromInt(main_heap_start + idx * 8); } @@ -31,8 +32,8 @@ pub fn istrPtrFromIdx(idx: u32) [*]const u8 { return @ptrFromInt(istr_heap_start + idx); } -pub fn codeIdxFromPtr(ptr: [*]Value) u32 { - return @intCast(@intFromPtr(ptr - code_heap_start) / 8); +pub fn listIdxFromPtr(ptr: [*]Value) u32 { + return @intCast(@intFromPtr(ptr - list_heap_start) / 8); } pub fn heapIdxFromPtr(ptr: HeapPtr) u32 { @@ -43,6 +44,26 @@ pub fn istrIdxFromPtr(ptr: [*]const u8) u32 { return @intCast(@intFromPtr(ptr - istr_heap_start)); } +pub fn allocHeap(comptime typ: HeapType, len: usize) !typ.PtrType() { + const aln = std.mem.Alignment.of(HeapPtr); + return @ptrCast(main_alloc.alignedAlloc(u8, aln, len)); +} + +pub fn createHeap(comptime typ: HeapType) !typ.PtrType() { + return @ptrCast(main_alloc.create(typ.ObjType())); +} + +pub fn packHeap(ptr: anytype) Value { + const idx = heapIdxFromPtr(ptr); + const typ = value.HeapType.of(ptr); + return .{ .hptr = .{ .idx = idx, .typ = typ } }; +} + +pub fn unpackHeap(comptime typ: HeapType, v: Value) typ.PtrType() { + if (!v.isHptrTyp(typ)) @panic("Wrong type."); + return heapPtrFromIdx(typ, v.hptr.idx); +} + // init var init_done = false; @@ -53,10 +74,10 @@ pub fn init() !void { main_alloc = std.heap.smp_allocator; - //code_heap_start = ...; + //list_heap_start = ...; main_list_pool = try ListPool.init(main_alloc); - main_istr_set = try IstrPool.init(main_alloc); + main_istr_pool = try IstrPool.init(main_alloc); } pub fn mainAlloc() Alloc { diff --git a/src/zisp/gc/CodePool.zig b/src/zisp/gc/CodePool.zig deleted file mode 100644 index 56bf384..0000000 --- a/src/zisp/gc/CodePool.zig +++ /dev/null @@ -1,357 +0,0 @@ -//! List allocation with optimization for short lists: -//! -//! The point of this is to ensure that whenever code consists of a bunch of -//! short lists, which is almost always the case for Lisp code, their elements -//! are allocated in tight bundles, without any padding, making them share a -//! cache line, or at least a page, whenever possible. -//! -//! To this effect, we allocate memory in blocks, and create the next whenever -//! the current one doesn't have enough space left for a requested allocation. -//! A block should be the size of a page or a multiple thereof. We have three -//! types of block; the first is the FlexiBlock which fulfills our goal of no -//! padding among short lists. -//! -//! Example of how a series of short list allocations (labeled a to e) may have -//! their elements allocated within a FlexiBlock: -//! -//! [ a0 a1 a2 b0 b1 b2 b3 b4 c0 d0 d1 e0 e1 e2 e3 __ __ __ __ ... ] -//! ^ ^ ^ ^ ^ ^ -//! a[3] b[5] c[1] d[2] e[4] FREE -> -//! -//! For list element counts of up to 8, each count is its own size class, and -//! they are allocated serially in a FlexiBlock without padding. Deallocation -//! pushes the freed heap index into a free-list for that exact list size. -//! -//! If the array 'b' were to be freed, its heap index (pointing to b0) would be -//! pushed onto free_lists[4] which holds the list of freed 5-element arrays in -//! already allocated blocks. -//! -//! Over time, each FlexiBlock ends up being "frozen" into a specific run of -//! size classes, since we never try to find adjacent freed arrays, but this -//! shouldn't be a problem since lists of length 1 to 8 are very frequent in -//! source code and should see high reuse. -//! -//! The second type of block is the ChunkBlock which introduces some waste to -//! reduce fragmentation for moderate-length lists. In the following, the -//! abbreviation 'CM' stands for ChunkMax: -//! -//! For element counts 9 to CM, we split blocks into a series of "chunks" where -//! each chunk has space for an array within a certain size class, such as 9 to -//! 12 elements, 13 to 16 elements, and so on. Thus, freeing a list of e.g. 11 -//! elements frees a chunk that can hold any list 9 to 12 elements. This helps -//! against fragmentation, since lists in these size ranges aren't as common as -//! the shorter ones, making free-lists for specific element counts impractical. -//! -//! A request for a list of e.g. 12 elements could still be fulfilled by chunks -//! larger than that, if the size class 9-12 is depleted. This avoids causing -//! too much wasted space if larger lists occur very rarely in source code. -//! -//! To perfectly fill a 4 KiB page, which can hold 512 Value (64-bit) elements, -//! we could combine various chunk sizes and counts (size classes). Currently, -//! the following is in use: -//! -//! 30 * 12 + 8 * 16 + 1 * 24 = 512 -//! -//! We could increase CM from 24 to e.g. 32, or use blocks that are multiple -//! pages in size, in which case the chunk split could take various different -//! forms; we could use empiric testing over large bodies of code to find an -//! optimum, but it's unlikely to make a difference since list sizes < 9 are -//! extremely dominant. -//! -//! Chunk use within the current (last allocated) block is kept track of via a -//! bit-map that indicates the used or not status of each chunk regardless of -//! size class. Finding the first available chunk for a given size class is -//! then a matter of (optionally) applying a bit-mask to mask out the bits for -//! the smaller size classes, followed with a bit-counting operation to locate -//! the index of the first suitable chunk. Since chunks have different sizes, -//! this index is mapped to an actual byte offset via a static lookup table. -//! -//! Upon deallocation, we can use 'MOD block_size' on the heap index of the -//! list, combined with a small series of less-than checks, to figure out the -//! size class. -//! -//! As an example: If the first group of chunks occupy elements [0, 24*12), and -//! we're given heap index J for a list to be deallocated, we can check if it's -//! in that first group by testing: J % 512 < 24*12 -//! -//! Finally, we have the ArrayBlock, which is simply an N-array of M-element -//! chunks. Currently, we use N = 64 with M = 32. This is probably not the -//! most useful optimization, but it's easy to implement anyway. -//! -//! Starting from 33 elements, we stop caring and call the underlying allocator -//! directly, since lists that long in source code are extremely rare. -//! -//! The main remaining issue that all of the above cannot solve is that if we -//! free and allocate new code repeatedly (e.g. of whole modules), each time -//! there will be bits and pieces that end up in a completely different place -//! due to the frozen nature of FlexiBlocks. E.g. freeing a module may have -//! freed 25 arrays of length 6, but the newly loaded code needs 28 arrays of -//! length 6, so three of them land somewhere far away. -//! -//! This shouldn't affect programs that simply load up all their modules, run -//! forever without dynamic modification, and thus never deallocate code. -//! -//! Otherwise, a simple solution is to use separate CodePool instances for -//! modules, or just forget about all of this and rely on a compacting GC. -//! - -const std = @import("std"); - -const Alloc = std.mem.Allocator; - -const gc = @import("../gc.zig"); -const value = @import("../value.zig"); -const seg_stack = @import("../util/seg_stack.zig"); - -const Value = value.Value; -const SegStack = seg_stack.SegStack; - -const i2p = gc.codePtrFromIdx; -const p2i = gc.codeIdxFromPtr; - -const Self = @This(); - -// 4 KiB blocks fit 512 Value elements, which should be good. -const block_size = 4096 / @sizeOf(Value); -const Block = [block_size]Value; - -// 30 + 8 + 1 chunk indices mapping to value indices (0-511). Value indices -// should be multiples of 2 (and even 4) so we could divide them to make them -// fit in a u8 each, fitting the whole map in a cache line, but then we'd need -// to multiply them (shift-left) on extraction, so whatever. -const chunk_real_idx_map: [39]u16 = undefined; -comptime { - // zig fmt: off - for ( 0..30) |i| chunk_real_idx_map[i] = ( i * 12 + 0 * 16); - for (30..38) |i| chunk_real_idx_map[i] = (30 * 12 + i * 16); - for (38..39) |i| chunk_real_idx_map[i] = (30 * 12 + 8 * 16); - // zig fmt: on -} - -const chunk_empty_all: u64 = 2 ^ 39 - 1; - -// zig fmt: off -const chunk_empty_sml: u64 = (2 ^ 30 - 1) << 0; -const chunk_empty_mid: u64 = (2 ^ 8 - 1) << 30; -const chunk_empty_big: u64 = (2 ^ 1 - 1) << 38; -// zig fmt: on - -const array_block_chunk_size = 32; -const array_block_max_index = block_size / array_block_chunk_size; - -alloc: Alloc, - -cur_flexi_block: *Block, -cur_chunk_block: *Block, -cur_array_block: *Block, - -cur_flexi_index: u16 = 0, -cur_chunk_empty: u64 = chunk_empty_all, -cur_array_index: u8 = 0, - -flexi_block_stack: SegStack(*Block, 512), -chunk_block_stack: SegStack(*Block, 256), -array_block_stack: SegStack(*Block, 64), - -flexi_free_lists: [8]SegStack(u32, 256), -chunk_free_lists: [3]SegStack(u32, 256), -array_free_list: SegStack(u32, 64), - -pub fn init(alloc: Alloc) !Self { - return .{ - .alloc = alloc, - .cur_flexi_block = try alloc.create(Block), - .cur_chunk_block = try alloc.create(Block), - .cur_array_block = try alloc.create(Block), - .flexi_block_stack = try .init(alloc), - .chunk_block_stack = try .init(alloc), - .array_block_stack = try .init(alloc), - .flexi_free_lists = .{ - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - }, - .chunk_free_lists = .{ - try .init(alloc), - try .init(alloc), - try .init(alloc), - }, - .array_free_list = try .init(alloc), - }; -} - -pub fn deinit(self: *Self) void { - self.array_free_list.deinit(self.alloc); - for (self.chunk_free_lists) |l| l.deinit(self.alloc); - for (self.flexi_free_lists) |l| l.deinit(self.alloc); - - while (self.array_block_stack.pop(self.alloc)) |b| self.alloc.destroy(b); - while (self.chunk_block_stack.pop(self.alloc)) |b| self.alloc.destroy(b); - while (self.flexi_block_stack.pop(self.alloc)) |b| self.alloc.destroy(b); - - self.array_block_stack.deinit(self.alloc); - self.chunk_block_stack.deinit(self.alloc); - self.flexi_block_stack.deinit(self.alloc); - - self.alloc.destroy(self.cur_array_block); - self.alloc.destroy(self.cur_chunk_block); - self.alloc.destroy(self.cur_flexi_block); -} - -fn newFlexiBlock(self: *Self, rem_len: u8) !void { - if (rem_len != 0) { - self.flexi_free_lists[rem_len - 1].push(self.curFlexiBlockPtr()); - } - try self.flexi_block_stack.push(self.alloc, self.cur_flexi_block); - self.cur_flexi_block = try self.alloc.create(Block); - self.cur_flexi_index = 0; -} - -fn newChunkBlock(self: *Self) !void { - // Put unused chunks in free lists: - var empty = self.cur_chunk_empty; - while (empty != 0) { - const idx = @ctz(chunks); - if (idx < 30) { - const heap_idx = p2i(curChunkBlockPtr(idx)); - self.chunk_free_lists[0].push(self.alloc, heap_idx); - empty &= ~@shlExact(@as(u64, 1), @intCast(idx)); - } else if (idx < 38) { - const heap_idx = p2i(curChunkBlockPtr(idx)); - self.chunk_free_lists[1].push(self.alloc, heap_idx); - empty &= ~@shlExact(@as(u64, 1), @intCast(idx)); - } else { - const heap_idx = p2i(curChunkBlockPtr(38)); - self.chunk_free_lists[2].push(self.alloc, heap_idx); - break; - } - } - try self.chunk_block_stack.push(self.alloc, self.cur_chunk_block); - self.cur_chunk_block = try self.alloc.create(Block); - self.cur_chunk_empty = chunk_empty_all; -} - -fn newArrayBlock(self: *Self) !void { - try self.array_block_stack.push(self.alloc, self.cur_array_block); - self.cur_array_block = try self.alloc.create(Block); - self.cur_array_index = 0; -} - -fn curFlexiBlockPtr(self: *Self) [*]Value { - return @ptrCast(&self.cur_flexi_block[self.cur_flexi_index]); -} - -fn curChunkBlockPtr(self: *Self, idx: u8) [*]Value { - const real_idx = chunk_real_idx_map[idx]; - return @ptrCast(&self.cur_chunk_block[real_idx]); -} - -fn curArrayBlockPtr(self: *Self) [*]Value { - const idx = self.cur_array_index * array_block_chunk_size; - return @ptrCast(&self.cur_array_block[idx]); -} - -pub fn allocVals(self: *Self, len: u8) ![*]Value { - std.debug.assert(len != 0); - - if (len > array_block_chunk_size) { - @branchHint(.unlikely); - return self.alloc.alloc(Value, len); - } - - if (len > 24) { - @branchHint(.unlikely); - if (self.array_free_list.pop(self.alloc)) |i| return i2p(i); - if (self.cur_array_index == array_block_max_index) { - try self.newArrayBlock(); - } - defer self.cur_array_index += 1; - return self.curArrayBlockPtr(); - } - - if (len > 16) { - @branchHint(.unlikely); - if (self.chunk_free_lists[2].pop(self.alloc)) |i| return i2p(i); - if ((self.cur_chunk_empty & chunk_empty_big) == 0) { - try self.newChunkBlock(); - } - self.cur_chunk_empty &= ~chunk_empty_big; - return self.curChunkBlockPtr(38); - } - - if (len > 12) { - @branchHint(.unlikely); - if (self.chunk_free_lists[1].pop(self.alloc)) |i| return i2p(i); - if (self.chunk_free_lists[2].pop(self.alloc)) |i| return i2p(i); - const empty = self.cur_chunk_empty & ~chunk_empty_sml; - if (empty != 0) { - const idx: u8 = @ctz(empty); - self.cur_chunk_empty &= ~@shlExact(@as(u64, 1), @intCast(idx)); - return self.curChunkBlockPtr(idx); - } else { - try self.newChunkBlock(); - self.cur_chunk_empty &= ~(1 << 30); - return self.curChunkBlockPtr(30); - } - } - - if (len > 8) { - if (self.chunk_free_lists[0].pop(self.alloc)) |i| return i2p(i); - if (self.chunk_free_lists[1].pop(self.alloc)) |i| return i2p(i); - if (self.chunk_free_lists[2].pop(self.alloc)) |i| return i2p(i); - const empty = self.cur_chunk_empty; - if (empty != 0) { - const idx: u8 = @ctz(empty); - self.cur_chunk_empty &= ~@shlExact(@as(u64, 1), @intCast(idx)); - return self.curChunkBlockPtr(idx); - } else { - try self.newChunkBlock(); - self.cur_chunk_empty &= ~@as(u64, 1); - return self.curChunkBlockPtr(0); - } - } - - if (self.flexi_free_lists[len - 1].pop(self.alloc)) |i| return i2p(i); - - const rem_len = self.cur_flexi_block.len - self.cur_flexi_index; - if (len > rem_len) try self.newFlexiBlock(rem_len); - - defer self.current_index += len; - return self.curBlockPtr(); -} - -pub fn freeVals(self: *Self, len: u8, ptr: [*]Value) !void { - std.debug.assert(len != 0); - if (len > array_block_chunk_size) { - @branchHint(.unlikely); - return self.alloc.free(ptr); - } - const idx = p2i(ptr); - if (len > 24) { - @branchHint(.unlikely); - return self.array_free_list.push(self.alloc, idx); - } - if (len > 16) { - @branchHint(.unlikely); - return self.chunk_free_lists[2].push(self.alloc, idx); - } - if (len > 12) { - @branchHint(.unlikely); - return self.chunk_free_lists[1].push(self.alloc, idx); - } - if (len > 8) { - return self.chunk_free_lists[0].push(self.alloc, idx); - } - return self.flexi_free_lists[len - 1].push(self.alloc, idx); -} - -pub fn freeList(self: *Self, list: Value) !void { - const len = value.list.getLenTag(list); - const ptr = value.list.getValPtr(list); - try self.freeVals(len, ptr); -} diff --git a/src/zisp/gc/ListPool.zig b/src/zisp/gc/ListPool.zig new file mode 100644 index 0000000..42bb50e --- /dev/null +++ b/src/zisp/gc/ListPool.zig @@ -0,0 +1,357 @@ +//! List allocation with optimization for short lists: +//! +//! The point of this is to ensure that whenever code consists of a bunch of +//! short lists, which is almost always the case for Lisp code, their elements +//! are allocated in tight bundles, without any padding, making them share a +//! cache line, or at least a page, whenever possible. +//! +//! To this effect, we allocate memory in blocks, and create the next whenever +//! the current one doesn't have enough space left for a requested allocation. +//! A block should be the size of a page or a multiple thereof. We have three +//! types of block; the first is the FlexiBlock which fulfills our goal of no +//! padding among short lists. +//! +//! Example of how a series of short list allocations (labeled a to e) may have +//! their elements allocated within a FlexiBlock: +//! +//! [ a0 a1 a2 b0 b1 b2 b3 b4 c0 d0 d1 e0 e1 e2 e3 __ __ __ __ ... ] +//! ^ ^ ^ ^ ^ ^ +//! a[3] b[5] c[1] d[2] e[4] FREE -> +//! +//! For list element counts of up to 8, each count is its own size class, and +//! they are allocated serially in a FlexiBlock without padding. Deallocation +//! pushes the freed heap index into a free-list for that exact list size. +//! +//! If the array 'b' were to be freed, its heap index (pointing to b0) would be +//! pushed onto free_lists[4] which holds the list of freed 5-element arrays in +//! already allocated blocks. +//! +//! Over time, each FlexiBlock ends up being "frozen" into a specific run of +//! size classes, since we never try to find adjacent freed arrays, but this +//! shouldn't be a problem since lists of length 1 to 8 are very frequent in +//! source code and should see high reuse. +//! +//! The second type of block is the ChunkBlock which introduces some waste to +//! reduce fragmentation for moderate-length lists. In the following, the +//! abbreviation 'CM' stands for ChunkMax: +//! +//! For element counts 9 to CM, we split blocks into a series of "chunks" where +//! each chunk has space for an array within a certain size class, such as 9 to +//! 12 elements, 13 to 16 elements, and so on. Thus, freeing a list of e.g. 11 +//! elements frees a chunk that can hold any list 9 to 12 elements. This helps +//! against fragmentation, since lists in these size ranges aren't as common as +//! the shorter ones, making free-lists for specific element counts impractical. +//! +//! A request for a list of e.g. 12 elements could still be fulfilled by chunks +//! larger than that, if the size class 9-12 is depleted. This avoids causing +//! too much wasted space if larger lists occur very rarely in source code. +//! +//! To perfectly fill a 4 KiB page, which can hold 512 Value (64-bit) elements, +//! we could combine various chunk sizes and counts (size classes). Currently, +//! the following is in use: +//! +//! 30 * 12 + 8 * 16 + 1 * 24 = 512 +//! +//! We could increase CM from 24 to e.g. 32, or use blocks that are multiple +//! pages in size, in which case the chunk split could take various different +//! forms; we could use empiric testing over large bodies of code to find an +//! optimum, but it's unlikely to make a difference since list sizes < 9 are +//! extremely dominant. +//! +//! Chunk use within the current (last allocated) block is kept track of via a +//! bit-map that indicates the used or not status of each chunk regardless of +//! size class. Finding the first available chunk for a given size class is +//! then a matter of (optionally) applying a bit-mask to mask out the bits for +//! the smaller size classes, followed with a bit-counting operation to locate +//! the index of the first suitable chunk. Since chunks have different sizes, +//! this index is mapped to an actual byte offset via a static lookup table. +//! +//! Upon deallocation, we can use 'MOD block_size' on the heap index of the +//! list, combined with a small series of less-than checks, to figure out the +//! size class. +//! +//! As an example: If the first group of chunks occupy elements [0, 24*12), and +//! we're given heap index J for a list to be deallocated, we can check if it's +//! in that first group by testing: J % 512 < 24*12 +//! +//! Finally, we have the ArrayBlock, which is simply an N-array of M-element +//! chunks. Currently, we use N = 64 with M = 32. This is probably not the +//! most useful optimization, but it's easy to implement anyway. +//! +//! Starting from 33 elements, we stop caring and call the underlying allocator +//! directly, since lists that long in source code are extremely rare. +//! +//! The main remaining issue that all of the above cannot solve is that if we +//! free and allocate new code repeatedly (e.g. of whole modules), each time +//! there will be bits and pieces that end up in a completely different place +//! due to the frozen nature of FlexiBlocks. E.g. freeing a module may have +//! freed 25 arrays of length 6, but the newly loaded code needs 28 arrays of +//! length 6, so three of them land somewhere far away. +//! +//! This shouldn't affect programs that simply load up all their modules, run +//! forever without dynamic modification, and thus never deallocate code. +//! +//! Otherwise, a simple solution is to use separate ListPool instances for +//! modules, or just forget about all of this and rely on a compacting GC. +//! + +const std = @import("std"); + +const Alloc = std.mem.Allocator; + +const gc = @import("../gc.zig"); +const value = @import("../value.zig"); +const seg_stack = @import("../util/seg_stack.zig"); + +const Value = value.Value; +const SegStack = seg_stack.SegStack; + +const i2p = gc.listPtrFromIdx; +const p2i = gc.listIdxFromPtr; + +const Self = @This(); + +// 4 KiB blocks fit 512 Value elements, which should be good. +const block_size = 4096 / @sizeOf(Value); +const Block = [block_size]Value; + +// 30 + 8 + 1 chunk indices mapping to value indices (0-511). Value indices +// should be multiples of 2 (and even 4) so we could divide them to make them +// fit in a u8 each, fitting the whole map in a cache line, but then we'd need +// to multiply them (shift-left) on extraction, so whatever. +const chunk_real_idx_map: [39]u16 = undefined; +comptime { + // zig fmt: off + for ( 0..30) |i| chunk_real_idx_map[i] = ( i * 12 + 0 * 16); + for (30..38) |i| chunk_real_idx_map[i] = (30 * 12 + i * 16); + for (38..39) |i| chunk_real_idx_map[i] = (30 * 12 + 8 * 16); + // zig fmt: on +} + +const chunk_empty_all: u64 = 2 ^ 39 - 1; + +// zig fmt: off +const chunk_empty_sml: u64 = (2 ^ 30 - 1) << 0; +const chunk_empty_mid: u64 = (2 ^ 8 - 1) << 30; +const chunk_empty_big: u64 = (2 ^ 1 - 1) << 38; +// zig fmt: on + +const array_block_chunk_size = 32; +const array_block_max_index = block_size / array_block_chunk_size; + +alloc: Alloc, + +cur_flexi_block: *Block, +cur_chunk_block: *Block, +cur_array_block: *Block, + +cur_flexi_index: u16 = 0, +cur_chunk_empty: u64 = chunk_empty_all, +cur_array_index: u8 = 0, + +flexi_block_stack: SegStack(*Block, 512), +chunk_block_stack: SegStack(*Block, 256), +array_block_stack: SegStack(*Block, 64), + +flexi_free_lists: [8]SegStack(u32, 256), +chunk_free_lists: [3]SegStack(u32, 256), +array_free_list: SegStack(u32, 64), + +pub fn init(alloc: Alloc) !Self { + return .{ + .alloc = alloc, + .cur_flexi_block = try alloc.create(Block), + .cur_chunk_block = try alloc.create(Block), + .cur_array_block = try alloc.create(Block), + .flexi_block_stack = try .init(alloc), + .chunk_block_stack = try .init(alloc), + .array_block_stack = try .init(alloc), + .flexi_free_lists = .{ + try .init(alloc), + try .init(alloc), + try .init(alloc), + try .init(alloc), + try .init(alloc), + try .init(alloc), + try .init(alloc), + try .init(alloc), + }, + .chunk_free_lists = .{ + try .init(alloc), + try .init(alloc), + try .init(alloc), + }, + .array_free_list = try .init(alloc), + }; +} + +pub fn deinit(self: *Self) void { + self.array_free_list.deinit(self.alloc); + for (self.chunk_free_lists) |l| l.deinit(self.alloc); + for (self.flexi_free_lists) |l| l.deinit(self.alloc); + + while (self.array_block_stack.pop(self.alloc)) |b| self.alloc.destroy(b); + while (self.chunk_block_stack.pop(self.alloc)) |b| self.alloc.destroy(b); + while (self.flexi_block_stack.pop(self.alloc)) |b| self.alloc.destroy(b); + + self.array_block_stack.deinit(self.alloc); + self.chunk_block_stack.deinit(self.alloc); + self.flexi_block_stack.deinit(self.alloc); + + self.alloc.destroy(self.cur_array_block); + self.alloc.destroy(self.cur_chunk_block); + self.alloc.destroy(self.cur_flexi_block); +} + +fn newFlexiBlock(self: *Self, rem_len: u8) !void { + if (rem_len != 0) { + self.flexi_free_lists[rem_len - 1].push(self.curFlexiBlockPtr()); + } + try self.flexi_block_stack.push(self.alloc, self.cur_flexi_block); + self.cur_flexi_block = try self.alloc.create(Block); + self.cur_flexi_index = 0; +} + +fn newChunkBlock(self: *Self) !void { + // Put unused chunks in free lists: + var empty = self.cur_chunk_empty; + while (empty != 0) { + const idx = @ctz(chunks); + if (idx < 30) { + const heap_idx = p2i(curChunkBlockPtr(idx)); + self.chunk_free_lists[0].push(self.alloc, heap_idx); + empty &= ~@shlExact(@as(u64, 1), @intCast(idx)); + } else if (idx < 38) { + const heap_idx = p2i(curChunkBlockPtr(idx)); + self.chunk_free_lists[1].push(self.alloc, heap_idx); + empty &= ~@shlExact(@as(u64, 1), @intCast(idx)); + } else { + const heap_idx = p2i(curChunkBlockPtr(38)); + self.chunk_free_lists[2].push(self.alloc, heap_idx); + break; + } + } + try self.chunk_block_stack.push(self.alloc, self.cur_chunk_block); + self.cur_chunk_block = try self.alloc.create(Block); + self.cur_chunk_empty = chunk_empty_all; +} + +fn newArrayBlock(self: *Self) !void { + try self.array_block_stack.push(self.alloc, self.cur_array_block); + self.cur_array_block = try self.alloc.create(Block); + self.cur_array_index = 0; +} + +fn curFlexiBlockPtr(self: *Self) [*]Value { + return @ptrCast(&self.cur_flexi_block[self.cur_flexi_index]); +} + +fn curChunkBlockPtr(self: *Self, idx: u8) [*]Value { + const real_idx = chunk_real_idx_map[idx]; + return @ptrCast(&self.cur_chunk_block[real_idx]); +} + +fn curArrayBlockPtr(self: *Self) [*]Value { + const idx = self.cur_array_index * array_block_chunk_size; + return @ptrCast(&self.cur_array_block[idx]); +} + +pub fn allocVals(self: *Self, len: u8) ![*]Value { + std.debug.assert(len != 0); + + if (len > array_block_chunk_size) { + @branchHint(.unlikely); + return self.alloc.alloc(Value, len); + } + + if (len > 24) { + @branchHint(.unlikely); + if (self.array_free_list.pop(self.alloc)) |i| return i2p(i); + if (self.cur_array_index == array_block_max_index) { + try self.newArrayBlock(); + } + defer self.cur_array_index += 1; + return self.curArrayBlockPtr(); + } + + if (len > 16) { + @branchHint(.unlikely); + if (self.chunk_free_lists[2].pop(self.alloc)) |i| return i2p(i); + if ((self.cur_chunk_empty & chunk_empty_big) == 0) { + try self.newChunkBlock(); + } + self.cur_chunk_empty &= ~chunk_empty_big; + return self.curChunkBlockPtr(38); + } + + if (len > 12) { + @branchHint(.unlikely); + if (self.chunk_free_lists[1].pop(self.alloc)) |i| return i2p(i); + if (self.chunk_free_lists[2].pop(self.alloc)) |i| return i2p(i); + const empty = self.cur_chunk_empty & ~chunk_empty_sml; + if (empty != 0) { + const idx: u8 = @ctz(empty); + self.cur_chunk_empty &= ~@shlExact(@as(u64, 1), @intCast(idx)); + return self.curChunkBlockPtr(idx); + } else { + try self.newChunkBlock(); + self.cur_chunk_empty &= ~(1 << 30); + return self.curChunkBlockPtr(30); + } + } + + if (len > 8) { + if (self.chunk_free_lists[0].pop(self.alloc)) |i| return i2p(i); + if (self.chunk_free_lists[1].pop(self.alloc)) |i| return i2p(i); + if (self.chunk_free_lists[2].pop(self.alloc)) |i| return i2p(i); + const empty = self.cur_chunk_empty; + if (empty != 0) { + const idx: u8 = @ctz(empty); + self.cur_chunk_empty &= ~@shlExact(@as(u64, 1), @intCast(idx)); + return self.curChunkBlockPtr(idx); + } else { + try self.newChunkBlock(); + self.cur_chunk_empty &= ~@as(u64, 1); + return self.curChunkBlockPtr(0); + } + } + + if (self.flexi_free_lists[len - 1].pop(self.alloc)) |i| return i2p(i); + + const rem_len = self.cur_flexi_block.len - self.cur_flexi_index; + if (len > rem_len) try self.newFlexiBlock(rem_len); + + defer self.current_index += len; + return self.curBlockPtr(); +} + +pub fn freeVals(self: *Self, len: u8, ptr: [*]Value) !void { + std.debug.assert(len != 0); + if (len > array_block_chunk_size) { + @branchHint(.unlikely); + return self.alloc.free(ptr); + } + const idx = p2i(ptr); + if (len > 24) { + @branchHint(.unlikely); + return self.array_free_list.push(self.alloc, idx); + } + if (len > 16) { + @branchHint(.unlikely); + return self.chunk_free_lists[2].push(self.alloc, idx); + } + if (len > 12) { + @branchHint(.unlikely); + return self.chunk_free_lists[1].push(self.alloc, idx); + } + if (len > 8) { + return self.chunk_free_lists[0].push(self.alloc, idx); + } + return self.flexi_free_lists[len - 1].push(self.alloc, idx); +} + +pub fn freeList(self: *Self, list: Value) !void { + const len = value.list.getLenTag(list); + const ptr = value.list.getValPtr(list); + try self.freeVals(len, ptr); +} diff --git a/src/zisp/value.zig b/src/zisp/value.zig index 9262a17..1a63349 100644 --- a/src/zisp/value.zig +++ b/src/zisp/value.zig @@ -19,6 +19,7 @@ pub const sval = @import("value/sval.zig"); pub const char = @import("value/char.zig"); pub const misc = @import("value/misc.zig"); +pub const pair = @import("value/pair.zig"); pub const array = @import("value/array.zig"); pub const boole = @import("value/boole.zig"); @@ -50,7 +51,7 @@ pub fn runeXsstr(v: Value) Value { } pub const MiscValue = enum(u8) { - // Make f/t only differ in one bit, to make `bool?` more efficient. + // Make sure f/t only differ in one bit, to make `bool?` more efficient. /// False f = 0, /// True @@ -71,20 +72,39 @@ pub const eof = Value{ .misc = .{ .value = .eof } }; pub const none = Value{ .misc = .{ .value = .none } }; // zig fmt: on -/// A plain (unpacked, untagged) pointer into the Zisp heap. -pub const HeapPtr = *anyopaque; +/// A plain (unpacked, untagged, uncompressed) pointer into the main heap. +pub const HeapPtr = *align(8) anyopaque; -/// Values for the lowest 4 bits of a heap pointer, indicating the heap type. +/// Values for the 8 type bits on main heap pointers. pub const HeapType = enum(u8) { + /// Pair (car, cdr) + pair, /// Array of various types: see `ArrayPtr`. array, + pub fn ObjType(self: HeapType) type { + return switch (self) { + .pair => pair.Pair, + .array => array.ArrayHeader, + else => @panic("Invalid HeapType."), + }; + } + pub fn PtrType(self: HeapType) type { return switch (self) { + .pair => pair.PairPtr, .array => array.ArrayPtr, else => @panic("Invalid HeapType."), }; } + + pub fn of(ptr: anytype) HeapType { + return switch (@TypeOf(ptr)) { + PairPtr => .pair, + ArrayHeader => .array, + else => @panic("Unknown heap pointer."), + }; + } }; fn hi16(comptime tag: u4) u16 { @@ -275,8 +295,8 @@ pub const Value = packed union { } /// Check for heap pointer (given type). - pub fn isHptrTyp(v: Value, comptime htype: HeapType) bool { - return v.hptr._hi == hi16_hptr and v.htptr.typ == htype; + pub fn isHptrTyp(v: Value, comptime typ: HeapType) bool { + return v.hptr._hi == hi16_hptr and v.hptr.typ == typ; } /// Check for istr pointer. diff --git a/src/zisp/value/array.zig b/src/zisp/value/array.zig index cdc5f75..88baf41 100644 --- a/src/zisp/value/array.zig +++ b/src/zisp/value/array.zig @@ -1,8 +1,6 @@ const builtin = @import("builtin"); const std = @import("std"); -const Alloc = std.mem.Allocator; - const gc = @import("../gc.zig"); const value = @import("../value.zig"); @@ -12,25 +10,24 @@ const Value = value.Value; /// /// The low 48 bits are either the length (element count, not buffer size) of /// the array contents that follow immediately, or a pointer to the header of -/// another array whose memory is shared with this one, or a null pointer that -/// has special meaning; see below. +/// another array whose memory is shared with this one, or null, which has a +/// special meaning; see below. /// /// NOTE: For strings, the length is in fact the size in bytes of the buffer. /// To get the "length" of a string according to other definitions of length, -/// such as count of Unicode Scalar Values, or count of Grapheme Clusters, +/// such as count of Unicode Scalar Values, count of UTF-16 code units, etc., /// different encoding-specific string APIs must be used. /// /// If this is a pointer (`is_ptr` is set) it means it's a re-interpretation of /// the contents of the array that is being pointed to. (But see below.) /// /// If this is a slice (`is_slice` is set) then two more u64 values follow this -/// one, marking the start and end of the slice of the pointed-to array that +/// one, marking the start and end byte offsets of the slice of the array that /// this one represents. (But see next paragraph.) /// /// If this is a pointer or slice, but the pointer value is null, then another -/// u64 follows this one immediately, and points directly to a memory buffer -/// (not array head) whose contents are used. In this case, if it's a slice, -/// the start and end u64 values come after that pointer instead. +/// u64 is found at the end, which is a direct pointer to a memory buffer (not +/// array head) whose contents are used. /// /// If this header encodes a non-slice, non-array, direct buffer pointer, then /// there is no length information, so the count of elements is unknown and @@ -48,7 +45,19 @@ const Value = value.Value; /// another array with the same buffer pointer and different type info. /// /// Other remaining bits provide information about element type and size. -pub const ArrayPtr = *align(@alignOf(value.Zptr)) ArrayHeader; +pub const ArrayPtr = *align(@alignOf(value.HeapPtr)) ArrayHeader; + +const ArrayType = enum(u2) { int, flt, val, str }; + +const Endian = enum(u1) { + little, + big, + + const native: Endian = switch (builtin.target.cpu.arch.endian()) { + .little => .little, + .big => .big, + }; +}; // Important: We may or may not use a hack one day in which an algorithm, like // for GC purposes, scans through certain memory regions looking for NaN-packed @@ -71,7 +80,7 @@ pub const ArrayHeader = packed struct(u64) { }, flt: packed struct(u12) { endian: Endian = .native, - _DONTUSE: bool = false + _DONTUSE: bool = false, size: u10, }, val: packed struct(u12) { @@ -98,26 +107,39 @@ pub const ArrayHeader = packed struct(u64) { return @ptrCast(self); } - fn bufContent(self: *Self) [*]u8 { + fn bufOfDirect(self: *Self) [*]u8 { std.debug.assert(!self.is_ptr); - return @ptrCast(self.bufU64() + 1); + return @ptrCast(&self.bufU64()[1]); } - fn bufPointer(self: *Self) [*]u8 { + fn bufOfPointer(self: *Self) [*]u8 { std.debug.assert(self.is_ptr); std.debug.assert(self.len_or_ptr == 0); return @ptrFromInt(self.bufU64()[1]); } + fn sliceInfo(self: *Self) [2]u64 { + std.debug.assert(self.is_slice); + const buf = self.bufU64(); + return .{ buf[1], buf[2] }; + } + + fn bufOfSlice(self: *Self) [*]u8 { + std.debug.assert(self.is_slice); + std.debug.assert(self.len_or_ptr == 0); + return @ptrFromInt(self.bufU64()[3]); + } + fn eltSize(self: *Self) u16 { std.debug.assert(!self.is_ptr); return switch (self.type) { .str => 1, + .val => 8, else => @panic("not implemented"), }; } - fn size(self: *Self) usize { + fn sizeInBytes(self: *Self) usize { std.debug.assert(!self.is_ptr); return self.len_or_ptr * self.eltSize(); } @@ -128,77 +150,76 @@ pub const ArrayHeader = packed struct(u64) { return if (p != 0) @ptrFromInt(p) else null; } - fn sliceInfo(self: *Self) [2]u64 { - std.debug.assert(self.is_slice); - const ptr = self.len_or_ptr; - const buf = self.bufU64(); - if (ptr != 0) { - return .{ buf[1], buf[2] }; - } else { - return .{ buf[2], buf[3] }; - } - } - - pub fn bufU8(self: *Self) [*]u8 { + /// Get a pointer to the array's contents as a u8 multi-pointer. + pub fn bufU8RW(self: *Self) [*]u8 { if (self.is_ptr) { - if (self.arrPointer()) |a| { - return a.bufContent(); + if (self.arrPointer()) |dest| { + std.debug.assert(!dest.is_ptr); + return dest.bufOfDirect(); + } else if (self.is_slice) { + return self.bufOfSlice(); } else { - return self.bufPointer(); + return self.bufOfPointer(); } - } else { - return self.bufContent(); } + return self.bufOfDirect(); + } + + /// Get a pointer to the array's contents as a const u8 multi-pointer. + pub fn bufU8RO(self: *Self) [*]const u8 { + return self.bufU8RW(); } - pub fn bytes(self: *Self) []u8 { + /// Get a u8 slice of the array's contents. + pub fn sliceU8RW(self: *Self) []u8 { if (self.is_slice) { - const buf = self.bufU8(); + std.debug.assert(self.is_ptr); const start, const end = self.sliceInfo(); + var buf = undefined; + if (self.arrPointer()) |dest| { + std.debug.assert(!dest.is_ptr); + std.debug.assert(end <= dest.sizeInBytes()); + buf = dest.bufOfDirect(); + } else { + buf = self.bufOfSlice(); + } return buf[start..end]; } var arr = self; if (self.is_ptr) { arr = self.arrPointer() orelse { - @panic("Called bytes() on array with direct buffer pointer."); + @panic("Array lacks length information; can't take slice."); }; } - return arr.bufContent()[0..arr.size()]; + return arr.bufContent()[0..arr.sizeInBytes()]; } - pub fn bytesRO(self: *Self) []const u8 { - return self.bytes(); + /// Get a const u8 slice of the array's contents. + pub fn sliceU8RO(self: *Self) []const u8 { + return self.sliceU8RW(); } }; -const ArrayType = enum(u2) { int, flt, val, str }; - -const Endian = enum(u1) { - little, - big, - - const native: Endian = switch (builtin.target.cpu.arch.endian()) { - .little => .little, - .big => .big, - }; -}; - -pub fn newString(alloc: Alloc, s: []const u8) !Value { +pub fn newString(s: []const u8) !Value { std.debug.assert(s.len <= std.math.maxInt(u48)); - const algn = std.mem.Alignment.of(ArrayPtr); - const size = @sizeOf(ArrayHeader) + s.len; - const arr: ArrayPtr = @ptrCast(try alloc.alignedAlloc(u8, algn, size)); + const len = @sizeOf(ArrayHeader) + s.len; + const arr = try gc.allocHeap(.array, len); arr.* = .{ .len_or_ptr = @intCast(s.len), .type = .str, .info = .{ .str = .{} }, }; - const buf = arr.bufContent(); + const buf = arr.bufOfDirect(); @memcpy(buf[0..s.len], s); - return value.ptr.pack(.array, arr); + return gc.packHeap(arr); +} + +pub fn checkAny(v: Value) ?ArrayPtr { + if (!v.isHptrTyp(.array)) return null; + return @ptrCast(gc.heapPtrFromIdx(v.hptr.idx)); } pub fn check(comptime t: ArrayType, v: Value) ?ArrayPtr { - if (v.getPtr(.array)) |p| if (p.type == t) return p; - return null; + const ptr = checkAny(v); + return if (ptr.type == t) ptr else null; } diff --git a/src/zisp/value/pair.zig b/src/zisp/value/pair.zig index 09e50f2..c4b6f2c 100644 --- a/src/zisp/value/pair.zig +++ b/src/zisp/value/pair.zig @@ -1,12 +1,13 @@ +const std = @import("std"); + const gc = @import("../gc.zig"); const value = @import("../value.zig"); -const ptr = @import("ptr.zig"); +const Alloc = std.mem.Allocator; -const PairPool = gc.PairPool; const Value = value.Value; -pub const PairPtr = *align(@alignOf(value.Zptr)) Pair; +pub const PairPtr = *align(@alignOf(value.HeapPtr)) Pair; pub const Pair = struct { car: Value, @@ -16,7 +17,8 @@ pub const Pair = struct { // Zig API pub fn check(v: Value) ?PairPtr { - return v.getPtr(.pair); + if (!v.isHptrTyp(.pair)) return null; + return @ptrCast(gc.heapPtrFromIdx(v.hptr.idx)); } pub fn assert(v: Value) PairPtr { @@ -30,20 +32,17 @@ pub fn unpack(v: Value) PairPtr { return assert(v); } -pub fn consInPool(pool: *PairPool, car: Value, cdr: Value) !Value { - const pair = try pool.cons(car, cdr); - return ptr.pack(.pair, pair); -} - // Zisp API pub fn pred(v: Value) Value { return value.boole.pack(check(v) != null); } -pub fn cons(car: Value, cdr: Value) Value { - const pool = gc.mainPairPool(); - return consInPool(pool, car, cdr) catch @panic("OOM"); // TODO +pub fn cons(car: Value, cdr: Value) !Value { + const pair = try gc.createHeap(.pair); + pair.car = car; + pair.cdr = cdr; + return gc.packHeap(pair); } pub fn getCar(v: Value) Value { -- cgit v1.2.3