The Lone Lisp Heap

5 hours ago

Lone began as a collection of C data structures with a union for types and a language built to assemble them into programs.
Initially, there was no malloc or dynamic memory allocation in freestanding C, so a custom memory allocator was written.
The first allocator used a linked list of blocks with first-fit search, splitting for requests and coalescing freed blocks, but it was inefficient and had high overhead.
Lone used this allocator for about three years to allocate memory for lisp objects despite its flaws.
A conservative garbage collector needed to identify pointers to lisp objects, leading to a heap redesign using linked lists of arrays for bulk allocation.
Values were stored in contiguous arrays within chunks to allow efficient pointer checking, with dead values being 'resurrected' for reuse.
The challenge of resizing arrays without invalidating pointers led to a change from pointers to indexes into a monolithic array.
The heap evolved into a large, page-aligned array mapped with mmap and managed with mremap for efficient resizing without copying.
Despite improvements, the heap still linearly scans for dead values starting from the beginning each time.

Hasty Briefsbeta