Time and space profiling for non-strict, higher-order functional languages

ABSTRACT

We present the first profiler for a compiled, non-strict, higher-order, purely functional language capable of measuring time as well as space usage. Our profiler is implemented in a production-quality optimising compiler for Haskell, has low overheads, and can successfully profile large applications.A unique feature of our approach is that we give a formal specification of the attribution of execution costs to cost centres. This specification enables us to discuss our design decisions in a precise framework. Since it is not obvious how to map this specification onto a particular implementation, we also present an implementation-oriented operational semantics, and prove it equivalent to the specification.

REFERENCES

• 1: AW Appel, BF Duba & DB MacQueen {Nov 1988}, "Profiling in the presence of optimization and garbage collection," Technical Report CS-TR-197-88, Princeton University.
• 2: L. Augustsson , T. Johnsson, The Chalmers lazy ML-compiler, The Computer Journal, v.32 n.2, p.127-141, April 1989 [doi>10.1093/comjnl/32.2.127]
• 3: C Clack, S Clayman & D Parrott{March 1994}, "Lexical Profiling: Theory and Practice," Dept of Computer Science, University College London. To appear in Journal of Functional Programming.
• 4: John Fairbairn , Stuart Wray, TIM: A simple, lazy abstract machine to execute supercombinators, Proc. of a conference on Functional programming languages and computer architecture, p.34-45, October 1987, Portland, Oregon, United States
• 5: SL Graham, PB Kessler & MK McKusick {1983}, "An execution profiler for modular programs," Software m Practice and Experience 13(8), 671-685.
• 6: Paul Hudak , Simon Peyton Jones , Philip Wadler , Brian Boutel , Jon Fairbairn , Joseph Fasel , María M. Guzmán , Kevin Hammond , John Hughes , Thomas Johnsson , Dick Kieburtz , Rishiyur Nikhil , Will Partain , John Peterson, Report on the programming language Haskell: a non-strict, purely functional language version 1.2, ACM SIGPLAN Notices, v.27 n.5, p.1-164, May 1992 [doi>10.1145/130697.130699]
• 7: SA Jarvis{April 1994}, "Profiling Large Scale Lazy Functional Systems," Artificial Intelligence Research Group, University of Durham.
• 8: Y. Kozato , G. P. Otto, Benchmarking real-life image processing programs in lazy functional languages, Proceedings of the conference on Functional programming languages and computer architecture, p.18-27, June 09-11, 1993, Copenhagen, Denmark [doi>10.1145/165180.165187]
• 9: John Launchbury, A natural semantics for lazy evaluation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.144-154, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158618]
• 10: J Launchbury{June 1993b}, "Lazy imperative programming," Proceedings of A CM SIGPLAN Workshop on State in Programming Languages, Copenhagen, Denmark, 46-56. Available as Research Report YALEU/DCS/RR-968, Yale University.
• 11: SL Peyton Jones {April 1992}, "Implementing lazy functional languages on stock hardware: the Spineless Tagless G-machine," Journal of Functional Programming 2(2), 12#-202
• 12: SL Peyton Jones, CV Hall, K Hammond, WD Partain & PL Wadler{March 1993}, "The Glasgow Haskell compiler: a technical overview," Joint Framework for Information Technology (JFIT) Technical Conference Digest, Keele, 249-257.
• 13: C Runciman & N RSjemo{1994}, "New dimensions in heap profiling," Departments of Computer Science, Chalmers University and University of York.
• 14: C Runciman & D Wakeling {April 1993}, "Heap profiling of lazy functional programs," Journal of Functional Programming 3(2), 217-245.
• 15: PM Sansom {1994a}, "Time profiling a lazy functional compiler," in Functional Programming, Glasgow 1993, K Hammond & J O'Donneli, eds., Workshops in Computing, Springer Verlag.
• 16: PM Sansom {Sept 1994b}, "Execution profiling for non-strict functional languages," PhD thesis, Research Report FP-1994-09, Dept of Computing Science, University of Glasgow. (ftp://ftp. dcs. glasgow, ac. uk/pub/ glasgow-fp/t ech.report s/ FP- 94- 09_ex ecut ~ on-prof ~ling. ps. Z ).
• 17: PM Sansom #z SL Peyton Jones{Nov 1994}, "Time and space profiling for non-strict, higher-order functional languages," Research Report FP-1994-10, Dept of Computing Science, University of Glasgow. (ftp: //ftp. dcs. glasgow, ac. uk/pub/ glasgow-fp/t ech_repor t s/ FP-94-10_t imespace-prof il ing. ps. Z).
• 18: P Sestoft {April 1994}, "Deriving a Lazy Abstract Machine," Dept of Computer Science, Techm'cal University of Denmark.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

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

          Nouns: Haskell
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Operational semantics

General Terms:
Algorithms, Languages, Performance