Coz: Finding Code that Counts with Causal Profiling

1. Introduction

• Conventional profilers rank code by execution time, but time spent does not necessarily identify code whose optimization improves performance.For example, optimizing fa entirely yields only a 4.5% speedup because fb becomes the new critical path.Source: §1 · p. 1
• Causal profiling estimates the impact of potential optimizations through virtual speedups, indicating where to focus and quantifying potential performance gains.It uses inserted pauses to slow concurrent threads as a proxy for speeding up a line, and experiments across speedup amounts to predict optimization effects.Source: §1 · p. 2

Contributions

• Causal profiling can measure potential optimization effects on throughput and latency using progress points that mark completed work or event boundaries.COZ’s contribution includes directly measuring these effects with virtual speedups and progress points.Source: §1 · p. 2, Contributions · p. 2
• COZ is a causal profiler for Linux that imposes a mean execution-time overhead of 17% (range: 0.1%–65%), compared with gprof’s overhead of up to 6×.The paper presents COZ as working on unmodified Linux binaries.Source: §1 · p. 2, Contributions · p. 2

1. Introduction

• 9% for Memcached, 25% for SQLite, and up to 68% for six PARSEC applications were achieved with COZ-guided optimizations.The changes typically involved under 10 lines, and measured improvements matched COZ’s predictions when their size could be accurately measured.Source: §1 · p. 2

2. Causal Profiling Overview

• Each COZ experiment selects a line and a virtual-speedup amount, then records visits to progress points over an experiment interval.If there are too few visits, COZ doubles the experiment time for the remainder of execution; it also subtracts inserted delay from runtime when recording effective duration.Source: §2 · p. 3
• Virtual speedups insert pauses in other threads whenever the selected line runs, mimicking the effect of actually speeding up that line.The illustrated comparison relates the virtual-experiment runtime to actual optimization by accounting for the inserted delay.Source: Figure 3 · p. 3, §2 · p. 3
• COZ combines experiments by selected line and speedup, compares progress-point visit rates with a 0% baseline, and plots the resulting program speedups.Lines without a baseline or with fewer than five virtual-speedup amounts are discarded by default.Source: §2 · pp. 3–4
• Contention-related fixes identified through causal profiles produced speedups of 37.5% in fluidanimate, 68.4% in streamcluster, and 9.4% in memcached.Steep downward profile slopes indicate that optimizing a line may hurt performance because the line interferes with the program’s critical path.Source: §2 · p. 4
• COZ sorts causal profiles by regression slope: upward slopes suggest optimization may help, flat slopes indicate little benefit, and downward slopes can signal harmful interference.Users interpret the profiles to decide which lines may be feasible to optimize.Source: §2 · p. 4

3. Implementation

• COZ’s implementation supports profiling unmodified Linux x86-64 executables through performance experiments, progress points, and virtual speedups.The section briefly describes the core mechanisms and implementation details for each component.Source: §3 · p. 4

3.1 Core Mechanisms

• COZ injects a runtime library with LD_PRELOAD, creates a profiler thread, and samples each thread’s program counter and user-space call stack every 1 ms.Samples are processed in batches of ten by default, every 10 ms, to limit overhead.Source: §3.1 · p. 4
• COZ maps sampled program-counter values to source locations using DWARF debug information, locating external debug information when necessary.Debug information can be available even for optimized code.Source: §3.1 · p. 4
• By default, COZ tests potential optimizations only in source files from the main executable; users can set source and binary scopes to select other code.The scope options let users specify which code they are willing or able to change.Source: §3.1 · p. 4

• COZ’s profiler thread coordinates experiments by selecting a line, choosing a virtual speedup, measuring progress-point effects, and logging results.Source: §3.2 · p. 4
• The profiler chooses a random virtual speedup from 0% to 100% in 5% increments; 0% is selected half the time to provide the baseline for computing speedup.Source: §3.2 · p. 4
• Randomly selecting lines and speedups avoids systematic bias because a line’s performance impact can vary between initialization and normal execution.A line that matters only after warmup could otherwise be missed, while one that matters only during initialization could be overstated.Source: §3.2 · p. 4
• After selecting a line and speedup, COZ saves progress counters, runs the experiment for a predetermined time, then logs its duration and measurements.If there are too few progress-point visits, five by default, COZ doubles the experiment time for the rest of execution.Source: §3.2 · p. 5

• COZ offers source-level, breakpoint, and sampled mechanisms for monitoring progress points.Source: §3.3 · p. 5
• Source-level points require inserting a COZ PROGRESS macro, while breakpoint points are specified on the command line and set at a line’s first instruction.Source: §3.3 · p. 5
• Sampled progress points count samples in a specified line rather than exact visits, but can still estimate the percent change in visits.Source: §3.3 · p. 5
• For latency, paired source-level or breakpoint points mark operation start and end; COZ derives average latency as L/λ using Little’s Law.L is the number of requests in progress and λ is the arrival rate; the law requires a stable system, where arrival rate does not exceed service rate.Source: §3.3 · p. 5

3.4 Virtual Speedup Implementation

• COZ models a virtual speedup by delaying other threads when a selected function runs, then uses sampling to approximate the effect without instrumentation.A delay of one quarter of the sampling period virtually speeds up the selected line by 25%.Source: §3.4 · pp. 5–6

3.4.1 Handling Suspended Threads

• When a thread resumes after blocking, COZ credits delays in the thread that woke it; otherwise, the resumed thread inserts accumulated delays, with intercepted calls handling block and wake cases.For blocking I/O, accumulated delays are inserted after the thread unblocks; a mutex waiter can skip delays already incurred by the unlocking thread.Source: §3.4.1 · p. 6, Table 1 · p. 6, Table 2 · p. 6

3.4.2 Attributing Samples to Source Lines

• When a sample falls outside an in-scope source line, COZ walks the callchain and attributes it to the first in-scope address, such as the original printf callsite.Source: §3.4.2 · p. 6

3.4.3 Optimization: Minimizing Delays

• To avoid unnecessary delays when threads execute the selected line, COZ preserves an invariant: each thread’s pauses plus its samples in that line must be equal.Threads update local and global delay counts to coordinate the required pauses.Source: §3.4.3 · p. 7

Adjusting for phases

• COZ avoids phase-related overestimation by splitting execution into periods when the selected line runs and when it does not, which need not be contiguous.Without correction, experiments on currently executing lines would overstate the effect of optimizing lines that run in phases.Source: Adjusting for phases · p. 7
• COZ estimates the selected line’s expected experiment samples from observed samples and measures virtual-speedup effects during phase A.The selected line’s sample count and the observed count during an experiment of duration tobs support the estimate.Source: Adjusting for phases · p. 7
• The profiler calculates progress with a virtual speedup and its percent change using phase-A visits and average progress periods with and without the speedup.The passages identify nA as the number of progress-point visits in phase A and distinguish pA′ and pA as average progress periods with and without a virtual speedup.Source: Adjusting for phases · p. 7
• COZ applies a correction factor to measured phase-A speedups in its final report.The report includes the factor involving T, the total runtime across the two phases.Source: Adjusting for phases · p. 7

4.2 Effectiveness

• COZ-guided changes improved two real applications and six PARSEC benchmarks, with gains as large as 68%; it found opportunities missed by conventional profilers, contention, and opportunities also found by conventional profilers.COZ identified opportunities in all PARSEC benchmarks, though some required changes out of scope for the paper.Source: §4.2 · p. 8, §4.2.8 · p. 11

4.2.1 Case Study: dedup

• In dedup, removing bit shifting raised hash-table utilization to 54.4%; XORing 32-bit key chunks then raised it to 82.0% and improved performance by 8.95% ± 0.27%, in a three-line change.Over 97% of buckets were never used during the entire execution. Gprof’s call graph obscured the importance of hash-table search.Source: §4.2.1 · p. 8

4.2.2 Case Study: ferret

• Ferret improved 21.27% ± 0.17% by reallocating the same number of threads across pipeline stages; gprof’s profile was virtually unchanged after optimization.The final allocation was 20, 1, 22, and 21 threads for segmentation, feature extraction, indexing, and ranking, respectively.Source: §4.2.2 · p. 9

4.2.3 Case Study: SQLite

• SQLite improved 25.60% ± 1.00% after indirect calls to three simple functions were replaced with direct calls.Perf attributed only 0.15% of runtime to those functions, despite their large performance impact.Source: §4.2.3 · pp. 9–10, Figure 7 · p. 9

4.2.4 Case Study: fluidanimate; 4.2.5 Case Study: streamcluster

• Replacing the contended custom barrier with pthread barriers sped fluidanimate by 37.5% ± 0.56% and streamcluster by 68.4% ± 1.12%.In fluidanimate, COZ’s downward-sloping profiles indicated that optimizing the identified lines would slow the application.Source: §4.2.4 · p. 10, §4.2.5 · p. 10

4.2.6 Case Study: Memcached

• Memcached improved 9.39% ± 0.95% after removing a lock from item removal, where atomic reference-count updates made the lock unnecessary.Its static lock array allowed accesses to distinct items with colliding lock indices to contend.Source: §4.2.6 · p. 10

4.2.7 Case Study: blackscholes; 4.2.8 Case Study: swaptions

• For blackscholes, manually eliminating common subexpressions and combining 61 piecewise calculations into 4 larger expressions yielded a 2.56% ± 0.41% program speedup; reordering nested loops and replacing the first loop with memset sped execution by 15.8% ± 1.10%.Source: §4.2.7 · p. 10, §4.2.8 · p. 11

4.3 Accuracy

• For ferret, COZ predicted a 21.4% program speedup versus 21.2% observed; for dedup, it predicted a 9% improvement versus 8.95% observed.The paper characterizes COZ’s predictions as highly accurate.Source: §4.3 · p. 11
• Increasing ferret’s indexing-stage threads from 16 to 22 raised line 320 throughput by 27%.COZ’s predicted program speedup was 21.4%, nearly matching the observed 21.2%.Source: §4.3 · p. 11
• For dedup, replacing the degenerate hash function reduced average bucket elements from 76.7 to 2.09 and loop iterations from 77.7 to 3.09.That change sped up COZ’s identified line by 96%.Source: §4.3 · p. 11

4.4 Efficiency

• COZ’s average PARSEC overhead was 17.6%: 2.6% from startup, 4.8% from sampling, and 10.2% from inserted delays.Figure 9 breaks down overhead by category across the PARSEC benchmarks.Source: §4.4 · p. 11, Figure 9 · p. 11
• COZ’s largest overhead component is delay insertion; reducing it by spacing experiments farther apart would require longer profiling runs.Lazy debug-information processing could reduce startup cost for especially large executables; global sampling could amortize per-thread sampling costs but may require root permissions.Source: §4.4 · pp. 11–12
• COZ overhead ranged from 0.1% to 65%, stayed under 30% on all but three benchmarks, and was 6% on ferret versus gprof’s 6× overhead.The paper concludes that COZ’s overhead is sufficiently low for practical use.Source: §4.4 · p. 12

5.1 General-Purpose Profilers

• Conventional profilers collect execution-time or hardware-counter information, but such profiles may not identify actionable optimization opportunities.Sampling can reduce probe effect, but it must be unbiased.Source: §5 · p. 12, §5.1 · p. 12

5.2 Parallel Profilers

• Critical-path and bottleneck profilers can locate candidate code, but generally do not quantify the performance gain possible before the critical path changes or a bottleneck is removed.Some potential-parallelism tools target serial code rather than diagnosing already-parallelized programs.Source: §5.2 · p. 12
• Causal profiling can measure parallel performance problems from sources beyond explicit thread communication, including cache coherence, scheduling dependencies, and I/O.Other cited bottleneck tools are limited to bottlenecks arising from explicit thread communication.Source: §5.2 · p. 12

5.3 Performance Guidance and Experimentation

• Earlier delay-based approaches generally do not predict the effect of potential optimizations; some require exponentially many configurations or manual perturbations.Active Dependence Discovery requires enumerating system components and manually inserting perturbations.Source: §5.3 · p. 13

6. Conclusion

• Execution time spent in code does not necessarily indicate where programmers should focus optimization efforts, and end-to-end time can miss server and interactive-application metrics.The paper identifies throughput and latency as key metrics for those applications.Source: §6 · p. 13
• Causal profiling runs experiments that virtually speed up lines to measure the impact of any degree of optimization on throughput or latency.The approach establishes relationships between hypothetical optimizations and their effects.Source: §6 · p. 13
• The paper concludes that its COZ prototype is efficient, accurate, and effective at guiding optimization efforts.Source: §6 · p. 13