I'm put to mind of Mike Pall's design (tragically unwritten) for a quad-color GC for LuaJIT: http://wiki.luajit.org/New-Garbage-Collector#gc-algorithms_q...

I'm just hearing of the Treadmill for the first time, so I can't compare the design in detail yet, but the two pictures tell a lot of that story.