Benchmarking and the doubling experiment

Counting steps tells you how an algorithm should grow; a measurement tells you what a real program on a real computer does. Measuring well is harder than it looks: the clock you pick, what else the computer is doing, a just-in-time compiler and even the order of your runs can each change the answer. This lesson shows how to time code honestly in five languages and how to read a growth rate off a few timings with the doubling experiment.

Pick a clock that only moves forwards

A computer has more than one clock. The wall clock tells the time of day; it can jump when the system clock is corrected, so the difference between two readings may even be negative. A monotonic clock never goes backwards and is not adjusted, which makes it the right tool for durations. Python’s documentation says so plainly about time.time(): a later call can return a smaller value if the system clock was set back in between. Python can tell you what each of its clocks promises:

import time

# What Python says about each of its clocks.
for name in ["perf_counter", "monotonic", "process_time", "time"]:
    info = time.get_clock_info(name)
    print(f"time.{name}(): monotonic={info.monotonic}, adjustable={info.adjustable}")

time.perf_counter(): monotonic=True, adjustable=False
time.monotonic(): monotonic=True, adjustable=False
time.process_time(): monotonic=True, adjustable=False
time.time(): monotonic=False, adjustable=True

• time.perf_counter() is the one to time code with: it is monotonic and has the highest resolution available. Its starting point is undefined, so only the difference between two readings means anything. time.perf_counter_ns() returns the same reading as a whole number of nanoseconds.
• time.process_time() counts the processor time of your program only. Time spent sleeping, or waiting while other programs use the processor, is not counted, which makes it steadier on a busy computer.
• time.time() is the wall clock: right for timestamps, wrong for durations.

Every language this track uses has a monotonic clock for measuring durations, and some have a benchmark tool:

• Python: time.perf_counter_ns(), in whole nanoseconds. The standard library’s benchmark tool is the timeit module, shown below.
• JavaScript: performance.now(), in milliseconds with a fractional part, counted from the start of the page or, in Node.js, of the process. Browsers deliberately coarsen it, to 100 microseconds on most pages (5 microseconds on cross-origin isolated ones), to make timing attacks harder. Date.now() is the wall clock in whole milliseconds. QuickJS, which runs JavaScript for this site’s Run buttons, has no performance object, so Date.now() is all a program can use there. The language has no benchmark tool.
• Java: System.nanoTime(), a long count of nanoseconds. The documentation says it is only for elapsed time: its origin is arbitrary and unrelated to the time of day, and it promises nanosecond precision but not nanosecond resolution. The JDK has no benchmark tool; JMH is a separate OpenJDK project.
• C++: std::chrono::steady_clock::now(); subtract two time points for a duration. The standard requires this clock never to decrease and to advance at a steady rate; the wall clock is std::chrono::system_clock. The standard library has no benchmark tool.
• Go: time.Now(), then time.Since(start) for a time.Duration. time.Now() carries a monotonic reading as well as the wall-clock time, and time.Since uses the monotonic one, so a measured duration survives a clock change. go test runs benchmarks written with testing.B and b.Loop().

Let the standard library repeat the runs

A single measurement catches whatever else the computer happened to be doing. Python’s timeit module runs a statement many times with time.perf_counter(), switches off garbage collection while it times, and with repeat gives you several measurements. Its documentation advises looking at the smallest of them: other programs can only add time, never take it away, so the fastest run is the closest to what the code itself costs.

Repeating a run is only fair if every run does the same work. This example shows how easily that goes wrong:

import random
import timeit

random.seed(42)
data = [random.random() for _ in range(100_000)]

# A trap: data.sort() sorts the list in place, so every run after the first sorts a list that is already sorted.
in_place = timeit.repeat("data.sort()", globals=globals(), repeat=5, number=1)

random.shuffle(data)
# Each run sorts the same shuffled list: sorted() returns a new list and leaves data as it was.
fresh = timeit.repeat("sorted(data)", globals=globals(), repeat=5, number=1)

for label, runs in [("data.sort(), in place", in_place), ("sorted(data), a new list", fresh)]:
    print(f"{label}:")
    print("  " + "  ".join(f"{seconds * 1000:.1f}" for seconds in runs) + " ms")
    print(f"  fastest: {min(runs) * 1000:.1f} ms")

data.sort(), in place:
  14.5  0.4  0.5  0.4  0.3 ms
  fastest: 0.3 ms
sorted(data), a new list:
  17.6  17.4  17.7  18.4  29.3 ms
  fastest: 17.4 ms

data.sort() sorts the list in place, so only its first run sorts shuffled data; every later run is handed a list that is already sorted. Python’s sort is adaptive: its documented cost is O(n log n), but sorted input takes only O(n) comparisons. The “fastest” run is therefore many times faster than real sorting, and wrong. sorted(data) returns a new list and leaves data shuffled, so all five runs do the same work, and only the computer’s other work makes their times differ. Whenever a measured piece of code changes its input, build a fresh input for every run, outside the timed part.

The doubling experiment

Suppose the running time grows like $T(n) \approx a \cdot n^b$ for some constant $a$ and an unknown exponent $b$. Doubling the input then multiplies the time by a fixed factor:

Time the code at n, 2n, 4n, 8n and look at the ratio of each time to the one before. A ratio near 2 means linear growth (b ≈ 1); a little above 2, such as 2.1 to 2.2, suggests n log n; near 4 means quadratic (b ≈ 2); and near 8 means cubic (b ≈ 3). The constant $a$, which depends on the computer and the language, cancels out, so the experiment works on any machine.

This helper does the experiment in Python. It builds a fresh input for every run outside the timing, keeps the fastest of three runs, prints each ratio with its exponent and, at the end, the slope of a straight line through all the points on a log-log scale, which is steadier than any single ratio. It compares two ways of emptying a queue:

import math
import time
from collections import deque


def best_time(work, make_input, n, clock, repeats=3):
    """Seconds taken by the fastest of `repeats` runs of work(make_input(n)); making the input is not timed."""
    best = float("inf")
    for _ in range(repeats):
        data = make_input(n)
        start = clock()
        work(data)
        best = min(best, clock() - start)
    return best


def doubling(name, work, make_input, sizes, clock=time.perf_counter):
    """Time work for each size; print T(n), the ratio T(n) / T(n/2) and its exponent b = log2(ratio)."""
    print(name)
    print(f"{'n':>8} {'ms':>9} {'ratio':>6} {'b':>5}")
    times = []
    for n in sizes:
        times.append(best_time(work, make_input, n, clock))
        line = f"{n:>8,} {times[-1] * 1000:>9.2f}"
        if len(times) > 1:
            ratio = times[-1] / times[-2]
            line += f" {ratio:>6.2f} {math.log2(ratio):>5.2f}"
        print(line)
    # The slope of log T against log n over all the sizes: steadier than any single ratio.
    xs = [math.log2(n) for n in sizes]
    ys = [math.log2(t) for t in times]
    mean_x, mean_y = sum(xs) / len(xs), sum(ys) / len(ys)
    slope = sum((x - mean_x) * (y - mean_y) for x, y in zip(xs, ys)) / sum((x - mean_x) ** 2 for x in xs)
    print(f"estimated exponent b = {slope:.2f}")


def empty_with_pop0(items):
    while items:
        items.pop(0)


def empty_with_popleft(items):
    while items:
        items.popleft()


SIZES = [10_000, 20_000, 40_000, 80_000]
# CPU time rather than wall-clock time: the computer that recorded this output was busy with other work.
doubling("list.pop(0) until empty", empty_with_pop0, lambda n: list(range(n)), SIZES, clock=time.process_time)
doubling("deque.popleft() until empty", empty_with_popleft, lambda n: deque(range(n)), SIZES, clock=time.process_time)

list.pop(0) until empty
       n        ms  ratio     b
  10,000      9.29
  20,000     45.59   4.91  2.29
  40,000    191.55   4.20  2.07
  80,000    769.48   4.02  2.01
estimated exponent b = 2.12
deque.popleft() until empty
       n        ms  ratio     b
  10,000      0.23
  20,000      0.46   2.01  1.01
  40,000      0.94   2.04  1.03
  80,000      1.97   2.09  1.06
estimated exponent b = 1.03

list.pop(0) gives ratios around 4 and an exponent near 2: emptying a list from the front is quadratic, because every pop(0) moves all the remaining items one place to the left, as the documentation of collections.deque warns. deque.popleft() gives ratios around 2 and an exponent near 1: it removes the front item without moving the rest. Single ratios wobble, most of all between the smallest sizes, which are the most sensitive to the processor’s caches and to whatever else the computer is doing; read the trend and the fitted exponent rather than one ratio. The output on this page was recorded with time.process_time(), which leaves out the time the program spent waiting for the processor, because the recording computer was busy with other work. On your own computer the default clock, time.perf_counter(), is the usual choice.

The same helper in JavaScript compares two ways of counting the distinct values in a list:

// performance.now() where it exists (Node.js, browsers); QuickJS has only Date.now(), in whole milliseconds.
const now = typeof performance === 'object' ? () => performance.now() : () => Date.now();

/** Milliseconds taken by the fastest of `repeats` runs of work(makeInput(n)); making the input is not timed. */
function bestTime(work, makeInput, n, repeats = 7) {
  let best = Infinity;
  for (let r = 0; r < repeats; r++) {
    const data = makeInput(n);
    const start = now();
    work(data);
    best = Math.min(best, now() - start);
  }
  return best;
}

const pad = (text, width) => String(text).padStart(width);
const withCommas = (n) => String(n).replace(/\B(?=(\d{3})+(?!\d))/g, ',');

/** Times work for each size; prints T(n), the ratio T(n) / T(n/2) and its exponent b = log2(ratio). */
function doubling(name, work, makeInput, sizes) {
  console.log(name);
  console.log(`${pad('n', 8)} ${pad('ms', 9)} ${pad('ratio', 6)} ${pad('b', 5)}`);
  const times = [];
  for (const n of sizes) {
    times.push(Math.max(bestTime(work, makeInput, n), 0.001));
    let line = `${pad(withCommas(n), 8)} ${pad(times.at(-1).toFixed(2), 9)}`;
    if (times.length > 1) {
      const ratio = times.at(-1) / times.at(-2);
      line += ` ${pad(ratio.toFixed(2), 6)} ${pad(Math.log2(ratio).toFixed(2), 5)}`;
    }
    console.log(line);
  }
  // The slope of log T against log n over all the sizes: steadier than any single ratio.
  const xs = sizes.map(Math.log2);
  const ys = times.map(Math.log2);
  const meanX = xs.reduce((a, b) => a + b) / xs.length;
  const meanY = ys.reduce((a, b) => a + b) / ys.length;
  let above = 0;
  let below = 0;
  for (let i = 0; i < xs.length; i++) {
    above += (xs[i] - meanX) * (ys[i] - meanY);
    below += (xs[i] - meanX) ** 2;
  }
  console.log(`estimated exponent b = ${(above / below).toFixed(2)}`);
}

// n different numbers in a scrambled order: 7919 is odd, so i * 7919 % n meets every value once when n is a power of 2.
const scrambled = (n) => Array.from({ length: n }, (_, i) => (i * 7919) % n);

function countDistinctWithArray(values) {
  const seen = [];
  for (const v of values) if (!seen.includes(v)) seen.push(v);
  return seen.length;
}

function countDistinctWithSet(values) {
  const seen = new Set();
  for (const v of values) seen.add(v);
  return seen.size;
}

doubling('distinct values with Array.prototype.includes()', countDistinctWithArray, scrambled, [2048, 4096, 8192, 16384]);
doubling('distinct values with a Set', countDistinctWithSet, scrambled, [16384, 32768, 65536, 131072]);

distinct values with Array.prototype.includes()
       n        ms  ratio     b
   2,048      0.65
   4,096      2.24   3.47  1.80
   8,192      8.99   4.01  2.00
  16,384     40.31   4.49  2.17
estimated exponent b = 1.99
distinct values with a Set
       n        ms  ratio     b
  16,384      0.71
  32,768      1.65   2.32  1.21
  65,536      3.73   2.26  1.17
 131,072      9.75   2.62  1.39
estimated exponent b = 1.25

includes() looks through the array element by element, so checking every new value against all the earlier ones is quadratic: its exponent comes out close to 2. The language standard requires a Set only to find a value in less than linear time on average; the measurement shows that one pass with a Set grows close to linearly. Its exponent comes out above 1 but well below 2: a step count treats every lookup as equally cheap, but a bigger table no longer fits in the processor’s fastest caches, so each lookup tends to cost a little more. The two workloads use different sizes, so that every measurement takes long enough to time.

Warm-up, just-in-time compilers and work that disappears

Engines with a just-in-time (JIT) compiler change speed while your program runs. V8, the engine in Node.js and Chrome, starts every function in its Ignition interpreter. A function that runs often is compiled to machine code: first quickly by Sparkplug, a compiler that does not optimise, and later by an optimising compiler, once V8 has seen what kinds of values the function handles. This program times the same function eight times:

// performance.now() where it exists (Node.js, browsers); QuickJS has only Date.now(), in whole milliseconds.
const now = typeof performance === 'object' ? () => performance.now() : () => Date.now();
const values = Array.from({ length: 200_000 }, (_, i) => (i * 7919) % 1000);

function sumOfSquares(items) {
  let total = 0;
  for (let i = 0; i < items.length; i++) total += items[i] * items[i];
  return total;
}

const engine = typeof process === 'object' ? `Node.js ${process.versions.node} (V8 ${process.versions.v8})` : 'not Node.js';
console.log(`engine: ${engine}`);
let checksum = 0;
for (let round = 1; round <= 8; round++) {
  const start = now();
  checksum += sumOfSquares(values);
  console.log(`round ${round}: ${(now() - start).toFixed(2)} ms`);
}
// Using the result keeps an optimising compiler from deciding the work is not needed.
console.log(`checksum ${checksum}`);

engine: Node.js 24.21.0 (V8 13.6.233.17-node.53)
round 1: 2.41 ms
round 2: 1.16 ms
round 3: 0.44 ms
round 4: 0.44 ms
round 5: 0.47 ms
round 6: 0.45 ms
round 7: 0.45 ms
round 8: 0.51 ms
checksum 532533600000

The first round in V8 is several times slower than the later ones: it started in the interpreter while V8 gathered information, and later rounds ran compiled code. Java’s virtual machine works the same way, starting in an interpreter and compiling the parts that run often, which is one reason the OpenJDK project offers JMH, a harness for building and running Java benchmarks. Three habits keep JIT engines honest:

• Warm up. Run the code a few times before you start the clock, or drop the first rounds.
• Use the result. An optimising compiler may leave out work whose result nobody reads. Every program in this lesson prints or checks what it computed, like the checksum above. In Go, write benchmarks with b.Loop(): its documentation says that the arguments and results of function calls inside the loop are kept alive, so the compiler cannot optimise the loop body away.
• Keep the timed part small and fixed. Build inputs before the clock starts and time only the code you mean to measure.

Report what you measured

A timing describes one program on one computer with one runtime. When you share a measurement, say which processor, operating system and runtime version produced it, and how you summarised the runs (fastest, median or mean). Each output on this page names the runtime and platform it was recorded with, so you can compare it with what you see when you press Run or run a file on your own computer.

Key takeaways

• Time durations with a monotonic clock: time.perf_counter_ns(), performance.now(), System.nanoTime(), std::chrono::steady_clock or time.Since; never with the wall clock.
• Repeat every measurement, keep the fastest run (or the median), and make sure every run does the same work on a freshly built input.
• In the doubling experiment the ratio T(2n) / T(n) is about 2ᵇ: around 2 for linear, a little above 2 for n log n, 4 for quadratic and 8 for cubic. Read the trend, not one ratio.
• JIT engines such as V8 and the Java virtual machine speed up as they run: warm up first, use every result, and report the hardware and runtime with your numbers.