Article

Free access

Generational reference counting: a reduced-communication distributed storage reclamation scheme

Author:

B. GoldbergAuthors Info & Claims

PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

Pages 313 - 321

https://doi.org/10.1145/73141.74846

Published: 21 June 1989 Publication History

Abstract

This paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. It has a significantly lower communication overhead than distributed versions of conventional reference counting. Although generational reference counting has greater computational and space requirements than ordinary reference counting, it may provide a significant saving in overall execution time on machines in which message passing is expensive.

The communication overhead for generational reference counting is one message for each copy of an interprocessor reference (pointer). Unlike conventional reference counting, when a reference to an object is copied no message is sent to the processor on which the object lies. A message is sent only when a reference is discarded. Unfortunately, generational reference counting shares conventional reference counting's inability to reclaim cyclical structures.

In this paper, we present the generational reference counting algorithm, prove it correct, and discuss some refinements that make it more efficient. We also compare it with weighted reference counting, another distributed reference counting scheme described in the literature.

References

[1]

H.G. Baker, Jr. List processing in real time on a serial computer. CA CM, 21(4):280-294, April 1978.

Digital Library

[2]

M. Ben-Art. Algorithms for on-the-fly garbage collection. Trans. on Prog. Lang. and Sys., 6(3):333-344, July 1974.

Digital Library

[3]

D.I. Bevan. Distributed garbage collection using reference counting. In PARLE Parallel Architectures and Languages Europe, pages 176-187, Springer-Verlag LNCS 259, June 1987.

[4]

D.R. Brownbridge. Cyclic reference counting for combinator machines. In Functional Programming Languages and Computer A rchilectur~, pages 273-288, Springer-Verlag LNCS 201, September 1985.

[5]

J. Cohen. Garbage collection of linked data structures. Computing Surveys, 13(3):341-367, September 1981.

Digital Library

[6]

A. Deb. Parallel garbage collection for graph machines. In Proceedings of the Santa Fe Workshop on Graph Reduction, pages 252-264, Springer- Verlag LNCS 279, September 1986.

Digital Library

[7]

L.P. Deutsch and D.G. Bobrow. An efficient incremental automatic garbage collector. CACM, 19(9):522-526, September 1976.

Digital Library

[8]

E.W. Dijkstra, L. Lamport, A.J. Martin, and E.M.F. Steffens. On-the-fly garbage collection: an exercise in cooperation. Commun. A CM, 21(11):966-975, November 1978.

Digital Library

[9]

D.P. Friedman and D.S. Wise. Reference counting can manage the circular environments of mutual recursion, inf Process. Left., 8(1):921-930, January 1979.

[10]

P. Hudak. Call-graph reclamation: an alternative storage reclamation scheme. AMPS Technical Memorandum 4, Dept. of Computer Science, University of Utah, August 1981.

[11]

P. Hudak. Object and Task Reclamation in Distributed Applicative Processing Systems. PhD thesis, University of Utah, July 1982.

Digital Library

[12]

P. Hudak and R.M. Keller. Garbage collection and task deletion in distributed applicative processing systems. In Proc. 1982 A CM Conf. on LISP and Functional Prog., pages 168-178, ACM, August 1982.

Digital Library

[13]

J. Hughes. A distributed garbage collection algorithm. In Functional Programming Languages and Computer Architecture, pages 256- 272, Springer-Verlag LNCS 201, September 1985.

[14]

R.J.M. Hughes. Backward Analysis of Functional Programs. Technical Report, Glasgow University, 1988.

[15]

D. Kranz, R. Kelsey, J. Rees, P. ttudak, J. Philbin, and N. Adams. Orbit: an optimizing compiler for Scheme. In $IGPLAN '86 Symposium on Compiler Construction, pages 219-233, ACM, June 1986. Published as SIGPLAN Notices Vol. 21, N o. 7, July 1986.

Digital Library

[16]

Claus-Werner Lermen and Dieter Maurer. A protocol for distributed reference counting. In Proc. 1986 A CM Conference on Lisp and Functional Programming, pages 343-350, ACM SIGPLAN/SIGACT/SIGART, Cambridge, Massachusetts, August 1986.

Digital Library

[17]

Paul Watson and Ian Watson. An effieient garbage collection scheme for parallel computer architectures. In PARLE Parallel Architectures and Languages Europe, pages 432-443, Springer- Verlag LNCS 259, June 1987.

[18]

K-S. Weng. An Abstract Implementation for a Generalized Daiafiow Language. MIT/LCS/TR 228, Massachusetts Institute of Technology, Laboratory for Computer Science, 1979.

Digital Library

Cited By

Mitake HYamada HNakajima TCui HLau FBansal SZhong L(2016)Analyzing The Tradeoff Between Throughput and Latency in Multicore Scalable In-Memory Database SystemsProceedings of the 7th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/2967360.2967361(1-9)Online publication date: 4-Aug-2016
https://dl.acm.org/doi/10.1145/2967360.2967361
Lee H(2010)Fast local-spin abortable mutual exclusion with bounded spaceProceedings of the 14th international conference on Principles of distributed systems10.5555/1940234.1940271(364-379)Online publication date: 14-Dec-2010
https://dl.acm.org/doi/10.5555/1940234.1940271
Lee H(2010)Fast Local-Spin Abortable Mutual Exclusion with Bounded SpacePrinciples of Distributed Systems10.1007/978-3-642-17653-1_27(364-379)Online publication date: 2010
https://doi.org/10.1007/978-3-642-17653-1_27
Show More Cited By

Index Terms

Generational reference counting: a reduced-communication distributed storage reclamation scheme
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Allocation / deallocation strategies
    2. Software functional properties
      1. Correctness
2. Theory of computation
  1. Logic
    1. Proof theory

Recommendations

Generational reference counting: a reduced-communication distributed storage reclamation scheme
Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniques

This paper describes generational reference counting, a new distributed storage reclamation scheme for loosely-coupled multiprocessors. It has a significantly lower communication overhead than distributed versions of conventional reference counting. ...
Ulterior reference counting: fast garbage collection without a long wait
OOPSLA '03: Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications

General purpose garbage collectors have yet to combine short pause times with high throughput. For example, generational collectors can achieve high throughput. They have modest average pause times, but occasionally collect the whole heap and ...
Ulterior reference counting: fast garbage collection without a long wait
Special Issue: Proceedings of the OOPSLA '03 conference

General purpose garbage collectors have yet to combine short pause times with high throughput. For example, generational collectors can achieve high throughput. They have modest average pause times, but occasionally collect the whole heap and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '89: Proceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation

June 1989

355 pages

ISBN:089791306X

DOI:10.1145/73141

Editor:
R. L. Wexelblat
ACM Headquarters, New York, NY

ACM SIGPLAN Notices Volume 24, Issue 7
Proceedings of the SIGPLAN '89 symposium on Interpreters and interpretive techniques
July 1989
355 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/74818
Editor:
Richard Wexelblat
Issue’s Table of Contents

Copyright © 1989 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI89

Sponsor:

SIGPLAN

PLDI89: Programming Language Design & Implementation

June 19 - 23, 1989

Oregon, Portland, USA

Acceptance Rates

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
465
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)9

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mitake HYamada HNakajima TCui HLau FBansal SZhong L(2016)Analyzing The Tradeoff Between Throughput and Latency in Multicore Scalable In-Memory Database SystemsProceedings of the 7th ACM SIGOPS Asia-Pacific Workshop on Systems10.1145/2967360.2967361(1-9)Online publication date: 4-Aug-2016
https://dl.acm.org/doi/10.1145/2967360.2967361
Lee H(2010)Fast local-spin abortable mutual exclusion with bounded spaceProceedings of the 14th international conference on Principles of distributed systems10.5555/1940234.1940271(364-379)Online publication date: 14-Dec-2010
https://dl.acm.org/doi/10.5555/1940234.1940271
Lee H(2010)Fast Local-Spin Abortable Mutual Exclusion with Bounded SpacePrinciples of Distributed Systems10.1007/978-3-642-17653-1_27(364-379)Online publication date: 2010
https://doi.org/10.1007/978-3-642-17653-1_27
Piquer J(2005)Indirect reference counting: A distributed garbage collection algorithmPARLE '91 Parallel Architectures and Languages Europe10.1007/BFb0035102(150-165)Online publication date: 23-Jun-2005
https://doi.org/10.1007/BFb0035102
Rodrigues HJones R(2005)A cyclic distributed garbage collector for network objectsDistributed Algorithms10.1007/3-540-61769-8_9(123-140)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-61769-8_9
Dehne FLins R(2005)Distributed cyclic reference countingParallel and Distributed Computing Theory and Practice10.1007/3-540-58078-6_9(95-100)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-58078-6_9
Lins R(2002)Efficient cyclic weighted reference counting14th Symposium on Computer Architecture and High Performance Computing, 2002. Proceedings.10.1109/CAHPC.2002.1180760(61-67)Online publication date: 2002
https://doi.org/10.1109/CAHPC.2002.1180760
Klintskog ENeiderud ABrand PHaridi S(2001)Fractional Weighted Reference CountingEuro-Par 2001 Parallel Processing10.1007/3-540-44681-8_71(486-490)Online publication date: 17-Aug-2001
https://doi.org/10.1007/3-540-44681-8_71
Moreau L(1998)Hierarchical distributed reference countingACM SIGPLAN Notices10.1145/301589.28686734:3(57-67)Online publication date: 1-Oct-1998
https://dl.acm.org/doi/10.1145/301589.286867
Moreau L(1998)A distributed garbage collector with diffusion tree reorganisation and mobile objectsACM SIGPLAN Notices10.1145/291251.28944334:1(204-215)Online publication date: 29-Sep-1998
https://dl.acm.org/doi/10.1145/291251.289443
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents