A garbage collector collects a generation of a collected heap in accordance with the train algorithm. It employs remembered sets associated with respective car sections to keep track of references into the associated car sections. Each remembered set contains entries that identify respective regions in the generation that contain references into the associated car section. In some collection cycles, the collector collects a collection set of more than one car section. When it does, it processes the remembered-set entries by searching the regions specified thereby not only for references into the associated car sections but also for references into other car sections in the collection set. The collector further treats the generation as divided into segments, for each of which it maintains a Boolean value that indicates whether the segment has been searched during the current collection cycle. If it has, the collector does not search it in response to a subsequently encountered remembered-set entry that identifies a region in which that segment is included.