Figure 2. The gprof and causal profiles for the code in Figure 1. In the causal profile, the y-axis shows the program speedup that would be
achieved by speeding up each line of code by the percentage on the x-axis. The gray area shows standard error. Gprof reports that fa and fb
comprise similar fractions of total runtime, but optimizing fa will improve performance by at most 4.5%, and optimizing fb would have no
effect on performance. The causal profile predicts both outcomes within 0.5%.
Causal profile for example.cpp
2. It presents Coz, a causal profiler that works on unmodified Linux binaries. It describes Coz’s implementation
(Section 3), and demonstrates its efficiency and effec-
Conventional profile for example.cpp
Ts/call calls name
55.20 a() 1 7.20 7.20
45.19 b() 1 5.89 13.09
time self children called name
55.0 7.20 0.00 a()
45.0 5.89 0.00 b()
line 2 (a) line 5 (b)
0% 25% 50% 75% 100%0% 25% 50% 75% 100%
(b) Causal profile for example.cpp (a) A gprof profile for example.cpp
92 COMMUNICATIONS OF THE ACM | JUNE 2018 | VOL. 61 | NO. 6
mimic the effect of optimizing a specific fragment of code
by a fixed amount. Fragments could be functions, basic
blocks, source lines. A fragment is virtually sped up by
inserting pauses to slow all other threads each time the
fragment runs. The key insight is that this slowdown has the
same relative effect as running that fragment faster, thus
“virtually” speeding it up. Figure 3 shows the equivalence of
virtual and actual speedups.
Figure 3. An illustration of virtual speedup: (a) shows the original
execution of two threads running functions f and g; (b) shows the
effect of a actually speeding up f by 40%; (c) shows the effect of
virtually speeding up f by 40%. Each time f runs in one thread, all
other threads pause for 40% of f’s original execution time (shown as
ellipsis). The difference between the runtime in (c) and the original
runtime plus nf · d—the number of times f ran times the delay size—
is the same as the effect of actually optimizing f.
Each performance experiment measures the effect of
virtually speeding up a fragment of code by a specific amount.
Speedups are measured in percent change; a speedup of 0%
means the fragment’s runtime is unchanged, while 75%
means the fragment takes a quarter of its original runtime.
By conducting many performance experiments over a range
of virtual speedups, a causal profiler can predict the effect
of any potential optimization on a program’s performance.
Illustration of virtual speedup
(a) Original program
(b) Actual speedup
Causal profiling further departs from conventional profiling by making it possible to view the effect of optimizations
on both throughput and latency. To profile throughput,
developers specify a progress point, indicating a line in the
code that corresponds to the end of a unit of work. For example, a progress point could be the point at which a transaction concludes, when a web page finishes rendering, or
when a query completes. A causal profiler then measures the
rate of visits to each progress point to determine any potential optimization’s effect on throughput. To profile latency,
programmers instead place progress points at the start and
end of an event of interest, such as when a transaction begins
and completes. A causal profiler then reports the effect of
potential optimizations on the average latency between
those two progress points.
(c) Virtual speedup
effect of optimizing by d f
Coz imposes low execution overhead. When it is possible, we
compare the observed performance improvements to Coz’s
predictions. In each case, we find that the real effect of our
optimization matches Coz’s prediction.
To demonstrate the effectiveness of causal profiling, we
have developed Coz, a causal profiler for Linux. We show that
causal profiling accurately predicts optimization opportunities, and that it is effective at guiding optimization efforts. We
apply Coz to Memcached, SQLite, and the extensively studied
PARSEC benchmark suite. Guided by Coz’s output, we improve
the performance of Memcached by 9%, SQLite by 25%, and six
PARSEC applications by as much as 68%. Our changes typically
require modifying under 10 lines of code. We also show that
1. 1. Contributions
This paper makes the following contributions:
1. It presents causal profiling, which identifies code
where optimizations will have the largest impact.
Using virtual speedups and progress points, causal profiling directly measures the effect of potential optimizations on both throughput and latency (Section 2).