The Collie: a wait-free compacting collector

Abstract

We describe the Collie collector, a fully concurrent compacting collector that uses transactional memory techniques to achieve wait-free compaction. The collector uses compaction as the primary means of reclaiming unused memory, and performs "individual object transplantations" as transactions. We introduce new terms and requirements useful for analyzing concurrent relocating collectors, including definitions of referrer sets, object transplantation and the notion of individually transplantable objects. The Collie collector builds on these terms and on a detailed analysis of an object's legal states during compaction.