Optimally profiling and tracing programs
Thomas Ball, James R. Larus · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · 1992
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.
Cited by 165 works. doi:10.1145/143165.143180
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- The Art of Computer Programming
- The C++ Programming Language
- Data Structures and Network Algorithms
- The C Programming Language
- Cache Memories
- Algorithms for network programming
- An execution profiler for modular programs
- Profile guided code positioning
- Parallel processing