Hacker News Reader

Comment by drewm1980 | Hacker News Reader

drewm1980

On my first skim through the article it seemed like objects were getting copied between regions, i.e. when they change color. I guess the key is one of the first sentences "all objects in the heap are organised in a cyclic double-linked list", so there is a layer of indirection, and the circle you see is not the actual address space as I initially assumed, but the linked list. Did I understand correctly?

View on HN

Double-linked list (Baker calls it "Knuth's double-linked list") allows O(1) insertions and deletions (hence moving) without actually moving objects and without additional indirection. Each object has a header that contains pointers to the next and previous objects in the list. To remove obj from the list do { obj->next->prev, obj->prev->next = obj->prev, obj->next } (I use "parallel assignment" for simplicity), similarly for insertion, see https://en.wikipedia.org/wiki/Doubly_linked_list . So the circles in the diagram are not actual address space (in the sense that object addresses are not increasing monotonically as you go clockwise), but there is no additional indirection because the header with the forward and backward pointers is part of the object.

Iirc, there are two approaches to managing your treadmill.

You either use one treadmill with a fixed size abject header/pointer. The “guts” of the object are placed on a heap which gets spaghettified and fragmented pretty fast, especially if your not going to move bodies, because… real time.

The other approach is to use multiple treadmills/rings for different size objects. Different rings are then used for different sizes of objects. In this way, your heap fragmentation/locality improves, but at the added cost of indirecting on object size.

It does mean that in a short period your heap will be a knotted spaghetti of objects with virtually pessimal locality as you chase pointers around the loop.

That's true, the worst case is bad. But if mutator locality of reference is reasonable, the scanner will preserve it. After all, Baker rejected his earlier copying design for a reason.

Yes

Reply on news.ycombinator.com