Add a note.

5 files changed, 385 insertions, 16 deletions

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/260811-fastcons4.md b/notes/260611-fastcons4.md
index 7c7ccd5..7c7ccd5 100644
--- a/notes/260811-fastcons4.md
+++ b/notes/260611-fastcons4.md
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
+
+<!--TOC-->
+
+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 #<foo> to represent "internal" stuff
+
+    (define (higher-order x y)
+      (#<make_lambda> #<copy_lexicals [x y]> (z)
+        (+ #<lexical:0> #<lexical:1> z)))
+
+    (define foo (higher-order 1 2))
+    ;foo = #<lambda lexicals:[1 2] (z)
+              (+ #<lexical:0> #<lexical:1> 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: `#<copy_lexicals [x y]>`.  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, `#<make_lambda>` 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 `#<make_lambda>` 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:
+
+    #<lambda meta:{ locals_count:N lexicals:[...] } (args) (body)>
+
+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/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;