Hacker News Reader

Comment by cwzwarich | Hacker News Reader

Why don't they just use the Deutsch-Schorr-Waite algorithm to store the mark stack in the heap itself with pointer-reversal tricks? This would remove the additional overhead.

View on HN

Is there any paper describing how this extends to objects containing N pointers without blowing up the number of bits needed?

Like say we are marking a vector containing pointers to objects. We need a state machine which tells us, on each visit to that object which tells us: "we have marked index [i]; now mark index [i+1]".

A list of 256 nodes doesn't have this problem: it has the marking bits in each node!

Also, how do we design the API for extending the heap with new kinds of objects. With the recursive traversal, you just provide a handler which traverses your objects and recurses down the pointers.

Perhaps we need some complicated protocol now whereby each object has methods like "init_traversal", "get_next_pointer", and "finish_traversal". In init_traversal, it receives a backpointer that it must store, and it returns a pointer that it would like the caller to retain (the one that is bumped to make space for the stashed one). In "finish_traversal", it gets back the retained pointer, in exchange for returning the stashed backpointer. Something like that.

Actually a protocol like this could perhaps clarify the algorithm.

I find the easiest way to think about this trick is to consider the CPS transformation of a depth-first traversal of a tree (in the case of a general graph, you use a DFS spanning tree). At each recursive call, you need to be able to produce and store the continuation upon return. Upon returning from a recursive call, you need to rematerialize the continuation.

The object pointer for the most recent continuation is stored in a global variable, and others are stored in a stack constructed by using pointers in objects that can now be inferred from the stacking nature of the recursion.

Part of the information for the code pointer for the most recent continuation is stored in the object pointer, i.e. from the object header you narrow the possibilities to process it. For an object containing N fields, you need log_2 N bits to store the field you were last processing. Since each object can appear in at most one stack frame of the recursive traversal (modulo where you put the marked check to bail out in the graph case), you need to put these log_2 N bits somewhere in the object.

You have a few options for where to put the bits:

- Find a few bits lying around where you can store them. This works pretty well for objects with few fields.

- Add an extra field with log_2 N bits to store them. This is the most straightforward solution for a larger object with an arbitrary number of fields.

- If you have an easy way of locating object headers from internal pointers, you can use internal pointers as your back pointers.

- Steal a few bits from every field that has a pointer value stored in it. This works because you actually only need log_2 M bits where M is the number of fields containing a pointer. The non-pointer fields can all be skipped.

This scheme can be generalized to implement arbitrary structural recursion on polynomial datatypes:

https://www.sciencedirect.com/science/article/pii/0096055193...

Huh. I wasn't aware of that trick. I'll look into it. Thanks.

Schorr-Waite works for binary graphs, storing the left/right choice in tag bits. Your block bitmap queue idea is more interesting, perhaps with two levels of bitmaps to scan 64*64 words with a single instruction.

For the naive implementation you could either use a stack and tail recurse on the last unmarked cell, or a queue with tail recursion on the first unmarked cell (that is, you push on the queue cells starting at the second unmarked cell, and tail recurse on the first to improve locality of reference).

(I wrote GNU Smalltalk's GC in another life :-)).

I believe something similar (maybe exactly that) was suggested later on in the thread.

> Why don't they just use the Deutsch-Schorr-Waite algorithm

Here is a good reason: you're debugging some problem that occurs in the middle of garbage collection. You have the world stopped and would like to look at some objects. Oops, pointers are scrambled by this algorithm and won't be put back in place until it runs to completion. (Which it might not even be able to do due to whatever bug you're trying to investigate, even if you have a way to initiate that.)

With regular recursive traversal, you can just bail garbage collection at any time: loop through all the heaps, and reset the gc bits of all objects to the "unmarked" state. Then examine whatever you want.

(If the bits aren't in the type tag, you don't even have to do that; though it's a good idea for them to be in a type tag because then an object which has been mis-handled by memory management (e.g. marked object remains in the live object graph after gc) then it has the wrong type and blows up when used.)

In practice, if you get something like this wrong and are forced to debug it, you will probably have to do some code inspection or printf debugging to find the cause. But it's still better than most concurrent GC algorithms in that regard.

What can't you debug with code inspection and printf?

Some black box with that has no printf (or not that you can insert into a custom build), and for which code isn't available.

For emacs it might be OK, usually mutating objects in the heap during marking is not a good idea, as it breaks sharing CoW pages with forks.

Much better would be a copying collector, like a twofinger collector, because emacs doesn't have much foreign pointers for political reasons, which can be handled separately. No stack, much faster, much slimmer.

emacs doesn't have much foreign pointers for political reasons

This is an interesting connection. Could you elaborate on this?

We support external modules these days. I specifically designed its interface to allow for a moving collector. The current implementation of the C core, however, precludes such a thing.

Copying collectors can handle foreign pointers. Why? Because foreign pointers can be managed via handle records. Those handle records are GC objects with a type tag and all that; they hold the foreign pointer as an opaque machine word in one of their fields. The handles themselves can be moved around by a copying/compacting allocator. Of course, the foreign objects aren't. You typically don't even know their size. They could be things like a library handle returned by dlopen(): don't even think about moving that. They could also be pointers into the middle of some object; a displaced C pointer can enter the GC world as a foreign pointer.

The biggest problem are callbacks from foreign calls back into your moved heap. Called back objects need to stay put, in a separate fixed area. All major lisps with proper FFI support do that.

modules are no big deal, FFI's with callbacks are. And since RMS opposed an FFI for emacs for decades (DLL or OLE/COM support) - there's now a simple internal one for the gtk binding - a moving collector would be pretty simple.

Emacs likes pointer reversal tricks!

https://github.com/emacs-mirror/emacs/blob/cc8ae51e6f62f86d0...

(Unrelated, but an amusing coincidence.)

Reply on news.ycombinator.com