I am looking for papers on the use of reference counts for
garbage collection.
I have Spector's paper (1982) in which he shows how the concept of
defining reference can be used to manage the deallocation of reentrant objects
too.
The only other similar reference I have found is a paper by
J. Dana Eckart.
Any other recent papers ?
Aloke Gupta
CSL Univ of Ill at Urbana-Champaign
Ref: - J.D. Eckart and R.J. LeBlanc, "Distributed Garbage Collection in
distributed systems", Procedings of the SIGPLAN '87 Symposium on
Interpretors and Interpretive Techniques , June 1987
- David Spector, "Minimal Overhead Garbae Collection of Complex List
Structures", ACM SIGPLAN Notices,vol. 17, No.3, pp. 80-82, March 1982
From: David Chase
Subject: Re: Reference Counts
Date:
Message-ID: <468@acornrc.UUCP>
>
> I am looking for papers on the use of reference counts for
> garbage collection.
The conventional wisdom doesn't have a lot to say for reference counting;
fortunately, I have some unconventional references. These are in a format
suitable for use with BibTeX if you put them in the appropriate wrappers.
(for example, ·@article{Collins:MOEL, ... }")
(The original reference)
AUTHOR = "G. E. Collins",
TITLE = "A Method for Overlapping and Erasure of Lists",
JOURNAL = cacm,
YEAR = 1960, VOLUME = 3, NUMBER = 12, PAGES = {655--657}
(A fun paper, good results)
AUTHOR = "W. R. Stoye and T. J. W. Clarke and A. C. Norman",
TITLE = "Some Practical Methods for Rapid Combinator Reduction",
BOOKTITLE = "{SIGPLAN} Symposium on {LISP} and Functional Programming",
YEAR = 1984, PAGES = {159--166}
(Three papers on reclamation of circular structures)
TITLE = "Managing Reentrant Structures Using Reference Counts",
AUTHOR = "Daniel G. Bobrow",
JOURNAL = toplas,
VOLUME = 2, NUMBER = 3, MONTH = jul, YEAR = 1980, PAGES = {269--273}
AUTHOR = "D. P. Friedman and D.S. Wise",
TITLE = "Reference Counting Can Manage the Circular Invironments[sic]
of Mutual Recursion",
JOURNAL = "Information Processing Letters",
YEAR = 1979, VOLUME = 8, NUMBER = 1, PAGES = {41--44}
AUTHOR = "D. R. Brownbridge",
TITLE = "Cyclic Reference Counting for Combinator Machines",
BOOKTITLE = "Functional Programming Languages and Computer Architecture",
YEAR = 1985, PAGES = {273--288}
(Springer-Verlag Lecture Notes in Computer Science #201)
(this book contains several other interesting articles; give it a browse)
(compaction and r. c.)
AUTHOR="David S. Wise",
TITLE="Morris's Garbage Compaction Algorithm Restores Reference Counts",
JOURNAL=toplas,
VOLUME=1, NUMBER=1, MONTH=jul, YEAR=1979, PAGES={115--120}
(the InterLisp collector and the Cedar Mesa collector and a related paper)
AUTHOR = "L. Peter Deutsch and Daniel G. Bobrow",
TITLE = "An Efficient, Incremental, Automatic Garbage Collector",
JOURNAL = cacm,
VOLUME = 19, NUMBER = 9, YEAR = 1976, MONTH = sep, PAGES = {522--526}
AUTHOR = "Paul Rovner",
TITLE = "On Adding Garbage Collection and Runtime Types to a Strongly-Typed,
Statically Checked, Concurrent Language",
INSTITUTION = PARC, YEAR = 1985, NUMBER = "CSL-84-7"
AUTHOR = "Jeffrey M. Barth",
TITLE = "Shifting Garbage Collection Overhead to Compile Time",
JOURNAL = cacm,
VOLUME = 20, NUMBER = 7, YEAR = 1977, MONTH = jul, PAGES = {513--518}
I also recommend the following papers describing behavior of "typical"
programs and allocation strategies, and the results of some "tricks".
These behaviors, of course, depend somewhat on the language, implementation,
and benchmarks chosen.
AUTHOR = "A. P. Batson and R. E. Brundage",
TITLE = "Segment Sizes and Lifetimes in {ALGOL} 60 Programs",
JOURNAL = cacm,
VOLUME = 20, NUMBER = 1, YEAR = 1977, MONTH = jan, PAGES = {36--44}
AUTHOR = "D. W. Clark and C. C. Green",
TITLE = "An Empirical Study of List Structure in {LISP}",
JOURNAL = cacm,
VOLUME = 20, NUMBER = 2, YEAR = 1977, MONTH = feb, PAGES = {78--87},
AUTHOR = "Douglas W. Clark",
TITLE = "Measurements of Dynamic List Structure Use in {L}isp",
JOURNAL = ieeese,
VOLUME = 5, NUMBER = 1, MONTH = jan, YEAR = 1979, PAGES = {51--59}
TITLE = "Compact Encodings of List Structure",
AUTHOR = "Daniel G. Bobrow and Douglas W. Clark",
JOURNAL = toplas,
VOLUME = 1, NUMBER = 2, MONTH = oct, YEAR = 1979, PAGES = {266--286}
AUTHOR = "Norman R. Nielsen",
TITLE = "Dynamic Memory Allocation in Computer Simulation",
JOURNAL = cacm,
YEAR = 1977, VOLUME = 20, NUMBER = 11, MONTH = nov, PAGES = {864--873}
I also have an ever-growing list of references for copying-compacting garbage
collectors.
> Aloke Gupta
> CSL Univ of Ill at Urbana-Champaign
David Chase
Olivetti Research Center, Palo Alto
In article <·······@uicsgva> ·····@uicsgva.UUCP writes:
>
> I am looking for papers on the use of reference counts for
>garbage collection.
>...
> Any other recent papers ?
The following are not recent, but very useful (I especially find
Standish's chapter excellent.):
Jacques Cohen, "Garbage Collection of Linked Data Structures"
Acm Computing Surveys 13(3) Sep. 1981
Thomas Standish, "Data Structure Techniques"
Addison-Wesley, 1980
[5.4 - Storage Reclamation / 5.4.3 Incremental Garbage
Collection]
oz
--
You see things, and you say "WHY?" Usenet: [decvax|ihnp4]!utzoo!yetti!oz
But I dream things that never were; ......!seismo!mnetor!yetti!oz
and say "WHY NOT?" Bitnet: ··@[yusol|yulibra|yuyetti]
[Back To Methuselah] Bernard Shaw Phonet: [416] 736-5257 x 3976