New Technical Report: "Optimally Profiling and Tracing Programs" (James Larus)
Tue, 10 Sep 1991 17:56:35 GMT

          From comp.compilers

Related articles
New Technical Report: "Optimally Profiling and Tracing Programs" (1991-09-10)
| List of all articles for this month |

Newsgroups: comp.arch,comp.compilers,comp.lang.misc
From: (James Larus)
Keywords: performance, experiment, FTP, report
Organization: University of Wisconsin CS Dept.
Date: Tue, 10 Sep 1991 17:56:35 GMT

A postscript version of this technical report is available for anonymous
ftp from in pub/

Optimally Profiling and Tracing Programs

Thomas Ball James R. Larus

Computer Sciences Department
University of Wisconsin--Madison
1210 W. Dayton St.
Madison, WI 53706 USA

Technical Report #1031

This paper presents two algorithms for inserting monitoring code to
profile and trace programs. These algorithms greatly reduce the cost of
measuring programs. Profiling, which counts the number of times each
basic block in a program executes, is widely used to measure instruction
set utilization of computers, identify program bottlenecks, and estimate
program execution times for code optimization. Instruction traces are the
basis for trace-driven simulation and analysis and are used also in
trace-driven debugging.

The profiling algorithm instruments a program for profiling by choosing a
placement of counters that is optimized--and frequently optimal--with
respect to the expected or measured execution frequency of each basic
block and branch in the program. The tracing algorithm instruments a
program to obtain a subsequence of the basic block trace--whose length is
optimized with respect to the program's execution--from which the entire
trace can be efficiently regenerated.

Both algorithms have been implemented and produce a substantial
improvement over previous approaches, as the performance figures in this
paper show. The profiling algorithm reduces the number of counters by a
factor of two and the number of counter increments by a factor of three.
The tracing algorithm reduces the file size and overhead of an already
highly optimized tracing system by 20-40%.

[An abridged version of this paper will appear in the 19th Symposium on
Principles of Programming Languages (January 19-22, 1992).]

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.