TY - GEN
T1 - Biased reference counting
T2 - 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018
AU - Choi, Jiho
AU - Shull, Thomas
AU - Torrellas, Josep
N1 - Publisher Copyright:
© 2018 Association for Computing Machinery.
PY - 2018/11/1
Y1 - 2018/11/1
N2 - 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%.
AB - 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%.
KW - Garbage collection
KW - Reference counting
KW - Swift
UR - http://www.scopus.com/inward/record.url?scp=85061538574&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85061538574&partnerID=8YFLogxK
U2 - 10.1145/3243176.3243195
DO - 10.1145/3243176.3243195
M3 - Conference contribution
AN - SCOPUS:85061538574
T3 - Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT
BT - Proceedings - 27th International Conference on Parallel Architectures and Compilation Techniques, PACT 2018
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 1 November 2018 through 4 November 2018
ER -