Capstone: Benchmark Your Language
Goal
Module 0 made three kinds of claim. Complexity Analysis said how the cost of an operation grows. How Data Structures Live in Memory said why two operations with the same growth can differ by 10x–30x. Your Language's Data Structures said what each built-in container actually costs. This capstone turns those claims into measurements on your own machine, in your own language.
You will build a small benchmark harness, use it to measure a dynamic array, a hash map, a sorted structure and two sorts, write down a prediction before every run, and then explain every gap between prediction and measurement. The deliverable is not the numbers. It is the write-up: a table of predicted against measured values and one paragraph per surprise saying which mechanism caused it.
Budget: three to five hours in one language. Doing it in a second language is the best way to learn the second language's costs.
Requirements
Your solution must:
- Be a single program in Python, Java, C++ or TypeScript, using only the standard library.
- Contain a reusable timing function that does one warm-up run, then timed runs (at least 3, ideally 5–11), and reports the median. Use a monotonic high-resolution clock:
time.perf_counter_ns,System.nanoTime,std::chrono::steady_clock,performance.now. - Check correctness of every measured computation with an assertion (sums equal, sizes equal, sorted outputs identical). Never assert on timing; timing varies between machines and runs.
- Make every computed result observable (return it, sum it, print it) so the compiler or JIT cannot delete the work you are timing.
- Run all experiments in under about 10 seconds with the default sizes, so you rerun it often.
- Print a table: experiment name, , median time, and the ratios the write-up needs.
- Come with a write-up (part 5) in which every prediction was recorded before the corresponding run.
Staged plan
flowchart LR
P1["Part 1<br/>timing harness"] --> P2["Part 2<br/>array access<br/>and insertion"]
P2 --> P3["Part 3<br/>hash map vs<br/>sorted structure"]
P3 --> P4["Part 4<br/>built-in sort vs<br/>your merge sort"]
P4 --> P5["Part 5<br/>predicted vs measured<br/>write-up"]
P5 -.->|"surprise? rerun"| P2
Part 1 — the timing harness
Write bench(fn, k) that calls fn once without timing (warm-up: page faults, cold caches, lazy initialisation, and in Java and V8 the JIT), then calls it times, records each duration, and returns the median and the last result. Why the median and not the mean: one run interrupted by the OS scheduler or a garbage collection can double the mean but barely moves the median. Why return the result: so the caller can assert on it and so the optimiser sees it used.
flowchart TD
S["bench(fn, k)"] --> W["warm-up: call fn once, discard time"]
W --> L{"runs < k?"}
L -->|"yes"| T["t0 = clock()<br/>result = fn()<br/>record clock() - t0"]
T --> L
L -->|"no"| M["sort times, take median"]
M --> R["return (median, result)"]
R --> A["caller asserts on result,<br/>never on time"]
Sanity checks before trusting it: time an empty function (that is your measurement floor; nothing below roughly 10x the floor means anything), and time the same function twice with the harness — the two medians should agree within about 10%. If they do not, close other programs, plug in the laptop, and increase . Benchmarks covers the methodology in depth: CPU frequency scaling, pinning, and why microbenchmarks lie.
Part 2 — array access and insertion
2a. Sequential versus random-order traversal. Fill an array with integers. Sum it in index order, then sum it in the order of a random permutation of the indices. Both sums must be equal. Predict: Big-O says the ratio is 1. The memory lesson says it is not. Write down a number.
Then vary : , , , (if memory allows). Predict where the ratio jumps — think about your L2 and L3 sizes and how many bytes each element really takes in your language (4 for a C++ int, 4 for a Java int[], 8 plus 28 for a Python list of ints).
2b. Push at the back versus insert at the front. Build a list of elements by appending, then by inserting each new element at index 0 (insert(0, x), add(0, x), insert(begin(), x), unshift). Predict: appending is total and front-insertion , so the ratio is on the order of … or is it? The shift is a memmove of contiguous memory. Predict a number, then double and check that the front-insertion time roughly quadruples while the append time doubles.
Part 3 — hash map versus sorted structure
For (and if your language finishes in time), build a hash map and a sorted structure holding the same random keys:
| Language | Hash map | Sorted structure |
|---|---|---|
| Python | dict | sorted list + bisect.bisect_left |
| Java | HashMap<Integer, Integer> | TreeMap<Integer, Integer> |
| C++ | std::unordered_map<int, int> | std::map<int, int> |
| TypeScript | Map<number, number> | sorted number[] + hand-written binary search |
Time successful lookups against each. Assert that both find every key. Predict: hash lookups are , so their time should be flat in ; sorted lookups are , so going from to should cost x. Then predict what the cache does to both curves: the hash map stops being flat when its table falls out of L2, and the tree in Java and C++ pays a pointer chase per level.
Part 4 — built-in sort versus your merge sort
Write a textbook top-down merge sort (from Sorting & Searching). Sort the same random integers with it and with the built-in sort (sorted, Arrays.sort, std::sort, Array.prototype.sort with a numeric comparator). Assert the outputs are identical. Predict the ratio. Both are ; the difference is entirely constant factors: language of implementation, allocation per call, insertion sort for small runs, adaptivity to existing order. Then rerun both on already-sorted input and predict again — Timsort (Python, Java objects, JavaScript) should become nearly linear; your merge sort should not.
Part 5 — the write-up
Copy this template and fill it in. The Predicted column must be filled before you run.
| Experiment | Predicted | Measured | Within 2x? | Mechanism | |
|---|---|---|---|---|---|
| random / sequential traversal | |||||
| random / sequential traversal | |||||
| front-insert / append | |||||
| front-insert time when doubles | |||||
| sorted / hash lookup | |||||
| sorted / hash lookup | |||||
| hash lookup time, vs | |||||
| merge sort / built-in sort, random | |||||
| merge sort / built-in sort, presorted |
Then one paragraph per row that missed by more than 2x, answering: what did I assume, what actually happens in the machine or the runtime, and how would I confirm it? "Cache misses" is not an explanation unless you can say which data structure missed and why. A good paragraph names the mechanism and proposes a follow-up experiment that would isolate it.
Acceptance tests
Your program passes when all of the following hold. Each is checkable by running it.
- It exits with status 0 and prints the table, in under about 10 seconds with default sizes.
- Every experiment asserts correctness: traversal sums equal ; both list-building methods produce elements; every lookup finds its key in both structures; both sorts produce identical output equal to a reference sort.
- Running it twice in a row gives medians that agree within roughly 20% for every experiment that takes more than a millisecond.
- Changing from 3 to 7 does not change any median by more than roughly 20%.
- Your write-up has a prediction for every row, recorded before the run, and an explanation for every miss larger than 2x.
Reference solution
Read this only after you have a working harness of your own. All four programs implement parts 1–4 with the same sizes, assert correctness only, and run in a few seconds each.
Reference solution
"""Module 0 capstone: measure, do not guess. Python 3.12+, standard library only."""
import bisect
import random
import statistics
import time
from collections.abc import Callable
K_RUNS = 3 # median of K timed runs, after one warm-up run
rng = random.Random(42)
def bench(fn: Callable[[], object], k: int = K_RUNS) -> tuple[float, object]:
"""Return (median seconds, result of the last run). The result is returned so callers can assert on it."""
result = fn() # warm-up (also fills caches, triggers lazy init)
times = []
for _ in range(k):
t0 = time.perf_counter_ns()
result = fn()
times.append(time.perf_counter_ns() - t0)
return statistics.median(times) / 1e9, result
def merge_sort(a: list[int]) -> list[int]:
if len(a) <= 1:
return a[:]
mid = len(a) // 2
left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
out: list[int] = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:]); out.extend(right[j:])
return out
def main() -> None:
rows: list[tuple[str, float]] = []
# Part 2a: sequential vs random-order traversal of the same array
n = 1_000_000
data = list(range(n))
perm = data[:]; rng.shuffle(perm)
t_seq, s_seq = bench(lambda: sum(data[i] for i in range(n)))
t_rand, s_rand = bench(lambda: sum(data[i] for i in perm))
assert s_seq == s_rand == n * (n - 1) // 2
rows += [("traverse sequential (1e6)", t_seq), ("traverse random order (1e6)", t_rand)]
# Part 2b: append at the back vs insert at the front
def push_back(m: int) -> int:
xs: list[int] = []
for i in range(m): xs.append(i)
return len(xs)
def insert_front(m: int) -> int:
xs: list[int] = []
for i in range(m): xs.insert(0, i)
return len(xs)
t_back, len_back = bench(lambda: push_back(20_000))
t_front, len_front = bench(lambda: insert_front(20_000))
assert len_back == len_front == 20_000
rows += [("20k append", t_back), ("20k insert(0)", t_front)]
# Part 3: hash map vs sorted structure, lookups at several n
queries_per_round = 100_000
for size in (1_000, 10_000, 100_000):
keys = rng.sample(range(10 * size), size)
d = {k: k for k in keys}
sorted_keys = sorted(keys)
qs = [keys[rng.randrange(size)] for _ in range(queries_per_round)]
t_hash, found_hash = bench(lambda: sum(1 for q in qs if q in d))
t_sorted, found_sorted = bench(
lambda: sum(1 for q in qs if sorted_keys[bisect.bisect_left(sorted_keys, q)] == q))
assert found_hash == found_sorted == queries_per_round
rows += [(f"dict lookup x1e5, n={size}", t_hash), (f"bisect lookup x1e5, n={size}", t_sorted)]
# Part 4: built-in sort vs your merge sort
arr = [rng.randrange(1_000_000) for _ in range(100_000)]
t_builtin, s1 = bench(lambda: sorted(arr))
t_merge, s2 = bench(lambda: merge_sort(arr))
assert s1 == s2 and s1 == sorted(arr)
rows += [("sorted() 1e5", t_builtin), ("merge_sort 1e5", t_merge)]
print(f"{'experiment':34} {'median s':>10}")
for name, t in rows:
print(f"{name:34} {t:10.4f}")
print(f"random/sequential ratio: {t_rand / t_seq:.1f}x")
print(f"insert(0)/append ratio: {t_front / t_back:.1f}x")
print(f"merge_sort/sorted ratio: {t_merge / t_builtin:.1f}x")
if __name__ == "__main__":
main()
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Random;
import java.util.TreeMap;
import java.util.function.LongSupplier;
public class Capstone {
static final int K_RUNS = 3;
static final Random rng = new Random(42);
/** Median of K timed runs after one warm-up. Returns {seconds, lastResult}. */
static double[] bench(LongSupplier fn) {
long result = fn.getAsLong(); // warm-up (JIT, caches)
long[] t = new long[K_RUNS];
for (int i = 0; i < K_RUNS; i++) {
long t0 = System.nanoTime();
result = fn.getAsLong();
t[i] = System.nanoTime() - t0;
}
Arrays.sort(t);
return new double[]{t[K_RUNS / 2] / 1e9, (double) result};
}
static int[] mergeSort(int[] a) {
if (a.length <= 1) return a.clone();
int mid = a.length / 2;
int[] l = mergeSort(Arrays.copyOfRange(a, 0, mid)), r = mergeSort(Arrays.copyOfRange(a, mid, a.length));
int[] out = new int[a.length];
int i = 0, j = 0, k = 0;
while (i < l.length && j < r.length) out[k++] = l[i] <= r[j] ? l[i++] : r[j++];
while (i < l.length) out[k++] = l[i++];
while (j < r.length) out[k++] = r[j++];
return out;
}
static void check(boolean ok, String msg) { if (!ok) throw new AssertionError(msg); }
public static void main(String[] args) {
List<String> names = new ArrayList<>();
List<Double> times = new ArrayList<>();
// Part 2a: sequential vs random-order traversal
int n = 1_000_000;
int[] data = new int[n], perm = new int[n];
for (int i = 0; i < n; i++) { data[i] = i; perm[i] = i; }
for (int i = n - 1; i > 0; i--) { int j = rng.nextInt(i + 1); int t = perm[i]; perm[i] = perm[j]; perm[j] = t; }
double[] seq = bench(() -> { long s = 0; for (int i = 0; i < n; i++) s += data[i]; return s; });
double[] rnd = bench(() -> { long s = 0; for (int i = 0; i < n; i++) s += data[perm[i]]; return s; });
check(seq[1] == rnd[1] && seq[1] == (double) ((long) n * (n - 1) / 2), "sums");
names.add("traverse sequential (1e6)"); times.add(seq[0]);
names.add("traverse random order (1e6)"); times.add(rnd[0]);
// Part 2b: add at the back vs add(0, x) at the front
double[] back = bench(() -> { ArrayList<Integer> xs = new ArrayList<>(); for (int i = 0; i < 20_000; i++) xs.add(i); return xs.size(); });
double[] front = bench(() -> { ArrayList<Integer> xs = new ArrayList<>(); for (int i = 0; i < 20_000; i++) xs.add(0, i); return xs.size(); });
check(back[1] == 20_000 && front[1] == 20_000, "sizes");
names.add("20k add(x)"); times.add(back[0]);
names.add("20k add(0, x)"); times.add(front[0]);
// Part 3: HashMap vs TreeMap lookups
int q = 100_000;
for (int size : new int[]{1_000, 10_000, 100_000}) {
int[] keys = new int[size];
HashMap<Integer, Integer> hm = new HashMap<>();
TreeMap<Integer, Integer> tm = new TreeMap<>();
for (int i = 0; i < size; i++) {
int k; do { k = rng.nextInt(10 * size); } while (hm.containsKey(k));
keys[i] = k; hm.put(k, k); tm.put(k, k);
}
int[] qs = new int[q];
for (int i = 0; i < q; i++) qs[i] = keys[rng.nextInt(size)];
double[] h = bench(() -> { long f = 0; for (int x : qs) if (hm.containsKey(x)) f++; return f; });
double[] t = bench(() -> { long f = 0; for (int x : qs) if (tm.containsKey(x)) f++; return f; });
check(h[1] == q && t[1] == q, "lookups");
names.add("HashMap lookup x1e5, n=" + size); times.add(h[0]);
names.add("TreeMap lookup x1e5, n=" + size); times.add(t[0]);
}
// Part 4: Arrays.sort vs merge sort
int[] arr = new int[100_000];
for (int i = 0; i < arr.length; i++) arr[i] = rng.nextInt(1_000_000);
int[][] holder = new int[2][];
double[] builtin = bench(() -> { holder[0] = arr.clone(); Arrays.sort(holder[0]); return holder[0][0]; });
double[] merge = bench(() -> { holder[1] = mergeSort(arr); return holder[1][0]; });
check(Arrays.equals(holder[0], holder[1]), "sort results differ");
names.add("Arrays.sort 1e5"); times.add(builtin[0]);
names.add("mergeSort 1e5"); times.add(merge[0]);
System.out.printf("%-34s %10s%n", "experiment", "median s");
for (int i = 0; i < names.size(); i++) System.out.printf("%-34s %10.4f%n", names.get(i), times.get(i));
System.out.printf("random/sequential ratio: %.1fx%n", rnd[0] / seq[0]);
System.out.printf("add(0)/add ratio: %.1fx%n", front[0] / back[0]);
System.out.printf("mergeSort/Arrays.sort: %.1fx%n", merge[0] / builtin[0]);
}
}
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <map>
#include <numeric>
#include <random>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
constexpr int K_RUNS = 3;
static std::mt19937 rng(42);
// Median of K timed runs after one warm-up. Returns {seconds, result of last run}.
template <typename F>
std::pair<double, std::int64_t> bench(F fn) {
std::int64_t result = fn();
std::vector<double> t;
for (int i = 0; i < K_RUNS; ++i) {
auto t0 = std::chrono::steady_clock::now();
result = fn();
t.push_back(std::chrono::duration<double>(std::chrono::steady_clock::now() - t0).count());
}
std::sort(t.begin(), t.end());
return {t[K_RUNS / 2], result};
}
std::vector<int> merge_sort(const std::vector<int>& a) {
if (a.size() <= 1) return a;
std::size_t mid = a.size() / 2;
std::vector<int> l = merge_sort({a.begin(), a.begin() + mid}), r = merge_sort({a.begin() + mid, a.end()});
std::vector<int> out;
out.reserve(a.size());
std::size_t i = 0, j = 0;
while (i < l.size() && j < r.size()) out.push_back(l[i] <= r[j] ? l[i++] : r[j++]);
while (i < l.size()) out.push_back(l[i++]);
while (j < r.size()) out.push_back(r[j++]);
return out;
}
int main() {
std::vector<std::pair<std::string, double>> rows;
// Part 2a: sequential vs random-order traversal
const int n = 1'000'000;
std::vector<int> data(n), perm(n);
std::iota(data.begin(), data.end(), 0);
perm = data;
std::shuffle(perm.begin(), perm.end(), rng);
auto seq = bench([&] { std::int64_t s = 0; for (int i = 0; i < n; ++i) s += data[i]; return s; });
auto rnd = bench([&] { std::int64_t s = 0; for (int i = 0; i < n; ++i) s += data[perm[i]]; return s; });
assert(seq.second == rnd.second && seq.second == static_cast<std::int64_t>(n) * (n - 1) / 2);
rows.push_back({"traverse sequential (1e6)", seq.first});
rows.push_back({"traverse random order (1e6)", rnd.first});
// Part 2b: push_back vs insert at begin()
auto back = bench([] { std::vector<int> xs; for (int i = 0; i < 20'000; ++i) xs.push_back(i); return (std::int64_t)xs.size(); });
auto front = bench([] { std::vector<int> xs; for (int i = 0; i < 20'000; ++i) xs.insert(xs.begin(), i); return (std::int64_t)xs.size(); });
assert(back.second == 20'000 && front.second == 20'000);
rows.push_back({"20k push_back", back.first});
rows.push_back({"20k insert(begin)", front.first});
// Part 3: unordered_map vs map lookups
const int q = 100'000;
for (int size : {1'000, 10'000, 100'000}) {
std::unordered_map<int, int> um;
std::map<int, int> om;
std::vector<int> keys;
std::uniform_int_distribution<int> dist(0, 10 * size - 1);
while ((int)keys.size() < size) {
int k = dist(rng);
if (um.emplace(k, k).second) { om[k] = k; keys.push_back(k); }
}
std::vector<int> qs(q);
std::uniform_int_distribution<int> pick(0, size - 1);
for (int& x : qs) x = keys[pick(rng)];
auto h = bench([&] { std::int64_t f = 0; for (int x : qs) f += um.count(x); return f; });
auto t = bench([&] { std::int64_t f = 0; for (int x : qs) f += om.count(x); return f; });
assert(h.second == q && t.second == q);
rows.push_back({"unordered_map lookup x1e5, n=" + std::to_string(size), h.first});
rows.push_back({"map lookup x1e5, n=" + std::to_string(size), t.first});
}
// Part 4: std::sort vs merge sort
std::vector<int> arr(100'000);
std::uniform_int_distribution<int> d2(0, 999'999);
for (int& x : arr) x = d2(rng);
std::vector<int> s1, s2;
auto builtin = bench([&] { s1 = arr; std::sort(s1.begin(), s1.end()); return (std::int64_t)s1[0]; });
auto merge = bench([&] { s2 = merge_sort(arr); return (std::int64_t)s2[0]; });
assert(s1 == s2);
rows.push_back({"std::sort 1e5", builtin.first});
rows.push_back({"merge_sort 1e5", merge.first});
std::printf("%-34s %10s\n", "experiment", "median s");
for (auto& [name, t] : rows) std::printf("%-34s %10.4f\n", name.c_str(), t);
std::printf("random/sequential ratio: %.1fx\n", rnd.first / seq.first);
std::printf("insert(begin)/push_back: %.1fx\n", front.first / back.first);
std::printf("merge_sort/std::sort: %.1fx\n", merge.first / builtin.first);
return 0;
}
import assert from "node:assert/strict";
const K_RUNS = 3;
let seed = 42;
const rand = (): number => (seed = (seed * 1664525 + 1013904223) >>> 0) / 2 ** 32; // deterministic LCG in [0, 1)
const randInt = (m: number): number => Math.floor(rand() * m);
/** Median of K timed runs after one warm-up. Returns [seconds, result of last run]. */
function bench(fn: () => number): [number, number] {
let result = fn();
const t: number[] = [];
for (let i = 0; i < K_RUNS; i++) {
const t0 = performance.now();
result = fn();
t.push(performance.now() - t0);
}
t.sort((a, b) => a - b);
return [t[K_RUNS >> 1] / 1e3, result];
}
function mergeSort(a: number[]): number[] {
if (a.length <= 1) return a.slice();
const mid = a.length >> 1;
const l = mergeSort(a.slice(0, mid)), r = mergeSort(a.slice(mid));
const out: number[] = [];
let i = 0, j = 0;
while (i < l.length && j < r.length) out.push(l[i] <= r[j] ? l[i++] : r[j++]);
while (i < l.length) out.push(l[i++]);
while (j < r.length) out.push(r[j++]);
return out;
}
function main(): void {
const rows: [string, number][] = [];
// Part 2a: sequential vs random-order traversal (typed arrays: packed, no holes, no boxing)
const n = 1_000_000;
const data = new Int32Array(n), perm = new Int32Array(n);
for (let i = 0; i < n; i++) { data[i] = i; perm[i] = i; }
for (let i = n - 1; i > 0; i--) { const j = randInt(i + 1); const t = perm[i]; perm[i] = perm[j]; perm[j] = t; }
const seq = bench(() => { let s = 0; for (let i = 0; i < n; i++) s += data[i]; return s; });
const rnd = bench(() => { let s = 0; for (let i = 0; i < n; i++) s += data[perm[i]]; return s; });
assert.equal(seq[1], rnd[1]);
assert.equal(seq[1], (n * (n - 1)) / 2);
rows.push(["traverse sequential (1e6)", seq[0]], ["traverse random order (1e6)", rnd[0]]);
// Part 2b: push vs unshift
const back = bench(() => { const xs: number[] = []; for (let i = 0; i < 20_000; i++) xs.push(i); return xs.length; });
const front = bench(() => { const xs: number[] = []; for (let i = 0; i < 20_000; i++) xs.unshift(i); return xs.length; });
assert.equal(back[1], 20_000);
assert.equal(front[1], 20_000);
rows.push(["20k push", back[0]], ["20k unshift", front[0]]);
// Part 3: Map vs sorted array + binary search
const lowerBound = (a: number[], k: number): number => {
let lo = 0, hi = a.length;
while (lo < hi) { const mid = (lo + hi) >>> 1; if (a[mid] < k) lo = mid + 1; else hi = mid; }
return lo;
};
const q = 100_000;
for (const size of [1_000, 10_000, 100_000]) {
const m = new Map<number, number>();
const keys: number[] = [];
while (keys.length < size) { const k = randInt(10 * size); if (!m.has(k)) { m.set(k, k); keys.push(k); } }
const sortedKeys = [...keys].sort((a, b) => a - b);
const qs = new Int32Array(q);
for (let i = 0; i < q; i++) qs[i] = keys[randInt(size)];
const h = bench(() => { let f = 0; for (let i = 0; i < q; i++) if (m.has(qs[i])) f++; return f; });
const s = bench(() => { let f = 0; for (let i = 0; i < q; i++) if (sortedKeys[lowerBound(sortedKeys, qs[i])] === qs[i]) f++; return f; });
assert.equal(h[1], q);
assert.equal(s[1], q);
rows.push([`Map lookup x1e5, n=${size}`, h[0]], [`bsearch lookup x1e5, n=${size}`, s[0]]);
}
// Part 4: built-in sort vs merge sort
const arr: number[] = Array.from({ length: 100_000 }, () => randInt(1_000_000));
let s1: number[] = [], s2: number[] = [];
const builtin = bench(() => { s1 = [...arr].sort((a, b) => a - b); return s1[0]; });
const merge = bench(() => { s2 = mergeSort(arr); return s2[0]; });
assert.deepEqual(s1, s2);
rows.push(["Array.sort 1e5", builtin[0]], ["mergeSort 1e5", merge[0]]);
console.log("experiment".padEnd(34) + "median s".padStart(11));
for (const [name, t] of rows) console.log(name.padEnd(34) + t.toFixed(4).padStart(11));
console.log(`random/sequential ratio: ${(rnd[0] / seq[0]).toFixed(1)}x`);
console.log(`unshift/push ratio: ${(front[0] / back[0]).toFixed(1)}x`);
console.log(`mergeSort/Array.sort: ${(merge[0] / builtin[0]).toFixed(1)}x`);
}
main();
What the numbers should look like
These are the medians the reference solutions printed on one Windows x86-64 desktop (CPython 3.14.6, OpenJDK 21, MSVC 2026 /O2, Node 24). Your absolute numbers will differ, possibly by 3x; the ratios and the shapes are what you should compare. Treat each as indicative, not as a specification.
| Experiment | Python | Java | C++ | TypeScript |
|---|---|---|---|---|
| random / sequential traversal, | 1.9x | 0.8x | 8.1x | 2.4x |
| front-insert / append, | 81x | 20x | 99x | 149x |
| sorted / hash lookup, | 3.8x | 4.4x | 7.2x | 4.1x |
| sorted / hash lookup, | 5.3x | 22x | 18x | 4.5x |
| merge sort / built-in sort, | 13.7x | 0.6x | 4.1x | 1.7x |
What to read from it:
- Traversal. Only C++ shows the full cache effect at (4 MB, which fits in many L3 caches but not L2). Python's ratio is diluted: the interpreter spends tens of nanoseconds per iteration whatever the access pattern, so a few nanoseconds of cache miss barely show. Java's 0.8x is a measurement artefact worth explaining in your write-up: with and only one warm-up, the JIT may still be compiling or may have compiled the two loops differently; raise the warm-up count and to and the ratio should rise well above 1. In the memory lesson, with and more warm-up, Java showed 6.8x. A surprising number is a prompt to fix the experiment, not to publish it.
- Front insertion. Far below the naive in every language, because each shift is one bulk
memmoverather than separate operations. It is still quadratic: doubling should roughly quadruple the time. - Hash versus sorted. Hash lookups are close to flat until the table outgrows the cache. The tree-based structures in Java and C++ degrade much faster than predicts, because each of their roughly 17 levels is a pointer chase to a separately allocated node; the sorted array in Python and TypeScript degrades more gently, because binary search over one contiguous block touches fewer distinct lines and the last few halvings land in the same line.
- Sorting. In Python, a merge sort written in Python is an order of magnitude slower than the C implementation of Timsort — this is the interpreter tax, not the algorithm. In Java, the reference merge sort works on
int[]whileArrays.sort(int[])was given a fresh clone each run, so the two are close; on this machine the hand-written one even won, a result worth investigating rather than celebrating (try more warm-up and larger ). In C++,std::sort(introsort, in place, insertion sort for small partitions) beats an allocating merge sort by about 4x.
Rough orders of magnitude to sanity-check against: a C++ sequential sum runs at well under 1 ns per element; Python at 30–70 ns per element; a hash lookup costs 5–60 ns in C++/Java/V8 depending on table size and 80–130 ns per iteration in a Python loop; a sort of ints takes about 5–40 ms in every language here. If you are an order of magnitude off these, suspect the harness first (debug build, no warm-up, timing the setup).
Stretch goals
- Memory measurement. Report bytes per element for each structure:
tracemallocorsys.getsizeofsummed over elements in Python;Runtime.totalMemory() - freeMemory()before and after (afterSystem.gc()) in Java, or JOL for exact layouts; a counting allocator or/proc/self/statusin C++;process.memoryUsage().heapUsedin Node. Compare with the per-language numbers in the memory lesson. - Plot the curves. Sweep over powers of 2 from to , write CSV, and plot time per element on a log-scale axis. Mark your L1, L2 and L3 sizes as vertical lines; the steps in the traversal and hash curves should line up with them.
- Cache-line stride experiment. Sum every -th element of a 256 MB array for and report time per touched element. The time per element should stay roughly flat in total until reaches 16
int32s (64 bytes), proving that the cache line, not the element, is the unit of memory traffic. The memory lesson's stride table is the expected shape. - Linear versus binary search crossover. For sorted arrays of , time a linear scan against binary search. Find your crossover; in compiled C++ it was between 128 and 256 on the test machine.
- Boxing tax. In Java, repeat part 2a with
ArrayList<Integer>and part 3 withintkeys in a hand-written open-addressing table. In TypeScript, repeat 2a with a plainnumber[]containing one non-integer value (forcing double elements) and with a holey array. - Second language. Port the harness to another of the four languages and explain the three biggest differences between the two tables.
Related lessons
- Module 0 overview · How to Use This Course · Complexity Analysis · Recursion & Induction · How Data Structures Live in Memory · Your Language's Data Structures · How to Solve Any Problem · Testing & Debugging Algorithms · Course home
- Methodology: Benchmarks. Background: How Computers Work, Hash Tables, Sorting & Searching.