Raced Profiles: Stop Wasting Cycles on Noisy Compiler Benchmarks

TL;DR

Determining the "best" compiler optimization is often a battle against measurement noise. Standard practices either run everything 30 times (wasting time) or take a few runs and hope for the best (yielding wrong data). Raced Profiles introduces a statistically rigorous "racing" algorithm that prunes bad optimizations early and focuses resources only on the top contenders, cutting benchmarking time by up to 89%.

The Benchmarking Dilemma: Noise vs. Time

In the world of performance engineering, a single execution time is a lie. Between OS interrupts, cache states, and even CPU temperature, the same code can fluctuate in runtime across multiple trials.

Historically, researchers faced a binary choice:

1. Iterative Compilation: Try hundreds of versions, running each a fixed number of times (e.g., 30 or 100). This is safe but painfully slow—training ML models for compilers can take months.
2. Statistically Rigorous Isolation (like JavaSTATS): Run a version until its confidence interval is small enough. This is accurate but inefficient because it spends as much time measuring a "slow" version as it does the "fastest" one.

The Insight: Performance as a Race

The authors realized that in optimization selection, we don't actually care what the absolute runtime of a bad version is—we just need to know it's worse than the current leader.

Instead of independent measurements, the paper proposes Raced Profiles. The algorithm treats all optimization candidates as runners in a race. As soon as a candidate lags behind a leader with statistical significance (using a Welch's t-test), it is "disqualified" and stops running.

Figure 1: The racing stages. (a) Initialize samples. (b) Prune clear losers. (c) Grow samples for contenders. (d) Finish when versions are equivalent.

Methodology: T-Tests and Equivalence

The core of the "Race" involves two sophisticated statistical hurdles:

• Welch’s T-test: Unlike a standard t-test, Welch’s does not assume the variances of two versions are equal. This is crucial because "bad" optimizations often exhibit higher variance (more noise) than "good" ones.
• Equivalence Testing ($ϵ$-Indifference): If two versions are within 0.5% of each other, they are effectively the same for any compiler writer. The algorithm uses an indifference region to stop the race when the top contenders are "close enough," preventing "infinite sampling" of identical binaries.

Experimental Proof: Massive Efficiency Gains

The authors tested this on loop unrolling (230 loops) and compiler flags (57 benchmarks).

Figure 2: Failure rate vs. sample size. Note how the Adaptive (Raced) plan reaches the <1% failure zone significantly faster than fixed or JavaSTATS approaches.

In "easy" cases where a winner is obvious, Raced Profiles needs as little as 2.15 samples per version. Even in high-noise environments, it maintains accuracy by dynamically scaling up.

Critical Analysis & Conclusion

Takeaway

Raced Profiles proves that we can achieve statistical rigor faster than brute-force benchmarking. By integrating the decision-making process (which is better?) with the measurement process (how long does it take?), we can prune the search space of compilers, autotuners, and even ML hyperparameter searches.

Limitations

• Log-Normal Assumption: The approach assumes a log-transform makes the data normal. While generally true for system timing, extremely heavy-tailed distributions (like those in distributed systems) might still challenge the t-test.
• Independence: The current algorithm doesn't "learn" across different loops/benchmarks; it treats every race as starting from scratch.

Future Impact

As we move toward AI-driven compilers (like MLGO), the ability to generate gold-standard training data in 1/10th of the time is a game-changer for the field.