3 ms·
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
by oecumena 4y ago
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 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.
- RodgerTheGreat 4y agoIt 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.
- oecumena 4y agoThat'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.
- travisgriggs 4y agoIirc, 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.