Gosh, I hate to be that "old guy," but using bitmaps for mark & sweep GC dates from the early 70's.
In particular, in GC implementations for Lisp and Lisp-like languages (such as the ECL implementation we used at Harvard in the mid-70's) where CONS cells were two eighteen-bit halfwords (CAR and CDR) fitting in a 36-bit word, there was no place for mark bits, so you'd use a bitmap instead (as rediscovered here).
And we used the same technique for finding the page headers (e.g., containing the mark bitmaps) for each part of the heap, aligning to a larger power of two so you could chop any pointer down by and'ing off the lower bits to get to the page header.
There really ain't much new under the sun. Too bad every generation has to rediscover all this stuff.
Indeed - information about good garbage collectors is readily available. Paul R. Wilson's "Uniprocessor Garbage Collection Techniques" (http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2...) is an excellent survey, and Jones, Hosking, and Moss's _The Garbage Collection Handbook_ is an excellent reference. (The previous book by Jones and Lins is also great, but the new one adds important material on concurrent GCs, real-time GC, and interactions between the GC and runtime systems.)
As an exercise, I wrote a simple standalone mark-bit-page & lazy sweeping garbage collector for C. (https://github.com/silentbicycle/oscar) Marking occurs in a user-provided callback, since I don't assume any particular data structure. It's only ~300 LOC.
> Too bad every generation has to rediscover all this stuff.
Even though this technique existed 30 years ago, doesn't mean that it's been recently "rediscovered" by the Ruby folks and excitedly implemented to the musings of, "how did we miss this technique?!?" There are likely lots of reasons why this wasn't used before. The abstract of their paper seems to shed some light on this:
[...]But Ruby interpreter runs on various platforms, and we do not have portable
memory allocation API to obtain aligned memory region without wasting region. In this paper, we propose portable scheme to map from object pointers to corresponding bitmap table
in constant time.[...]
I may be totally wrong, and the paper is entirely in Japanese, but I think there is more to it.
Ruby has been around since 1995. That's over 15 years.
Implementing bitmaps for mark-and-sweep a project well within the skills of a final year undergrad, or first year graduate student of CS.
You can say many things, but I doubt they didn't implement this because they didn't have time, or didn't have the skills to do so. They merely prioritized against it from day-one.
In particular, in GC implementations for Lisp and Lisp-like languages (such as the ECL implementation we used at Harvard in the mid-70's) where CONS cells were two eighteen-bit halfwords (CAR and CDR) fitting in a 36-bit word, there was no place for mark bits, so you'd use a bitmap instead (as rediscovered here).
And we used the same technique for finding the page headers (e.g., containing the mark bitmaps) for each part of the heap, aligning to a larger power of two so you could chop any pointer down by and'ing off the lower bits to get to the page header.
There really ain't much new under the sun. Too bad every generation has to rediscover all this stuff.