Ball and Larus describe algorithms they developed for profiling and tracing programs. The components to be analyzed can be either the vertices of the program graph or its edges. The profile counts for the vertices can be deduced from those for the edges but not conversely. For an edge-based profile, not all edges need counters; in particular, the full set of edge counts can be deduced even if all edges in a spanning tree of the graph are left without counters.

A minimum-cost profile for the vertices, computed using the edges, is always at least as cheap as any other profile, but finding such a profile is a hard problem in general. For well-structured programs, a minimum-cost profile for the edges is just as good and yields both vertex and edge profiles, but for other programs a vertex profile may be cheaper.

The authors present algorithms for computing both edge profiles and vertex profiles, computed using edge counts. (For a vertex profile of an ill-structured program, not all edge counts may be needed.) They compare experimentally the cost of profiling using these algorithms with the cost of profiling edges exhaustively and show that the algorithms dramatically reduce the overhead introduced by profiling.

An optimal solution to the edge-profiling problem is also an optimal solution to the tracing problem for single procedures, but multiple procedures need additional treatment. The authors present a way of handling multiple procedures using “blocking witnesses.”