Comment by mbrock
16 days ago
I actually made a Lisp interpreter in Zig a couple of years ago that has each object type in a separate heap array. In fact each field of each object type has its own array: every CDR is in one contiguous array. This was mostly for fun and to experiment with data-driven techniques using Zig metaprogramming. The code turned out relatively clean and simple.
https://github.com/mbrock/wisp
GC is stop© which as a side effect compacts each of those arrays and improves locality. I think most lists should end up having their CDRs next to each other in memory making iteration very cache friendly. But I didn't verify any performance qualities, beyond making it efficient enough for basic use.
It also has delimited continuation control, compiles to WebAssembly, and hooks promises into the continuation system, among some other pretty cool features!
Well I'll be damned! That sounds very much like what I want Nova to eventually be :) We don't have fields split apart at present, mostly because Rust doesn't make that quite as easy as I would want to. Otherwise it sounds like it's very much all the same, in a good way.
I'll definitely be taking a look at wisp, thank you very much for the link! If you ever have the time, I'd love seeing a comparison of this sort of engine design against a more traditional one.
Sorry, what is "CDR" in this context though?
Quick reply to the cdr thing: car/cdr are old Lisp names for the head/tail fields of linked list cells! :)
Ah, of course!
Yes. the right thing to do is to treat a list as a general case and other uses of cons as special case
I've flipped that idea around in a few of my own language designs, where pairs are the central feature and lists are just pairs with pair cdrs. Works fine from what I can see.
Yes pairs is the 1980s lisp design, but it’s not good for modern caches. Both obviously work.
Oh yeah, continuation pointers also have their own array like every other field kind, which should have similar benefits as list traversal but for continuation copying... It's a really interesting design area, I think. Zig makes it easy!
Yeah, I'm quite envious of the MultiArrayList or whatever it was that Zig has: If only Rust had that sort of a type built-in <3
That's how I got interested in this kind of memory layout in the first place. I wanted a nice Lisp for WebAssembly and had recently gotten into Zig. When I started defining the word structure I remembered Andy Kelley's talk about using data-oriented design to make the Zig compiler fast, so I thought I'd try it, and the more I thought about it the more reasonable it seemed.
There are like a dozen object types with different growing multiarrays. Words are 32 bit with 1 for GC state and 27 for index and the rest are the type tag. Ints are 28 bits. Byte arrays have their own heap too, as well as general 32 bit vectors.