From aaaa9d9eb290991b9b6d732c375472c891ddaf29 Mon Sep 17 00:00:00 2001 From: Taylan Kammer Date: Fri, 26 Jun 2026 00:00:00 +0200 Subject: Add a note. --- _tests/test.zig | 34 +++-- notes/260611-fastcons4.md | 81 +++++++++++ notes/260625-optimize.md | 360 ++++++++++++++++++++++++++++++++++++++++++++++ notes/260811-fastcons4.md | 81 ----------- notes/index.md | 3 +- src/zisp/gc/IstrSet.zig | 4 + 6 files changed, 466 insertions(+), 97 deletions(-) create mode 100644 notes/260611-fastcons4.md create mode 100644 notes/260625-optimize.md delete mode 100644 notes/260811-fastcons4.md diff --git a/_tests/test.zig b/_tests/test.zig index 21e8c14..6a61827 100644 --- a/_tests/test.zig +++ b/_tests/test.zig @@ -1,24 +1,28 @@ const std = @import("std"); -const List = std.ArrayListAlignedUnmanaged; +// const List = std.ArrayListAlignedUnmanaged; -const MyList = List(u8, .fromByteUnits(1 << 20)); +// const MyList = List(u8, .fromByteUnits(1 << 20)); -pub fn main() !u8 { - const alloc = std.heap.smp_allocator; +pub export fn main(argc: c_int, argv: [*]const [*:0]const u8) c_int { + const arr: [argc]u8 = undefined; + arr[0] = argv[0][0]; + std.debug.print("{}\n", .{arr[0]}); - var my_list = try MyList.initCapacity(alloc, 4); - try my_list.append(alloc, 0); - try my_list.append(alloc, 1); - try my_list.append(alloc, 2); - try my_list.append(alloc, 3); + // const alloc = std.heap.smp_allocator; - std.debug.print("addrs: {}, {}, {}, {}\n", .{ - &my_list.items[0], - &my_list.items[1], - &my_list.items[2], - &my_list.items[3], - }); + // var my_list = try MyList.initCapacity(alloc, 4); + // try my_list.append(alloc, 0); + // try my_list.append(alloc, 1); + // try my_list.append(alloc, 2); + // try my_list.append(alloc, 3); + + // std.debug.print("addrs: {}, {}, {}, {}\n", .{ + // &my_list.items[0], + // &my_list.items[1], + // &my_list.items[2], + // &my_list.items[3], + // }); return 0; } diff --git a/notes/260611-fastcons4.md b/notes/260611-fastcons4.md new file mode 100644 index 0000000..7c7ccd5 --- /dev/null +++ b/notes/260611-fastcons4.md @@ -0,0 +1,81 @@ +# Cons cell optimization AGAIN + +_2026 June_ + +Last episode: [Cons cell optimization again](260810-fastcons3.html) + +I am completely straying from my original idea of: "Just make a naive, +simple interpreter, with bindings to libgccjit, and anyone who needs +performance can just ask for specific functions in their code (or all +of them) to be compiled to native code." + +(See: [The interpreter and the compiler](260522-interpreter.html)) + +To be clear, I won't ditch that overall design idea. However, as I +started asking myself how to at least make a *reasonably* efficient +interpreter through the use of some smart tricks, I fell into a big +rabbit hole, and found myself enthralled by the idea of an advanced +direct AST interpreter that tries to approach the performance of a +byte-code VM while sticking to a tree representation of code. + +One of the many causes of inefficiency in AST walking is the need to +chase around pointers and, if using traditional s-expressions with +cons cells, the terrible data density. (Citation needed? I think +this is widely accepted.) + +A cons cell is 50% wasted space, using half of its memory to point to +the next cell. This is mostly alleviated by the array-segmented list +idea, but they still need a nil terminator for proper lists. + +That nil terminator is a whopping 8 bytes. If I also used 16-byte +alignment, I'd be wasting an average of 12 bytes per list! That's +what, almost 1/5 of a cache line? It's 18.75% to be exact. Even +using 8-byte alignment, wasting only 8 bytes per list, it's 1/8 or +12.5% of a cache line. + +Another way to look at it is total memory overhead. To calculate it, +you'd need to know the exact average length of lists in code. Let's +say it's 4 or something. (That's probably quite generous?) At that +length, every 1 out of 5 elements is just the nil terminator; a data +overhead of 20%! + +Reducing the memory footprint of code by ~10-20% or so is a highly +attractive prospect. And all we need to do is ditch improper lists. + +The new strategy is this: + +* A 3-bit tag on a list pointer indicates the length; either 1 to 7, + or if the tag value is 0, greater than 7. + +* For lists longer than 7 elements, with the tag value 0, the array + continues until a sentinel bit pattern is reached. + +A list is always an array; there are no linked segment chains. There +is no zero length list, since tag 0 means greater than 7, and other +values mean that exact count of elements. + +The vast majority of functions have only a handful of arguments; we +support up to 6 arguments without needing to rely on the special list +array format that is sentinel-terminated. + +This means the data density is 100% for function call expressions up +to 6 arguments (7 elements with the function itself). Perfect! + +## But... improper lists :( + +I honestly like improper lists. I think it's so elegant how Scheme +uses them to denote rest arguments. I even had this fancy idea of +using them for function calls where you pass on your own rest arg. + +(See: [Stop the "cons" madness!](250210-cons.html)) + +But sometimes you have to make sacrifices! Besides, I think the only +reason I like them is familiarity. They are kinda wonky if you think +about it. Common Lisp and Emacs Lisp don't use improper lists in any +part of their actual syntax, if I remember correctly. They use some +special identifier to mark rest args, and I could do a similar thing. + +Damn it: I spent so much time refining the documentation of the Zisp +parser, and now I'll have to make massive revisions again. Serves me +well for obsessing on one component without yet having a clear bigger +picture in mind. diff --git a/notes/260625-optimize.md b/notes/260625-optimize.md new file mode 100644 index 0000000..d43ddc6 --- /dev/null +++ b/notes/260625-optimize.md @@ -0,0 +1,360 @@ +# AST Optimizations + + + +I might be deluded, but I think it should be possible to make a tree +walking AST interpreter pretty much as efficient as a bytecode VM, if +we're smart enough about the AST representation and a well-selected +set of optimizations performed on it. + +Here's what I came up with so far. + +## Abandon linked lists (cons cells / pairs) + +Using traditional cons cells to represent code forms as linked lists +means you're paying a memory overhead of 50% to store lists. That's +ridiculous. Just use arrays. + +See my latest [cons cell optimization](260611-fastcons4.html) article +on how I've decided to implement this. Briefly: Most lists in code +are under 8 elements anyway, so we use the low 3 bits of a pointer to +encode whether the length is 1 to 7, or greater; only if it's greater +does the array being pointed to require a termination marker. + +(We could put the length in a 64-bit head if longer than 7, but the +AST walker will be going through the list one way or another, so it +doesn't really matter; having the elements always start at zero is +simpler.) + +## Tight packing of short arrays + +To further ensure minimal memory footprint of AST nodes, we make sure +that they're allocated tightly in blocks, without any padding between +them. See `src/zisp/gc/ListPool.zig` for how I've implemented this. +Cache locality and memory density should now be perfect. + +## Help the prefetcher (ABANDONED) + +Memory prefetching refers to a modern CPU feature in which the CPU +notices that you're accessing memory addresses sequentially, and +decides to prefetch memory beyond what you've requested. + +It would be neat if we could order the memory of our AST nodes such +that they occur in the order the interpreter will walk them, but it's +difficult to achieve without significant complications that make the +parser slower in general, having to constantly copy around arrays to +put them in the right order. + +I've decided to abandon this idea, because most code jumps around a +lot anyway. By the time you've accessed 3-4 sequential cache lines, +and the prefetcher started to warm up to the pattern, you suddenly +jump to a completely different point in the AST because a function +call that's not inlined is encountered. + +So yeah, scrap that. Hopefully it makes no difference. + +## Quoted data directly in the AST + +This may just be a stupid micro-optimization, because data that could +be confused for code to evaluate (lists and identifiers) but is meant +as a constant value can simply be wrapped in `(#QUOTE x)` which is a +pointer to a two-value array which should be very quick to evaluate, +but I had a lot of spare value ranges in my NaN packing strategy so +I've decided to dedicate some of them to "implicitly" quoted values. + +A two-value array is a two-value array. There will be fewer of them +this way, and you'll be saving two 64-bit values per quoted object. + +This isn't actually that bad considering Zisp conflates strings and +symbols. Code with lots of string literals would otherwise end up +with lots of quote forms (automatically emitted by the parser upon +encountering a double-quoted string) if not for this optimization. + +## Constant propagation + +Standard stuff: If a variable is an immutable reference to a value +known statically, just inline the value when the variable is used. + +Example Scheme code: + + ;; before optimization + (define x 5) + (define (foo) (+ x 1)) + + ;; after + (define (foo) (+ 5 1)) + + ;; in fact, probably this + (define (foo) 6) + +Any operator in the standard library (whose bindings are immutable) +may be marked as "pure" which makes it eligible for evaluation at +optimization time to fold constants. + +The same could be done with non-exported functions in user code, so +the following works as well... + + ;; before + (define x 5) + (let (foo) (+ x 1)) + (define (bar) (foo)) + + ;; after + (define (bar) 6) + +Note: `(let (foo) ...)` is a local function definition in Zisp. Not +married to this syntax, but I think I like it. + +Actually, we may decide *not* to do this optimization for exported +constants, so they can be redefined. Let's say `define` creates +public bindings and `let` local ones: + + ;; before + + (define x 5) + (let y 10) + (let (z) (* y 2)) + + (define (foo) (+ x 1)) + (define (bar) (+ y 1)) + (define (qux) (+ (z) 1)) + + ;; after + + (define x 5) + + (define (foo) (+ x 1)) + (define (bar) 11) + (define (qux) 21) + +I think I like that. There could still be a way for other modules to +"statically link" to a module, which would effectively turn public +bindings of that module into local bindings within the importing +module, thus making the constants eligible for folding anyway! + +## Lexical closure references by flat index + +Now we're getting to the hot stuff. + +Zisp won't allow capturing mutable variables by reference in closures; +you'll need to copy the variable's current value into a non-mutable +variable if you want to capture it. (There's precedent for this in +other languages, like Java; nothing newly invented here.) + +You can still simply capture a reference to a mutable heap object, +like a one-element array aka "box" object type, so you're not really +losing any power. IMO, this actually makes code cleaner anyway, as +capturing mutable state in a closure becomes clearly demarcated via +explicit heap allocation. + +Given that captures are immutable, they can be passed by value rather +than by reference. This is conceptually implemented by the following +algorithm, though we'll optimize it greatly: + +1. Whenever a `lambda` is evaluated, walk through it to locate the + lexically captured variables, giving each a number. + +2. Put their values in a `captures` array and associate it with the + lambda object. + +3. Replace the lexical variable references in the lambda body with + indexing operations into said array. + +Although well-written code probably shouldn't be calling `lambda` all +the time, it would still be bad if we need to walk the entire body +every time we encounter one. + +The walk only needs to happen once; we can then create a "template" +array that contains references to the *current* scope, and the next +time the lambda is encountered, we copy the array and evaluate the +contained local references, then attach that new array to the new +closure object. + +Here's some Scheme-like pseudo-code to demonstrate: + + ;; Raw source + + (define (higher-order x y) + (lambda (z) + (+ x y z))) + + (define foo (higher-order 1 2)) + + ;; Optimized; using # to represent "internal" stuff + + (define (higher-order x y) + (# # (z) + (+ # # z))) + + (define foo (higher-order 1 2)) + ;foo = # # z)> + +This "fattens" closures a bit but I think it's worth it. I'm pretty +sure that various Scheme implementations do this when they can prove +that a captured variable is immutable. Another cache locality win, +and no 2D environment traversal at execution time. + +If you look carefully, you'll notice that we inserted a node into the +AST: `#`. This is to be avoided, as I want the +AST optimizations to happen purely in-place to preserve the tightly +packed nature of the list-arrays making up the source code, and to +avoid unnecessary allocations and code bloat. + +Fortunately, `#` could actually be represented with just +a few bits... In the NaN packing strategy, there is a special type of +pointer which basically means "pointer to optimized code expression." +The first element of the destination, then, doesn't need to be treated +as an arbitrary NaN-packed value, but can instead be a sort of tightly +packed instruction with a payload. Say, lower 8 bits for the opcode, +and higher 56 bits as payload. Now `#` can itself have +the pointer to `[x y]` in its payload, implicitly meaning those are +the lexicals to be copied. + +This still means there's an extra allocation happening which isn't +*strictly* necessary as we could walk the body every single time the +`lambda` is executed (i.e., at closure creation time), but let's not +be unreasonable. So long as I keep the original shape of the AST, +only needing small auxiliary allocations, I consider it a success. + +To summarize: References to captured lexicals are now literally just +`lexicals[i]` where `lexicals` could, I suppose, be a thread-local +global variable, given that only one function is active at a time, or +it could be an implicitly passed argument; we'll see. + +Meanwhile, creating a lambda is still reasonably cheap, requiring only +the copying of a (usually very small) array and iterating through it +to replace "local variable reference" objects with their values. + +Those "local variable reference" objects can also just be flat array +indexes, thanks to other optimizations... + +## Eager stack frame allocation + +This may just be a micro-optimization; I've not thought about it that +much yet. But basically, the idea is to walk the body of a lambda, +and note how many local variables it uses, so you can allocate its +entire stack frame at once, then turn local variable references into +flat array indexes. + +We can combine this with the previous strategy: The same walk through +the body can count local declarations, numbering them and turning them +into literally just `locals[i]` (regardless of whether it's assignment +or reference). The count can be stored alongside the array of lexical +captures, changing our closure shape on the heap to: + + # + +The `locals` array could be a thread local or implicit argument like +the `lexicals` array, or it could actually just be based on the stack +pointer. (Referring to the Zisp stack, not the native stack.) + +Oh, and function parameters are of course just the first few entries +in this (conceptual) locals array (which may just be a stack pointer) +and get populated at the call-site with the passed arguments. + +## Lexical and local reference representation + +Above, I've said that lexical and local variable references literally +become `lexicals[i]` and `locals[i]`, but that was a bit of a lie. +This is an interpreter after all. + +What I meant is: + +The AST will contain nodes that are NaN-packed values (like almost +everything in the AST) with a tag saying e.g. "lexical reference," +holding a payload value of up to 48 bits, which is the index. + +So, the interpreter's code would contain something like this: + + const tag: u16 = getTag(nan_value); + const payload: u48 = getPayload(nan_value); + return switch (tag) { + ... + LOCAL_REF => locals[payload], + LEXICAL_REF => lexicals[payload], + ... + }; + +Realistically, you don't need 48 bits for a local or lexical variable +index. Even 16 bits would be more than enough. So, there's a bit of +waste here compared to what we could do with bytecode. + +## VM opcode in expression head + +I've already explained this above as part of the lexical references +optimization: + +Once a list (array) has been analyzed and deemed to be a valid form, +the pointer to it can have its tag switched to mean "optimized code +expression pointer" and then the first element doesn't need to be +treated as an arbitrary NaN-packed value anymore, and can instead +denote various operations (8 bits) with a payload (56 bits). + +Now in our AST we can essentially have VM opcodes standing for things +like IF, WHILE, LAMBDA (as explained above), CALL, and so on, with a +payload that can fit a 48-bit pointer with 8 bits to spare. + +Given that various operations like IF don't actually need a payload, +this is likely to end up being one of the remaining sources of memory +waste in our AST, along with the generally pointer-rich structure as +it is still a tree with a uniform 64-bit NaN-packed value/node format. + +## Wrapping up + +I think this is all the ideas I had floating in my mind so far; might +add more later if I can think of any. + +There's no question that bytecode would be more compact than this AST +despite all the optimizations. Wasting 56 bits on an unused opcode +payload here, 32 bits on an overly large locals index there, and the +generally pointer-rich structure of the tree... These will add up, +and bytecode could fix all that. But the beauty of this strategy is +that you literally just work directly on the data structure returned +by the parser, doing only in-place mutations and a small number of +auxiliary allocations. Even after optimizations, the AST should be +almost trivial to serialize in a pretty-printed format to get either +some nice insights into what the optimizer did, or, if allocation of +debug metadata was enabled, it may even be possible to turn it back +into original source form. + +So, the low latency and the REPL/debug experience will be impeccable. +Not to mention the incredible simplicity of it all: We don't need a +complex bytecode design, a bytecode VM, a bytecode debugger, etc.; +only a few "VM opcodes" in the first position of some arrays which +simply represent AST nodes. + +And if you need peak performance, there's always native compilation. + +In my opinion, JIT is unnecessary, because one can just use GCC or +LLVM for AOT-quality codegen at runtime these days. (They call it +JIT, like in libgccjit, but it's really AOT as a library.) Either +way, you can skip the bytecode. There's actually a little research +indicating that JIT from AST is as good as, if not better than, JIT +from bytecode: + +[AST vs. Bytecode: Interpreters in the Age of Meta-Compilation](https://stefan-marr.de/downloads/oopsla23-larose-et-al-ast-vs-bytecode-interpreters-in-the-age-of-meta-compilation.pdf) + +That's using RPython and GraalVM, but I think the same should apply +when using LLVM or GCC. Any optimizations specific to the Lispish +nature of a language should be possible to perform on the original +AST, or something close to it; after that, send it to LLVM/GCC and +have them perform the brunt of complex, slow, AOT-tier optimizations. + +Transforming to bytecode first may even act as obfuscation and end up +worsening the work of GCC/LLVM on the code. Don't quote me on that, +though. + +In Zisp, I want to support what I've dubbed "manual JIT" meaning the +programmer is in control over what should be native-compiled and when. + +A performance-critical application could be shipped as source code, +but compile itself at startup, for instance. I've written more about +this idea here: + +[The interpreter and the compiler](260522-interpreter.html) + +And when you want the REPL experience, or quick source-only scripts +for which you don't even want to deal with annoying on-disk bytecode +cache files, then the in-place optimizing AST interpreter should do a +fine job. diff --git a/notes/260811-fastcons4.md b/notes/260811-fastcons4.md deleted file mode 100644 index 7c7ccd5..0000000 --- a/notes/260811-fastcons4.md +++ /dev/null @@ -1,81 +0,0 @@ -# Cons cell optimization AGAIN - -_2026 June_ - -Last episode: [Cons cell optimization again](260810-fastcons3.html) - -I am completely straying from my original idea of: "Just make a naive, -simple interpreter, with bindings to libgccjit, and anyone who needs -performance can just ask for specific functions in their code (or all -of them) to be compiled to native code." - -(See: [The interpreter and the compiler](260522-interpreter.html)) - -To be clear, I won't ditch that overall design idea. However, as I -started asking myself how to at least make a *reasonably* efficient -interpreter through the use of some smart tricks, I fell into a big -rabbit hole, and found myself enthralled by the idea of an advanced -direct AST interpreter that tries to approach the performance of a -byte-code VM while sticking to a tree representation of code. - -One of the many causes of inefficiency in AST walking is the need to -chase around pointers and, if using traditional s-expressions with -cons cells, the terrible data density. (Citation needed? I think -this is widely accepted.) - -A cons cell is 50% wasted space, using half of its memory to point to -the next cell. This is mostly alleviated by the array-segmented list -idea, but they still need a nil terminator for proper lists. - -That nil terminator is a whopping 8 bytes. If I also used 16-byte -alignment, I'd be wasting an average of 12 bytes per list! That's -what, almost 1/5 of a cache line? It's 18.75% to be exact. Even -using 8-byte alignment, wasting only 8 bytes per list, it's 1/8 or -12.5% of a cache line. - -Another way to look at it is total memory overhead. To calculate it, -you'd need to know the exact average length of lists in code. Let's -say it's 4 or something. (That's probably quite generous?) At that -length, every 1 out of 5 elements is just the nil terminator; a data -overhead of 20%! - -Reducing the memory footprint of code by ~10-20% or so is a highly -attractive prospect. And all we need to do is ditch improper lists. - -The new strategy is this: - -* A 3-bit tag on a list pointer indicates the length; either 1 to 7, - or if the tag value is 0, greater than 7. - -* For lists longer than 7 elements, with the tag value 0, the array - continues until a sentinel bit pattern is reached. - -A list is always an array; there are no linked segment chains. There -is no zero length list, since tag 0 means greater than 7, and other -values mean that exact count of elements. - -The vast majority of functions have only a handful of arguments; we -support up to 6 arguments without needing to rely on the special list -array format that is sentinel-terminated. - -This means the data density is 100% for function call expressions up -to 6 arguments (7 elements with the function itself). Perfect! - -## But... improper lists :( - -I honestly like improper lists. I think it's so elegant how Scheme -uses them to denote rest arguments. I even had this fancy idea of -using them for function calls where you pass on your own rest arg. - -(See: [Stop the "cons" madness!](250210-cons.html)) - -But sometimes you have to make sacrifices! Besides, I think the only -reason I like them is familiarity. They are kinda wonky if you think -about it. Common Lisp and Emacs Lisp don't use improper lists in any -part of their actual syntax, if I remember correctly. They use some -special identifier to mark rest args, and I could do a similar thing. - -Damn it: I spent so much time refining the documentation of the Zisp -parser, and now I'll have to make massive revisions again. Serves me -well for obsessing on one component without yet having a clear bigger -picture in mind. diff --git a/notes/index.md b/notes/index.md index b38c529..346bcb6 100644 --- a/notes/index.md +++ b/notes/index.md @@ -32,4 +32,5 @@ * [Static analysis to optimize GC](260524-gc-opt.html) * [Cons cell optimization!](260608-fastcons2.html) * [Cons cell optimization again](260610-fastcons3.html) -* [Cons cell optimization AGAIN](260811-fastcons4.html) +* [Cons cell optimization AGAIN](260611-fastcons4.html) +* [AST Optimizations](260625-optimize.html) diff --git a/src/zisp/gc/IstrSet.zig b/src/zisp/gc/IstrSet.zig index 900caa7..179476e 100644 --- a/src/zisp/gc/IstrSet.zig +++ b/src/zisp/gc/IstrSet.zig @@ -1,3 +1,7 @@ +//! Interned string set + +// TODO: Allocate the strings in tight blocks just like ListPool. + const std = @import("std"); const Alloc = std.mem.Allocator; -- cgit v1.2.3