Reducing sweep time for a nearly empty heap

ABSTRACT

Mark and sweep garbage collectors are known for using time proportional to the heap size when sweeping memory, since all objects in the heap, regardless of whether they are live or not, must be visited in order to reclaim the memory occupied by dead objects. This paper introduces a sweeping method which traverses only the live objects, so that sweeping can be done in time dependent only on the number of live objects in the heap. This allows each collection to use time independent of the size of the heap, which can result in a large reduction of overall garbage collection time in empty heaps. Unfortunately, the algorithm used may slow down overall garbage collection if the heap is not so empty. So a way to select the sweeping algorithm depending on the heap occupancy is introduced, which can avoid any significant slowdown.

REFERENCES

• 1: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 2: Paul R. Wilson. Uniprocessor garbage collection techniques. Technical report, University of Texas~ January 1994.
• 3: 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]
• 4: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 5: Andrew W. Appel, Garbage collection can be faster than stack allocation, Information Processing Letters, v.25 n.4, p.275-279, June 17, 1987 [doi>10.1016/0020-0190(87)90175-X]
• 6: Michael Hicks , Luke Hornof , Jonathan T. Moore , Scott M. Nettles, A study of large object spaces, Proceedings of the 1st international symposium on Memory management, p.138-145, October 17-19, 1998, Vancouver, British Columbia, Canada
• 7: Joel F. Bartlett. Compacting garbage collection with ambiguous roots. Research Report 88/2, Compaq Western Research Laboratory, February 1988.
• 8: Edsger W. Dijkstra , Leslie Lamport , A. J. Martin , Carel S. Scholten , E. F. M. Steffens, On-the-fly garbage collection: an exercise in cooperation, Language Hierarchies and Interfaces, International Summer School, p.43-56, July 23-August 02, 1975
• 9: P.W. Purdom, S. M. Stigler, and Tat-Ong Cheam. Statistical investigation of three storage algorithms. BIT, 11:187-195, 1971.
• 10: 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]
• 11: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 12: C. J. Stephenson, New methods for dynamic storage allocation (Fast Fits), Proceedings of the ninth ACM symposium on Operating systems principles, p.30-32, October 10-13, 1983, Bretton Woods, New Hampshire, United States
• 13: R. P. Brent, Efficient implementation of the first-fit strategy for dynamic storage allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.11 n.3, p.388-403, July 1989 [doi>10.1145/65979.65981]
• 14: David Ungar , Frank Jackson, An adaptive tenuring policy for generation scavengers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.1, p.1-27, Jan. 1992 [doi>10.1145/111186.116734]
• 15: Andrew W. Appel , Kai Li, Virtual memory primitives for user programs, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.96-107, April 08-11, 1991, Santa Clara, California, United States
• 16: LaTTe: A fast and efficient Java VM just-in-time compiler, http://latte, snu.ac.kr/.
• 17: Byung-Sun Yang , Soo-Mook Moon , Seongbae Park , Junpyo Lee , SeungIl Lee , Jinpyo Park , Yoo C. Chung , Suhyun Kim , Kemal Ebcioglu , Erik Altman, LaTTe: A Java VM Just-in-Time Compiler with Fast and Efficient Register Allocation, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.128, October 12-16, 1999
• 18: Byung-Sun Yang , Junpyo Lee , Jinpyo Park , Soo-Mook Moon , Kemal Ebcioğlu , Erik Altman, Lightweight monitor for Java VM, ACM SIGARCH Computer Architecture News, v.27 n.1, p.35-38, March 1999 [doi>10.1145/309758.309773]
• 19: SeungIl Lee, Byung-Sun Yang, Suhyun Kim, Seongbae Park, Soo-Mook Moon, Kemal Ebcio~lu, and Erik Altman. On-demand translation of Java exception handlers in the LaTTe JVM just-in-time compiler. In Proceedings of the 1999 Workshop on Binary Translation, New Port Beach, California, October 1999.
• 20: Yoo C. Chung. interpreter design for LaTTe. Available at http://pallas.snu,ac,kr/'chungyc/papers/ interpreter, ps.
• 21: ~oo C. Chung. Allocation with increments in a nonmoving collector. Available at http://pallas, snu. ac. kr/~ chungyc/papers/fast-allot, ps.
• 22: Dominique Colnet , Philippe Coucaud , Olivier Zendra, Compiler support to customize the mark and sweep algorithm, Proceedings of the 1st international symposium on Memory management, p.154-165, October 17-19, 1998, Vancouver, British Columbia, Canada
• 23: Hans-Juergen Boehm , Mark Weiser, Garbage collection in an uncooperative environment, Software—Practice & Experience, v.18 n.9, p.807-820, September 1988 [doi>10.1002/spe.4380180902]
• 24: Yoo C. Chung, Junpyo Lee, Soo-Mook Moon, and Kemal Ebcio~lu. Memory management in the LaTTe Java virtual machine. In preparation.
• 25: SPEC JVM98 Benchmarks. http'//www, spec. org/ osg/jvm98/.
• 26: Dan Sahlin. Making garbage collection independent of the amount of garbage. Research Report R87008, Swedish Institute of Computer Science, 1987.
• 27: 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]
• 28: Hans-Juergen Boehm. Mark-sweep vs. copying collection and asymptotic complexity. Available at http ://www. hpl. hp. com/personal/Hans_Boehm/gc / complexity, html.
• 29: R. John M. Hughes. A semi-incremental garbage collection algorithm. Software Practice and Experience, 12(11):1081-1084, November 1982.
• 30: Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992 [doi>10.1145/130854.130862]
• 31: Paul R. Wilson , Barry Hayes, Garbage collection in object oriented systems, Addendum to the proceedings on Object-oriented programming systems, languages, and applications (Addendum), p.63-71, October 06-11, 1991, Phoenix, Arizona, United States
• 32: Proceedings of the International Symposium on Memory Management (ISMM '98), Vancouver, British Coumbia, Canada, October 1998. ACM Press.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Design, Languages