The lone lisp heap
16 points by veqq
16 points by veqq
It’s interesting to read this article that how lone lisp is implemented. I have also wrote some similar topics on Elisp that I think it’s worth sharing.
This is really interesting, thanks. Had never explored Emacs's internals before.
The fat pointers in the article stood out to me. Lone used that representation for quite a while. I moved away from it for the same memory efficiency reasons.
The heap is literally just a big dumb flat array of values now. A black monolith. An absolute unit. Lone values simply index into this array. The array could be anywhere in memory, it doesn't matter where it is. The real pointers are simply calculated on the fly.
I think is similar to how memory was handled in classic Mac OS (and Windows). You got a handle, which was a pointer to a master pointer. The memory manager could reorganise the heap, updating the master pointer as needed. The downside as you had to dereference two pointers to get to the actual data.
The downside as you had to dereference two pointers to get to the actual data.
I was going to joke that as a CISC the 68000 probably had an indirect addressing mode that allowed you to double-dereference in one shot, but it turns out memory indirect addressing was one of the ill-advised super-CISC features added in the 68020.
It compiles to a couple of shifts plus a load+add operation.
shr $0x18, %rax ; extract 40-bit index
shl $0x6, %rax ; multiply by sizeof(heap_value) == 64
add 0x28(%rdi), %rax ; load heap.values base pointer and add offset
On x86_64 it's 3 uops, around 4-6 cycles. With link time optimization, this is inlined pretty much everywhere and GCC often keeps the base pointer in a register, which simplifies the above to add <reg>, %rax. In these cases, it's a single pointer dereference.