Fast garbage collection without a long wait

Abstract

General purpose garbage collectors have yet to combine short pause times with fast throughput. Collectors such as reference counting attain short pause times with significant performance penalties. Pure and hybrid generational collectors can achieve high throughput and have modest average pause times, but occasionally collect the whole heap and consequently incur long pauses. This paper introduces RC-hybrid, which combines copying nursery collection and reference counting the older generation to achieve both goals. Key to our algorithm is a generalization of deferred reference counting which allows RC-hybrid to safely ignore mutations to nursery objects. RC-hybrid thus restricts copying and reference counting to the objects for which they perform well. Copying collectors’ bump pointer allocation is extremely fast, and collection time is proportional to the live objects whose survival rates are low and bounded in a fixed size nursery. Reference counting time is proportional to object mutations and the number of dead objects, both of which are typically low for older objects. We further bound time spent reference counting with collection triggers and buffering. We compare RC-hybrid with pure reference counting, a stateof-the-art copying and mark-sweep hybrid, and a number of other collectors. We show that RC-hybrid combines fast throughput, and low average and maximum pause times. Show more