3 ms·
> Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array. This happens naturally if you bump-allocate them
by kazinator 2y ago
> Instead of allocating Expr objects willy-nilly on the heap, we’ll pack them into a single, contiguous array.
This happens naturally if you bump-allocate them in a garbage-collected run-time, particularly under a copying collector. Free lists also tend to co-locate because they are produced during sweep phases of GC which run through heaps in order of address.
Don't make me bring out the L word for the billionth time.
> A flat array of Exprs can make it fun and easy to implement hash consing
OK, it's not a case of L-ignorance, just willful neglect.
- samps 2y agoFWIW I did acknowledge this in the article: > A sufficiently smart memory allocator might achieve the same thing, especially if you allocate the whole AST up front and never add to it > Again, a really fast malloc might be hard to compete with—but you basically can’t beat bump allocation on sheer simplicity.
- layer8 2y agoAnd if you don’t need more than 32 GB of heap space, the JVM also gives you the ability to reduce reference sizes to 32 bits, with compressed references. (Due to alignment requirements, the lower 3 bits of a pointer are zero and hence do not need to be stored, which effectively gives you a 35-bit address space.) Of course, the presence of object headers counteracts this to a certain extent.