[jwatte]

I'm not sure I agree work based allocators are out. Specifically, if you follow/mark N references for each M words allocated, you can guarantee to not fall behind and still have a strict upper bound on collection cost/run-time jitter. This adds a linear-in-size cost to memory allocation, which already typically has an amortized linear cost (because you touch all memory allocated) so it's analytically very well behaved.