C OZ: Finding Code that Counts with Causal Proﬁling
Charlie Curtsinger ∗Emery D. Berger

Department of Computer Science
Grinnell College
curtsinger@cs.grinnell.edu

College of Information and Computer Sciences
University of Massachusetts Amherst
emery@cs.umass.edu

Abstracttance, they often do not have enough of an impact on performance to meet programmers’ demands [10]. Programmers
seeking to increase the throughput or responsiveness of theirapplications thus must resort to manual performance tuning.
Manually inspecting a program to ﬁnd optimization opportunities is impractical, so developers use proﬁlers. Conventional proﬁlers rank code by its contribution to total execution time. Prominent examples include oproﬁle, perf, andgprof [17, 27, 29]. Unfortunately, even when a proﬁler accurately reports where a program spends its time, this information can lead programmers astray. Code that runs for along time is not necessarily a good choice for optimization.
For example, optimizing code that draws a loading animation
during a ﬁle download will not make the program run faster,even though this code runs just as long as the download.
This phenomenon is not limited to I/O operations. Figure 1
shows a simple program that illustrates the shortcomings ofexisting proﬁlers, along with its gprof proﬁle in Figure 2a.
This program spawns two threads, which invoke functions
fa and fb respectively. Most proﬁlers will report that thesefunctions comprise roughly half of the total execution time.
Other proﬁlers may report that fa is on the critical path, or thatthe main thread spends roughly equal time waiting for fa andfb [23]. While accurate, all of this information is potentiallymisleading. Optimizing fa away entirely will only speed up
the program by 4.5% because fb becomes the new criticalpath.

Improving performance is a central concern for softwaredevelopers. To locate optimization opportunities, developers
rely on software proﬁlers. However, these proﬁlers only report
where programs spent their time: optimizing that code may
have no impact on performance. Past proﬁlers thus both waste
developer time and make it difﬁcult for them to uncoversigniﬁcant optimization opportunities.
This paper introduces causal proﬁling. Unlike past proﬁling approaches, causal proﬁling indicates exactly where
programmers should focus their optimization efforts, andquantiﬁes their potential impact. Causal proﬁling works byrunning performance experiments during program execution.
Each experiment calculates the impact of any potential optimization by virtually speeding up code: inserting pausesthat slow down all other code running concurrently. The key
insight is that this slowdown has the same relative effect asrunning that line faster, thus “virtually” speeding it up.
We present C OZ, a causal proﬁler, which we evaluate on
a range of highly-tuned applications: Memcached, SQLite,and the PARSEC benchmark suite. C OZ identiﬁes previously
unknown optimization opportunities that are both signiﬁcantand targeted. Guided by C OZ, we improve the performanceof Memcached by 9%, SQLite by 25%, and accelerate six
PARSEC applications by as much as 68%; in most cases,
these optimizations involve modifying under 10 lines of code.

1.

Introduction

Improving performance is a central concern for softwaredevelopers. While compiler optimizations are of some assis-

example.cpp
1∗ This work was initiated and partially conducted while Charlie Curtsinger

2

was a PhD student at the University of Massachusetts Amherst.

4

3
5
6

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor proﬁt or commercial advantage and that copies bear this notice and the full citationon the ﬁrst page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior speciﬁc permission
and/or a fee. Request permissions from permissions@acm.org.
SOSP’15, October 4–7, 2015, Monterey, CA.
Copyright is held by the owner/author(s). Publication rights licensed to ACM.
ACM 978-1-4503-3834-9/15/10. . . $15.00.
http://dx.doi.org/10.1145/2815400.2815409

7
8
9
10
11

void a() { // ˜6.7 secondsfor(volatile size_t x=0; x<2000000000; x++) {}}void b() { // ˜6.4 secondsfor(volatile size_t y=0; y<1900000000; y++) {}}int main() {// Spawn both threads and wait for them.
thread a_thread(a), b_thread(b);a_thread.join(); b_thread.join();}Figure 1: A simple multithreaded program that illustrates theshortcomings of existing proﬁlers. Optimizing fa will improve
performance by no more than 4.5%, while optimizing fb would
have no effect on performance.

184

Conventional Proﬁle for example.cpp
cumulative
seconds
7.20
13.09% timeself

self
seconds
7.20
5.89

children

calls
1
1

self
Ts/calltotal
Ts/callline 2 (a)
name
a()
b()

Program Speedup

%
time
55.20
45.19

Causal Proﬁle For example.cpp

calledname<spontaneous>
55.0
7.20
0.00
a()
-------------------------------------------------<spontaneous>
45.0
5.89
0.00
b()

4%

line 5 (b)●●● ● ●● ●●● ●●●● ●● ●

6%

●
●● ●

2%
0%

●

0%

25% 50% 75% 100% 0%

25% 50% 75% 100%

Line Speedup(a) A conventional proﬁle for example.cpp, collected with gprof(b) Causal proﬁle for example.cpp

Figure 2: The gprof and causal proﬁles for the code in Figure 1. In the causal proﬁle, the y-axis shows the program speedup that would beachieved 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 noeffect on performance. The causal proﬁle predicts both outcomes within 0.5%.

Conventional proﬁlers do not report the potential impact of
optimizations; developers are left to make these predictions
based on their understanding of the program. While thesepredictions may be easy for programs as simple as the one
in Figure 1, accurately predicting the effect of a proposed
optimization is nearly impossible for programmers attempting
to optimize large applications.
This paper introduces causal proﬁling, an approach that
accurately and precisely indicates where programmers should
focus their optimization efforts, and quantiﬁes their potential
impact. Figure 2b shows the results of running C OZ, ourprototype causal proﬁler. This proﬁle plots the hypothetical
speedup of a line of code (x-axis) versus its impact on
execution time (y-axis). The graph correctly shows that
optimizing either fa or fb in isolation would have little effect.
A causal proﬁler conducts a series of performance experiments to empirically observe the effect of a potential optimization. Of course it is not possible to automatically speed
up any line of code by an arbitrary amount. Instead, a causal
proﬁler uses the novel technique of virtual speedups to mimic
the effect of optimizing a speciﬁc line of code by a ﬁxed
amount. A line is virtually sped up by inserting pauses toslow all other threads each time the line runs. The key insightis that this slowdown has the same relative effect as runningthat line faster, thus “virtually” speeding it up. Figure 3 showsthe equivalence of virtual and actual speedups.
Each performance experiment measures the effect of virtually speeding up one line by a speciﬁc amount. By conducting many performance experiments over the range of virtual
speedup from between 0% (no change) and 100% (the line iscompletely eliminated), a causal proﬁler can predict the effectof any potential optimization on a program’s performance.
Causal proﬁling further departs from conventional proﬁling by making it possible to view the effect of optimizations
on both throughput and latency. To proﬁle throughput, developers specify a progress point, indicating a line in the codethat corresponds to the end of a unit of work. For example, aprogress point could be the point at which a transaction con-cludes, when a web page ﬁnishes rendering, or when a querycompletes. A causal proﬁler then measures the rate of visits toeach progress point to determine any potential optimization’s
effect on throughput. To proﬁle latency, programmers instead
place two progress points that correspond to the start andend of an event of interest, such as when a transaction begins
and completes. A causal proﬁler then reports the effect ofpotential optimizations on the average latency between those
two progress points.
To demonstrate the effectiveness of causal proﬁling, wehave developed C OZ, a causal proﬁler for Linux. We showthat C OZ imposes low execution time overhead (mean: 17%,min: 0.1%, max: 65%), making it substantially faster than
gprof (up to 6× overhead).
We show that causal proﬁling accurately predicts optimization opportunities, and that it is effective at guiding optimization efforts. We apply C OZ to Memcached, SQLite, and theextensively studied PARSEC benchmark suite. Guided by
C OZ’s output, we optimized the performance of Memcached
by 9%, SQLite by 25%, and six PARSEC applications by asmuch as 68%. These optimizations typically involved modifying under 10 lines of code. When possible to accurately
measure the size of our optimizations on the line(s) identiﬁed
by C OZ, we compare the observed performance improvements to C OZ’s predictions: in each case, we ﬁnd that the realeffect of our optimization matches C OZ’s prediction.
Contributions
This paper makes the following contributions:
1. It presents causal proﬁling, which identiﬁes code where
optimizations will have the largest impact. Using virtual
speedups and progress points, causal proﬁling directly
measures the effect of potential optimizations on boththroughput and latency (§2).
2. It presents C OZ, a causal proﬁler that works on unmodiﬁed Linux binaries. It describes C OZ’s implementation(§3), and demonstrates its efﬁciency and effectiveness at
identifying optimization opportunities (§4).

185

Causal Proﬁling Overview

Illustration of Virtual Speedup(a) Original ProgramThis section describes the major steps in collecting, processing, and interpreting a causal proﬁle with C OZ, our prototypecausal proﬁler.

f

t1
t2

Proﬁler startup. A user invokes C OZ using a command of
the form coz run --- <program> <args>. At the
beginning of the program’s execution, C OZ collects debug
information for the executable and all loaded libraries. Users
may specify ﬁle and binary scope, which restricts C OZ’s
experiments to speedups in the speciﬁed ﬁles. By default,
C OZ will consider speedups in any source ﬁle from the main
executable. C OZ builds a map from instructions to sourcelines using the program’s debug information and the speciﬁed
scope. Once the source map is constructed, C OZ creates a
proﬁler thread and resumes normal execution.

g

g

f

f
g
original runtime(b) Actual Speedup

t1
t2

f

g

g

f

f
original runtime+
nf · dgeffect of optimizing(c) Virtual Speedup

Experiment initialization. C OZ’s proﬁler thread begins anexperiment by selecting a line to virtually speed up, and arandomly-chosen percent speedup. Both parameters must be
selected randomly; any systematic method of exploring lines
or speedups could lead to systematic bias in proﬁle results.
One might assume that C OZ could exclude lines or virtual
speedup amounts that have not shown a performance effectearly in previous experiments, but prioritizing experiments
based on past results would prevent C OZ from identifying
an important line if its performance only matters after somewarmup period. Once a line and speedup have been selected,
the proﬁler thread saves the number of visits to each progresspoint and begins the experiment.

t1

f

t2

g…g

f

g

…

2.

f

f

by d

f
g… g

Figure 3: An illustration of virtual speedup: (a) shows the original
execution of two threads running functions f and g; (b) shows theeffect of a actually speeding up f by 40%; (c) shows the effect ofvirtually speeding up f by 40%. Each time f runs in one thread, allother 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 delaysize—is the same as the effect of actually optimizing f.

Producing a causal proﬁle. After an application has been
proﬁled with C OZ, the results of all the performance experiments can be combined to produce a causal proﬁle. Eachexperiment has two independent variables: the line chosen
for virtual speedup and the amount of virtual speedup. C OZ
records the dependent variable, the rate of visits to eachprogress point, in two numbers: the total number of visits
to each progress point and the effective duration of the experiment (the real runtime minus the total length of all pauses).
Experiments with the same independent variables can be
combined by adding the progress point visits and experiment
durations.
Once experiments have been combined, C OZ groups experiments by the line that was virtually sped up. Any linesthat do not have a measurement of 0% virtual speedup are
discarded; without this baseline measurement we cannot compute a percent speedup relative to the original program. Measuring this baseline separately for each line guarantees thatany line-dependent overhead from virtual speedups, such as
the additional cross-thread communication required to insert
delays when a frequently-executed line runs, will not skew
proﬁle results. By default, C OZ will also discard any lines
with fewer than 5 different virtual speedup amounts (a plotthat only shows the effect of a 75% virtual speedup is notparticularly useful). Finally, we compute the percent program

Applying a virtual speedup. Every time the proﬁled program creates a thread, C OZ begins sampling the instruction
pointer from this thread. C OZ processes samples within eachthread to implement a sampling version of virtual speedups.
In Section 3.4, we show the equivalence between the virtual
speedup mechanism shown in Figure 3 and the sampling
approach used by C OZ. Every time a sample is available, athread checks whether the sample falls in the line of code
selected for virtual speedup. If so, it forces other threads topause. This process continues until the proﬁler thread indicates that the experiment has completed.
Ending an experiment. C OZ ends the experiment after a
pre-determined time has elapsed. If there were too few visits
to progress points during the experiment—ﬁve is the default
minimum—C OZ doubles the experiment time for the restof the execution. Once the experiment has completed, theproﬁler thread logs the results of the experiment, including
the effective duration of the experiment (runtime minus thetotal inserted delay), the selected line and speedup, and thenumber of visits to all progress points. Before beginning thenext experiment, C OZ will pause for a brief cooloff period toallow any remaining samples to be processed before the next
experiment begins.

186speedup for each grouped experiment as the percent change inrate of visits to each progress point over the baseline (virtual
speedup of 0%). C OZ then plots the resulting table of line
and program speedups for each line, producing the proﬁlegraphs shown in this paper.

necessary [14]. Note that debug information is available
even for optimized code, and most Linux distributions offer
packages that include this information for common libraries.
By default, C OZ will only collect debug information forthe main executable. This means C OZ will only test potential
optimizations in the main program’s source ﬁles. Users can
specify a source scope to control which source ﬁles C OZ will
select lines from to evaluate potential optimizations. Likewise,
users can specify a binary scope to control which executables
and libraries will be proﬁled. Users should use these scope
options to specify exactly which code they are willing or able
to change to improve their program’s performance.

Interpreting a causal proﬁle. Once causal proﬁle graphs
have been generated, it is up to the user to interpret them andmake an educated choice about which lines may be possible
to optimize. To help the user identify important lines, C OZ
sorts the graphs by the slope of their linear regression. Steep
upward slopes indicate a line where optimizations will generally have a positive impact, while a ﬂat line indicates that
optimizing this line will not improve program performance.
C OZ also ﬁnds lines with a steep downward slope, meaning
any optimization to this line will actually hurt performance.
This downward sloping proﬁle is a strong indication of contention; the line that was virtually sped up interferes with theprogram’s critical path, and optimizing this line increases theamount of interference. This phenomenon is surprisingly common, and can often result in signiﬁcant optimization opportunities. In our evaluation we identify and ﬁx contention issues
in three applications: fluidanimate, streamcluster,and memcached, resulting in speedups of 37.5%, 68.4%,
and 9.4% respectively.

3.

3.2

C OZ uses a dedicated proﬁler thread to coordinate performance experiments. This thread is responsible for selecting a line to virtually speed up, selecting the size of the virtual speedup, measuring the effect of the virtual speedup on
progress points, and writing proﬁler output.
Starting a performance experiment. A single proﬁler
thread, created during program initialization, coordinates
performance experiments. Before an experiment can begin,
the proﬁler selects a source line to virtually speed up. To dothis, all program threads sample their instruction pointersand map these addresses to source lines. The ﬁrst thread tosample a source line that falls within the speciﬁed proﬁling
scope sets this as the line selected for virtual speedup.
Once the proﬁler receives a valid line from one of the
program’s threads, it chooses a random virtual speedup between 0% and 100%, in multiples of 5%. For any given virtual
speedup, the effect on program performance is 1 − pp0s , where
p0 is the period between progress point visits with no virtual
speedup, and ps is the same period measured with some virtual speedup s. Because p0 is required to compute program
speedup for every ps , a virtual speedup of 0 is selected with
50% probability. The remaining 50% is distributed evenly
over the other virtual speedup amounts.
Lines for virtual speedup must be selected randomly toprevent bias in the results of performance experiments. A
seemingly reasonably (but invalid) approach would be to
begin conducting performance experiments with small virtual speedups, gradually increasing the speedup until it nolonger has an effect on program performance. However, thisapproach may both over- and under-state the impact of optimizing a particular line if its impact varies over time.
For example, a line that has no performance impact during
a program’s initialization would not be measured later in execution, when optimizing it could have signiﬁcant performance
beneﬁt. Conversely, a line that only affects performance during initialization would have exaggerated performance impact
unless future experiments re-evaluate virtual speedup values
for this line during normal execution. Any systematic approach to exploring the space of virtual speedup values could
potentially lead to systematic bias in the proﬁle output.

Implementation

This section describes C OZ’s basic functionality and implementation. We brieﬂy discuss the core mechanisms required
to support proﬁling unmodiﬁed Linux x86-64 executables,
along with implementation details for each of the key components of a causal proﬁler: performance experiments, progresspoints, and virtual speedups.
3.1

Performance Experiment Implementation

Core Mechanisms

C OZ uses sampling to implement both virtual speedups
and progress points. When a user starts a program withthe coz command, C OZ injects a proﬁling runtime library
into the program’s address space using LD PRELOAD. Thisruntime library creates a dedicated proﬁler thread to run
performance experiments, but also intercepts each thread
startup and shutdown to start and stop sampling in the threadusing the perf even API. Using the perf event API,C OZ collects both the current program counter and user-spacecall stack from each thread every 1ms. To keep overhead low,
C OZ processes samples in batches of ten by default (every10ms). Processing samples more frequently is unlikely to
improve accuracy, as the additional overhead would distort
program execution.
Attributing samples to source locations. C OZ uses DWARF
debug information to map sampled program counter values tosource locations. The proﬁled program does not need to contain DWARF line information; C OZ will use the same search
procedure as GDB to locate external debug information if

187

Once a line and speedup amount have been selected, C OZ
saves the current values of all progress point counters andbegins the performance experiment.

Little’s Law holds under a wide variety of circumstances,and is independent of the distributions of the arrival rate andservice time. The key requirement is that Little’s Law only
holds when the system is stable: the arrival rate cannot exceed
the service rate. Note that all usable systems are stable: if asystem is unstable, its latency will grow without bound since
the system will not be able to keep up with arrivals.

Running a performance experiment. Once a performanceexperiment has started, each of the program’s threads processes samples and inserts delays to perform virtual speedups.
After the pre-determined experiment time has elapsed, theproﬁler thread logs the end of the experiment, including thecurrent time, the number and size of delays inserted for virtual speedup, the running count of samples in the selected
line, and the values for all progress point counters. After aperformance experiment has ﬁnished, C OZ waits until all
samples collected during the current experiment have beenprocessed. By default, C OZ will process samples in groupsof ten, so this pause time is just ten times the sampling rateof 1ms. Lengthening this cooloff period will reduce C OZ’s
overhead by inserting fewer delays at the cost of increased
proﬁling time to conduct the same number of performanceexperiments.
3.3

3.4

Virtual Speedup Implementation

A critical component of any causal proﬁler is the ability tovirtually speed up any fragment of code. A naive implementation of virtual speedups is shown in Figure 3; each time thefunction f runs, all other threads are paused brieﬂy. If f has
an average runtime of t¯f each time it is called and threads arepaused for time d each time f runs, then f has an effective
average runtime of t¯f − d.
If the real runtime of f was t¯f − d, but we forced every
thread in the program to pause for time d after f ran (including the thread that just executed f) we would measure
the same total runtime as with a virtual speedup. The only
difference between virtual speedup and a real speedup withthese additional pauses is that we use the time d to allow one
thread to ﬁnish executing f. The pauses inserted for virtual
speedup increase the total runtime by nf · d, where nf is thetotal number of times f by any thread. Subtracting nf ·d fromthe total runtime with virtual speedup gives us the execution
time we would measure if f had runtime tf − d.

Progress Point Implementation

C OZ supports three mechanisms for monitoring progresspoints: source-level, breakpoint, and sampled.
Source-level progress points. Source-level progress points
are the only progress points that require program modiﬁcation.
To indicate a source-level progress point, a developer simply
inserts the COZ PROGRESS macro in the program’s sourcecode at the appropriate location.

Implementing virtual speedup with sampling. The previous discussion of virtual speedups assumes an implementation where every time a speciﬁc line of code executes all otherthreads instantaneously pause for a very brief time (a fractionof the time require to run a single line). Unfortunately, thisapproach would incur prohibitively high overhead that would
distort program execution, making the proﬁle useless. Instead,C OZ periodically samples the program counter and counts
samples that fall in the line selected for virtual speedup. Then,other threads are delayed proportionally to the number ofsamples. The number of samples in the selected line, s, isapproximatelyn · t̄s≈(1)P
where P is the period of time between samples, t̄ is theaverage time required to run the selected line once, and n
is the number of times the selected line is executed.
In our original model of virtual speedups, delaying otherthreads by time d each time the selected line is executed
has the effect of shortening this line’s runtime by d. With
sampling, only some executions of the selected line will result
in delays. The effective runtime of the selected line whensampled is t̄ − d, while executions of the selected line that are
not sampled simply take time t̄. The effective average time to
run the selected line isBreakpoint progress points. Breakpoint progress points
are speciﬁed at the command line. C OZ uses the Linux
perf event API to set a breakpoint at the ﬁrst instruction
in a line speciﬁed in the proﬁler arguments.
Sampled progress points. Sampled progress points are
speciﬁed on the command line. However, unlike source-leveland breakpoint progress points, sampled progress points do
not keep a count of the number of visits to the progress point.
Instead, sampled progress points count the number of samples
that fall within the speciﬁed line. As with virtual speedups,
the percent change in visits to a sampled progress point canbe computed even when exact counts are unknown.
Measuring latency. Source-level and breakpoint progresspoints can also be used to measure the impact of an optimization on latency rather than throughput. To measure latency, adeveloper must specify two progress points: one at the start ofsome operation, and the other at the end. The rate of visits tothe starting progress point measures the arrival rate, and thedifference between the counts at the start and end points tells
us how many requests are currently in progress. By denoting
L as the number of requests in progress and λ as the arrivalrate, we can solve for the average latency W via Little’s Law,
which holds for nearly any queuing system: L = λW [30].
Rewriting Little’s Law, we then compute the average latency
as L/λ.

t̄e =

188

(n − s) · t̄ + s · (t̄ − d)
.
n

(2)

Using (1), this reduces to
t̄e =

t̄
n · t̄ · (1 − Pt̄ ) + n·d
P · (t̄ − d)= t̄ · (1 − )nPPotentially unblocking calls
pthread mutex unlock
unlock a mutex
pthread cond signal
wake one waiter on a c.v.
pthread cond broadcast wake all waiters on c.v.
pthread barrier wait
wait at a barrier
pthread killsend signal to a thread
pthread exit
terminate this thread(3)

The relative difference between t and t̄e , the amount of virtual
speedup, is simply
Δt̄ = 1 −

t̄e
d
= .
P
t̄

Table 1: C OZ intercepts POSIX functions that could wake a blocked
thread. To ensure correctness of virtual speedups, C OZ forces threads
to execute any unconsumed delays before invoking any of thesefunctions and potentially waking another thread.

(4)

This result lets C OZ virtually speed up selected lines by
a speciﬁc amount without instrumentation. Inserting a delaythat is one quarter of the sampling period will virtually speed
up the selected line by 25%.

Potentially blocking calls
pthread mutex lock
lock a mutex
pthread cond wait
wait on a condition variable
pthread barrier wait wait at a barrier
pthread join
wait for a thread to complete
sigwaitwait for a signal
sigwaitinfo
wait for a signal
sigtimedwait
wait for a signal (with timeout)
sigsuspend
wait for a signal

Pausing other threads. When one thread receives a sample
in the line selected for virtual speedup, all other threads must
pause. Rather than using POSIX signals, which would haveprohibitively high overhead, C OZ controls inter-thread pausing using counters. The ﬁrst counter, shared by all threads,
records the number of times each thread should have paused
so far. Each thread has a local counter of the number of times
that thread has already paused. Whenever a thread’s local
count of pauses is less than the number of required pausesin the global counter, a thread must pause (and increment its
local counter). To signal all other threads to pause, a thread
simply increments both the global counter and its own local counter. Every thread checks if pauses are required after
processing its own samples.

Table 2: C OZ intercepts POSIX functions that could block waiting
for a thread, instrumenting them to update delay counts before andafter blocking.

unlocked that mutex. If the unlocking thread has executed all
the required delays, then the blocked thread has effectively
already been delayed; it should not insert any additional
delays after unblocking.
To correctly handle suspended threads, a causal proﬁler
must follow a simple rule: If a suspended thread resumes
execution because of another thread, the suspended thread
should be “credited” for any delays inserted in the thread
responsible for waking it up. Otherwise, the thread should
insert all the necessary delays that accumulated during thetime the thread was suspended. To simplify the implementation of this policy, C OZ forces a thread to execute all required
delays before it does anything that could block that thread(see Table 2) or wake a suspended thread (shown in Table 1).
This means that any resumed thread can skip any required
delays after returning from a call which may have blocked
the thread. Note that this special handling is only required for
operations that can suspend a thread. C OZ can accommodate
programs with ad-hoc synchronization that does not suspend
threads with no special handling.

Ensuring accurate timing. C OZ uses the nanosleep
POSIX function to insert delays. This function only guarantees that the thread will pause for at least the requested time,
but the pause may be longer than requested. C OZ tracks any
excess pause time, which is subtracted from future pauses.
Thread creation. To start sampling and adjust delays, C OZ
interposes on the pthread create function. C OZ ﬁrst
initiates perf event sampling in the new thread. It theninherits the parent thread’s local delay count; any previously
inserted delays to the parent thread also delayed the creationof the new thread.
3.4.1

Handling Suspended Threads

C OZ only collects samples and inserts delays in a thread whilethat thread is actually executing. This means that required
delays will accumulate in a thread while it is suspended.
When a thread is suspended on a blocking I/O operation, thisis the desired behavior; pausing the thread while it is alreadysuspended on I/O would not delay the thread’s progress. C OZ
simply adds these delays after the thread unblocks.
However, a thread can also be suspended while waiting
for a mutex or other POSIX synchronization primitive. As
with blocking I/O, required delays will accumulate while
the thread is suspended, but C OZ may not need to insert allof these delays when the thread resumes. When one threadresumes after waiting for a mutex, another thread must have

3.4.2

Attributing Samples to Source Lines

Samples are attributed to source lines using the source map
constructed at startup. When a sample does not fall in any
in-scope source line, the proﬁler walks the sampled callchain
to ﬁnd the ﬁrst in-scope address. This has the effect of attributing all out-of-scope execution to the last in-scope callsite responsible. For example, a program may call printf,
which calls vfprintf, which in turn calls strlen. Any
samples collected during this chain of calls will be attributed
to the source line that issues the original printf call.

189

3.4.3

Summary of Optimization Results
Application Speedup
Diff Size
blackscholes 2.56% ± 0.41%−61, +4
dedup 8.95% ± 0.27%−3, +3ferret 21.27% ± 0.17% −4, +4
ﬂuidanimate 37.5% ± 0.56%−1, +0streamcluster 68.4% ± 1.12%−1, +0swaptions 15.8% ± 1.10%−10, +16
Memcached 9.39% ± 0.95%−6, +2
SQLite 25.60% ± 1.00% −7, +7

Optimization: Minimizing Delays

If every thread executes the selected line, forcing each thread
to delay num threads−1 times unnecessarily slows execution.
If all but one thread executes the selected line, only that threadneeds to pause. The invariant that must be preserved is thefollowing: for each thread, the number of pauses plus thenumber of samples in the selected line must be equal. Whena sample falls in the selected line, C OZ increments only the
local delay count. If the local delay count is still less than the
global delay count after processing all available samples, C OZ
inserts pauses. If the local delay count is larger than global
delay count, the thread increases the global delay count.

Table 3: All benchmarks were run ten times before and after
optimization. Standard error for speedup was computed usingt −tEfron’s bootstrap method, where speedup is deﬁned as 0 t0opt .
All speedups are statistically signiﬁcant at the 99.9% conﬁdence
level (α = 0.001) using the one-tailed Mann-Whitney U test, which
does not rely on any assumptions about the distribution of execution
times. Lines of code do not include blank or comment-only lines.

Adjusting for phases
C OZ randomly selects a recently-executed line of code at
the start of each performance experiment. This increases thelikelihood that experiments will yield useful information—a virtual speedup would have no effect on lines that neverrun—but could bias results for programs with phases.
If a program runs in phases, optimizing a line will nothave any effect on progress rate during periods when the line
is not being run. However, C OZ will not run performanceexperiments for the line during these periods because only
currently-executing lines are selected. If left uncorrected, thisbias would lead C OZ to overstate the effect of optimizing
lines that run in phases.
To eliminate this bias, we break the program’s execution
into two logical phases: phase A, during which the selectedline runs, and phase B, when it does not. These phases neednot be contiguous. The total runtime T = tA + tB is the sumof the durations of the two phases. The average progress rateduring the entire execution is:P =T
tA + tB=.
N
N

where nA is the number of progress point visits during phase
A. Using (5), the new value for P with the virtual speedup isP =therefore

tobs
tA ≈ s ·
.
sobs



ΔP =

ΔpA =

ΔP = ΔpA

4.

(5)

=

tA − tA 
tA(8)

Evaluation

Our evaluation answers the following questions: (1) Does
causal proﬁling enable effective performance tuning? (2)Are C OZ’s performance predictions accurate? (3) Is C OZ’s
overhead low enough to be practical?
4.1

Experimental Setup

We perform all experiments on a 64 core, four socket AMD
Opteron machine with 60GB of memory, running Linux 3.14
with no modiﬁcations. All applications are compiled using
GCC version 4.9.1 at the -O3 optimization level and debug
information generated with -g. We disable frame pointerelimination with the -fno-omit-frame-pointer ﬂag
so the Linux can collect accurate call stacks with each sample.
C OZ is run with the default sampling period of 1ms, withsample processing set to occur after every 10 samples. Each
performance experiment runs with a cooling-off period of
10ms after each experiment to allow any remaining samples
to be processed before the next experiment begins. Due tospace limitations, we only proﬁle throughput (and not latency)
in this evaluation.

(6)

where pA  and pA are the average progress periods with andwithout a virtual speedup; this can be rewritten as:
ΔpA =

tA
tobs s≈ ΔpA ·
· .
T
sobs TC OZ multiplies all measured speedups, ΔpA , by the correction factor stobs· Ts in its ﬁnal report.
obs

pA − pA 
pA

tA
tA 
nA − n AtA
nAtA +tB− tA +tB
tA − tA 
P − P
= N T N.
=P
T
N

Finally, using (6) and (7),C OZ measures the effect of a virtual speedup during phaseA,tA  + tB
N

and the percent change in P is

C OZ collects samples during the entire execution, recording the number of samples in each line. We deﬁne s to be
the number of samples in the selected line, of which sobs
occur during a performance experiment with duration tobs .
The expected number of samples during the experiment is:
tobs,
E[sobs ] = s ·
tA

LOC
342
2,570
5,937
1,015
1,779
970
10,475
92,635

(7)

190

300
200
100
0

Original

200
150
100
50
0

Midpoint    

7.5
5.0
2.5
0.0
0

1000

2000

3000

 


     

Figure 5: Ferret’s pipeline. The middle four stages each have anassociated thread pool; the input and output stages each consist of
one thread. The colors represent the impact on throughput of eachstage, as identiﬁed by C OZ: green is low impact, orange is medium
impact, and red is high impact.

Optimized

Keys Assigned to Bucket

Hash Bucket Collisions in dedup

4000

Bucket Index

buckets; over 97% of buckets were never used during theentire execution.
The original hash function adds characters of the hash table
key, which leads to virtually no high order bits being set. The
resulting hash output is then passed to a bit shifting procedure
intended to compensate for poor hash functions. We removed
the bit shifting step, which increased hash table utilization to54.4%. We then changed the hash function to bitwise XOR
32 bit chunks of the key. This increased hash table utilization
to 82.0% and resulted in an 8.95% ± 0.27% performance
improvement. Figure 4 shows the rate of bucket collisions of
the original hash function, the same hash function without
the bit shifting “improvement”, and our ﬁnal hash function.
The entire optimization required changing just three lines ofcode. As with ferret, this result was achieved by one graduate
student who was initially unfamiliar with the code; the entire
proﬁling and tuning effort took just two hours.

Figure 4: In the dedup benchmark, C OZ identiﬁed hash bucket
traversal as a bottleneck. These plots show collisions per-bucket
before, mid-way through, and after optimization of the dedup benchmark (note different y-axes). The dashed horizontal line shows average collisions per-utilized bucket for each version. Fixing dedup’s
hash function improved performance by 8.9%.

4.2

EffectivenessWe demonstrate causal proﬁling’s effectiveness through casestudies. Using C OZ, we collect causal proﬁles for Memcached, SQLite, and the PARSEC benchmark suite. Using
these causal proﬁles, we were able to make small changes
to two of the real applications and six PARSEC benchmarks,
resulting in performance improvements as large as 68%. Table 3 summarizes the results of our optimization efforts. We
describe our experience using C OZ below, with three general outcomes: (1) cases where C OZ found optimization opportunities that gprof and perf did not (dedup, ferret, andSQLite); (2) cases where C OZ identiﬁed contention (ﬂuidanimate, streamcluster, and Memcached); and (3) cases where
both C OZ and a conventional proﬁler identiﬁed the optimization we implemented (blackscholes and swaptions).
4.2.1

Comparison with gprof. We ran both the original and optimized versions of dedup with gprof. As with ferret, theoptimization opportunities identiﬁed by C OZ were not obvious in gprof’s output. Overall, hashtable search had
the largest share of highest execution time at 14.38%, butcalls to hashtable search from the hash computation
stage accounted for just 0.48% of execution time; Gprof’s
call graph actually obscured the importance of this code. After optimization, hashtable search’s share of execution
time reduced to 1.1%.

Case Study: dedup

The dedup application performs parallel ﬁle compression
via deduplication. This process is divided into three mainstages: ﬁne-grained fragmentation, hash computation, andcompression. We placed a progress point immediately after
dedup completes compression of a single block of data
(encoder.c:189).
C OZ identiﬁes the source line hashtable.c:217 as
the best opportunity for optimization. This code is the topof the while loop in hashtable search that traverses
the linked list of entries that have been assigned to the samehash bucket. This suggests that dedup’s shared hash table hasa signiﬁcant number of collisions. Increasing the hash tablesize had no effect on performance. This led us to examine
dedup’s hash function, which could also be responsible forthe large number of hash table collisions. We discovered thatdedup’s hash function maps keys to just 2.3% of the available

4.2.2

Case Study: ferret

The ferret benchmark performs a content-based image similarity search. Ferret consists of a pipeline with six stages: theﬁrst and the last stages are for input and output. The middle
four stages perform image segmentation, feature extraction,indexing, and ranking. Ferret takes two arguments: an input ﬁle and a desired number of threads, which are divided
equally across the four middle stages. We ﬁrst inserted a
progress point in the ﬁnal stage of the image search pipeline
to measure throughput (ferret-parallel.c:398). We
then ran C OZ with the source scope set to evaluate optimizations only in ferret-parallel.c, rather than across theentire ferret toolkit.

191

Causal Proﬁle for ferretLine 358

Line 255

Line 16916

100%
●
● ●●
●
●● ●

75%
50%
25%
0%

Program Speedup

Program Speedup

Line 320

Causal and Perf Proﬁles for SQLite

●
●

●●● ●
●
●
●
●● ●

0%

50%

100% 0%50%

100% 0%

50%

100%

0%

Line 18974

Line 40345

●●●●●
●●
●
●
●

−25%

●
●
●●

●

−50%
0%

Line Speedup

50%

0%

50%

0%

50%

Line Speedup

Figure 6: C OZ output for the unmodiﬁed ferret application. The
x-axis shows the amount of virtual speedup applied to each line,
versus the resulting change in throughput on the y-axis. The top twolines are executed by the indexing and ranking stages; the third line
is executed during image segmentation.

(a) C OZ’s output for SQLite before optimizations.
% Runtime
Symbol85.55%_raw_spin_lock
1.76%
x86_pmu_enable_all... 30 lines ...
0.10%
rcu_irq_enter
0.09%
sqlite3MemSize
0.09%
source_load... 26 lines ...
0.03%__queue_work
0.03%
pcache1Fetch
0.03%
kmem_cache_free
0.03%
update_cfs_rq_blocked_load
0.03%
pthreadMutexLeave
0.03%
sqlite3MemMalloc

Figure 6 shows the top three lines identiﬁed by C OZ, using
its default ranking metric. Lines 320 and 358 are calls tocass table query from the indexing and ranking stages.
Line 255 is a call to image segment in the segmentation
stage. Figure 5 depicts ferret’s pipeline with the associatedthread pools (colors indicate C OZ’s computed impact on
throughput of optimizing these stages).
Because each important line falls in a different pipeline
stage, and because C OZ did not ﬁnd any important lines in thequeues shared by adjacent stages, we can easily “optimize”
a speciﬁc line by shifting threads to that stage. We modiﬁed
ferret to let us specify the number of threads assigned to eachstage separately, a four-line change.
C OZ did not ﬁnd any important lines in the feature extraction stage, so we shifted threads from this stage to the threeother main stages. After three rounds of proﬁling and adjusting thread assignments, we arrived at a ﬁnal thread allocationof 20, 1, 22, and 21 to segmentation, feature extraction, indexing, and ranking respectively. The reallocation of threads led
to a 21.27% ± 0.17% speedup over the original conﬁguration,using the same number of threads.

(b) Perf’s output for SQLite before optimizations.
Figure 7: C OZ and perf output for SQLite before optimizations.
The three lines in the causal proﬁle correspond to the function
prologues for sqlite3MemSize, pthreadMutexLeave, andpcache1Fetch. A small optimization to each of these lines will
improve program performance, but beyond about a 25% speedup,
C OZ predicts that the optimization would actually lead to a slowdown. Changing indirect calls into direct calls for these functions
improved overall performance by 25.6% ± 1.0%.

load, where each thread rapidly inserts rows to its own private
table. While this benchmark is synthetic, it exposes any scalability bottlenecks in the database engine itself because all
threads should theoretically operate independently. We placeda progress point in the benchmark itself (which is linked withthe database), which executes after each insertion.
C OZ identiﬁed three important optimization opportunities,
shown in Figure 7a. At startup, SQLite populates a large
number of structs with function pointers to implementationspeciﬁc functions, but most of these functions are only evergiven a default value determined by compile-time options.
The three functions C OZ identiﬁed unlock a standard pthread
mutex, retrieve the next item from a shared page cache, andget the size of an allocated object. These simple functions dovery little work, so the overhead of the indirect function callis relatively high. Replacing these indirect calls with directcalls resulted in a 25.60% ± 1.00% speedup.

Comparison with gprof. We also ran ferret with gprof inboth the initial and ﬁnal conﬁgurations. Optimization opportunities are not immediately obvious from that proﬁle. For example, in the ﬂat proﬁle, the function cass table query
appears near the bottom of the ranking, and is tied with 56
other functions for most cumulative time.
Gprof also offers little guidance for optimizing ferret. In
fact, its output was virtually unchanged before and after our
optimization, despite a large performance change.
4.2.3

25%

Case Study: SQLite

The SQLite database library is widely used by many applications to store relational data. The embedded database,which can be included as a single large C ﬁle, is used formany applications including Firefox, Chrome, Safari, Opera,
Skype, iTunes, and is a standard component of Android, iOS,
Blackberry 10 OS, and Windows Phone 8. We evaluated
SQLite performance using a write-intensive parallel work-

Comparison with conventional proﬁlers. Unfortunately,
running SQLite with gprof segfaults immediately. The application does run with the Linux perf tool, which reportsthat the three functions C OZ identiﬁed account for a total ofjust 0.15% of total runtime (shown in Figure 7b). Using perf,

192

Causal Proﬁle for ﬂuidanimate

a developer would be misled into thinking that optimizingthese functions would be a waste of time. C OZ accurately
shows that the opposite is true: optimizing these functions
has a dramatic impact on performance.

Program Speedup

4.2.4

Line 151

Case Study: ﬂuidanimate

The ﬂuidanimate benchmark, also provided by Intel, is a physical simulation of an incompressible ﬂuid for animation. The
application spawns worker threads that execute in eight concurrent phases, separated by a barrier. We placed a progresspoint immediately after the barrier, so it executes each time
all threads complete a phase of the computation.
C OZ identiﬁes a single modest potential speedup in thethread creation code, but there was no obvious way to speed
up this code. However, C OZ also identiﬁed two signiﬁcant
points of contention, indicated by a downward sloping causal
proﬁle. Figure 8 shows C OZ’s output for these two lines.
This result tells us that optimizing the indicated line of code
would actually slow down the program, rather than speed
it up. Both lines C OZ identiﬁes are in a custom barrier
implementation, immediately before entering a loop that
repeatedly calls pthread mutex trylock. Removing
this spinning from the barrier would reduce the contention,
but it was simpler to replace the custom barrier with thedefault pthread barrier implementation. This one line
change led to a 37.5% ± 0.56% speedup.
4.2.5

0%
−10%

●●
●
●
● ●
●
●●● ●

●
●

● ●●

●
●●

●
●

−20%
0%

50%

100%0%

50%

100%

Line Speedup
Figure 8: C OZ output for ﬂuidanimate, prior to optimization. C OZ ﬁnds evidence of contention in two lines inparsec barrier.cpp, the custom barrier implementation usedby both ﬂuidanimate and streamcluster. This causal proﬁle reportsthat optimizing either line will slow down the application, not speed
it up. These lines precede calls to pthread mutex trylock on
a contended mutex. Optimizing this code would increase contention
on the mutex and interfere with the application’s progress. Replacing this inefﬁcient barrier implementation sped up ﬂuidanimate andstreamcluster by 37.5% and 68.4% respectively.

using a hash of its key. Consequently, locking any one item
can potentially contend with independent accesses to otheritems whose keys happen to hash to the same lock index.
Because reference counts are updated atomically, we cansafely remove the lock from this function, which resulted ina 9.39% ± 0.95% speedup.

Case Study: streamcluster

4.2.7

The streamcluster benchmark performs online clustering ofstreaming data. As with ﬂuidanimate, worker threads executein concurrent phases separated by a custom barrier, where
we placed a progress point. C OZ identiﬁed a call to a random number generator as a potential line for optimization.
Replacing this call with a lightweight random number generator had a modest effect on performance (˜2% speedup).
As with ﬂuidanimate, C OZ highlighted the custom barrier
implementation as a major source of contention. Replacing
this barrier with the default pthread barrier led to a
68.4% ± 1.12% speedup.
4.2.6

Line 184

10%

Case Study: blackscholes

The blackscholes benchmark, provided by Intel, solves theBlack–Scholes differential equation to price a portfolio ofstock options. We placed a progress point after each threadcompletes one round of the iterative approximation to the differential equation (blackscholes.c:259). C OZ identiﬁes many lines in the CNDF and BlkSchlsEqEuroNoDiv
functions that would have a small impact if optimized. Thissame code was identiﬁed as a bottleneck by ParaShares [26];this is the only optimization we describe here that was previously reported. This block of code performs the main
numerical work of the program, and uses many temporary
variables to break apart the complex computation. Manually eliminating common subexpressions and combining 61
piecewise calculations into 4 larger expressions resulted in a
2.56% ± 0.41% program speedup.

Case Study: Memcached

Memcached is a widely-used in-memory caching system. To
evaluate cache performance, we ran a benchmark ported fromthe Redis performance benchmark. This program spawns 50
parallel clients that collectively issue 100,000 SET and GET
requests for randomly chosen keys. We placed a progresspoint at the end of the process command function, whichhandles each client request.
Most of the lines C OZ identiﬁes are cases of contention,with a characteristic downward-sloping causal proﬁle plot.
One such line is at the start of item remove, which locks
an item in the cache and then decrements its reference
count, freeing it if the count goes to zero. To reduce lockinitialization overhead, Memcached uses a static array oflocks to protect items, where each item selects its lock

4.2.8

Case Study: swaptions

The swaptions benchmark is a Monte Carlo pricing algorithm
for swaptions, a type of ﬁnancial derivative. Like blackscholes
and ﬂuidanimate, this program was developed by Intel. We
placed a progress point after each iteration of the main loop executed by worker threads (HJM Securities.cpp:99).
C OZ identiﬁed three signiﬁcant optimization opportunities,
all inside nested loops over a large multidimensional array.
One of these loops zeroed out consecutive values. A second
loop ﬁlled part of the same large array with values froma distribution function, with no obvious opportunities for193netlist elem.cpp:82

taskQDistCommon.c:109

MATRIX 3X3.h:136

fp tree.cpp:383

fp tree.cpp:301

BinnedAllDims...:98

RTEmulatedSSE.hxx:784

threadgroup.c:360

im Lab2LabQ.c:98

encoder.c:1165

common.c:687

Table 4: The locations of inserted progress points for the remaining
PARSEC benchmarks, and the top optimization opportunities thatC OZ identiﬁes. The progress point for raytrace was placed on line
98 of BinnedAllDimsSaveSpace.cxx.

20%0%BenchmarkDelaysSampling

Startup

Figure 9: Percent overhead for each of C OZ’s possible sources ofoverhead. Delays are the overhead due to adding delays for virtual
speedups, Sampling is the cost of collecting and processing samples,and Startup is the initial cost of processing debugging information.
Note that sampling results in slight performance improvements forswaptions, vips, and x264.

optimization. The third nested loop iterated over the samearray again, but traversed the dimensions in an irregular order.
Reordering these loops and replacing the ﬁrst loop with a callto memset sped execution by 15.8% ± 1.10%.
Effectiveness Summary. Our case studies conﬁrm thatC OZ is effective at identifying optimization opportunities
and guiding performance tuning. In every case, the information C OZ provided led us directly to the optimization we
implemented. In most cases, C OZ identiﬁed around 20 lines
of interest, with as many as 50 for larger programs (Memcached and x264). C OZ identiﬁed optimization opportunities
in all of the PARSEC benchmarks, but some required moreinvasive changes that are out of scope for this paper. Table 4summarizes our ﬁndings for the remaining PARSEC benchmarks. We have submitted patches to the developers of all
the applications we optimized.
4.3

40%

ks
c
bo hole
dy s
tra
ca ck
nn
ea
de l
du
fa p
ce
si
flu f m
e
id rr
an et
im
fre ateqmi
str ray ne
ea tram ceclsw ust
ap er
tio
ns
vi
ps
x2
64
m
ea
n

ParticleFilter.h:262

annealer thread.cpp:87

60%

ac

TicketDispenser.h:106

Overhead of C OZ

Percent Overhea

Results for Unoptimized Applications
Progress PointTop Optimizationbl

Benchmarkbodytrackcannealfacesimfreqmine
raytrace
vips
x264

4.4

Efﬁciency

We measure C OZ’s proﬁling overhead on the PARSEC benchmarks running with the native inputs. The sole exception is
streamcluster, where we use the test inputs because execution
time was excessive with the native inputs.
Figure 9 breaks down the total overhead of running C OZ
on each of the PARSEC benchmarks by category. The averageoverhead with C OZ is 17.6%. C OZ collects debug information
at startup, which contributes 2.6% to the average overhead.
Sampling during program execution and attributing thesesamples to lines using debug information is responsiblefor 4.8% of the average overhead. The remaining overhead(10.2%) comes from the delays C OZ inserts to perform virtual
speedups.
These results were collected by running each benchmark
in four conﬁgurations. First, each program was run without
C OZ to measure a baseline execution time. In the second
conﬁguration, each program was run with C OZ, but execution
terminated immediately after startup work was completed.
Third, programs were run with C OZ conﬁgured to sample
the program’s execution but not to insert delays (effectively
testing only virtual speedups of size zero). Finally, eachprogram was run with C OZ fully enabled. The difference
in execution time between each successive conﬁguration giveus the startup, sampling, and delay overheads, respectively.

Accuracy

For most of the optimizations described above, it is notpossible to quantify the effect our optimization had on thespeciﬁc lines that C OZ identiﬁed. However, for two of ourcase studies—ferret and dedup—we can directly computethe effect our optimization had on the line C OZ identiﬁed
and compare the resulting speedup to C OZ’s predictions. Our
results show that C OZ’s predictions are highly accurate.
To optimize ferret, we increased the number of threads
for the indexing stage from 16 to 22, which increases thethroughput of line 320 by 27%. C OZ predicted that thisimprovement would result in a 21.4% program speedup,
which is nearly the same as the 21.2% we observe.
For dedup, C OZ identiﬁed the top of the while loopthat traverses a hash bucket’s linked list. By replacing thedegenerate hash function, we reduced the average numberof elements in each hash bucket from 76.7 to just 2.09. Thischange reduces the number of iterations from 77.7 to 3.09
(accounting for the ﬁnal trip through the loop). This reduction
corresponds to a speedup of the line C OZ identiﬁed by 96%.
For this speedup, C OZ predicted a performance improvementof 9%, very close to our observed speedup of 8.95%.

Reducing overhead. Most programs have sufﬁciently longrunning times (mean: 103s) to amortize the cost of processing
debug information, but especially large executables can be
expensive to process at startup (x264 and vips, for example). C OZ could be modiﬁed to collect and process debug
information lazily to reduce startup overhead. Sampling overhead comes mainly from starting and stopping sampling withthe perf event API at thread creation and exit. This cost
could be amortized by sampling globally instead of per-thread,194which would require root permissions on most machines. If
the perf event API supported sampling all threads in aprocess this overhead could be eliminated. Delay overhead,
the largest component of C OZ’s total overhead, could be reduced by allowing programs to execute normally for sometime between each experiment. Increasing the time between
experiments would signiﬁcantly reduce overhead, but a longer
proﬁling run would be required to collect a usable proﬁle.

optimizations will have some impact, but these approaches
to not give developers any information about how much performance gain is possible before the critical path changes.
Hollingsworth and Miller introduce two new metrics to approximate optimization potential: slack, how much a procedure can be improved before the critical path changes; andlogical zeroing, the reduction in critical path length whena procedure is completely removed [22]. These metrics are
similar to the optimization potential measured by a causal
proﬁler, but can only be computed with a complete program
activity graph. Collection of a program activity graph iscostly, and could introduce signiﬁcant probe effect.

Efﬁciency summary. C OZ’s proﬁling overhead is on average 17.6% (minimum: 0.1%, maximum: 65%). For all but
three of the benchmarks, its overhead was under 30%. Given
that the widely used gprof proﬁler can impose much higher
overhead (e.g., 6× for ferret, versus 6% with C OZ), theseresults conﬁrm that C OZ has sufﬁciently low overhead to be
used in practice.

5.

Bottleneck identiﬁcation. Several approaches have usedhardware performance counters to identify hardware-level
performance bottlenecks [8, 12, 32]. Techniques based on
binary instrumentation can identify cache and heap performance issues, contended locks, and other program hotspots [5,31, 36]. ParaShares and Harmony identify basic blocks thatrun during periods with little or no parallelism [25, 26]. Codeidentiﬁed by these tools is a good candidate for parallelization
or classic serial optimizations. Bottlenecks, a proﬁle analysis
tool, uses heuristics to identify bottlenecks using call-tree
proﬁles [3]. Given call-tree proﬁles for different executions,
Bottlenecks can pinpoint which procedures are responsible
for the difference in performance. The FreeLunch proﬁler
and Visual Studio’s contention proﬁler identify locks that are
responsible for signiﬁcant thread blocking time [11, 16]. BIS
uses similar techniques to identify highly contended criticalsections on asymmetric multiprocessors, and automaticallymigrates performance-critical code to faster cores [24]. Bottle
graphs present thread execution time and parallelism in a visual format that highlights program bottlenecks [13]. Unlike
causal proﬁling, these tools do not predict the performance
impact of removing bottlenecks. All these systems can only
identify bottlenecks that arise from explicit thread communication, while causal proﬁling can measure parallel performance problems from any source, including cache coherence
protocols, scheduling dependencies, and I/O.

Related Work

Causal proﬁling identiﬁes and quantiﬁes optimization opportunities, while most past work on proﬁlers has focused oncollecting detailed (though not necessarily actionable) information with low overhead.
5.1

General-Purpose Proﬁlers

General-purpose proﬁlers are typically implemented using
instrumentation, sampling, or both. Systems based on sampling (including causal proﬁling) can arbitrarily reduce probe
effect, although sampling must be unbiased [35].
The UNIX prof tool and oproﬁle both use sampling exclusively [29, 42]. Oproﬁle can sample using a variety of
hardware performance counters, which can be used to identify cache-hostile code, poorly predicted branches, and otherhardware bottlenecks. Gprof combines instrumentation andsampling to measure execution time [17]. Gprof produces
a call graph proﬁle, which counts invocations of functions
segregated by caller. Cho, Moseley, et al. reduce the overheadof Gprof’s call-graph proﬁling by interleaving instrumented
and un-instrumented execution [9]. Path proﬁlers add further
detail, counting executions of each path through a procedure,or across procedures [2, 6].
5.2

Proﬁling for parallelization and scalability. Several systems have been developed to measure potential parallelism inserial programs [15, 43, 45]. Like causal proﬁling, these systems identify code that will beneﬁt from developer time. Unlike causal proﬁling, these tools are not aimed at diagnosing
performance issues in code that has already been parallelized.
Kulkarni, Pai, and Schuff present general metrics for available parallelism and scalability [28]. The Cilkview scalability analyzer uses performance models for Cilk’s constrained
parallelism to estimate the performance effect of adding additional hardware threads [20]. Causal proﬁling can detect
performance problems that result from poor scaling on thecurrent hardware platform.

Parallel Proﬁlers

Past work on parallel proﬁling has focused on identifying
the critical path or bottlenecks, although optimizing the critical path or removing the bottleneck may not signiﬁcantly
improve program performance.
Critical path proﬁling. IPS uses traces from messagepassing programs to identify the critical path, and reports
the amount of time each procedure contributes to the critical
path [34]. IPS-2 extends this approach with limited support for shared memory parallelism [33, 44]. Other critical
path proﬁlers rely on languages with ﬁrst-class threads andsynchronization to identify the critical path [21, 37, 40]. Identifying the critical path helps developers ﬁnd code where

Time attribution proﬁlers. Time attribution proﬁlers assign“blame” to concurrently executing code based on what other195

Acknowledgments

threads are doing. Quartz introduces the notion of “normalized processor time,” which assigns high cost to code thatruns while a large fraction of other threads are blocked [4].
CPPROFJ extends this approach to Java programs with aspects [19]. CPPROFJ uses ﬁner categories for time: running,
blocked for a higher-priority thread, waiting on a monitor,and blocked on other events. Tallent and Mellor-Crummey
extend this approach further to support Cilk programs, withan added category for time spent managing parallelism [41].
The WAIT tool adds ﬁne-grained categorization to identify
bottlenecks in large-scale production Java systems [1]. Unlike
causal proﬁling, these proﬁlers can only capture interference
between threads that directly affects their scheduler state.
5.3This material is based upon work supported by the National
Science Foundation under Grants No. CCF-1012195 andCCF-1439008. Charlie Curtsinger was supported by a Google
PhD Research Fellowship. The authors thank Dan Barowy,
Steve Freund, Emma Tosch, John Vilk, and our shepherd Tim
Harris for their feedback and helpful comments.

References[1] E. R. Altman, M. Arnold, S. Fink, and N. Mitchell. Performance analysis of idle programs. In OOPSLA, pages 739–753.
ACM, 2010.
[2] G. Ammons, T. Ball, and J. R. Larus. Exploiting hardware
performance counters with ﬂow and context sensitive proﬁling.
In PLDI, pages 85–96. ACM, 1997.

Performance Guidance and Experimentation[3] G. Ammons, J.-D. Choi, M. Gupta, and N. Swamy. Finding
and removing performance bottlenecks in large systems. In
ECOOP, volume 3086 of Lecture Notes in Computer Science,
pages 170–194. Springer, 2004.

Several systems have employed delays to extract information about program execution times. Mytkowicz et al. use
delays to validate the output of proﬁlers on single-threaded
Java programs [35]. Snelick, JáJá et al. use delays to proﬁleparallel programs [38]. This approach measures the effect ofslowdowns in combination, which requires a complete execution of the program for each of an exponential number of
conﬁgurations. Active Dependence Discovery (ADD) introduces performance perturbations to distributed systems andmeasures their impact on response time [7]. ADD requires acomplete enumeration of system components, and requires
developers to insert performance perturbations manually. Gunawi, Agrawal et al. use delays to identify causal dependencies between events in the EMC Centera storage system toanalyze Centera’s protocols and policies [18]. Song and Lu
use machine learning to identify performance anti-patterns insource code [39]. Unlike causal proﬁling, these approaches
do not predict the effect of potential optimizations.

6.

[4] T. E. Anderson and E. D. Lazowska. Quartz: A tool for tuning
parallel program performance. In SIGMETRICS, pages 115–
125, 1990.
[5] M. M. Bach, M. Charney, R. Cohn, E. Demikhovsky, T. Devor,
K. Hazelwood, A. Jaleel, C.-K. Luk, G. Lyons, H. Patil, and
A. Tal. Analyzing parallel programs with Pin. Computer,
43(3):34–41, Mar. 2010.
[6] T. Ball and J. R. Larus. Efﬁcient path proﬁling. In MICRO,
pages 46–57, 1996.
[7] A. B. Brown, G. Kar, and A. Keller. An active approach to characterizing dynamic dependencies for problem determination ina distributed environment. In Integrated Network Management,
pages 377–390. IEEE, 2001.
[8] M. Burtscher, B.-D. Kim, J. R. Diamond, J. D. McCalpin,
L. Koesterke, and J. C. Browne. PerfExpert: An easy-to-use
performance diagnosis tool for HPC applications. In SC, pages
1–11. IEEE, 2010.

Conclusion[9] H. K. Cho, T. Moseley, R. E. Hank, D. Bruening, and S. A.
Mahlke. Instant proﬁling: Instrumentation sampling for proﬁling datacenter applications. In CGO, pages 1–10. IEEE
Computer Society, 2013.

Proﬁlers are the primary tool in the programmer’s toolbox for
identifying performance tuning opportunities. Previous proﬁlers only observe actual executions and correlate code withexecution time or performance counters. This information
can be of limited use because the amount of time spent does
not necessarily correspond to where programmers should focus their optimization efforts. Past proﬁlers are also limited toreporting end-to-end execution time, an unimportant quantity
for servers and interactive applications whose key metrics ofinterest are throughput and latency. Causal proﬁling is a new,experiment-based approach that establishes causal relationships between hypothetical optimizations and their effects. By
virtually speeding up lines of code, causal proﬁling identiﬁes
and quantiﬁes the impact on either throughput or latency ofany degree of optimization to any line of code. Our prototypecausal proﬁler, C OZ, is efﬁcient, accurate, and effective at
guiding optimization efforts.

[10] C. Curtsinger and E. D. Berger. S TABILIZER: Statisticallysound performance evaluation. In ASPLOS, New York, NY,
USA, 2013. ACM.
[11] F. David, G. Thomas, J. Lawall, and G. Muller. Continuously
measuring critical section pressure with the free-lunch proﬁler.
In OOPSLA, pages 291–307, 2014.
[12] J. R. Diamond, M. Burtscher, J. D. McCalpin, B.-D. Kim, S. W.
Keckler, and J. C. Browne. Evaluation and optimization of multicore performance bottlenecks in supercomputing applications.
In ISPASS, pages 32–43. IEEE Computer Society, 2011.
[13] K. Du Bois, J. B. Sartor, S. Eyerman, and L. Eeckhout. Bottle
graphs: Visualizing scalability bottlenecks in multi-threaded
applications. In OOPSLA, pages 355–372, 2013.
[14] Free Software Foundation. Debugging with GDB, tenth edition.

196

parallel program measurement system. IEEE Transactions on
Parallel Distributed Systems, 1(2):206–217, 1990.

[15] S. Garcia, D. Jeon, C. M. Louie, and M. B. Taylor. Kremlin:
rethinking and rebooting gprof for the multicore age. In PLDI,
pages 458–469. ACM, 2011.

[34] B. P. Miller and C.-Q. Yang. IPS: An interactive and automatic
performance measurement tool for parallel and distributed
programs. In ICDCS, pages 482–489, 1987.

[16] M. Goldin. Thread performance: Resource contention concurrency proﬁling in visual studio 2010. MSDN magazine,
page 38, 2010.

[35] T. Mytkowicz, A. Diwan, M. Hauswirth, and P. F. Sweeney.
Evaluating the accuracy of Java proﬁlers. In PLDI, pages
187–197. ACM, 2010.

[17] S. L. Graham, P. B. Kessler, and M. K. McKusick. gprof: a callgraph execution proﬁler. In SIGPLAN Symposium on Compiler
Construction, pages 120–126. ACM, 1982.

[36] N. Nethercote and J. Seward. Valgrind: a framework forheavyweight dynamic binary instrumentation. In PLDI, pages
89–100. ACM, 2007.

[18] H. S. Gunawi, N. Agrawal, A. C. Arpaci-Dusseau, R. H. ArpaciDusseau, and J. Schindler. Deconstructing commodity storage
clusters. In ISCA, pages 60–71. IEEE Computer Society, 2005.

[37] Y. Oyama, K. Taura, and A. Yonezawa. Online computationof critical paths for multithreaded languages. In IPDPS
Workshops, volume 1800 of Lecture Notes in Computer Science,
pages 301–313. Springer, 2000.

[19] R. J. Hall. CPPROFJ: Aspect-Capable Call Path Proﬁling ofMulti-Threaded Java Applications. In ASE, pages 107–116.
IEEE Computer Society, 2002.

[38] R. Snelick, J. JáJá, R. Kacker, and G. Lyon. Syntheticperturbation techniques for screening shared memory programs.
Software Practice & Experience, 24(8):679–701, 1994.

[20] Y. He, C. E. Leiserson, and W. M. Leiserson. The Cilkview
scalability analyzer. In SPAA, pages 145–156. ACM, 2010.
[21] J. M. D. Hill, S. A. Jarvis, C. J. Siniolakis, and V. P. Vasilev.
Portable and architecture independent parallel performancetuning using a call-graph proﬁling tool. In PDP, pages 286–
294, 1998.

[39] L. Song and S. Lu. Statistical debugging for real-world
performance problems. In OOPSLA, pages 561–578, 2014.
[40] Z. Szebenyi, F. Wolf, and B. J. N. Wylie. Space-efﬁcient timeseries call-path proﬁling of parallel applications. In SC. ACM,
2009.

[22] J. K. Hollingsworth and B. P. Miller. Slack: a new performance
metric for parallel programs. University of Maryland andUniversity of Wisconsin-Madison, Tech. Rep, 1994.

[41] N. R. Tallent and J. M. Mellor-Crummey. Effective performance measurement and analysis of multithreaded applications.
In PPOPP, pages 229–240. ACM, 2009.

[23] Intel. Intel VTune Ampliﬁer 2015, 2014.
[24] J. A. Joao, M. A. Suleman, O. Mutlu, and Y. N. Patt. Bottleneck
identiﬁcation and scheduling in multithreaded applications. In
ASPLOS, pages 223–234. ACM, 2012.

[42] K. Thompson and D. M. Ritchie. UNIX Programmer’s Manual.
Bell Telephone Laboratories, 1975.
[43] C. von Praun, R. Bordawekar, and C. Cascaval. Modeling
optimistic concurrency using quantitative dependence analysis.
In PPoPP, pages 185–196. ACM, 2008.

[25] M. Kambadur, K. Tang, and M. A. Kim. Harmony: Collection
and analysis of parallel block vectors. In ISCA, pages 452–463.
IEEE Computer Society, 2012.

[44] C.-Q. Yang and B. P. Miller. Performance measurement
for parallel and distributed programs: A structured and automatic approach. IEEE Transactions on Software Engineering,
15(12):1615–1629, 1989.

[26] M. Kambadur, K. Tang, and M. A. Kim. Parashares: Finding
the important basic blocks in multithreaded programs. In EuroPar, Lecture Notes in Computer Science, pages 75–86, 2014.
[27] kernel.org. perf: Linux proﬁling with performance counters,
2014.

[45] X. Zhang, A. Navabi, and S. Jagannathan. Alchemist: A
transparent dependence distance proﬁling infrastructure. In
CGO, pages 47–58. IEEE Computer Society, 2009.

[28] M. Kulkarni, V. S. Pai, and D. L. Schuff. Towards architecture independent metrics for multicore performance analysis.
SIGMETRICS Performance Evaluation Review, 38(3):10–14,
2010.
[29] J. Levon and P. Elie. oproﬁle: A system proﬁler for Linux.
http://oproﬁle.sourceforge.net/, 2004.
[30] J. D. Little. OR FORUM: Little’s Law as Viewed on Its 50th
Anniversary. Operations Research, 59(3):536–549, 2011.
[31] C.-K. Luk, R. S. Cohn, R. Muth, H. Patil, A. Klauser, P. G.
Lowney, S. Wallace, V. J. Reddi, and K. M. Hazelwood. Pin:building customized program analysis tools with dynamic
instrumentation. In PLDI, pages 190–200, 2005.
[32] B. P. Miller, M. D. Callaghan, J. M. Cargille, J. K.
Hollingsworth, R. B. Irvin, K. L. Karavanic, K. Kunchithapadam, and T. Newhall. The paradyn parallel performancemeasurement tool. IEEE Computer, 28(11):37–46, 1995.
[33] B. P. Miller, M. Clark, J. K. Hollingsworth, S. Kierstead, S.-S.
Lim, and T. Torzewski. IPS-2: The second generation of a197