A lightweight cyclic reference counting algorithm

Chin Yang Lin, Ting-Wei Hou

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

7 Citations (Scopus)

Abstract

This paper focuses on a major weakness of reference counting technique - the lack of collecting cyclic garbage. Most reference counted systems handle this problem by either invoking a global mark-sweep collector occasionally, or incorporating a local ("partial") tracing collector that considers only the cycle candidates (objects) but needs several traces on them. This paper proposes a "lightweight" cycle detector, which is based on the partial tracing approach but collects garbage cycles in a simpler and more efficient way. Key to the algorithm is the removal of multiple traces on the cycle candidates - It effectively reclaims garbage cycles in only one trace. We have evaluated the algorithm in the Jikes Research Virtual Machine, where a set of benchmark programs from SPECjvm98 were applied. The experiments demonstrate the efficiency and practicability of the lightweight cycle detector, compared to a modern cycle detector that requires multiple traces on objects.

Original languageEnglish
Title of host publicationAdvances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings
PublisherSpringer Verlag
Pages346-359
Number of pages14
ISBN (Print)3540338098, 9783540338093
DOIs
Publication statusPublished - 2006 Jan 1
Event1st International Conference on Grid and Pervasive Computing,GPC 2006 - Taichung, Taiwan
Duration: 2006 May 32006 May 5

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3947 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other1st International Conference on Grid and Pervasive Computing,GPC 2006
CountryTaiwan
CityTaichung
Period06-05-0306-05-05

Fingerprint

Counting
Detectors
Cycle
Trace
Detector
Tracing
Partial
Virtual Machine
Sweep
Experiments
Benchmark
Demonstrate
Experiment
Virtual machine

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Lin, C. Y., & Hou, T-W. (2006). A lightweight cyclic reference counting algorithm. In Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings (pp. 346-359). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3947 LNCS). Springer Verlag. https://doi.org/10.1007/11745693_35
Lin, Chin Yang ; Hou, Ting-Wei. / A lightweight cyclic reference counting algorithm. Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings. Springer Verlag, 2006. pp. 346-359 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{a92c8c19cc9e4fec898c9c4f441016af,
title = "A lightweight cyclic reference counting algorithm",
abstract = "This paper focuses on a major weakness of reference counting technique - the lack of collecting cyclic garbage. Most reference counted systems handle this problem by either invoking a global mark-sweep collector occasionally, or incorporating a local ({"}partial{"}) tracing collector that considers only the cycle candidates (objects) but needs several traces on them. This paper proposes a {"}lightweight{"} cycle detector, which is based on the partial tracing approach but collects garbage cycles in a simpler and more efficient way. Key to the algorithm is the removal of multiple traces on the cycle candidates - It effectively reclaims garbage cycles in only one trace. We have evaluated the algorithm in the Jikes Research Virtual Machine, where a set of benchmark programs from SPECjvm98 were applied. The experiments demonstrate the efficiency and practicability of the lightweight cycle detector, compared to a modern cycle detector that requires multiple traces on objects.",
author = "Lin, {Chin Yang} and Ting-Wei Hou",
year = "2006",
month = "1",
day = "1",
doi = "10.1007/11745693_35",
language = "English",
isbn = "3540338098",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "346--359",
booktitle = "Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings",
address = "Germany",

}

Lin, CY & Hou, T-W 2006, A lightweight cyclic reference counting algorithm. in Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 3947 LNCS, Springer Verlag, pp. 346-359, 1st International Conference on Grid and Pervasive Computing,GPC 2006, Taichung, Taiwan, 06-05-03. https://doi.org/10.1007/11745693_35

A lightweight cyclic reference counting algorithm. / Lin, Chin Yang; Hou, Ting-Wei.

Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings. Springer Verlag, 2006. p. 346-359 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3947 LNCS).

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

TY - GEN

T1 - A lightweight cyclic reference counting algorithm

AU - Lin, Chin Yang

AU - Hou, Ting-Wei

PY - 2006/1/1

Y1 - 2006/1/1

N2 - This paper focuses on a major weakness of reference counting technique - the lack of collecting cyclic garbage. Most reference counted systems handle this problem by either invoking a global mark-sweep collector occasionally, or incorporating a local ("partial") tracing collector that considers only the cycle candidates (objects) but needs several traces on them. This paper proposes a "lightweight" cycle detector, which is based on the partial tracing approach but collects garbage cycles in a simpler and more efficient way. Key to the algorithm is the removal of multiple traces on the cycle candidates - It effectively reclaims garbage cycles in only one trace. We have evaluated the algorithm in the Jikes Research Virtual Machine, where a set of benchmark programs from SPECjvm98 were applied. The experiments demonstrate the efficiency and practicability of the lightweight cycle detector, compared to a modern cycle detector that requires multiple traces on objects.

AB - This paper focuses on a major weakness of reference counting technique - the lack of collecting cyclic garbage. Most reference counted systems handle this problem by either invoking a global mark-sweep collector occasionally, or incorporating a local ("partial") tracing collector that considers only the cycle candidates (objects) but needs several traces on them. This paper proposes a "lightweight" cycle detector, which is based on the partial tracing approach but collects garbage cycles in a simpler and more efficient way. Key to the algorithm is the removal of multiple traces on the cycle candidates - It effectively reclaims garbage cycles in only one trace. We have evaluated the algorithm in the Jikes Research Virtual Machine, where a set of benchmark programs from SPECjvm98 were applied. The experiments demonstrate the efficiency and practicability of the lightweight cycle detector, compared to a modern cycle detector that requires multiple traces on objects.

UR - http://www.scopus.com/inward/record.url?scp=33745867947&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33745867947&partnerID=8YFLogxK

U2 - 10.1007/11745693_35

DO - 10.1007/11745693_35

M3 - Conference contribution

AN - SCOPUS:33745867947

SN - 3540338098

SN - 9783540338093

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 346

EP - 359

BT - Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings

PB - Springer Verlag

ER -

Lin CY, Hou T-W. A lightweight cyclic reference counting algorithm. In Advances in Grid and Pervasive Computing - First International Conference, GPC 2006, Proceedings. Springer Verlag. 2006. p. 346-359. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/11745693_35