diff options
| -rw-r--r-- | src/zisp/gc.zig | 47 | ||||
| -rw-r--r-- | src/zisp/gc/CodePool.zig | 357 | ||||
| -rw-r--r-- | src/zisp/gc/IstrPool.zig | 193 | ||||
| -rw-r--r-- | src/zisp/gc/IstrSet.zig | 157 | ||||
| -rw-r--r-- | src/zisp/gc/ListPool.zig | 110 | ||||
| -rw-r--r-- | src/zisp/util/seg_stack.zig (renamed from src/zisp/lib/seg_stack.zig) | 38 | ||||
| -rw-r--r-- | src/zisp/value.zig | 198 | ||||
| -rw-r--r-- | src/zisp/value/sval.zig | 6 |
8 files changed, 715 insertions, 391 deletions
diff --git a/src/zisp/gc.zig b/src/zisp/gc.zig index 0e47682..0e26aa9 100644 --- a/src/zisp/gc.zig +++ b/src/zisp/gc.zig @@ -5,21 +5,58 @@ const Alloc = std.mem.Allocator; const value = @import("value.zig"); -pub const ListPool = @import("gc/ListPool.zig"); -pub const IstrSet = @import("gc/IstrSet.zig"); +pub const CodePool = @import("gc/CodePool.zig"); +pub const IstrPool = @import("gc/IstrPool.zig"); + +const HeapPtr = value.HeapPtr; var main_alloc: Alloc = undefined; + +var code_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_set: IstrSet = undefined; +var main_istr_pool: IstrPool = undefined; + +pub fn codePtrFromIdx(idx: u32) [*]Value { + return @ptrFromInt(code_heap_start + idx * 8); +} + +pub fn heapPtrFromIdx(idx: u32) HeapPtr { + return @ptrFromInt(main_heap_start + idx * 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 heapIdxFromPtr(ptr: HeapPtr) u32 { + return @intCast(@intFromPtr(ptr - main_heap_start) / 8); +} + +pub fn istrIdxFromPtr(ptr: [*]const u8) u32 { + return @intCast(@intFromPtr(ptr - istr_heap_start)); +} + +// init var init_done = false; pub fn init() !void { if (init_done) return; defer init_done = true; + main_alloc = std.heap.smp_allocator; + + //code_heap_start = ...; + main_list_pool = try ListPool.init(main_alloc); - main_istr_set = try IstrSet.init(main_alloc); + main_istr_set = try IstrPool.init(main_alloc); } pub fn mainAlloc() Alloc { @@ -32,7 +69,7 @@ pub fn mainListPool() *ListPool { return &main_list_pool; } -pub fn mainIstrSet() *IstrSet { +pub fn mainIstrPool() *IstrPool { init() catch @panic("OOM"); // TODO this is only here for the test suite return &main_istr_set; } diff --git a/src/zisp/gc/CodePool.zig b/src/zisp/gc/CodePool.zig new file mode 100644 index 0000000..56bf384 --- /dev/null +++ b/src/zisp/gc/CodePool.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 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/IstrPool.zig b/src/zisp/gc/IstrPool.zig new file mode 100644 index 0000000..bbf6e63 --- /dev/null +++ b/src/zisp/gc/IstrPool.zig @@ -0,0 +1,193 @@ +//! Interned string pool +//! +//! This is a fairly standard open-address linear-search hash-set, specialized +//! for our istr data type, not supporting removal. + +// TODO: Allocate the strings in tight blocks just like ListPool. + +// TODO: Vector instructions. + +const std = @import("std"); + +const Alloc = std.mem.Allocator; + +const value = @import("../value.zig"); + +const Value = value.Value; + +const Self = @This(); + +const max_fill_percent = 80; + +/// Fingerprint: 8 bit length, 24 bits from the real u64 hash. +const Fp = packed union(u32) { + info: packed struct(u32) { + // Put length first; allows more optimal instructions. + len: u8, + fp: u24, + }, + bits: u32, +}; + +const Bucket = packed struct(u64) { + // Put fp first; allows more optimal instructions. + fp: Fp = .{ .bits = 0 }, + idx: u32 = 0, + + pub fn empty(self: Bucket) bool { + // On x64 this is just checking an 8-bit low virtual register thanks to + // fp.info.len being the lowest 8 bits. + return self.fp.info.len == 0; + } + + pub fn getIstr(self: Bucket) Value { + return .{ .istr = .{ .idx = self.idx, .len = self.fp.info.len } }; + } + + pub fn putIstr(self: *Bucket, v: Value, fp: Fp) void { + self.idx = v.istr.idx; + self.fp = fp; + } +}; + +alloc: Alloc, +buckets: []Bucket = undefined, + +used_buckets: usize = 0, +used_threshold: usize = undefined, + +const test_stdlib_impl = false; + +const default_bcount = 512; + +pub fn init(alloc: Alloc) !Self { + return initCustom(alloc, default_bcount); +} + +pub fn initCustom(alloc: Alloc, bcount: usize) !Self { + if (test_stdlib_impl) { + try map.ensureTotalCapacity(alloc, 512); + return Self{ .alloc = alloc }; + } + std.debug.assert(@popCount(bcount) == 1); // Must be power of 2. + var self = Self{ .alloc = alloc }; + try self.allocBuckets(bcount); + return self; +} + +fn allocBuckets(self: *Self, bcount: usize) !void { + self.buckets = try self.alloc.alloc(Bucket, bcount); + @memset(self.buckets, Bucket{}); + self.used_threshold = bcount * max_fill_percent / 100; +} + +pub fn deinit(self: *Self) void { + self.alloc.free(self.buckets); +} + +/// Get the istr with the given string contents, or alloc and store a new one. +pub fn getOrNew(self: *Self, s: []const u8) !Value { + std.debug.assert(s.len <= 255); + if (test_stdlib_impl) { + return self.addStdlib(s); + } + return self.getOrPutOrNew(s.ptr, @intCast(s.len), null); +} + +/// Get the canonical istr with the same contents, or store this one as it. +pub fn getOrPut(self: *Self, v: Value) !Value { + const sptr = gc.istrPtrFromIdx(v.istr.idx); + const len = v.istr.len; + return self.getOrPutOrNew(sptr, len, v); +} + +fn getOrPutOrNew(self: *Self, sptr: [*]const u8, len: u8, put: ?Value) !Value { + if (self.used_buckets > self.used_threshold) { + try self.resize(); + } + + const hash = hashBytes(sptr, len); + const fp = makeHashFp(hash, len); + + const idx_mask = self.buckets.len - 1; + const idx_start = hash & idx_mask; + + var idx = idx_start; + while (true) : (idx = (idx + 1) & idx_mask) { + const bucket = &self.buckets[idx]; + if (bucket.empty()) { + self.used_buckets += 1; + const v = put orelse try self.newIstr(sptr, len); + bucket.putIstr(v, fp); + return v; + } + if (bucket.fp.bits == fp.bits) { + const ptr = gc.istrPtrFromIdx(bucket.idx); + if (eqBytes(sptr, ptr, len)) return bucket.getIstr(); + } + } +} + +fn newIstr(self: *Self, sptr: [*]const u8, len: u8) !Value { + // TODO: Alloc manually in slabs, like ListPool FlexiBlock. + const ptr = try self.alloc.alloc(len); + const idx = gc.istrIdxFromPtr(ptr); + return .{ .istr = .{ .idx = idx, .len = len } }; +} + +fn resize(self: *Self) !void { + const old_buckets = self.buckets; + try self.allocBuckets(old_buckets.len << 1); + defer self.alloc.free(old_buckets); + const new_buckets = self.buckets; + + const idx_mask = new_buckets.len - 1; + for (old_buckets) |old| { + if (old.empty()) continue; + const len = old.fp.info.len; + const ptr = gc.istrPtrFromIdx(old.idx); + var idx = hashBytes(ptr, len) & idx_mask; + while (!new_buckets[idx].empty()) idx = (idx + 1) & idx_mask; + new_buckets[idx] = old; + } +} + +fn hashBytes(s: [*]const u8, len: u8) u64 { + // TODO: Can do better than this. + return std.hash_map.hashString(s[0..len]); +} + +fn eqBytes(s1: [*]const u8, s2: [*]const u8, len: u8) bool { + // TODO: Can do better than this. + return std.hash_map.eqlString(s1[0..len], s2[0..len]); +} + +fn makeHashFp(hash: u64, len: u8) Fp { + // + // Should compile to just two instructions; e.g. on x64: + // + // shl edi, 8 + // + // lea eax, [rdi + rsi] + // + return .{ .info = .{ .len = len, .fp = @truncate(hash) } }; +} + +// Using stdlib, to compare + +const str_ctx = std.hash_map.StringContext{}; + +const Map = std.hash_map.StringHashMapUnmanaged(Value); +var map: Map = .empty; + +pub fn addStdlib(self: *Self, s: []const u8) !Value { + const gop = map.getOrPutAdapted(self.alloc, s, str_ctx) catch @panic("OOM"); + if (gop.found_existing) { + return gop.value_ptr.*; + } + + const istr = try self.newIstr(s); + gop.key_ptr.* = istr.bytes(); + gop.value_ptr.* = istr; + return istr; +} diff --git a/src/zisp/gc/IstrSet.zig b/src/zisp/gc/IstrSet.zig deleted file mode 100644 index 179476e..0000000 --- a/src/zisp/gc/IstrSet.zig +++ /dev/null @@ -1,157 +0,0 @@ -//! Interned string set - -// TODO: Allocate the strings in tight blocks just like ListPool. - -const std = @import("std"); - -const Alloc = std.mem.Allocator; - -const value = @import("../value.zig"); - -const IstrPtr = value.istr.IstrPtr; -const IstrHead = value.istr.IstrHead; - -const Set = @This(); - -const max_fill_percent = 80; - -const Bucket = packed struct(u64) { - ptr: u48 = 0, - fp: u16 = 0, - - pub fn empty(self: Bucket) bool { - return self.ptr == 0; - } - - pub fn istrPtr(self: *const Bucket) IstrPtr { - return @ptrFromInt(self.ptr); - } - - pub fn putIstrPtr(self: *Bucket, istr: IstrPtr) void { - self.ptr = @intCast(@intFromPtr(istr)); - } -}; - -alloc: Alloc, -buckets: []Bucket = undefined, - -used_buckets: usize = 0, -used_threshold: usize = undefined, - -const test_stdlib_impl = false; - -const default_bcount = 512; - -pub fn init(alloc: Alloc) !Set { - return initCustom(alloc, default_bcount); -} - -pub fn initCustom(alloc: Alloc, bcount: usize) !Set { - if (test_stdlib_impl) { - try map.ensureTotalCapacity(alloc, 512); - return Set{ .alloc = alloc }; - } - std.debug.assert(@popCount(bcount) == 1); // Must be power of 2. - var self = Set{ .alloc = alloc }; - try self.allocBuckets(bcount); - return self; -} - -fn allocBuckets(self: *Set, bcount: usize) !void { - self.buckets = try self.alloc.alloc(Bucket, bcount); - @memset(self.buckets, Bucket{}); - self.used_threshold = bcount * max_fill_percent / 100; -} - -pub fn deinit(self: *Set) void { - self.alloc.free(self.buckets); -} - -/// Get the istr with the given string contents, or alloc and store a new one. -pub fn getOrNew(self: *Set, s: []const u8) !IstrPtr { - std.debug.assert(s.len <= value.istr.max_len); - if (test_stdlib_impl) { - return self.addStdlib(s); - } - return self.getOrPutOrNew(s, null); -} - -/// Get the canonical istr with the same contents, or store this one as it. -pub fn getOrPut(self: *Set, istr: IstrPtr) !IstrPtr { - return self.getOrPutOrNew(istr.bytes(), istr); -} - -fn getOrPutOrNew(self: *Set, s: []const u8, ptr: ?IstrPtr) !IstrPtr { - if (self.used_buckets > self.used_threshold) { - try self.resize(); - } - - const hash = strHash(s); - const fp = hashFp(hash); - - const idx_mask = self.buckets.len - 1; - const idx_start = hash & idx_mask; - - var idx = idx_start; - while (true) : (idx = (idx + 1) & idx_mask) { - const bucket = &self.buckets[idx]; - if (bucket.empty()) { - self.used_buckets += 1; - const istr = ptr orelse try value.istr.new(self.alloc, s); - bucket.putIstrPtr(istr); - bucket.fp = fp; - return istr; - } - if (bucket.fp == fp) { - const istr = bucket.istrPtr(); - if (strEq(s, istr.bytes())) return istr; - } - } -} - -fn resize(self: *Set) !void { - const old_buckets = self.buckets; - try self.allocBuckets(old_buckets.len << 1); - defer self.alloc.free(old_buckets); - const new_buckets = self.buckets; - - const idx_mask = new_buckets.len - 1; - for (old_buckets) |old| { - if (old.empty()) continue; - const str = old.istrPtr().bytes(); - var idx = strHash(str) & idx_mask; - while (!new_buckets[idx].empty()) idx = (idx + 1) & idx_mask; - new_buckets[idx] = old; - } -} - -fn strHash(s: []const u8) u64 { - return std.hash_map.hashString(s); -} - -fn strEq(s: []const u8, s2: []const u8) bool { - return std.hash_map.eqlString(s, s2); -} - -fn hashFp(hash: u64) u16 { - return @intCast(hash >> 48); -} - -// Using stdlib, to compare - -const str_ctx = std.hash_map.StringContext{}; - -const Map = std.hash_map.StringHashMapUnmanaged(IstrPtr); -var map: Map = .empty; - -pub fn addStdlib(self: *Set, s: []const u8) !IstrPtr { - const gop = map.getOrPutAdapted(self.alloc, s, str_ctx) catch @panic("OOM"); - if (gop.found_existing) { - return gop.value_ptr.*; - } - - const istr = try self.newIstr(s); - gop.key_ptr.* = istr.bytes(); - gop.value_ptr.* = istr; - return istr; -} diff --git a/src/zisp/gc/ListPool.zig b/src/zisp/gc/ListPool.zig deleted file mode 100644 index 668735d..0000000 --- a/src/zisp/gc/ListPool.zig +++ /dev/null @@ -1,110 +0,0 @@ -//! List array pool -//! -//! Strategy: To ensure list arrays are allocated sequentially without any -//! padding, we allocate memory in large blocks, and whenever a list array with -//! a certain length is to be allocated, we check if the current block still has -//! enough room; otherwise we allocate the next block. -//! -//! This is only used for lists up to 7 elements. Starting at 8, they can't -//! share a cache line with other list elements anyway. - -const std = @import("std"); - -const Alloc = std.mem.Allocator; -const ArrayList = std.ArrayListUnmanaged; - -const value = @import("../value.zig"); -const seg_stack = @import("../lib/seg_stack.zig"); - -const Value = value.Value; -const SegStack = seg_stack.SegStack; - -const Self = @This(); - -// 4 KiB blocks fit 512 Value elements, which should be good. -const Block = [4096 / @sizeOf(Value)]Value; - -alloc: Alloc, - -current_block: *Block, -current_index: usize = 0, - -full_list: SegStack(*Block, 4096), -free_lists: [7]SegStack([*]Value, 512), - -pub fn init(alloc: Alloc) !Self { - return .{ - .alloc = alloc, - .current_block = try alloc.create(Block), - .full_list = try .init(alloc), - .free_lists = .{ - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - try .init(alloc), - }, - }; -} - -pub fn deinit(self: *Self) void { - for (self.free_lists) |l| l.deinit(self.alloc); - while (self.full_list.pop(self.alloc)) |block| self.alloc.destroy(block); - self.full_list.deinit(self.alloc); - self.alloc.destroy(self.current_block); -} - -fn newBlock(self: *Self) !void { - try self.full_list.push(self.alloc, self.current_block); - self.current_block = try self.alloc.create(Block); - self.current_index = 0; -} - -fn curBlockPtr(self: *Self) [*]Value { - return @ptrCast(&self.current_block[self.current_index]); -} - -fn popFree(self: *Self, len: u3) ?[*]Value { - return self.free_lists[len - 1].pop(self.alloc); -} - -fn pushFree(self: *Self, len: u3, ptr: [*]Value) !void { - try self.free_lists[len - 1].push(self.alloc, ptr); -} - -pub fn allocVals(self: *Self, len: u3) ![*]Value { - std.debug.assert(len != 0); - - if (self.popFree(len)) |ptr| return ptr; - - if (len > self.current_block.len - self.current_index) { - try self.newBlock(); - } - - defer self.current_index += len; - return self.curBlockPtr(); -} - -pub fn freeVals(self: *Self, len: u3, ptr: [*]Value) !void { - std.debug.assert(len != 0); - - // Is it simply the last allocation? If so, just undo it. - if (self.current_index >= len) { - const ptr_val = @intFromPtr(ptr); - const last_ptr_val = @intFromPtr(self.curBlockPtr() - len); - if (ptr_val == last_ptr_val) { - self.current_index -= len; - return; - } - } - - try self.pushFree(len, ptr); -} - -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/lib/seg_stack.zig b/src/zisp/util/seg_stack.zig index d2c6aaa..4abb6ef 100644 --- a/src/zisp/lib/seg_stack.zig +++ b/src/zisp/util/seg_stack.zig @@ -7,8 +7,8 @@ const Alloc = std.mem.Allocator; /// Segmented linked list backed stack pub fn SegStack(T: type, seg_max_bytes: comptime_int) type { - // Each Node has a pointer (= usize) and the element array; calculate the - // correct segment size (as in element count) based on that. + // Each Segment has a pointer (= usize) and the element array; calculate + // correct segment size (in element count) based on that. const seg_size = (seg_max_bytes - @sizeOf(usize)) / @sizeOf(T); const IdxType = std.math.IntFittingRange(seg_size); @@ -19,7 +19,7 @@ pub fn SegStack(T: type, seg_max_bytes: comptime_int) type { } } - const Node = struct { + const Segment = struct { const Self = @This(); prev: ?*Self = null, @@ -35,55 +35,55 @@ pub fn SegStack(T: type, seg_max_bytes: comptime_int) type { return struct { const Self = @This(); - head: *Node, + cur: *Segment, idx: IdxType = 0, // To prevent "thrashing" we don't immediately deallocate the current - // node when it's emptied but rather save it aside. - aside: ?*Node = null, + // segment when it's emptied but rather save it aside. + aside: ?*Segment = null, pub fn init(alloc: Alloc) !Self { - return .{ .head = try .new(alloc) }; + return .{ .cur = try .new(alloc) }; } pub fn deinit(self: *Self, alloc: Alloc) void { if (self.aside) |aside| alloc.destroy(aside); - var node: ?Node = self.head; - while (node) |n| { + var seg: ?Segment = self.cur; + while (seg) |n| { alloc.destroy(n); - node = n.prev; + seg = n.prev; } } pub fn push(self: *Self, alloc: Alloc, elt: T) !void { if (self.idx == seg_size) { if (self.aside) |aside| { - self.head = aside; + self.cur = aside; self.aside = null; } else { - const prev = self.head; - self.head = try .new(alloc); - self.head.prev = prev; + const prev = self.cur; + self.cur = try .new(alloc); + self.cur.prev = prev; } self.idx = 0; } - self.head.elts[self.idx] = elt; + self.cur.elts[self.idx] = elt; self.idx += 1; } pub fn pop(self: *Self, alloc: Alloc) ?T { if (self.idx == 0) { - if (self.head.prev) |prev| { + if (self.cur.prev) |prev| { if (self.aside) |aside| alloc.destroy(aside); - self.aside = self.head; - self.head = prev; + self.aside = self.cur; + self.cur = prev; self.idx = seg_size; } else { return null; } } self.idx -= 1; - return self.head.elts[self.idx]; + return self.cur.elts[self.idx]; } }; } diff --git a/src/zisp/value.zig b/src/zisp/value.zig index c16b937..9262a17 100644 --- a/src/zisp/value.zig +++ b/src/zisp/value.zig @@ -8,12 +8,14 @@ const gc = @import("gc.zig"); pub const double = @import("value/double.zig"); pub const fixnum = @import("value/fixnum.zig"); -pub const ptr = @import("value/ptr.zig"); pub const list = @import("value/list.zig"); +pub const hptr = @import("value/hptr.zig"); pub const istr = @import("value/istr.zig"); pub const sstr = @import("value/sstr.zig"); pub const srat = @import("value/srat.zig"); pub const rune = @import("value/rune.zig"); +pub const sval = @import("value/sval.zig"); + pub const char = @import("value/char.zig"); pub const misc = @import("value/misc.zig"); @@ -47,8 +49,19 @@ pub fn runeXsstr(v: Value) Value { return @bitCast(v.bits ^ (1 << 50)); } -// Make sure false/true only differ in LSb. -pub const MiscValue = enum(u8) { f, t, nil, eof, none }; +pub const MiscValue = enum(u8) { + // Make f/t only differ in one bit, to make `bool?` more efficient. + /// False + f = 0, + /// True + t = 1, + /// Empty list + nil, + /// End of file + eof, + /// Stand-in for "literally no value" (never exposed to Zisp code) + none, +}; // zig fmt: off pub const f = Value{ .misc = .{ .value = .f } }; @@ -59,14 +72,10 @@ pub const none = Value{ .misc = .{ .value = .none } }; // zig fmt: on /// A plain (unpacked, untagged) pointer into the Zisp heap. -pub const Zptr = *align(16) anyopaque; +pub const HeapPtr = *anyopaque; /// Values for the lowest 4 bits of a heap pointer, indicating the heap type. -pub const HeapType = enum(u4) { - /// Unused so the 48-bit payload of a NaN-packed pointer is never zero and - /// cannot be confused for an actual NaN even in case of a null index. - _unused = 0, - +pub const HeapType = enum(u8) { /// Array of various types: see `ArrayPtr`. array, @@ -78,19 +87,31 @@ pub const HeapType = enum(u4) { } }; -/// Make a "pointer etc." high 16-bit pattern with a 3-bit sub-range tag. -fn ptrEtc(comptime tag: u3) u16 { - return @as(u16, 0x7ff8) + tag; +fn hi16(comptime tag: u4) u16 { + return @as(u16, 0x7ff0) + tag; } -const hi16_tag_ptr = ptrEtc(0b000); -const hi16_tag_list = ptrEtc(0b001); -const hi16_tag_istr = ptrEtc(0b010); -const hi16_tag_sstr = ptrEtc(0b011); -const hi15_tag_srat = @as(u15, @intCast(ptrEtc(0b100) >> 1)); -const hi16_tag_rune = ptrEtc(0b111); - -/// Represents a Zisp value. +pub const hi16_list = hi16(0b0000); +pub const hi16_hptr = hi16(0b0001); +pub const hi16_istr = hi16(0b0010); +pub const hi16_sstr = hi16(0b0011); +pub const hi16_rpos = hi16(0b0100); +pub const hi16_rneg = hi16(0b0101); +pub const hi16_ndef = hi16(0b0110); +pub const hi16_rune = hi16(0b0111); + +pub const hi15_srat: u15 = @intCast(hi16(0b0100) >> 1); + +pub const hi16_const_list = hi16(0b1000); +pub const hi16_const_hptr = hi16(0b1001); +pub const hi16_const_istr = hi16(0b1010); +pub const hi16_const_sstr = hi16(0b1011); +pub const hi16_vm_op_list = hi16(0b1100); +pub const hi16_vm_op_heap = hi16(0b1101); +pub const hi16_vm_var_loc = hi16(0b1110); +pub const hi16_vm_var_lex = hi16(0b1111); + +/// Represents any Zisp value. pub const Value = packed union { /// To get an agnostic value for direct comparison with == i.e. eq? as well /// as manual bit-fiddling to test for and extract packed values. @@ -113,66 +134,77 @@ pub const Value = packed union { sign: bool, }, - /// 52-bit signed fixnum + /// Signed integer fixnum: packed struct { code: u51, - negative: bool, + sign: bool, _exp: u11 = max(u11), _is_fixnum: bool = true, }, - /// Ordinary heap pointer - ptr: packed struct { - index: u44, - htype: HeapType, - _hi16_tag: u16 = hi16_tag_ptr, - }, - /// List pointer list: packed struct { - len_tagged_ptr: u48, - _hi16_tag: u16 = hi16_tag_list, + idx: u32, + _gc: u8 = 0, + len: u8, + _hi: u16 = hi16_list, + }, + + /// Heap pointer + hptr: packed struct { + idx: u32, + _gc: u8 = 0, + typ: HeapType, + _hi: u16 = hi16_hptr, }, /// Istr pointer istr: packed struct { - ptr: u48, - _hi16_tag: u16 = hi16_tag_istr, + idx: u32, + _gc: u8 = 0, + len: u8, + _hi: u16 = hi16_istr, }, /// Short string sstr: packed struct { // actually [6]u8 but packed struct cannot contain arrays bytes: u48, - _hi16_tag: u16 = hi16_tag_sstr, + _hi: u16 = hi16_sstr, }, /// Small rat (rational number) srat: packed struct { q: u24, p: i25, - _hi16_tag: u15 = hi15_tag_srat, + _hi: u15 = hi15_srat, + }, + + /// Undefined, for now + ndef: packed struct { + _: u48, + _hi: u16 = hi16_ndef, }, /// Rune (6-byte ASCII string) rune: packed struct { // actually [6]u8 but packed struct cannot contain arrays name: u48, - _hi16_tag: u16 = hi16_tag_rune, + _hi: u16 = hi16_rune, }, // TODO: Use a general Small Value type registration mechanism. char: packed struct { value: u24, _sv_tag: u24 = 0x000080, - _hi16_tag: u16 = hi16_tag_rune, + _hi: u16 = hi16_rune, }, // TODO: Use a general Small Value type registration mechanism. misc: packed struct { value: MiscValue, _sv_tag: u40 = 0x0000000080, - _hi16_tag: u16 = hi16_tag_rune, + _hi: u16 = hi16_rune, }, /// Dumps the value for inspection. @@ -200,17 +232,10 @@ pub const Value = packed union { return v1.bits == v2.bits; } - // It would be great if we could just write the most readable code in the - // following functions, using the packed struct definitions above, but the - // optimizer isn't smart enough, so manual bit fiddling it is. + // We do some manual bit-fiddling for optimal codegen. - /// Checks for a double, including: +nan, -nan, +inf, -inf. + /// Checks for a regular double, including +nan, -nan, +inf, -inf. pub fn isDouble(v: Value) bool { - // Readable version: - // - // return v.ieee.exp != max(u11) or v.ieee.rest == 0; - // - // Optimized: // // 1. Shift the 12 highest bits all the way to the right, then mask out // the sign bit. Allows efficiently checking if the exponent is all @@ -219,21 +244,13 @@ pub const Value = packed union { // 2. Shift out 13 high bits (sign, expt, quiet) so we can easily check // if the rest bits are zero. // - const expt = v.bits >> 52 & 0x7ff; - const rest = v.bits << 13; + const expt: u16 = @intCast(v.bits >> 52 & 0x7ff); + const rest: u64 = v.bits << 13; return expt != 0x7ff or rest == 0; } - // Imagine there's an isPacked() implemented as !isDouble() here, used to - // make the following functions more readable. - - /// Checks for a fixnum integer. + /// Checks for a signed integer. pub fn isFixnum(v: Value) bool { - // Readable version: - // - // return v.isPacked() and v.ieee.sign; - // - // Optimized: // // 1. Shift the 12 highest bits all the way to the right; these need to // be all set, since the sign bit (and all exponent bits) being set @@ -242,66 +259,47 @@ pub const Value = packed union { // 2. But also verify that the lowest 51 bits aren't zero, since that // would be a cqNaN or Infinity. // - const expt = v.bits >> 52; - const rest = v.bits << 13; + const expt: u16 = @intCast(v.bits >> 52); + const rest: u64 = v.bits << 13; return expt == 0xfff and rest != 0; } - /// Checks if the value is any type-tagged pointer. You probably want to - /// use getPtr() or getPtrAny() instead, so you can combine the check with - /// the extraction of the pointer and type tag. - pub fn isPtrAny(v: Value) bool { - const hi: u16 = @intCast(v.bits >> 48); - const lo: u48 = @truncate(v.bits); - return hi == hi16_tag_ptr and lo != 0; - } - - /// Checks for a pointer with a given type tag, returning null on failure - /// and the pointer value otherwise. - pub fn getPtr(v: Value, comptime ht: HeapType) ?ht.PtrType() { - // Check if the 20 highest bits equal the combination of the 16-bit - // pattern marking a pointer, followed by the 4-bit heap type tag. - const hi20_bits: u20 = @intCast(v.bits >> 44); - const ptr_bits: u20 = hi16_tag_ptr; - const tag_bits: u20 = @intFromEnum(ht); - if (hi20_bits != ptr_bits << 4 | tag_bits) return null; - return @ptrFromInt(v.bits << 20 >> 16); + /// Check for list pointer. + pub fn isList(v: Value) bool { + return v.list._hi == hi16_istr; } - /// Checks for a pointer and returns the value and tag separately, or null - /// if this isn't a pointer at all. Could be useful for a dispatch table. - /// Note that unlike getPtr(), this can actually return a null pointer as - /// such, not conflating it with the "not a heap pointer" case. - pub fn getPtrAny(v: Value) ?struct { HeapType, ?Zptr } { - const hi16_bits: u16 = @intCast(v.bits >> 48); - if (hi16_bits != hi16_tag_ptr) return null; - - const ht: u4 = @intCast(v.bits << 16 >> 60); - const pval: u48 = @intCast(v.bits << 20 >> 16); - return .{ @enumFromInt(ht), @ptrFromInt(pval) }; + /// Check for heap pointer (any type). + pub fn isHptrAny(v: Value) bool { + return v.hptr._hi == hi16_hptr; } - /// Checks if the value is a list pointer. - pub fn isList(v: Value) bool { - return v.bits >> 48 == hi16_tag_list; + /// 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; } - /// Checks if the value is an istr pointer. + /// Check for istr pointer. pub fn isIstr(v: Value) bool { - return v.bits >> 48 == hi16_tag_istr; + return v.istr._hi == hi16_istr; } - /// Checks if the value is a short string. + /// Check for short string. pub fn isSstr(v: Value) bool { - return v.bits >> 48 == hi16_tag_sstr; + return v.sstr._hi == hi16_sstr; } - /// Checks if the value is a small rat (rational number). + /// Check for small rat (rational number). pub fn isSrat(v: Value) bool { - return v.bits >> 49 == hi15_tag_srat; + return v.srat._hi == hi15_srat; + } + + /// Placeholder: Check for (undefined). + pub fn isNdef(v: Value) bool { + return v.ndef._hi == hi15_ndef; } - /// Checks for a rune. + /// Check for rune. pub fn isRune(v: Value) bool { // This check isn't used much, since one typically checks for specific // runes via direct equality, so the efficiency here is unimportant. diff --git a/src/zisp/value/sval.zig b/src/zisp/value/sval.zig new file mode 100644 index 0000000..a3c49a3 --- /dev/null +++ b/src/zisp/value/sval.zig @@ -0,0 +1,6 @@ +//! Small Values +//! +//! This is for registering and handling "small value" immediates that inhabit +//! the same 48-bit range as runes. + +// todo |