When the Analysis Lies

Last timeOccasionally Expensive, Usually Free

Three situations where the growth comparison confidently recommends the slower option: small inputs, memory behaviour, and constants nobody counted. All three are common.

Everything in this course is a tool for predicting how cost moves as the

input grows. This lesson is about the three situations where that prediction

recommends the slower option, and it is the lesson that keeps the rest of the

course honest.

FIG 1What the analysis says and what happens

	the analysis prefers	measurement prefers	why	how common
sorting 20 items	2	1	1	3
walking a grid by column	1	1	2	3
a better shaped procedur	2	1	3	2
two linear procedures	0	1	4	3

The first two columns code which option each instrument picks, with one for the simple option and two for the sophisticated one; the third codes the reason as small input, memory behaviour, uncounted constants, or no shape difference at all; the last codes how often this arises, from rare to constant. The first marked cell is memory behaviour, which is the largest of the uncounted costs on real hardware. The second is the zero in the last row: when two procedures share a shape the analysis does not express a preference, and a reader who insists on one anyway is reading something that is not there.

Small inputs

The apparatus describes growth. An input that never grows has no growth to

describe, so the shapes do not apply and the constants are the whole story.

Real sorting libraries act on this. Below a threshold of a few dozen items

they abandon the better shape and use insertion sort, because it has almost

no setup and touches memory in order. The threshold is found by measuring,

not by arguing, and it is written into the source as a number.

FIG 2The same operation count, four times, at different speeds

step	what is done	operations	measured time	why
1	sum a grid along its rows	one per cell	1.0	each value sits beside the last
2	sum the same grid down its columns	one per cell	4.3	each value is a row apart
3	sum a linked structure of the same size	one per item	9.6	each item is somewhere unrelated
4	sum an array in order	one per item	0.6	the simplest possible access pattern

4 steps

Four ways to add up the same quantity of numbers, with the same operation count, and a sixteenfold spread between the fastest and the slowest. Nothing in the counting model can see this, because the model treats reading a value as one step regardless of where the value is. The practical rule that follows is worth more than most growth comparisons: data laid out contiguously and walked in order is fast, and data scattered across memory and reached through references is slow, whatever the shapes say.

FIG 3Measuring the cost the count cannot see

python

import time

R, C = 2000, 2000
grid = [[1.0] * C for _ in range(R)]

def by_row(g):
    t = 0.0
    for r in range(R):
        row = g[r]
        for c in range(C):
            t += row[c]
    return t

def by_col(g):
    t = 0.0
    for c in range(C):
        for r in range(R):
            t += g[r][c]
    return t

for f in (by_row, by_col):
    s = time.perf_counter()
    f(grid)
    print(f.__name__, round(time.perf_counter() - s, 3))

Both loops add up every entry of the same grid and perform the same number of additions. The row version walks memory in the order it is stored and the column version jumps a row at a time, and the second is typically several times slower on the same machine with the same data. Running this is the quickest way to stop treating the counting model as the whole truth, and it also demonstrates the general method: when the analysis says two things are equal and the stopwatch disagrees, the stopwatch has found something the analysis discarded.

Uncounted constants

A step counted as one may be a network round trip, a disk read or a call into

another language. A procedure whose every step crosses one of those

boundaries loses to a crude procedure whose steps are arithmetic, at every

size anybody runs.

The check is to ask what the counted unit actually is before comparing two

procedures, particularly when one is a loop in a scripting language and the

other is a single call into a compiled library.

The lesson stops here

2 more paragraphs to go

You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.

The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.

See the plan The contents

This is the reading half

Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.

The contents

When the Analysis Lies

Small inputs

Uncounted constants

2 more paragraphs to go

This is the reading half

Read alongside