Benchmarking and testing your data structure

Invariant checks that run after every operation, randomised fuzzing against a reference implementation, and how to measure throughput, latency and memory without fooling yourself.

Test the invariant, not the output

A data structure has an internal promise. Checking that promise after every mutation catches bugs at the operation that broke it, rather than tests later when the failure surfaces somewhere unrelated.

def check_heap(h):
    """Parent must never exceed its children."""
    for i in range(1, len(h)):
        parent = (i - 1) // 2
        assert h[parent] <= h[i], f"heap order violated at {i}"

def check_bst(node, low=float("-inf"), high=float("inf")):
    if node is None:
        return
    assert low < node.key < high, f"{node.key} outside ({low}, {high})"
    check_bst(node.left, low, node.key)
    check_bst(node.right, node.key, high)

def check_avl(node):
    """Returns height; also asserts the balance factor."""
    if node is None:
        return 0
    lh, rh = check_avl(node.left), check_avl(node.right)
    assert abs(lh - rh) <= 1, "AVL balance violated"
    return 1 + max(lh, rh)

Fuzz against a reference model

import random, bisect

def test_against_reference():
    random.seed(1234)               # reproducible failures
    model, mine = [], MySortedSet()
    for step in range(20_000):
        op = random.choice(["add", "remove", "contains", "rank"])
        x = random.randrange(200)   # small range forces collisions and duplicates
        if op == "add":
            bisect.insort(model, x)
            mine.add(x)
        elif op == "remove":
            if x in model:
                model.remove(x)
            mine.remove(x)
        elif op == "contains":
            assert mine.contains(x) == (x in model), f"step {step} op {op} x={x}"
        else:
            assert mine.rank(x) == bisect.bisect_left(model, x)
        assert list(mine) == model, f"diverged at step {step}"
    print("ok")

The reference model should be obviously correct and slow — a sorted list, or the language's own dict. If the two implementations disagree, one of them is wrong, and the seed makes the run reproducible.

Measuring without lying to yourself

import time, tracemalloc

def measure(fn, repeat=7):
    times = []
    for _ in range(repeat):
        tracemalloc.start()
        t0 = time.perf_counter_ns()
        fn()
        times.append(time.perf_counter_ns() - t0)
        _, peak = tracemalloc.get_traced_memory()
        tracemalloc.stop()
    times.sort()
    return {"p50_ms": times[len(times) // 2] / 1e6,
            "max_ms": times[-1] / 1e6,
            "peak_mb": peak / (1024 * 1024)}

FAQ

Related

Amortised analysis: what operations really cost LRU caches and composite structures

Last refreshed 2026-09-18.