Incremental incrementally compacting garbage collection

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.
• 2: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 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: Mordechai Ben-Ari, Algorithms for on-the-fly garbage collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.6 n.3, p.333-344, July 1984 [doi>10.1145/579.587]
• 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: Daniel G. Bobrow , Douglas W. Clark, Compact Encodings of List Structure, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.266-286, Oct. 1979 [doi>10.1145/357073.357081]
• 7: Daniel G. Bobrow , Daniel L. Murphy, Structure of a LISP system using two-level storage, Communications of the ACM, v.10 n.3, p.155-159, March 1967 [doi>10.1145/363162.363185]
• 8: Rodney A. Brooks , Richard P. Gabriel , Guy L. Steele, Jr., S-1 Common Lisp implementation, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.108-113, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802141]
• 9: Rodney A. Brooks, Trading data space for reduced time and code space in real-time garbage collection on stock hardware, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.256-262, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802042]
• 10: Jérome Chailloux , Ma´thieu Devin , Jean-Marie Hullot, LELISP, a portable and efficient LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.113-122, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802027]
• 11: C. J. Cheney, A nonrecursive list compacting algorithm, Communications of the ACM, v.13 n.11, p.677-678, Nov 1970 [doi>10.1145/362790.362798]
• 12: Douglas W. Clark, An efficient list-moving algorithm using constant workspace, Communications of the ACM, v.19 n.6, p.352-356, June 1976 [doi>10.1145/360238.360247]
• 13: Jacques Cohen, Garbage Collection of Linked Data Structures, ACM Computing Surveys (CSUR), v.13 n.3, p.341-367, Sept. 1981 [doi>10.1145/356850.356854]
• 14: Jacques Cohen , Alexandru Nicolau, Comparison of Compacting Algorithms for Garbage Collection, ACM Transactions on Programming Languages and Systems (TOPLAS), v.5 n.4, p.532-553, Oct. 1983 [doi>10.1145/69575.357226]
• 15: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 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: Jeffrey L. Dawson, Improved effectiveness from a real time LISP garbage collector, Proceedings of the 1982 ACM symposium on LISP and functional programming, p.159-167, August 15-18, 1982, Pittsburgh, Pennsylvania, United States [doi>10.1145/800068.802146]
• 18: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 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: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , C. S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Communications of the ACM, v.21 n.11, p.966-975, Nov. 1978 [doi>10.1145/359642.359655]
• 21: Robert R. Fenichel , Jerome C. Yochelson, A LISP garbage-collector for virtual-memory computer systems, Communications of the ACM, v.12 n.11, p.611-612, Nov. 1969 [doi>10.1145/363269.363280]
• 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: Eiichi Goto , Tetsuo Ida , Kei Hiraki , Masayuki Suzuki , Nobuyuki Inada, FLATS, a machine for numerical, symbolic and associative computing, Proceedings of the 6th annual symposium on Computer architecture, p.102-110, April 23-25, 1979 [doi>10.1145/800090.802898]
• 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: Robert H. Halstead, Jr., Implementation of multilisp: Lisp on a multiprocessor, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.9-17, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802017]
• 26: Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969 [doi>10.1145/363219.363225]
• 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: Yasushi Hibino, A practical parallel garbage collection algorithm and its implementation, Proceedings of the 7th annual symposium on Computer Architecture, p.113-120, May 06-08, 1980, La Baule, United States [doi>10.1145/800053.801916]
• 30: Tim Hickey , Jacques Cohen, Performance analysis of on-the-fly garbage collection, Communications of the ACM, v.27 n.11, p.1143-1154, Nov. 1984 [doi>10.1145/1968.358298]
• 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.
• 35: [LanW 72] Lang, B., and Wegbreit, B., Fast Compactification, Rep. 25-72, Harvard Univ., Cambridge (Mass.), November 1972.
• 36: Kai Li , Paul Hudak, A new list compaction method, Software—Practice & Experience, v.16 n.2, p.145-163, Feb. 1986 [doi>10.1002/spe.4380160206]
• 37: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 38: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 39: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 40: David A. Moon, Garbage collection in a large LISP system, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.235-246, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802040]
• 41: F. Lockwood Morris, A time- and space-efficient garbage compaction algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978 [doi>10.1145/359576.359583]
• 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: J H Reppy , E R Gansner, A foundation for programming environments, ACM SIGPLAN Notices, v.22 n.1, p.218-227, January 1987
• 45: Martin Rudalics, Distributed copying garbage collection, Proceedings of the 1986 ACM conference on LISP and functional programming, p.364-372, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319877]
• 46: H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
• 47: John E. Shore, On the external storage fragmentation produced by first-fit and best-fit allocation strategies, Communications of the ACM, v.18 n.8, p.433-440, Aug. 1975 [doi>10.1145/360933.360949]
• 48: Guy L. Steele, Jr., Multiprocessing compactifying garbage collection, Communications of the ACM, v.18 n.9, p.495-508, Sept. 1975 [doi>10.1145/361002.361005]
• 49: C. J. Stephenson, New methods for dynamic storage allocation (Fast Fits), ACM SIGOPS Operating Systems Review, v.17 n.5, p.30-32, October 1983
• 50: [Tho 76] Thorelli, L. E., A Fast Compactifying Garbage Collector, BIT, Vol. 16, No. 4, pp. 426-441, 1976.
• 51: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 52: Philip L. Wadler, Analysis of an algorithm for real time garbage collection, Communications of the ACM, v.19 n.9, p.491-500, Sept. 1976 [doi>10.1145/360336.360338]
• 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.

INDEX TERMS

Classification:
  D. Software
  D.4 OPERATING SYSTEMS

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Languages, Theory