Exploit unique pointers (project)
Here is a simple, folk-lore idea for reducing GC load in GHC, which I discussed with Daan Leijen and Anton Lorenzen at ICFP'23. This ticket is just to record the idea.
The opportunity
-
Claim: many data structures are allocated, consumed, and discarded, without ever being duplicated. E.g. in
map f (reverse xs)
, the list produced byreverse
is immediately consumed bymap
. -
A one-bit reference count on each heap object would suffice, in many cases, to tell us at runtime when a heap object (such as the list returned by
reverse
) is uniquely referenced. -
When a function consumes a unique input object, two opportunities arise:
- We could could return the cell to the storage manager.
- We could immediately re-use the cell. For example, if
map
consumes a unique list, it can allocate the returned cells in the input cells. See Daan Leijen's ICFP '23 paper Fully in place functional programming. NB that paper describes something more ambitious than I am describing here. But the immediate-reuse stuff is relevant, and the paper has a number of compelling examples.
-
If a uniquely-referenced thunk is entered, it doesn't need to be updated. That could be another saving.
-
The garbage collector still runs un-modified, just as now. So we will still recover cycles, cells used more than once, etc.
-
Even the reference count on an object says "many", at GC time there might now be only one pointer to it. So the GC (which traces all references) can restore unique-pointer information.
Reflecting on the opportunity
-
A one-bit reference count means that an object is either "unique" or "many". As soon as it goes to "many" we lose track of the count, so it can never go back to "unique" (except by the action of the GC). So this plan will only be effective if many objects are born and die without every having a shared pointer to them. Before investing much we'd need data on how common that is. (My intuition is that it'd be very common.)
Of course you could always have a 2-bit or 3-bit ref count instead.
-
Opportunity (1) is to give back a freed object to the storage manager. But because these freed objects are scattered, we can't use bump-pointer allocation for them. However, especially with the non-moving collection, old generations use free-lists and so may just possibly exploit such freed objects. But my guess is that (1) is of marginal importance, and that (2) is the real win.
-
Note that there extra run-time tests (and extra code) to check for uniqueness. Binary sizes will increase; don't know how much.
-
GHC currently does one bump-pointer heap check to cover multiple allocations. It's not clear how to adapt this if some, but not all, of those allocations are being done in-place instead.
-
When would this be a win? It depends on whether uniquely-referenced data is common in practice. we need data! And we could perhaps gather that data without (yet) exploiting. (Much of the implementation cost is associated with the exploitation, I think, so gathering the data might take a lot less effort.
-
When a unique heap object is consumed, we may re-use it. But if it is in the old generation, reusing it would mean adding lots of pointers to the remembered set (pointers into the young generation). That's just as expensive as allocation! So it probably does not make sense to re-use old-generation objects.
-
Where could we store a 1-bit reference count? Two thoughts
- In the least-significant bit of the info pointer. We'd need to mask it before entering it.
- In the pointer to the object. E.g. a unique pointer has LS bit=0, a shared pointer has
LS bit=1. Messing with the pointer would avoid memory traffic (good). But:
- We use those same bits for pointer tagging, so we'd have to steal one back for this sharing purpose.
- It would be harder for the GC to restore unique-pointer info. I think much harder.
What next?
Exploring this idea could be a very interesting project, but it would be a non-trivial amount of work.
The first thing would be to gather data about how often unique pointeres are encountered in practice.