Are you sure about this? The main overhead of a mark-and-sweep GC isn't the marking phase, it's the sweeping phase - you need to find and free all dead objects (to mark them as free/add them to the free list), and since you don't know where they are (by definition, since they are dead, they have no references pointing at them) you have to scan the whole heap (or at least all the pages that were objects were allocated/live on since the last GC cycle).