Article

Free access

Incremental incrementally compacting garbage collection

Authors:

F. DupontAuthors Info & Claims

SIGPLAN '87: Papers of the Symposium on Interpreters and interpretive techniques

Pages 253 - 263

https://doi.org/10.1145/29650.29677

Published: 01 July 1987 Publication History

Abstract

A mixed-strategy garbage collection algorithm is presented, which combines mark-and-sweep and copy collection. The intent is to benefit from the compacting and linearizing properties of copy collection without losing computational use of half the memory. The stop-and-collect version of the algorithm is a simple and cheap technique to fight memory fragmentation. The collection strategy may be dynamically adapted to minimize the cost of collection, according to the amount of memory actually accessed by the computing process. The parallel version of the algorithm is to our knowledge the only parallel compacting collector for varisized cells, that leaves most (more than half) of the memory available for the computing process.

References

[1]

[Arn 72] Arnborg, S., Storage Administration in a Virtual Memory Simula System, BIT, Vol. 12, pp. 125-141, 1972.

Digital Library

[2]

[Bak 78] Baker, H. G., List Processing in Real Time on a Serial Computer, Comm. ACM, Vol. 21, No. 4, pp. 280-294, April 1978.

Digital Library

[3]

[BekCRU 86] Bekkers, Y., Canet, B., Ridoux, O., and Ungaro, L., MALI: A Memory with a Real-time Garbage Collector for Implementing Logic Programming Languages, Proc. of the 3rd IEEE Symp. on Logic Programming, Salt-Lake City (Utah), September 1986.

[4]

[Ben 84] Ben-Ari, M., Algorithms for On-the-fly Garbage Collection, ACM Trans. on Programming Languages and Systems, Vol. 6, No. 3, pp. 333-344, July 1984.

Digital Library

[5]

[Bob 66] Bobrow, D. G., Storage Management in LISP, Proc. of the IFIP working Conf. on Symbol Manipulation Languages and Techniques, North-Holland (1968), D. G. Bobrow (ed.), pp. 291-301, Pisa (Italy), September 1966.

[6]

[BobC 79] Bobrow, D. G., and Clark, D. W., Compact Encodings of List Structure, ACM Trans. on Programming Languages and Systems, Vol. 1, No. 2, pp. 266-286, October 1979.

Digital Library

[7]

[BobM 67] Bobrow, D. G., and Murphy, D. L., Structure of a LISP System Using Two-Level Storage, Comm. ACM, Vol. 10, No. 3, pp. 155-159, March 1967.

Digital Library

[8]

[BroGS 82] Brooks, R. A., Gabriel, R. P., and Steele, G. L. Jr., S-1 Common Lisp Implementation, Conf. Record of the 1982 ACM Symp. on Lisp and Functional Programming , Pittsburgh (Pennsylvania), pp. 108-113, August 1982.

Digital Library

[9]

[Bro 84] Brooks, R. A., Trading Data Space to Reduce Time and Code Space in Real-time Garbage Collection on Stock Hardware, Proc. of the 1984 ACM Symposium on Lisp and Functional Programming, Austin (Texas), pp. 256-262, August 1984.

Digital Library

[10]

[ChaDH 84] Chailloux, J., Devin, M., and Hullot, J. M., Le_Lisp: A Portable and Efficient Lisp System, Proc. of the 1984 ACM Symposium on Lisp and Functional Programming, Austin (Texas), pp. 113-122, August 1984.

Digital Library

[11]

[Che 70] Cheney, C. J., A Nonrecursive List Compacting Algorithm, Comm. ACM, Vol. 13, No. 11, pp. 677-678, November 1970.

Digital Library

[12]

[Cla 76] Clark, D. W., An Efficient List Moving Algorithm using Constant Workspace, Comm. ACM, Vol. 19, No. 6, pp. 352-354, June 1976.

Digital Library

[13]

[Coh 81] Cohen, J., Garbage Collection of Linked Data Structures, ACM Computing Surveys, Vol. 13, No. 3, pp. 341-367, September 1981.

Digital Library

[14]

[CohN 83] Cohen, J., and Nicolau, A., Comparison of Compaction Algorithms for Garbage Collection, ACM Toplas, Vol. 5, No. 4, pp. 532-553, October 1983.

Digital Library

[15]

[Col 60] Collins, G. E., A Method for Overlapping and Erasure of Lists, Comm. ACM, Vol. 3, No. 12, pp. 655- 657, December 1960.

Digital Library

[16]

[Con 74] Conrad, W. R., A Compactifying Garbage Collector for ECL's Non-Homogeneous Heap, Tech. Report 2-74, Harvard Univ., Cambridge (Mass.), February 1974.

[17]

[Daw 82] Dawson, J. L., Improved Effectiveness from a real time Lisp Garbage Collector, Conf. Record of the 1982 ACM Symp. on Lisp and Functional Programming , Pittsburgh (Pennsylvania), pp. 159-167, August 1982.

Digital Library

[18]

[DeuB 76] Deutsch, L. P., and Bobrow, D. G., An Efficient, Incremental, Automatic Garbage Collector, Comm. ACM, Vol. 19, No. 9, pp. 522-526, September 1976.

Digital Library

[19]

[DewM 77] Dewar R. B. K., and McCann, A. P., MACRO SPITBOL - a SNOBOL4 Compiler, Software - Practice and Experience, Vol. 7, No. 1, pp. 95-113, January 1977.

[20]

[DijLMSS 78] Dijkstra, E. W., Lamport, L., Martin, A. J., Scholten, C. S., and Steffens, E. F. M., On-the-fly Garbage Collection: An Exercise in Cooperation, Comm. ACM, Vol. 21, No. 11, pp. 966-975, November 1978.

Digital Library

[21]

[FenY 69] Fenichel, R. R., and Yochelson, J. C., A LISP Garbage Collector for Virtual-memory Computer Systems, Comm. ACM, Vol. 12, No. 11, pp. 611-612, November 1969.

Digital Library

[22]

[FitN 78] Fitch, J. P., and Norman, A. C., A note on Compacting Garbage Collection, The Computer Journal, Vol. 21, No. 1, pp. 31-34, February 1978.

[23]

[GotTHSI 79] Goto, E., Tetsuo, I., Hiraki, K., Susuki, M., and Inada, N., FLATS, A machine for Numerical, Symbolic and Associative Computing, Conf. Proc. of The 6th Ann. Symp. on Computer Architecture, Philadelphia, pp. 102-110, April 1979.

Digital Library

[24]

[HadW 67] Haddon, B. K., and Waite, W. M., A Compaction Procedure for Variable-length Storage Elements, The Computer Journal, Vol. 10, pp. 162-165, August 1967.

[25]

[Hal 84] Halstead, R. H. Jr., Implementation of Multilisp: Lisp on a Multiprocessor, Proc. of the 1984 ACM Symposium on Lisp and Functional Programming, Austin (Texas), pp. 9-17, August 1984.

Digital Library

[26]

[Han 69] Hansen, W. J., Compact List Representation: Definition, Garbage Collection, and System Implementation, Comm. ACM, Vol. 12, No. 9, pp. 499-507, September 1969.

Digital Library

[27]

[Han 77] Hanson, D. R., Storage Management for an Implementation of SNOBOL4, Software - Practice and Experience, Vol. 7, No. 2, pp. 179-192, March 1977.

[28]

[Har 64] Hart, T. P., and Evans, T. G., Notes on Implementing Lisp for the M 460 computer, in The Programming Language LISP, E. C. Berkeley and D. G. Bobrow (eds.), M.I.T., Cambridge (Mass.), 4th printing, 1974.

[29]

[Hib 80] Hibino, Y., A Practical Parallel Garbage Collection Algorithm and its Implementation, Conf. Proc. of The 7th Ann. Symp. on Computer Architecture, Rennes (France), May 1980, in SIGARCH Newsletter, Vol. 8, No. 3, pp. 113-120.

Digital Library

[30]

[HicC 64] Hickey, T., and Cohen, J., Performance Analysis of On-the-Fly Garbage Collection, Comm. ACM, Vol. 27, No. 11, pp. 1143-1154, November 1984.

Digital Library

[31]

[Jon 79] Jonkers, H. B. M., A Fast Garbage Compaction Algorithm, Inform. Processing Letters, Vol. 9, No. 1, pp. 26-30, July 1979.

[32]

[Knu 68] Knuth, D. E., The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968.

[33]

[KorK 85] Korn, D. G., and Kiem-Phong, V., In Search of a Better Malloc, Summer Conf. Proc. of the Usenix Association, Portland (Oregon), pp. 489-506, June 1985.

[34]

[KunS 77] Kung, H. T., and Song, S. W., An Efficient Garbage Collection System and its Correctness Proof, Proc. of IEEE 18th Symposium on Foundations of Computer Science, Providence (R.I.), pp. 120-131, October-November 1977.

Digital Library

[35]

[LanW 72] Lang, B., and Wegbreit, B., Fast Compactification, Rep. 25-72, Harvard Univ., Cambridge (Mass.), November 1972.

[36]

[LiH 86] Li, K., and Hudak, P., A New List Compaction Method, Software - Practice and Experience, Vol. 16, No. 2, pp. 145-163, February 1986.

Digital Library

[37]

[LieH 83] Liebermann, H., and Hewitt, C., A Real-time Garbage Collector Based on the Lifetimes of Objects, Comm. ACM, Vol. 26, No. 6, pp. 419-429, June 1983.

Digital Library

[38]

[McC 60] McCarthy, J., Recursive Functions of Symbolic Expressions and Their Computation by Machine, Comm. ACM, Vol. 3, No. 4, pp. 184-195, April 1960.

Digital Library

[39]

[Min 63] Minsky, M. L., A Lisp Garbage Collector Algorithm using Serial Secondary Storage, Memo 58, M.I.T. A.I. Lab., M.I.T., Cambridge, Mass., December 1963.

Digital Library

[40]

[Moo 84] Moon, D. A., Garbage Collection in a Large Lisp System, Proc. of the 1984 ACM Symposium on Lisp and Functional Programming, Austin (Texas), pp. 235- 246, August 1984.

Digital Library

[41]

[Mor 78] Morris, F. L., A Time- and Space-Efficient garbage compaction algorithm, Comm. ACM, Vol. 21, No. 8, pp. 662-665, August 1978.

Digital Library

[42]

[NewSW 83] Newman, I. A., Stallard, R. P., and Woodward M. C., A Parallel Compaction Algorithm for Multiprocessor Garbage Collection, Proc. of Internat. Conf. on Parallel Computing 83, Feilmeier M., Joubert J. and Schendel U. (eds.), Elsevier Science Publishers B. V. (North-Holland), 1983.

[43]

[NiwYHH 86] Niwa M., Yuhara M., Hayashi K., and Hattori A., Garbage Collection with Area Optimization for Facom ALPHA, Proc. of the 31st IEEE Comp. Soc. Int. Conf., Spring CompCon 86, San Francisco (Cal.), A. G. Bell (ed.), pp. 235-240, March 1986.

[44]

[RepG 86] Reppy, J. H., and Gansner, E. R., A Foundation for Programming Environments, Proc. of the ACM SIGSOFT/SIGPLAN Soft. Eng. Symp. on Practical Software Development Environments, P. B. Henderson (ed.), Palo-Alto (California), December 1986, published as SIGPLAN Notices, Vol. 22, No. 1, pp. 218-227, January 1987.

Digital Library

[45]

[Rud 86] Rudalics, M., Distributed Copying Garbage Collection, Proc. of the 1986 ACM Conf. on Lisp and Functional Programming, Cambridge (Mass.), pp. 364-372, August 1986.

Digital Library

[46]

[SchW 67] Schorr, H., and Waite, W. M., An Efficient Machine-independent Procedure for Garbage Collection in various List Structures, Comm. ACM, Vol. 10, No. 8, pp. 501-506, August 1967.

Digital Library

[47]

[Sho 75] Shore, J. E., On the External Storage Fragmentation Produced by First-Fit and Best-Fit Allocation Strategies, Comm. ACM, Vol. 18, No. 8, pp. 433-440, August 1975.

Digital Library

[48]

[Ste 75] Steele, G. L. Jr., Multiprocessing Compactifying Garbage Collection, Comm. ACM, Vol. 18, No. 9, pp. 495-508, September 1975.

Digital Library

[49]

[Stephenson, C.J.,] Fast Fits: New Methods for Dynamic Storage Allocation, Ninth ACM Symp. on Operating Systems, SIGOPS Review, Vol. 17, No. 5, pp. 30-32, 1983.

Digital Library

[50]

[Tho 76] Thorelli, L. E., A Fast Compactifying Garbage Collector, BIT, Vol. 16, No. 4, pp. 426-441, 1976.

Digital Library

[51]

[Ung 84] Ungar, D., Generation Scavenging: A Nondisruptive High Performance Storage Reclamation Algorithm, Proc. of ACM SIGSOFT/SIGPLAN Conference on Practical Programming Environments, Henderson P.B. (ed.), pp. 157-167, April 1984.

Digital Library

[52]

[Wad 76] Wadler, P. L., Analysis of an Algorithm for Real Time Garbage Collection, Comm. ACM, Vol. 19, No. 9, pp. 491-500, September 1976.

Digital Library

[53]

[Weg 72a] Wegbreit, B., A Generalized Compactifying Garbage Collector, The Computer journal, Vol. 15, No. 3, pp. 204-208, August 1972.

[54]

[Weg 72b] Wegbreit, B., A Space-Efficient List Structure Tracing Algorithm, IEEE Transactions on Computers, Vol. C-21, No. 9, pp. 1009-1010, September 1972.

[55]

[Yua 86] Yuasa, T., Realtime Garbage Collection on General-purpose Machines, Research Report, Research Institute for Mathematical Sciences, Kyoto University, Japan, February 1986.

Cited By

Yamazaki TNakamaru TShioya RUgawa TChiba S(2023)Collecting Cyclic Garbage across Foreign Function Interfaces: Who Takes the Last Piece of Cake?Proceedings of the ACM on Programming Languages10.1145/35912447:PLDI(591-614)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591244
Ma HLiu SWang CQiao YBond MBlackburn SKim MXu GJhala RDillig I(2022)Mako: a low-pause, high-throughput evacuating collector for memory-disaggregated datacentersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523441(92-107)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523441
Onozawa HUgawa TIwasaki HWang ZWrigstad T(2021)Fusuma: double-ended threaded compactionProceedings of the 2021 ACM SIGPLAN International Symposium on Memory Management10.1145/3459898.3463903(94-106)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3459898.3463903
Show More Cited By

Recommendations

Incremental incrementally compacting garbage collection

A mixed-strategy garbage collection algorithm is presented, which combines mark-and-sweep and copy collection. The intent is to benefit from the compacting and linearizing properties of copy collection without losing computational use of half the ...
Age-based garbage collection

Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Starvation-free heap size for replication-based incremental compacting garbage collection
ILC '10: Proceedings of the 2010 international conference on Lisp

We present a method to estimate the amount of the heap required to execute application programs on runtime systems with our replication-based incremental compacting garbage collector. Our method provides a strategy for adjusting the timing to trigger ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGPLAN '87: Papers of the Symposium on Interpreters and interpretive techniques

July 1987

291 pages

ISBN:0897912357

DOI:10.1145/29650

Editor:
Richard L. Wexelblat
Philips Laboratories, Briarcliff Manor, NY

ACM SIGPLAN Notices Volume 22, Issue 7
July 1987
291 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/960114
Issue’s Table of Contents

Copyright © 1987 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: 01 July 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

40
Total Citations
View Citations
587
Total Downloads

Downloads (Last 12 months)74
Downloads (Last 6 weeks)18

Reflects downloads up to 19 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yamazaki TNakamaru TShioya RUgawa TChiba S(2023)Collecting Cyclic Garbage across Foreign Function Interfaces: Who Takes the Last Piece of Cake?Proceedings of the ACM on Programming Languages10.1145/35912447:PLDI(591-614)Online publication date: 6-Jun-2023
https://dl.acm.org/doi/10.1145/3591244
Ma HLiu SWang CQiao YBond MBlackburn SKim MXu GJhala RDillig I(2022)Mako: a low-pause, high-throughput evacuating collector for memory-disaggregated datacentersProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523441(92-107)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519939.3523441
Onozawa HUgawa TIwasaki HWang ZWrigstad T(2021)Fusuma: double-ended threaded compactionProceedings of the 2021 ACM SIGPLAN International Symposium on Memory Management10.1145/3459898.3463903(94-106)Online publication date: 22-Jun-2021
https://dl.acm.org/doi/10.1145/3459898.3463903
Zhao WBlackburn SNagarakatte SBaumann AKasikci B(2020)Deconstructing the garbage-first collectorProceedings of the 16th ACM SIGPLAN/SIGOPS International Conference on Virtual Execution Environments10.1145/3381052.3381320(15-29)Online publication date: 17-Mar-2020
https://dl.acm.org/doi/10.1145/3381052.3381320
Springer MMasuhara HSinger JXu H(2019)Massively parallel GPU memory compactionProceedings of the 2019 ACM SIGPLAN International Symposium on Memory Management10.1145/3315573.3329979(14-26)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3315573.3329979
Wagner GLarsen PBrunthaler SFranz M(2016)Thinking Inside the BoxACM Transactions on Programming Languages and Systems10.1145/286657638:3(1-37)Online publication date: 8-Apr-2016
https://dl.acm.org/doi/10.1145/2866576
Ugawa TIwasaki HYuasa TWhite JLeitao A(2010)Starvation-free heap size for replication-based incremental compacting garbage collectionProceedings of the 2010 international conference on Lisp10.1145/1869643.1869649(43-52)Online publication date: 19-Oct-2010
https://dl.acm.org/doi/10.1145/1869643.1869649
Ugawa TIwasaki HYuasa T(2010)Improved replication-based incremental garbage collection for embedded systemsACM SIGPLAN Notices10.1145/1837855.180666445:8(73-82)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1837855.1806664
Ugawa TIwasaki HYuasa TVitek JLea D(2010)Improved replication-based incremental garbage collection for embedded systemsProceedings of the 2010 international symposium on Memory management10.1145/1806651.1806664(73-82)Online publication date: 5-Jun-2010
https://dl.acm.org/doi/10.1145/1806651.1806664
Wegiel MKrintz C(2009)The single-referent collectorACM Transactions on Architecture and Code Optimization10.1145/1596510.15965136:4(1-26)Online publication date: 29-Oct-2009
https://dl.acm.org/doi/10.1145/1596510.1596513
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

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