Optimally profiling and tracing programs

ABSTRACT

This paper describes algorithms for inserting monitoring code to profile and trace programs. These algorithms greatly reduce the cost of measuring programs with respect to the commonly used technique of placing code in each basic block. Program profiling counts the number of times each basic block in a program executes. Instruction tracing records the sequence of basic blocks traversed in a program execution. The algorithms optimize the placement of counting/tracing code with respect to the expected or measured frequency of each block or edge in a program's control-flow graph. We have implemented the algorithms in a profiling/tracing tool, and they substantially reduce the overhead of profiling and tracing.We also define and study the hierarchy of profiling problems. These problems have two dimensions: what is profiled (i.e., vertices (basic blocks) or edges in a control-flow graph) and where the instrumentation code is placed (in blocks or along edges). We compare the optimal solutions to the profiling problems and describe a new profiling problem: basic-block profiling with edge counters. This problem is important because an optimal solution to any other profiling problem (for a given control-flow graph) is never better than an optimal solution to this problem. Unfortunately, finding an optimal placement of edge counters for vertex profiling appears to be a hard problem in general. However, our work shows that edge profiling with edge counters works well in practice because it is simple and efficient and finds optimal counter placements in most cases. Furthermore, it yields more information than a vertex profile. Tracing also benefits from placing instrumentation code along edges rather than on vertices.

REFERENCES

• 1: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Thomas Ball , James R. Larus, Optimally profiling and tracing programs, Proceedings of the 19th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.59-70, January 19-22, 1992, Albuquerque, New Mexico, United States [doi>10.1145/143165.143180]
• 3: Thomas Ball , James R. Larus, Branch prediction for free, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.300-313, June 21-25, 1993, Albuquerque, New Mexico, United States
• 4: Jong-Deok Choi , Barton P. Miller , Robert H. B. Netzer, Techniques for debugging parallel programs with flowback analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.491-530, Oct. 1991 [doi>10.1145/115372.115324]
• 5: Robert F. Cmelik , Shing I. Kong , David R. Ditzel , Edmund J. Kelly, An analysis of MIPS and SPARC instruction set utilization on the SPEC benchmarks, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.290-302, April 08-11, 1991, Santa Clara, California, United States
• 6: Joseph A. Fisher , John R. Ellis , John C. Ruttenberg , Alexandru Nicolau, Parallel processing: a smart compiler and a dumb machine, Proceedings of the 1984 SIGPLAN symposium on Compiler construction, p.37-47, June 17-22, 1984, Montreal, Canada
• 7: Ira R. Forman, On the time overhead of counters and traversal markers, Proceedings of the 5th international conference on Software engineering, p.164-169, March 09-12, 1981, San Diego, California, United States
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: GOLDBERG, A. 1991. Reducing overhead in counter-based execution profiling. Tech. Rep. CSL-TR- 91-495, Computer Systems Lab., Stanford Univ., Stanford, Calif., Oct.
• 10: A. J. Goldberg , J. L. Hennessy, Mtool: An Integrated System for Performance Debugging Shared Memory Multiprocessor Applications, IEEE Transactions on Parallel and Distributed Systems, v.4 n.1, p.28-40, January 1993 [doi>10.1109/71.205651]
• 11: GRAHAM, S. L., KESSLER, P. B., AND MCKUSICK, M. K. 1983. An execution profiler for modular programs. Softw. Pratt. Exper. 13, 671-685.
• 12: Jeff L. Kennington , Richard V. Helgason, Algorithms for Network Programming, John Wiley & Sons, Inc., New York, NY, 1980
• 13: Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
• 14: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 15: KNUTH, D. E., AND STEVENSON, F, R, 1973. Optimal measurement points for program fre-quency counts. BIT 13, 313-322.
• 16: J. R. Larus, Abstract execution: a technique for efficiently tracing programs, Software—Practice & Experience, v.20 n.12, p.1241-1258, Dec. 1990 [doi>10.1002/spe.4380201205]
• 17: Computer Staff, Efficient program tracing, Computer, v.26 n.5, p.52-61, May 1993 [doi>10.1109/2.211900]
• 18: James R. Larus , Thomas Ball, Rewriting executable files to measure program behavior, Software—Practice & Experience, v.24 n.2, p.197-218, Feb. 1994 [doi>10.1002/spe.4380240204]
• 19: MAHESHWARI, S. 1976. Traversal marker placement problems are NP-complete. Rep. CU-CS-092- 76, Dept. of Computer Science, Univ of Colorado, Boulder, Colo.
• 20: Scott McFarling, Procedure merging with instruction caches, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.71-79, June 24-28, 1991, Toronto, Ontario, Canada
• 21: MENDOZA, K., ED 1989. Systems performance evaluation cooperative. SPEC Newsl. 1, 1 (Fall).
• 22: MIPS COMPUTERSYSTEMS. 1990. UMIPS-V Reference Manual (pixie and pixstats). MIPS Com-puter Systems, Sunnyvale, Calif.
• 23: W. G. Morris, CCG: a prototype coagulating code generator, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.45-58, June 24-28, 1991, Toronto, Ontario, Canada
• 24: Karl Pettis , Robert C. Hansen, Profile guided code positioning, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.16-27, June 1990, White Plains, New York, United States
• 25: PROBERT, R. L. 1975. Optimal insertion of software probes in well-dehmited programs. IEEE Trans. Softa,. Eng. SE-8, 1(Jan.), 34-42
• 26: RAMAMOORTHY, C. V., KIM, K. H., AND CHEN, W. T. 1975 Optimal placement of software monitors aiding systematic testing, IEEE Trans. Softw. Eng. SE-1, 4 (Dec.), 403 -410.
• 27: M. V. S. Ramanath , Marvin Solomon, Optimal code for control structures, Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.82-94, January 25-27, 1982, Albuquerque, Mexico [doi>10.1145/582153.582163]
• 28: Alan Dain Samples, Profile-driven compilation, University of California at Berkeley, Berkeley, CA, 1992
• 29: V. Sarkar, Determining average program execution times and their variance, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.298-312, June 19-23, 1989, Portland, Oregon, United States
• 30: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 31: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 32: David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Tracing

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Programmer workbench**
      D.2.5 Testing and Debugging
          Subjects: Diagnostics

General Terms:
Algorithms, Measurement

Keywords:
control-flow graph, instruction tracing, instrumentation, profiling