3 ms·
I saw that Kilo Lisp claimed "constant space garbage collection." I understand why a project like Kilo Lisp might like this, but I was curious about how that wa
by KirinDave 8y ago
I saw that Kilo Lisp claimed "constant space garbage collection." I understand why a project like Kilo Lisp might like this, but I was curious about how that was accomplished, so I looked through the code.
The actual GC cycle code is pretty small, and looks like a classic mark-and-sweep over a fixed heap:
int gc(void) {
int i, k;
k = 0;
for (i=0; Root[i]; i++) mark(Root[i][0]);
Freelist = NIL;
for (i=0; i<NNODES; i++) {
if (0 == (Tag[i] & MARK)) {
setcdr(i, Freelist);
Freelist = i;
k = k+1;
}
else {
Tag[i] &= ~MARK;
}
}
/* ... */
return k;
}
Cutting out the verbose GC stuff, there is a finite number of nodes and a free list. Exactly what one might expect. Even sorta feels like hardware.
The function mark is a classic algorithm, the Schorr-Waite algorithm [1], which traverses a directed graph and reverses the pointers, which modifies the heap graph as it traverses it to keep track of how much the graph has.
This is an interesting choice, and gave me pause because in a traditional large heap this would be a fantastically bad decision. But it's pretty interesting that the entire memory image of KiloLisp can exist in side the L2 cache of a raspberry pi and and in some circumstances half the memory can be hot and still reside in L1.
So actually, this is pretty clever. I suspect it's a good case of mechanical sympathy in recognizing that filling L2 will probably remove any gains that a "fancier" algorithm or a non-constant algorithm would bring. Very cool.
[1]: https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf https://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec... is a good reference for this. The original article is annoying to get and hard to read.