article

Open access

On the usefulness of type and liveness accuracy for garbage collection and leak detection

Authors:

Johannes HenkelAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 24, Issue 6

Pages 593 - 624

https://doi.org/10.1145/586088.586089

Published: 01 November 2002 Publication History

Abstract

The effectiveness of garbage collectors and leak detectors in identifying dead objects depends on the accuracy of their reachability traversal. Accuracy has two orthogonal dimensions: (i) whether the reachability traversal can distinguish between pointers and nonpointers (type accuracy), and (ii) whether the reachability traversal can identify memory locations that will be dereferenced in the future (liveness accuracy). This article presents an experimental study of the importance of type and liveness accuracy for reachability traversals. We show that liveness accuracy reduces the reachable heap size by up to 62% for our benchmark programs. However, the simpler liveness schemes (e.g., intraprocedural analysis of local variables) are largely ineffective for our benchmark runs: one must analyze global variables using interprocedural analysis to obtain significant benefits. Type accuracy has an insignificant impact on a garbage collector's ability to find unreachable objects in our benchmark runs. We report results for programs written in C, C++, and Eiffel.

References

[1]

Agesen, O., Detlefs, D., and Moss, J. E. B. 1998. Garbage collection and local variable type-precision and liveness in Java virtual machines. In Programming Language Design and Implementation (PLDI). ACM, New York, pp. 269--279.

[2]

Alpern, B., Attanasio, C. R., Barton, J. J., Burke, M. G., Cheng, P., Choi, J.-D., Cocchi, A., Fink, S. J., Grove, D., Hind, M., Hummel, S. F., Lieber, D., Litvinov, V., Mergen, M. F., Ngo, T., Russell, J. R., Sarkar, V., Serrano, M. J., Shepherd, J. C., Smith, S. E., Sreedhar, V. C., Srinivasan, H., and Whaley, J. 2000. The Jalape no virtual machine. IBM Syst. J., 39, 1 (Feb.), 211--238.

[3]

Appel, A. W. 1990. A runtime system. LISP Symb. Computat., 3, 4 (Nov.), 343--380.

[4]

Attanasio, C. R., Bacon, D. F., Cocchi, A., and Smith, S. 2001. A comparative evaluation of parallel garbage collector implementations. In Workshop on Languages and Compilers for Parallel Computing (LCPC), (Aug.).

[5]

Bartlett, J. F. 1988. Compacting garbage collection with ambiguous roots. Tech. Rep. 88/2. DEC Western Research Laboratory, Palo Alto, Calif. (Also in LISP Pointers 1, 6 (Apr.-June), 2--12.

[6]

Bartlett, J. F. 1989. Mostly-copying garbage collection picks up generations and C++. Tech. Rep. DEC Western Research Laboratory, Palo Alto, Calif.

[7]

Boehm, H.-J., Demers, A. J., and Shenker, S. 1991. Mostly parallel garbage collection. In Programming Language Design and Implementation (PLDI) (Nov.). ACM, New York, pp. 157--164.

[8]

Boehm, H.-J., Demers, A. J., and Weiser, M. 2002. A garbage collector for C and C++. http://www.hpl.hp.com/personal/Hans_Boehm/gc/.

[9]

Boehm, H.-J. and Shao, Z. 1993. Inferring type maps during garbage collection. In OOPSLA '93 Workshop on Memory Management and Garbage Collection (Sept.). ACM, New York.

[10]

Boehm, H.-J. and Weiser, M. 1988. Garbage collection in an uncooperative environment. Softw.---Pract. Exp. (SPE), 18, 9 (Sept.), 807--820.

[11]

Colnet, D. Coucaud, P., and Zendra, O. 1998. Compiler support to customize the mark and sweep algorithm. In International Symposium on Memory Management (ISMM) (Oct.), pp. 154--165.

[12]

Dion, J. and Monier, L. 2002. Third degree. http://research.compaq.com/wrl/projects/om/third.html.

[13]

Diwan, A., Moss, J. E. B., and Hudson, R. L. 1992. Compiler support for garbage collection in a statically typed language. In Programming Language Design and Implementation (PLDI) (July). ACM, New York, pp. 273--282.

[14]

Edison Design Group. 2002. http://www.edg.com.

[15]

Fitzgerald, R. and Tarditi, D. 2000. The case for profile-directed selection of garbage collectors. In International Symposium on Memory Management (ISMM) (Oct.), pp. 111--120.

[16]

Geodesic Systems. 2002. Great Circle---Real-time error detection and code diagnosis for developers. http://www.geodesic.com/solutions/products_gc_overview.html.

[17]

Gosling, J., Joy, B., and Steele, G. 1996. The Java Language Specification. Addison-Wesley, Reading, Mass.

[18]

Hastings, R. and Joyce, B. 1992. Fast detection of memory leaks and access errors. In Proceedings of the Winter '92 USENIX Conference, pp. 125--136.

[19]

Henderson, F. 2002. Accurate garbage collection in an uncooperative environment. In International Symposium on Memory Management (ISMM) (June).

[20]

Hicks, M. W., Moore, J. T., and Nettles, S. M. 1997. The measured cost of copying garbage collection mechanisms. In International Conference on Functional Programming (ICFP) (June), pp. 292--305.

[21]

Hudson, R. L., Moss, J. E. B., Diwan, A., and Weight, C. F. 1991. A language-independent garbage collector toolkit. Tech. Rep. 91-47. Univ. Massachusetts at Amherst, Amherst, Mass.

[22]

Jones, R. and Lins, R. 1997. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. Wiley, New York.

[23]

Milner, R., Tofte, M., and Harper, R. 1990. The definition of Standard ML. MIT Press, Cambridge, Mass.

[24]

Nelson, G. 1991. (Ed.) Systems Programming with Modula-3. Prentice Hall, Englewood Cliffs, N.J.

[25]

Röjemo, N. and Runciman, C. 1996. Lag, drag, void and use---heap profiling and space-efficient compilation revisited. In International Conference on Functional Programming (ICFP) (Philadelphia, Pa. May) pp. 34--41. (Also available as ACM SIGPLAN Notices 31, 6).

[26]

Shaham, R., Kolodner, E. K., and Sagiv, M. 2000. On the effectiveness of GC in Java. In International Symposium on Memory Management (ISMM) (Oct.), pp. 12--17.

[27]

Shaham, R., Kolodner, E. K., and Sagiv, M. 2001. Heap profiling for space-efficient Java. In Programming Language Design and Implementation (PLDI) (June). ACM, New York, pp. 104--113.

[28]

Smith, F. and Morrisett, G. 1998. Comparing mostly-copying and mark-sweep conservative collection. In International Symposium on Memory Management (ISMM) (Oct.), pp. 68--78.

[29]

Stanford University SUIF Research Group. 2002. SUIF compiler system version 1.x. http://suif.stanford.edu/suif/suif1/index.html.

[30]

Stichnoth, J. M., Lueh, G.-Y., and Cierniak, M. 1999. Support for garbage collection at every instruction in a Java compiler. In Programming Language Design and Implementation (PLDI) (May). ACM, New York, pp. 118--127.

[31]

Tarditi, D., Morrisett, G., Cheng, P., Stone, C., Harper, R., and Lee, P. 1996. TIL: A type-directed optimizing compiler for ML. In Programming Language Design and Implementation (PLDI) (May). ACM, New York, pp. 181--192.

[32]

Tofte, M. 1998. A brief introduction to regions. In International Symposium on Memory Management (ISMM) (Oct.), pp. 186--195.

[33]

Ungar, D. 1984. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In Software Engineering Symposium on Practical Software Development Environments (SDE). pp. 157--167.

[34]

Wilson, P. 1992. Uniprocessor garbage collection techniques. In International Workshop on Memory Management (Sept.), pp. 1--42.

[35]

Wilson, R. P., French, R. S., Wilson, C. S., Amarasinghe, S. P., Anderson, J.-A. M., Tjiang, S. W. K., Liao, S.-W., Tseng, C.-W., Hall, M. W., Lam, M. S., and Hennessy, J. L. 1994. SUIF: An infrastructure for research on parallelizing and optimizing compilers. ACM SIGPLAN Not. 29, 12 (Dec.), 31--37.

[36]

Zorn, B. 1993. The measured cost of conservative garbage collection. Softw.---Pract. Exp. 23, 7 (July), 733--756.

[37]

Zorn, B. G., 1991. The effect of garbage collection on cache performance. Tech. Rep. CU-CS-528-91. Univ. Colorado at Boulder, Boulder, Col., May.

Cited By

Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Zhu XZhang SZhu YZheng WYang Y(2020)Self-weighted Multi-view Fuzzy ClusteringACM Transactions on Knowledge Discovery from Data10.1145/339623814:4(1-17)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3396238
Bansal AGoel SShah PSanyal AKumar PDing CMaas M(2020)Garbage collection using a finite liveness domainProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397208(1-15)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3381898.3397208
Show More Cited By

Index Terms

On the usefulness of type and liveness accuracy for garbage collection and leak detection
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Memory management
        Garbage collection
2. Theory of computation
  1. Logic
  2. Semantics and reasoning

Recommendations

Liveness-based garbage collection for lazy languages
ISMM '16

We consider the problem of reducing the memory required to run lazy first-order functional programs. Our approach is to analyze programs for liveness of heap-allocated data. The result of the analysis is used to preserve only live data—a subset of ...
Conservative garbage collection for general memory allocators

This paper explains a technique that integrates conservative garbage collection on top of general memory allocators. This is possible by using two data structures named malloc-tables and jump-tables that are computed at garbage collection time to map ...
Conservative garbage collection for general memory allocators
ISMM '00: Proceedings of the 2nd international symposium on Memory management

This paper explains a technique that integrates conservative garbage collection on top of general memory allocators. This is possible by using two data structures named malloc-tables and jump-tables that are computed at garbage collection time to map ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 24, Issue 6

November 2002

212 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/586088

Issue’s Table of Contents

Copyright © 2002 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 2002

Published in TOPLAS Volume 24, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

57
Total Citations
View Citations
884
Total Downloads

Downloads (Last 12 months)30
Downloads (Last 6 weeks)10

Reflects downloads up to 20 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Banerjee SDevecsery DChen PNarayanasamy S(2020)Sound garbage collection for C using pointer provenanceProceedings of the ACM on Programming Languages10.1145/34282444:OOPSLA(1-28)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428244
Zhu XZhang SZhu YZheng WYang Y(2020)Self-weighted Multi-view Fuzzy ClusteringACM Transactions on Knowledge Discovery from Data10.1145/339623814:4(1-17)Online publication date: 22-Jun-2020
https://dl.acm.org/doi/10.1145/3396238
Bansal AGoel SShah PSanyal AKumar PDing CMaas M(2020)Garbage collection using a finite liveness domainProceedings of the 2020 ACM SIGPLAN International Symposium on Memory Management10.1145/3381898.3397208(1-15)Online publication date: 16-Jun-2020
https://dl.acm.org/doi/10.1145/3381898.3397208
Waghmare AXue QZhang DZhao YMittal SArora NByrne CStarner TAbowd G(2020)UbiquiTouchProceedings of the ACM on Interactive, Mobile, Wearable and Ubiquitous Technologies10.1145/33809894:1(1-22)Online publication date: 18-Mar-2020
https://dl.acm.org/doi/10.1145/3380989
Kanvar VKhedker U(2017)"What's in a name?" going beyond allocation site names in heap analysisACM SIGPLAN Notices10.1145/3156685.309226752:9(92-103)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3156685.3092267
Kanvar VKhedker UKirsch CTitzer B(2017)"What's in a name?" going beyond allocation site names in heap analysisProceedings of the 2017 ACM SIGPLAN International Symposium on Memory Management10.1145/3092255.3092267(92-103)Online publication date: 18-Jun-2017
https://dl.acm.org/doi/10.1145/3092255.3092267
Yan HSui YChen SXue J(2017)AutoFixACM SIGAPP Applied Computing Review10.1145/3040575.304057916:4(38-50)Online publication date: 13-Jan-2017
https://dl.acm.org/doi/10.1145/3040575.3040579
Dwyer M(2017)Improving Timeliness and Visibility in Publishing Software Engineering ResearchIEEE Transactions on Software Engineering10.1109/TSE.2017.266391843:3(205-206)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TSE.2017.2663918
Giuffrida CIorgulescu CTamburrelli GTanenbaum A(2017)Automating Live Update for Generic Server ProgramsIEEE Transactions on Software Engineering10.1109/TSE.2016.258406643:3(207-225)Online publication date: 1-Mar-2017
https://dl.acm.org/doi/10.1109/TSE.2016.2584066
Kumar K. PSanyal AKarkare A(2016)Liveness-based garbage collection for lazy languagesACM SIGPLAN Notices10.1145/3241624.292669851:11(122-133)Online publication date: 14-Jun-2016
https://dl.acm.org/doi/10.1145/3241624.2926698
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents