> then changes one bit on every page in the entire virtual space

Yeah that sucks. Naively implemented garbage collectors have the same problem: they put the live and mark bits in the object itself which spreads those bits all over the address space. This leads to the garbage collector touching every single page when it scans and writes all of those bits.

The proper solution is to allocate separate bitmap pages. This dramatically improves cache efficiency. Machines always want a structure of arrays.