A garbage collector that reclaims memory space no longer needed by a mutator treats a generation of a dynamically allocated heap as being divided into "car" sections. For each car section, the collector maintains a remembered-set structure in which it keeps a record of the locations in the generation where the collector has previously found references to locations in that car section. The collector operates in increments in each of which it collects a respective collection set consisting of one or more of the generation's car sections. From the remembered sets associated with a collection set's car sections, it generates scratch-pad lists whose entries tell where locations identified by those remembered sets still contain references to collection-set locations. In situations in which the remembered sets are particularly large, the collector divides the operation of generating the scratch-pad lists into a plurality of collection intervals separated by mutator intervals. The collector bases its identification of reachable collection-set objects on the scratch-pad-list entries. By dividing the scratch-pad-list generation into multiple collection intervals, the collector can keep pause times low while employing relatively large collection sets.