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.
- [Arn 72] Arnborg, S., Storage Administration in a Virtual Memory Simula System, BIT, Vol. 12, pp. 125-141, 1972.Google ScholarDigital Library
- [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 ScholarDigital Library
- [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 Scholar
- [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 ScholarDigital Library
- [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 Scholar
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [Che 70] Cheney, C. J., A Nonrecursive List Compacting Algorithm, Comm. ACM, Vol. 13, No. 11, pp. 677-678, November 1970. Google ScholarDigital Library
- [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 ScholarDigital Library
- [Coh 81] Cohen, J., Garbage Collection of Linked Data Structures, ACM Computing Surveys, Vol. 13, No. 3, pp. 341-367, September 1981. Google ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 Scholar
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarCross Ref
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarCross Ref
- [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 ScholarDigital Library
- [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 ScholarCross Ref
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarCross Ref
- [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 Scholar
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [Jon 79] Jonkers, H. B. M., A Fast Garbage Compaction Algorithm, Inform. Processing Letters, Vol. 9, No. 1, pp. 26-30, July 1979.Google ScholarCross Ref
- [Knu 68] Knuth, D. E., The Art of Computer Programming, Vol. 1, Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968.Google Scholar
- [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 Scholar
- [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 ScholarDigital Library
- [LanW 72] Lang, B., and Wegbreit, B., Fast Compactification, Rep. 25-72, Harvard Univ., Cambridge (Mass.), November 1972.Google Scholar
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 Scholar
- [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 Scholar
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [Ste 75] Steele, G. L. Jr., Multiprocessing Compactifying Garbage Collection, Comm. ACM, Vol. 18, No. 9, pp. 495-508, September 1975. Google ScholarDigital Library
- [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 ScholarDigital Library
- [Tho 76] Thorelli, L. E., A Fast Compactifying Garbage Collector, BIT, Vol. 16, No. 4, pp. 426-441, 1976.Google ScholarCross Ref
- [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 ScholarDigital Library
- [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 ScholarDigital Library
- [Weg 72a] Wegbreit, B., A Generalized Compactifying Garbage Collector, The Computer journal, Vol. 15, No. 3, pp. 204-208, August 1972.Google Scholar
- [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 Scholar
- [Yua 86] Yuasa, T., Realtime Garbage Collection on General-purpose Machines, Research Report, Research Institute for Mathematical Sciences, Kyoto University, Japan, February 1986.Google Scholar
Index Terms
Incremental incrementally compacting garbage collection
Recommendations
Incremental incrementally compacting garbage collection
SIGPLAN '87: Papers of the Symposium on Interpreters and interpretive techniquesA 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 LispWe 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