Potential improvement in compacting GC

[Ben Gamari]

Ömer Sinan Ağacan <omeragacan at gmail.com> writes:

> Here's another improvement that fixes a very old issue in GHC's compacting GC
> [1].
>
> To summarize the problem: when untreading an object we update references to the
> object that we've seen so far to the object's new location. But to get the
> object's new location we need to know the object's size, because depending on
> the size we may need to move the object to a new block (when the current block
> does not have enough space for the object).
>
> For this we currently walk the thread twice, once to get the info table (used
> to get the size), then again to update references to the object. Ideally we
> want to do just one pass when unthreading.
>
> The solution is explained in The GC Handbook, section 3.4. Instead of using one
> bit to mark an object, we use two bits: one for the first word of the object,
> one for the last word. Using two bits is not a problem in GHC because heap
> objects are at least 2 words. For example, an object with two words is marked
> with `11`, 3 words is marked with `101` and so on.
>
> Now we can scan the bitmap to find object size, and unthread it without having
> to find the info table first.
>
Thanks Ömer! I have plopped all of these ideas into a ticket, #20328.
Hopefully someone will come along to implement.

Cheers,

- Ben

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 487 bytes
Desc: not available
URL: <http://mail.haskell.org/pipermail/ghc-devs/attachments/20210902/ffb737f4/attachment.sig>