> The vast majority of the traces are a waste of time, but GC can't know that

It can, it does, and you've basically described generational collection. Generational GCs try to only trace through recently allocated objects, and only bother with old ones if they can't free enough memory. Not wasting time on unnecessary traces is much of the point of generational GCs.

More modern GCs like OpenJDK's G1 go some steps further. They're region-based, and they keep track of inter-region pointers that tell them the likelihood that a region may benefit from compaction.

> A ref-counting approach will have two RMWs for every pointer assignment and the objects modified will almost certainly be in the cache.

A tracing GC does that without any bookkeeping. An object born and dead between young-gen collections will never even make its existence known to the GC (generational GCs usually only need to learn about an object's existence once it's promoted); it will never have been visited and traced. The old objects would not have been traced either (in that interim) if few enough young objects survive.

In fact, in such ideal situation where some fixed number of objects live forever and some large number of objects are continuously allocated and die, a generational GC will effectively need to do nothing: the old objects will have been promoted into the old generation, and the GC won't have to ever look at them again if there's always sufficient RAM, while the young objects will be allocated by a pointer bump, and when it reaches the end the GC will wake up and want to start tracing, but will find that all the roots still point into the old generation, so the young generation will simply disappear (i.e. the allocation pointer will be reset to the beginning). The GC in this case requires zero operations (well, except for some fixed number required to notice it has nothing to do).

> It's not clear that those RMWs will cost more than tracing that 100MB.

It's clear that they cost more than not tracing it, which is what a generational GC won't do.

> Note that the 1MB is probably in L3. If N is large enough to keep the number of traces down, the Nx1MB will cache-fault like crazy

That prompt reclamation has some benefits on locality is true, but so does compaction. The problem isn't so much cache faults (because we're talking about writes, which fill up the write buffer, not reads that cause stalls) but exhausting the memory buffer. This can and does happen with super-high allocation rates (which makes it an interesting problem), and indeed the memory bus's bandwidth is sometimes the limiting factor on throughput, but we're talking about allocation rates that far exceed those that common refcounting GCs can deal with anyway.

It's been well established by now that tracing GCs offer better performance than (crude) refcounting GCs, which is why they're the choice of every high-performance language that heavily relies on GC. The price you pay for modern tracing GCs is in memory footprint and in cost of implementation. There is, however, constant research in GC, and some advances in refcounting might make it more appealing, but we're talking about sophisticated implementations that are comparable in complexity to tracing.