Biased reference counting: Minimizing atomic operations in garbage collection

Jiho Choi, Thomas Shull, Josep Torrellas

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Reference counting (RC) is one of the two fundamental approaches to garbage collection. It has the desirable characteristics of low memory overhead and short pause times, which are key in today's interactive mobile platforms. However, RC has a higher execution time overhead than its counterpart, tracing garbage collection. The reason is that RC implementations maintain per-object counters, which must be continually updated. In particular, the execution time overhead is high in environments where low memory overhead is critical and, therefore, non-deferred RC is used. This is because the counter updates need to be performed atomically. To address this problem, this paper proposes a novel algorithm called Biased Reference Counting (BRC), which significantly improves the performance of non-deferred RC. BRC is based on the observation that most objects are only accessed by a single thread, which allows most RC operations to be performed non-atomically. BRC leverages this by biasing each object towards a specific thread, and keeping two counters for each object - one updated by the owner thread and another updated by the other threads. This allows the owner thread to perform RC operations non-atomically, while the other threads update the second counter atomically. We implement BRC in the Swift programming language runtime, and evaluate it with client and server programs. We find that BRC makes each RC operation more than twice faster in the common case. As a result, BRC reduces the average execution time of client programs by 22.5%, and boosts the average throughput of server programs by 7.3%.

Original languageEnglish (US)
Title of host publicationProceedings - 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781450359863
DOIs
StatePublished - Nov 1 2018
Event27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018 - Limassol, Cyprus
Duration: Nov 1 2018Nov 4 2018

Publication series

NameParallel Architectures and Compilation Techniques - Conference Proceedings, PACT
ISSN (Print)1089-795X

Conference

Conference27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018
Country/TerritoryCyprus
CityLimassol
Period11/1/1811/4/18

Keywords

  • Garbage collection
  • Reference counting
  • Swift

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture

Fingerprint

Dive into the research topics of 'Biased reference counting: Minimizing atomic operations in garbage collection'. Together they form a unique fingerprint.

Cite this