commit b7e7127585b30cb5b1f3148c3462e4958616a10c
parent 11a446bd9f6769c66417fde56bdbbbd5fb11c607
Author: Szymon Mikulicz <szymon.mikulicz@posteo.net>
Date: Tue, 25 Aug 2026 22:12:13 +0200
GC with heap tracking
Diffstat:
3 files changed, 129 insertions(+), 87 deletions(-)
diff --git a/zlox/src/gc.zig b/zlox/src/gc.zig
@@ -27,15 +27,18 @@ pub const GC = struct {
}
};
- const DBG_STRESS = true;
+ const DBG_STRESS = false;
const DBG_LOG = true;
+ const GC_HEAP_GROW_FACTOR = 2;
allocator: std.mem.Allocator,
io: std.Io,
- table: Obj.String.Table,
+ pool: Obj.String.Pool,
objs: ObjList,
callbacks: CallbackList,
greys: GreyList,
+ allocated: usize,
+ next: usize,
fn dbg_print(comptime fmt: []const u8, args: anytype) void {
if (DBG_LOG) {
@@ -47,10 +50,12 @@ pub const GC = struct {
return Self{
.allocator = allocator,
.io = io,
- .table = Obj.String.Table.init(allocator),
+ .pool = Obj.String.Pool.init(allocator),
.objs = ObjList.init(allocator),
.callbacks = CallbackList.init(allocator),
.greys = GreyList.init(allocator),
+ .allocated = 0,
+ .next = 1024 * 1024,
};
}
@@ -60,6 +65,7 @@ pub const GC = struct {
self.trace_references();
self.table_remove_white();
self.sweep();
+ self.next = self.allocated * GC_HEAP_GROW_FACTOR;
}
}
@@ -119,12 +125,14 @@ pub const GC = struct {
}
fn table_remove_white(self: *Self) void {
- const tbl = &self.table;
- tbl.for_each(tbl, struct {
- pub fn fun(table: *Obj.String.Table, key: Obj.String.Table.Key, _: Obj.String.Table.Value) void {
+ const Table = Obj.String.Pool.Table;
+ const table = &self.pool.table;
+
+ table.for_each(table, struct {
+ pub fn fun(tbl: *Table, key: Table.Key, _: Table.Value) void {
const obj = key.cast();
if (obj.fields.gc and !obj.fields.mark)
- _ = table.delete(key);
+ _ = tbl.delete(key);
}
}.fun);
}
@@ -137,6 +145,9 @@ pub const GC = struct {
iter.pop();
dbg_obj("O", "free", obj, false);
obj.free(self.allocator);
+ switch (obj.type) {
+ inline else => |tp| self.allocated -= @sizeOf(tp.get()) + if (tp == .String) (obj.cast(tp) catch unreachable).len else 0,
+ }
} else {
obj.fields.mark = false;
}
@@ -175,47 +186,37 @@ pub const GC = struct {
}
}
- pub fn emplace(self: *Self, comptime tp: Obj.Type, arg: tp.get().Arg) (ObjList.Error || tp.get().Error)!*tp.get() {
- if (DBG_STRESS) {
+ pub fn emplace(self: *Self, comptime tp: Obj.Type, arg: tp.get().Arg) (ObjList.Error || tp.get().Error || Obj.String.Pool.Error)!*tp.get() {
+ if (tp == .String)
+ if (self.pool.find(arg)) |obj|
+ return obj;
+
+ const chd = try tp.get().init(arg, self.allocator);
+
+ self.allocated += @sizeOf(tp.get()) + if (tp == .String) chd.len else 0;
+ if (DBG_STRESS or self.allocated > self.next) {
self.collect();
}
- var newObj = true;
- const obj = switch (tp) {
- .String => try Obj.String.intern(arg, &self.table, &newObj, self.allocator),
- else => try tp.get().init(arg, self.allocator),
- };
+ if (tp == .String)
+ try self.pool.put(chd);
- if (newObj) {
- const obj_p = obj.cast();
+ const obj = chd.cast();
+ dbg_obj("O", "new", obj, true);
+ dbg_print("{d}/{d}\n", .{ self.allocated, self.next });
- dbg_obj("O", "new", obj_p, true);
- try self.objs.push(0, obj_p);
- }
+ try self.objs.push(0, obj);
- return obj;
+ return chd;
}
pub fn mark(self: *Self, msg: []const u8, arg: anytype) void {
- const T = @TypeOf(arg);
-
- switch (T) {
- Value => switch (arg) {
- .obj => |o| {
- self.mark(msg, o);
- },
- else => {},
- },
- *Obj => if (arg.fields.gc and !arg.fields.mark) {
- dbg_obj(msg, "mark", arg, true);
- arg.fields.mark = true;
- self.greys.push(-1, arg) catch @panic("Grey stack overflow");
- },
- else => if (comptime Obj.is_child(T)) {
- self.mark(msg, arg.cast());
- } else {
- @compileError("Unable to mark " ++ @typeName(T));
- },
+ if (Obj.from(arg)) |obj| {
+ if (obj.fields.gc and !obj.fields.mark) {
+ dbg_obj(msg, "mark", obj, true);
+ obj.fields.mark = true;
+ self.greys.push(-1, obj) catch @panic("Grey stack overflow");
+ }
}
}
@@ -223,7 +224,7 @@ pub const GC = struct {
obj.fields.gc = false;
}
- pub fn emplace_cast(self: *Self, comptime tp: Obj.Type, arg: tp.get().Arg) (ObjList.Error || tp.get().Error)!*Obj {
+ pub fn emplace_cast(self: *Self, comptime tp: Obj.Type, arg: tp.get().Arg) !*Obj {
return (try self.emplace(tp, arg)).cast();
}
@@ -236,6 +237,6 @@ pub const GC = struct {
el.free(self.allocator);
}
self.objs.free();
- self.table.deinit();
+ self.pool.free();
}
};
diff --git a/zlox/src/obj.zig b/zlox/src/obj.zig
@@ -1,6 +1,7 @@
const std = @import("std");
const utils = @import("lib::utils.zig");
+const Value = @import("value.zig").Value;
pub fn Obj(fields: anytype) type {
return packed struct {
@@ -28,7 +29,7 @@ pub fn Obj(fields: anytype) type {
Closure,
Upvalue,
- pub fn get(comptime self: @This()) type {
+ pub fn get(self: @This()) type {
return @field(Self, @tagName(self));
}
};
@@ -76,6 +77,19 @@ pub fn Obj(fields: anytype) type {
};
}
+ pub fn from(arg: anytype) ?*Self {
+ const T = @TypeOf(arg);
+
+ return switch (T) {
+ Value => switch (arg) {
+ .obj => |o| Self.from(o),
+ else => null,
+ },
+ *Self => arg,
+ else => if (comptime Self.is_child(T)) arg.cast() else null,
+ };
+ }
+
pub fn is(self: *const Self, tp: Type) bool {
return self.type == tp;
}
diff --git a/zlox/src/obj::string.zig b/zlox/src/obj::string.zig
@@ -12,9 +12,63 @@ pub fn String(fields: anytype) type {
return packed struct {
const Self = @This();
- pub const Table = table.Table(*Self, void, hash.hash_t(*const Self), Self.eql);
+
pub const Arg = []const []const u8;
- pub const Error = error{ OutOfMemory, IndexOutOfBounds } || Table.Error;
+ pub const Error = error{ OutOfMemory, IndexOutOfBounds };
+
+ pub const Pool = struct {
+ pub const Table = table.Table(*Self, void, hash.hash_t(*const Self), Self.eql);
+ pub const Error = Table.Error;
+
+ table: Table,
+
+ pub fn init(allocator: std.mem.Allocator) Pool {
+ return .{ .table = Table.init(allocator) };
+ }
+
+ fn check(arg: Arg, len: usize, hsh: u32) struct {
+ arg: Arg,
+ len: usize,
+ hash: u32,
+
+ pub fn check(self: *const @This(), other: *const Self) bool {
+ if (other.hash == self.hash and other.len == self.len) {
+ var idx: usize = 0;
+ for (self.arg) |el| {
+ if (!std.mem.eql(u8, other.data()[idx .. idx + el.len], el))
+ return false;
+ idx += el.len;
+ }
+ return true;
+ }
+ return false;
+ }
+ } {
+ return @TypeOf(check(arg, len, hsh)){
+ .arg = arg,
+ .len = len,
+ .hash = hsh,
+ };
+ }
+
+ pub fn put(self: *Pool, str: *Self) !void {
+ _ = try self.table.set(str, {});
+ }
+
+ pub fn find(self: *Pool, arg: Arg) ?*Self {
+ if (self.table.count == 0) return null;
+
+ const pre = Self.prehash(arg);
+
+ const entry = Table.find_(self.table.entries, pre.hash, check(arg, pre.len, pre.hash));
+
+ return if (entry.* != .some) null else entry.some.key;
+ }
+
+ pub fn free(self: *Pool) void {
+ self.table.deinit();
+ }
+ };
obj: Super,
len: usize = 0,
@@ -25,11 +79,11 @@ pub fn String(fields: anytype) type {
return p + @sizeOf(Self);
}
- fn new(arg: Arg, params: ArgParams, allocator: std.mem.Allocator) Error!*Self {
- const ret: *Self = @ptrCast(try allocator.alignedAlloc(u8, std.mem.Alignment.of(Self), @sizeOf(Self) + params.len));
+ fn new(arg: Arg, len: usize, hsh: u32, allocator: std.mem.Allocator) Error!*Self {
+ const ret: *Self = @ptrCast(try allocator.alignedAlloc(u8, std.mem.Alignment.of(Self), @sizeOf(Self) + len));
ret.* = Self{
.obj = Super.make(Self),
- .hash = params.hash,
+ .hash = hsh,
};
for (arg) |el| {
@memcpy(ret.data() + ret.len, el);
@@ -53,57 +107,30 @@ pub fn String(fields: anytype) type {
return @intFromPtr(self) == @intFromPtr(other);
}
pub fn get(self: *const Self, index: value.Value) Error!value.Value {
- if (!index.is(value.Value.number) or index.number >= @as(value.Value.tagType(value.Value.number), @floatFromInt(self.len)) or index.number < 0) {
+ if (!index.is(value.Value.number) or index.number >= @as(
+ value.Value.tagType(value.Value.number),
+ @floatFromInt(self.len),
+ ) or index.number < 0) {
return Error.IndexOutOfBounds;
}
return value.Value.init(self.data()[@intFromFloat(index.number)]);
}
- const ArgParams = struct { len: usize, hash: u32 };
-
- fn table_check(m_arg: Arg, m_params: ArgParams) struct {
- arg: Arg,
- params: ArgParams,
- pub fn check(self: *const @This(), k2: *const Self) bool {
- if (k2.hash == self.params.hash and k2.len == self.params.len) {
- var idx: usize = 0;
- for (self.arg) |el| {
- if (!std.mem.eql(u8, k2.data()[idx .. idx + el.len], el))
- return false;
- idx += el.len;
- }
- return true;
- }
- return false;
- }
- } {
- return @TypeOf(table_check(m_arg, m_params)){ .arg = m_arg, .params = m_params };
- }
-
- fn arg_params(arg: Arg) ArgParams {
- var ret = ArgParams{ .len = 0, .hash = hash.hash_t([]const u8)(&.{}) };
+ fn prehash(arg: Arg) struct { len: usize, hash: u32 } {
+ var len: usize = 0;
+ var hsh = hash.hash_t([]const u8)(&.{});
for (arg) |el| {
- ret.len += el.len;
- ret.hash = hash.hash_append(ret.hash, el);
+ len += el.len;
+ hsh = hash.hash_append(hsh, el);
}
- return ret;
+ return .{ .len = len, .hash = hsh };
}
- pub fn intern(arg: Arg, tabl: *Self.Table, isNewKey: *bool, allocator: std.mem.Allocator) Error!*Self {
- const params = arg_params(arg);
-
- try tabl.checkCapacity();
- const entry = Self.Table.find_(tabl.entries, params.hash, table_check(arg, params));
- isNewKey.* = entry.* != Self.Table.Entry.some;
- if (isNewKey.*) {
- _ = tabl.set_(entry, try new(arg, params, allocator), {});
- }
- return entry.some.key;
- }
+ pub fn init(arg: Arg, allocator: std.mem.Allocator) Error!*Self {
+ const pre = Self.prehash(arg);
- pub fn init(_: Arg, _: std.mem.Allocator) Error!*Self {
- @compileError("The String Obj has to be interned");
+ return new(arg, pre.len, pre.hash, allocator);
}
pub fn free(self: *const Self, allocator: std.mem.Allocator) void {
