Parallel remembered-set processing respecting popular-object detection
View Patent ↗A garbage collector that operates in multiple threads divides a generation of a garbage-collected heap into heap sections, with which it associates respective remembered sets of locations where references to objects in those heap sections have been found. When such a heap section comes up for collection, each of a plurality of parallel garbage-collector threads that is processing its remembered set maintains a separate “popularity”—indicating count map, which includes an entry for each of a set of segments into which the collector has divided that heap section. The thread increments an entry in its count map each time it finds a reference to an object in the associated segment. If an object is located in a segment for which the associated count-map entry has exceeded a threshold, the thread evacuates the object in a manner different from that in which it evacuates objects not thus been found to be popular.
1. A computer implemented method for performing garbage collection in a multithreaded environment, comprising:
obtaining a collection set of objects in a computer system, wherein the collection set is associated with a collector interval of a collection cycle;
partitioning the collection set of objects into a plurality of sections, wherein a section of the plurality of sections corresponds to memory of the computer system and is associated with a remembered set;
partitioning the section into a plurality of segments, wherein a first segment of the plurality of segments corresponds to a portion of the memory of the computer system;
obtaining a first count-map for the section, wherein the first count-map is associated with a first thread executing on a processor of the computer system, and wherein a first entry in the first count-map is associated with the first segment of the plurality of segments;
identifying a first plurality of references to objects in the first segment using the remembered set;
incrementing the first entry based on a size of the first plurality of references;
comparing the first entry with a popular-object threshold to generate a first comparison; and
evacuating a first object from the first segment based on the first comparison to reclaim the portion of the memory of the computer system for reuse.
2. The computer implemented method of claim 1 , further comprising:
obtaining a second count-map for the section, wherein the second count-map is associated with a second thread, and wherein a second entry in the second count-map is associated with the first segment;
identifying a second plurality of referenced to objects in the first segment using the remembered set;
incrementing the second entry based on a size of the second plurality of references;
incrementing the first entry based on the second entry before comparing the first entry with the popular-object threshold.
3. The computer implemented method of claim 1 , further comprising:
obtaining a second count-map for the section, wherein the second count-map is associated with a second thread, and wherein a second entry in the second count-map is associated with a second segment of the plurality of segments;
identifying a second plurality of references to objects in the second segment using the remembered set;
incrementing the second entry based on a size of the second plurality of references;
comparing the second entry with the popular-object threshold to generate a second comparison; and
evacuating a second object from the second segment based on the second comparison to reclaim memory of the computer system for reuse.
4. The computer implemented method of claim 1 , wherein evacuating the first object comprises:
adding a new section to the plurality of sections; and
placing the first object in the new section, wherein the new section is exclusively occupied by the first object.
5. The computer implemented method of claim 3 , wherein evacuating the second object comprises:
adding a new section to the plurality of sections; and
placing the second object in the new section, wherein the new section is exclusively occupied by the second object.
6. The computer implemented method of claim 1 , wherein the popular-object threshold is an individual-map threshold.
7. The computer implemented method of claim 2 , wherein the popular-object threshold is a multiple-map threshold.
8. The computer implemented method of claim 1 , wherein at least one of the plurality of segments is smaller than a minimum object size.
9. A computer readable medium storing instructions for performing garbage collection in a multithreaded environment, the instructions comprising functionality to:
obtain a collection set of objects in a computer system, wherein the collection set is associated with a collector interval of a collection cycle;
partition the collection set of objects into a plurality of sections, wherein a section of the plurality of sections is associated with a remembered set;
partition the section into a plurality of segments;
obtain a first count-map for the section, wherein the first count-map is associated with a first thread, and wherein a first entry in the first count-map is associated with a first segment of the plurality of segments;
identify a first plurality of references to objects in the first segment using the remembered set;
increment the first entry based on a size of the first plurality of references;
compare the first entry with a popular-object threshold to generate a first comparison; and
evacuate a first object from the first segment based on the first comparison to reclaim memory of the computer system for reuse.
10. The computer readable medium of claim 9 , the instructions further comprising functionality to:
obtain a second count-map for the section, wherein the second count-map is associated with a second thread, and wherein a second entry in the second count-map is associated with the first segment;
identify a second plurality of referenced to objects in the first segment using the remembered set;
increment the second entry based on a size of the second plurality of references;
increment the first entry based on the second entry before comparing the first entry with the popular-object threshold.
11. The computer readable medium of claim 9 , the instructions further comprising functionality to:
obtain a second count-map for the section, wherein the second count-map is associated with a second thread, and wherein a second entry in the second count-map is associated with a second segment of the plurality of segments;
identify a second plurality of references to objects in the second segment using the remembered set;
increment the second entry based on a size of the second plurality of references;
compare the second entry with the popular-object threshold to generate a second comparison; and
evacuate a second object from the second segment based on the second comparison to reclaim memory of the computer system for reuse.
12. The computer readable medium of claim 9 , wherein the instructions for evacuating the first object comprise functionality to:
add a new section to the plurality of sections; and
place the first object in the new section, wherein the new section is exclusively occupied by the first object.
13. The computer readable medium of claim 11 , wherein the instructions for evacuating the second object comprise functionality to:
add a new section to the plurality of sections; and
place the second object in the new section, wherein the new section is exclusively occupied by the second object.
14. The computer readable medium of claim 9 , wherein the popular-object threshold is an individual-map threshold.
15. The computer readable medium of claim 9 , wherein the popular-object threshold is a multiple-map threshold.
16. The computer readable medium of claim 9 , wherein at least one of the plurality of segments is smaller than a minimum object size.
17. An apparatus for performing garbage collection in a multithreaded environment, comprising:
a first means for obtaining a collection set of objects in a computer system, wherein the collection set is associated with a collector interval of a collection cycle;
a second means for partitioning the collection set of objects into a plurality of sections, wherein a section of the plurality of sections is associated with a remembered set;
a third means for partitioning the section into a plurality of segments;
a fourth means for obtaining a count-map for the section, wherein the count-map is associated with a thread, and wherein an entry in the count-map is associated with a segment of the plurality of segments;
a fifth means for identifying a plurality of references to objects in the segment using the remembered set;
a sixth means for incrementing the entry based on a size of the plurality of references;
a seventh means for comparing the entry with a popular-object threshold to generate a comparison; and
an eighth means for evacuating an object from the segment based on the comparison to reclaim memory of the computer system for reuse;
wherein a portion of at least one selected from a group consisting of the first means, the second means, the third means, the fourth means, the fifth means, the sixth means, the seventh means, and the eighth means comprises a hardware processor.