skip to main content
article
Free Access

Incremental incrementally compacting garbage collection

Authors Info & Claims
Published:01 July 1987Publication History
Skip Abstract Section

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.Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  11. [Che 70] Cheney, C. J., A Nonrecursive List Compacting Algorithm, Comm. ACM, Vol. 13, No. 11, pp. 677-678, November 1970. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  13. [Coh 81] Cohen, J., Garbage Collection of Linked Data Structures, ACM Computing Surveys, Vol. 13, No. 3, pp. 341-367, September 1981. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle ScholarCross RefCross Ref
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle ScholarCross RefCross Ref
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle ScholarCross RefCross Ref
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle ScholarCross RefCross Ref
  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.Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle ScholarCross RefCross Ref
  32. [Knu 68] Knuth, D. E., The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968.Google ScholarGoogle Scholar
  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.Google ScholarGoogle Scholar
  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.Google ScholarGoogle ScholarDigital LibraryDigital Library
  35. [LanW 72] Lang, B., and Wegbreit, B., Fast Compactification, Rep. 25-72, Harvard Univ., Cambridge (Mass.), November 1972.Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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.Google ScholarGoogle Scholar
  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.Google ScholarGoogle Scholar
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  48. [Ste 75] Steele, G. L. Jr., Multiprocessing Compactifying Garbage Collection, Comm. ACM, Vol. 18, No. 9, pp. 495-508, September 1975. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  50. [Tho 76] Thorelli, L. E., A Fast Compactifying Garbage Collector, BIT, Vol. 16, No. 4, pp. 426-441, 1976.Google ScholarGoogle ScholarCross RefCross Ref
  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. Google ScholarGoogle ScholarDigital LibraryDigital 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. Google ScholarGoogle ScholarDigital LibraryDigital Library
  53. [Weg 72a] Wegbreit, B., A Generalized Compactifying Garbage Collector, The Computer journal, Vol. 15, No. 3, pp. 204-208, August 1972.Google ScholarGoogle Scholar
  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.Google ScholarGoogle Scholar
  55. [Yua 86] Yuasa, T., Realtime Garbage Collection on General-purpose Machines, Research Report, Research Institute for Mathematical Sciences, Kyoto University, Japan, February 1986.Google ScholarGoogle Scholar

Index Terms

  1. Incremental incrementally compacting garbage collection

                    Recommendations

                    Comments

                    Login options

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

                    Sign in

                    Full Access

                    • Published in

                      cover image ACM SIGPLAN Notices
                      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
                      • 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

                      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]

                      Publisher

                      Association for Computing Machinery

                      New York, NY, United States

                      Publication History

                      • Published: 1 July 1987

                      Check for updates

                      Qualifiers

                      • article

                    PDF Format

                    View or Download as a PDF file.

                    PDF

                    eReader

                    View online with eReader.

                    eReader