PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust benchmarking in noisy environments

Jiahao Chen, Jarrett Revels

arXiv:1608.04295v1cs.PF

TL;DR

Benchmark timing is vulnerable to timer error and non-i.i.d. statistics, especially for short executions. The paper models environmental delays and uses that model to motivate an automated benchmarking procedure. It reports that minimum-time estimation is robust to nonideal statistics, while repeated execution does not always eliminate external variation.

  • Problem

    Short benchmark executions can be vulnerable to timer error, and timing measurements may be non-i.i.d., making conventional statistical assumptions unsuitable.

    Source: §I · p. 1, B. Statistics of timing measurements… · p. 2

  • Method

    The paper models environmental effects as added delay instructions and proposes an automated procedure that selects executions per measurement to reduce timing error within a time budget.

    Source: A. User benchmarks run with… · p. 3, §IV · p. 4

  • Results

    The minimum estimator is reported to be robust to nonideal timing statistics and to provide the smallest error, while repeated execution does not always make external variation negligible.

    Source: B. Repeated benchmark execution is… · p. 4, §VI · p. 7

  • Takeaways & Limitations

    The methodology is implemented in BenchmarkTools and used in Julia continuous integration to evaluate performance effects of proposed standard-library changes.

    Source: §VI · p. 7

    Increasing benchmark repetitions does not always eliminate bias from external variation; whether the delay contribution becomes negligible depends on trigger-count distributions.

    Source: B. Repeated benchmark execution is… · p. 4

Abstract

from arXiv · show

We propose a benchmarking strategy that is robust in the presence of timer error, OS jitter and other environmental fluctuations, and is insensitive to the highly nonideal statistics produced by timing measurements. We construct a model that explains how these strongly nonideal statistics can arise from environmental fluctuations, and also justifies our proposed strategy. We implement this strategy in the BenchmarkTools Julia package, where it is used in production continuous integration (CI) pipelines for developing the Julia language and its ecosystem.

I. INTRODUCTION

Benchmarking is needed to detect performance regressions, but timing results are affected by environmental variation and often violate the assumptions behind standard statistical analyses. The paper motivates a language- and platform-agnostic approach that accommodates short benchmarks and non-i.i.d. measurements.

I. INTRODUCTION

  • Ad hoc benchmark interpretation can waste development time and lead to decisions that worsen performance.Source: §I · p. 1
  • The proposed methodology targets language- and platform-agnostic benchmarking for CI and manual workflows, especially for short runs vulnerable to timer error on microsecond or shorter scales.Source: §I · p. 1

A. Accounting for performance variations

  • Environmental factors such as temperature, workload, power availability, network traffic, and OS configuration can make consecutive timing measurements fluctuate, potentially in correlated ways.Source: A. Accounting for performance variations · p. 1

B. Statistics of timing measurements are not i.i.d.

C. Existing benchmarking methodologies

Existing benchmarking approaches address timing error or environmental variation but have trade-offs that limit robustness, efficiency, or automation. The paper presents a fully automated methodology intended to handle non-i.i.d. timing statistics efficiently.

C. Existing benchmarking methodologies

II. TERMS AND DEFINITIONS

  • A timing measurement T_i is the duration of n_i executions, while t_P0 denotes the minimum single-execution time of P0 on a given computer.Source: §II · p. 2
  • An experiment yields trials, each containing timing measurements; τ_budget is the experiment time budget, and τ_acc and τ_prec describe timer accuracy and precision.Source: §II · p. 3
  • The oracle function ν estimates an execution count n intended to overcome timer error due to τ_acc and τ_prec.Source: §II · p. 3

III. A MODEL FOR BENCHMARK TIMING DISTRIBUTIONS

The paper develops a statistical description of serial benchmark execution to explain timing behavior without assuming measurements are i.i.d. This model is intended to justify a new automated experimental procedure.

  • The section presents a statistical description of benchmark programs run in serial.Source: §III · p. 3
  • The model deliberately avoids assuming timing measurements are i.i.d.Source: §III · p. 3
  • The model is later used to justify the design of an automated experimental procedure.Source: §III · p. 3

A. User benchmarks run with uncontrollable delays

The model treats environmental effects as added delay instructions that preserve program semantics while increasing runtime. Delay triggers with nonidentical probabilities yield a Poisson binomial trigger count and a random runtime distribution.

A. User benchmarks run with uncontrollable delays

  • Environmental factors are modeled as extra delay instructions interleaved with the original program, adding runtime without changing its semantics.Source: A. User benchmarks run with… · p. 3
  • Because delay contributions are nonnegative, the executed program's runtime is at least the original program's runtime.Source: A. User benchmarks run with… · p. 3
  • Each delay factor is modeled as triggering with a fixed probability and contributing a fixed time; trigger counts sum independent Bernoulli variables with nonidentical success probabilities.Source: A. User benchmarks run with… · p. 3
  • The resulting program runtime is a random variable whose distribution depends on the delay factors' trigger probabilities and the original program.Source: A. User benchmarks run with… · p. 3

B. Repeated benchmark execution is often necessary but not always sufficient

The model shows that repeated execution can reduce timer error but cannot always eliminate external-delay bias. Whether delay effects vanish depends on their trigger-count distributions.

B. Repeated benchmark execution is often necessary but not always sufficient

  • Repeated execution is necessary to reduce timer error, but whether the delay term vanishes depends on how often delay factors trigger.Timer error becomes negligible after dividing by n, while delay-factor behavior depends on its trigger pattern.Source: B. Repeated benchmark execution is… · p. 4
  • The model represents n executions as concatenated copies of P0, then interleaves delay instructions to model the program that is actually timed.The observed timing also includes timer-inaccuracy error.Source: B. Repeated benchmark execution is… · p. 4
  • Increasing repetitions cannot always remove external-delay bias: the large-n outcome depends on delay-trigger-count distributions.The model identifies this as a key result.Source: B. Repeated benchmark execution is… · p. 4
  • Assuming speed-increasing factors are controlled by maximal-performance power settings, T/n at large n is at best an overestimate of true run time.The model’s worst case has every delay factor trigger on every instruction, so the delay contribution does not disappear.Source: B. Repeated benchmark execution is… · pp. 3–4

IV. AN AUTOMATED PROCEDURE FOR CONFIGURING PERFORMANCE EXPERIMENTS

The procedure automatically selects useful repetition counts for a benchmark program. It prioritizes minimizing timing error, then maximizing the number of measurements within a time budget.

IV. AN AUTOMATED PROCEDURE FOR CONFIGURING PERFORMANCE EXPERIMENTS

  • The procedure automatically estimates a useful repetition count n for a given benchmark program.It is justified by the model of serial benchmark execution.Source: §IV · p. 4
  • Its primary objective is to minimize error in timing measurements.Source: §IV · p. 4
  • Secondarily, it maximizes the number of measurements obtainable within a given time budget.Source: §IV · p. 4

A. An algorithm for estimating the optimal n value

Algorithm 1 estimates the benchmark’s minimum repetition count by measuring batches of executions, estimating single-run time from the lowest per-execution measurement, and applying an oracle. Its repetition search is bounded and can be cached after preprocessing.

A. An algorithm for estimating the optimal n value

  • The procedure takes P0, τacc, τprec, and oracle ν as inputs and returns the repetition count n.The algorithm is described as estimating the repetitions needed to minimize timer error while maximizing data points within a time budget.Source: A. An algorithm for estimating the… · p. 4
  • Algorithm 1 measures execution batches, uses the lowest per-execution time to estimate single-run time, then applies oracle ν to choose n.The procedure is applied once per benchmark, and its estimate can be cached for later experiments on the same machine.Source: A. An algorithm for estimating the… · p. 4
  • The search is capped at j, the timer-accuracy-to-precision ratio, because beyond j repetitions timer inaccuracy contributes less than timer precision.An overestimate of timer accuracy raises the selected n but remains acceptable.Source: A. An algorithm for estimating the… · p. 4

B. Justifying the minimum estimator

The minimum is used to estimate benchmark time because it selects the sample with the smallest observed error and is less sensitive to multimodal timing distributions than common location estimators. Across observed trials, its distribution was unimodal, supporting more reproducible selection of n.

B. Justifying the minimum estimator

  • For branchsum, individual T/n curves can oscillate widely, but their pointwise minimum is smoother and tends asymptotically toward the same constant.The figure plots T/n against n across repeated experiments running Algorithm 1.Source: Figure 2 · p. 5
  • The minimum estimate selects the timing measurement with the smallest sampled error term.The paper states that this estimate minimizes the error terms appearing in the sample.Source: B. Justifying the minimum estimator · pp. 4–5
  • When timer error can be negative, the minimum may underestimate tP0, causing the algorithm to choose a larger n than strictly necessary.The authors describe that outcome as acceptable; when delay-factor time scales exceed τacc, total error terms are always positive.Source: B. Justifying the minimum estimator · p. 5
  • Across observed trials, the minimum was unimodal, while median and trimmed-mean estimates could vary with captured modes and make the selected n less reproducible.The timing distributions can be multimodal; the minimum was unimodal in all cases observed by the authors.Source: B. Justifying the minimum estimator · p. 5, Figure 3 · p. 5, Figure 4 · p. 5

C. The oracle function

The oracle ν maps expected run time to a repetition count, with design criteria that reduce repetition as runtime grows and limit dependence on uncertain timer parameters. The authors report better practical results from empirically tuning a lookup table to the smallest n at which minimum estimates converge to a lower bound.

C. The oracle function

  • The oracle maps expected runtime to a discrete repetition count that decreases with runtime, reaching about j for short runs and about 1 for runs at least τacc.Its dependence on timer precision near τprec and timer accuracy near τacc should be weak because those parameters may be uncertain.Source: C. The oracle function · p. 6
  • A generalized logistic function is one suitable oracle form, with 0.005 < aτprec < 0.02 and 0.4 < b < 0.6 as reasonable parameter ranges.The figure also illustrates a logistic curve using a = 0.009/τprec and b = 0.5.Source: C. The oracle function · p. 6
  • In practice, the authors report better results from approximating the logistic function with an empirically adjusted lookup table.They selected the smallest n at which the minimum estimate appeared to converge to a lower bound for benchmarks with varied known runtimes; one example was about n = 250.Source: C. The oracle function · p. 6

V. IMPLEMENTATION IN JULIA

The methodology is implemented in BenchmarkTools and used by Julia’s on-demand CI benchmarking service. The package’s benchmark suite covers workloads that stress memory retrieval, random-number generation, reallocations, branching, and allocations.

V. IMPLEMENTATION IN JULIA

  • BenchmarkTools implements the on-demand CI service used by Julia core developers to compare proposed language changes across more than 1300 benchmarks.Since the service began in early 2016, it has caught and prevented dozens of serious standard-library performance regressions, defined as at least a 30% increase in a benchmark’s minimum execution time.Source: §V · p. 6
  • The suite includes sumindex for memory-layout-sensitive element retrieval and pushall! for random-number generation and periodic dynamic-array reallocation.The paper identifies these as Julia benchmarks written and executed using BenchmarkTools.Source: §V · p. 6
  • The branchsum and manyallocs benchmarks stress periodically costly branching and frequent allocations of differently sized arrays, respectively.manyallocs also exercises random-number generation, with the generator reseeded to keep the program deterministic.Source: §V · p. 6

VI. CONCLUSION

Timing measurements can be highly nonideal even for simple benchmarks, complicating regression detection. The paper models environmental delays, recommends minimum-based estimation, and implements a timer-error heuristic in BenchmarkTools.

  • Environmental fluctuations can produce highly nonideal, even multimodal timings in simple benchmarks, complicating regression detection.Source: §VI · p. 6
  • The minimum estimator of true benchmark run time is more robust to nonideal statistics and yields the smallest error, versus the mean or median.Source: §VI · p. 7
  • The timer-error heuristic is implemented in BenchmarkTools, used in Julia CI to evaluate standard-library changes, and available for user-authored packages.Source: §VI · p. 7

Related papers

Loading 1608.04295v1…