Understanding memory allocation of scheme programs

ABSTRACT

Memory is the performance bottleneck of modern architectures. Keeping memory consumption as low as possible enables fast and unobtrusive applications. But it is not easy to estimate the memory use of programs implemented in functional languages, due to both the complex translations of some high level constructs, and the use of automatic memory managers.To help understand memory allocation behavior of Scheme programs, we have designed two complementary tools. The first one reports on frequency of allocation, heap configurations and on memory reclamation. The second tracks down memory leaks¹. We have applied these tools to our Scheme compiler, the largest Scheme program we have been developing. This has allowed us to drastically reduce the amount of memory consumed during its bootstrap process, without requiring much development time.Development tools will be neglected unless they are both conveniently accessible and easy to use. In order to avoid this pitfall, we have carefully designed the user interface of these two tools. Their integration into a real programming environment for Scheme is detailed in the paper.

REFERENCES

• 1: A. Appel, F. Duba, D. MacQueen, and A Tomach. Profiling in the Presence of Optimization and Garbage Collection.Technical Report CS-TR-197-88, Princeton University,November 1988.
• 2: Hans-Juergen Boehm, Space efficient conservative garbage collection, ACM SIGPLAN Notices, v.28 n.6, p.197-206, June 1993
• 3: L. Cannon, R. Elliot, L. Kircho, J. Miller, J. Milner, R. Mitze, E. Schan, N. Whittinton, D. Spencer, H. Keppel, and M. Brader. Recommended C Style and Coding Standards, June 1990.
• 4: Wim De Pauw , Gary Sevitsky, Visualizing Reference Patterns for Solving Memory Leaks in Java, Proceedings of the 13th European Conference on Object-Oriented Programming, p.116-134, June 14-18, 1999
• 5: J. Fenlason and B. Baccala. GNU-gprof: user manual. Technical report, Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA, 1997.
• 6: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• 7: H. Abelson , R. K. Dybvig , C. T. Haynes , G. J. Rozas , N. I. Adams Iv , D. P. Friedman , E. Kohlbecker , G. L. Steele, Jr. , D. H. Bartley , R. Halstead , D. Oxley , G. J. Sussman , G. Brooks , C. Hanson , K. M. Pitman , M. Wand, Revised Report on the Algorithmic Language Scheme, Higher-Order and Symbolic Computation, v.11 n.1, p.7-105, August 1998 [doi>10.1023/A:1010051815785]
• 8: David A. Patterson , John L. Hennessy, Computer organization and design (2nd ed.): the hardware/software interface, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 9: S. Peyton Jones and S. Marlow. Secrets of the Glasgow Haskell Compiler Inliner. InImplementation of Declarative Languages, Paris, France, September 1999.
• 10: Niklas Röjemo, Generational Garbage Collection without Temporary Space Leaks for Lazy Functional Languages, Proceedings of the International Workshop on Memory Management, p.145-162, September 27-29, 1995
• 11: Niklas Röjemo , Colin Runciman, Lag, drag, void and use—heap profiling and space-efficient compilation revisited, Proceedings of the first ACM SIGPLAN international conference on Functional programming, p.34-41, May 24-26, 1996, Philadelphia, Pennsylvania, United States
• 12: Colin Runciman , Niklas Röjemo, Heap Profiling for Space Efficiency, Advanced Functional Programming, Second International School-Tutorial Text, p.159-183, August 26-30, 1996
• 13: C. Runciman and N. Rojemo. New dimensions in heap pro~ling. Journal of Functional Programming, 6, 1996.
• 14: C. Runciman and D. Wakeling. Heap profiling of lazy functional programs. Journal of Functional Programming, 3(2):217{245, 1993.
• 15: Patrick M. Sansom , Simon L. Peyton Jones, Profiling Lazy Functional Programs, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.227-239, July 06-08, 1992
• 16: Patrick M. Sansom , Simon L. Peyton Jones, Profiling Lazy Functional Programs, Proceedings of the 1992 Glasgow Workshop on Functional Programming, p.227-239, July 06-08, 1992
• 17: Patrick M. Sansom , Simon L. Peyton Jones, Time and space profiling for non-strict, higher-order functional languages, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.355-366, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199531]
• 18: Manuel Serrano, Bee: an integrated development environment for the Scheme programming language, Journal of Functional Programming, v.10 n.4, p.353-395, July 2000 [doi>10.1017/S0956796800003725]
• 19: Benjamin Zorn, The measured cost of conservative garbage collection, Software—Practice & Experience, v.23 n.7, p.733-756, July 1993 [doi>10.1002/spe.4380230704]
• 20: B. Zorn and P. Hilnger. AMemory Allocation Profiler for C andLisp Programs. In Usenix conference, pages 223-237, 1998.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: SCHEME

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Code generation; Compilers
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

General Terms:
Design, Languages, Measurement, Performance, Theory