Shifting garbage collection overhead to compile time

ABSTRACT

This paper discusses techniques which enable automatic storage reclamation overhead to be partially shifted to compile time. The paper assumes a transaction oriented collection scheme, as proposed by Deutsch and Bobrow, the necessary features of which are summarized. Implementing the described optimizations requires global flow analysis to be performed on the source program. It is shown that at compile time certain program actions that affect the reference counts of cells can be deduced. This information is used to find actions that cancel when the code is executed and those that can be grouped to achieve improved efficiency.

REFERENCES

• 1: H. Boom, Experience with the use of ALGOL as SIL, ALGOL Bulletin [doi>10.1145/1061646.1061655]
• 2: Douglas W. Clark , C. Cordell Green, An empirical study of list structure in Lisp, Communications of the ACM, v.20 n.2, p.78-87, Feb. 1977 [doi>10.1145/359423.359427]
• 3: 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]
• 4: Kathleen Jensen , Niklaus Wirth, Pascal-User Manual and Report, Springer-Verlag New York, Inc., Secaucus, NJ, 1975
• 5: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 6: Rosen, B.K. Data flow analysis for recursive PL/1 programs. IBM Res. Rep., IBM, Yorktown Heights, N.Y., Jan. 1975,
• 7: Tarjan, R.E. Depth first search and linear graph algorithms. SlAM J. Compmg. 1, 2 (1972), 146-160.

INDEX TERMS

Keywords:
garbage collection, global flow analysis, list processing, optimization, reference counts, storage management