> traversal is proportional to the number of pointers (rooted or dangling) in the heap and stack at the time of running.

That's not quite how it works. Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking).

I do agree there are tradeoffs, but they're much more nuanced than that. There is certainly a footprint tradeoff, and there is a latency tradeoff (that can be mitigated).

> Traversal is proportional to the number of pointers changed since the last collection (HotSpot's GCs do card marking).

True. I was just trying to make the point that GC comes with complexity cost, and this should be considered—it's not "free" for an arbitrary algorithm.

A card in the card table covers more than one object, so the entire dirty card needs to be scanned. Card marks only help with old->young references, and stack based roots still need to be visited each time, irrespective of what happened in the last collection.

Except card marking (this region of the heap was changed) is only one way of flagging changes. It's entire possible to instead record the address of objects unconditionally and then flag them as they are visiting during a generation.

You could but it's likely to perform worse for common case. Where are you going to record the addresses? How are you going to size that buffer? Card table is fixed size, and doesn't care whether you're using compressed pointers or full blown word sized ones. Cards also benefit from cache locality if recording objects in the same card. Marking a card clean is dirt cheap, and incremental cleaning is cheaper than removing entries individually from an exact buffer.

The downside to card marking is the impreciseness but with java being very reference heavy, I don't know how much that is a problem. Secondary problem is false sharing of memory when multiple mutators write in there; Hotspot, e.g. has a special flag to enable conditional marking, but it's not on by default.

That's why I said proportional.