Ömer Sinan Ağacan
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