Two Loops Doing Exactly the Same Arithmetic, One of Them Fifty Times Slower

Both versions perform the same multiplications and the same additions in the same quantity. One finishes in a second and the other takes a minute. The count was never the thing.

The experiment

Here are two loops. They add up every element of a two-dimensional array of

numbers. The first walks along each row in turn, the second walks down each

column in turn. The set of elements visited is identical, the number of

additions is identical, the number of index calculations is identical.

FIG 1Two traversals of the same array

plaintext

version A, along the rows:

    total = 0
    for r in 0 to n-1:
        for c in 0 to n-1:
            total = total + a[r][c]

version B, down the columns:

    total = 0
    for c in 0 to n-1:
        for r in 0 to n-1:
            total = total + a[r][c]

Every arithmetic operation in the second version has a counterpart in the first. The loops are swapped and nothing else is. On a four thousand by four thousand array of eight-byte numbers, the second version typically takes between ten and fifty times as long, with the ratio growing as the array gets bigger.

Run it before reading on if you can. The number is more convincing when it is

your own machine, and the surprise is the whole point of the lesson. Nothing in

the source distinguishes these two programs by cost. An operation count says

they are the same program. A reader counting multiplications and additions

would predict the same time and be wrong by a factor that would be considered

catastrophic in any other engineering estimate.

Why one of them is slow

The array is laid out in memory one row after another. Row zero occupies a run

of bytes, then row one, and so on. That is a choice the language made and it is

the same choice almost every language makes.

Memory is not fetched one number at a time. The hardware moves a whole line,

typically sixty-four bytes, holding eight of these numbers. Asking for one of

them brings the other seven along at no extra cost.

FIG 2What the hardware does for each version, step by step

step	step	version A asks for	version B asks for	lines fetched so far	what happened
1	1	a[0][0], a line arrives with 8 numbers	a[0][0], a line arrives with 8 numbers	1 and 1	Identical so far. Both versions pay one full memory access for the first element, and both receive seven neighbours they did not ask for.
2	2	a[0][1], already in the line	a[1][0], a different line entirely	1 and 2	Here the paths separate. Version A reads the next number along the row, which arrived with the first. Version B jumps forward by a whole row, which is thirty-two thousand bytes away, and needs a new line.
3	3	a[0][2], already in the line	a[2][0], another new line	1 and 3	Version A is still working through the line it already has. Version B has used one number out of eight from every line it fetched and will not come back for the others in time.
4	8	a[0][7], the line is now used up	a[7][0], eight lines fetched	1 and 8	After eight elements version A has made one memory request and version B has made eight. That ratio continues for the whole traversal, which is the factor of eight in bytes moved before anything else is counted.

4 steps

Eight memory requests against one, for the same eight additions. The arithmetic is free in both versions and the delivery is what is being paid for. The measured gap is usually worse than eight because version B also defeats the hardware prefetcher, which recognises a forward walk through memory and fetches ahead, and does nothing useful for a walk with a large stride.

So the count was not wrong about the arithmetic. It was complete about the

arithmetic and silent about everything else, and everything else is where the

time went.

What each thing actually costs

The reason counting ever worked is that it was once true that operations cost

roughly the same. On a machine from 1980 an addition and a memory access were

within a small factor of each other, so counting operations was a reasonable

estimate of time.

FIG 3Approximate cost of one of each, on a current processor

	cycles, roughly	times the cost of one ad
an addition or a multipl	1	3
reaching the nearest cac	4	12
reaching the second cach	14	42
reaching the last cache	45	135
reaching main memory	250	750
a branch the processor g	18	54
a branch it got right	1	3

Two and a half orders of magnitude between the cheapest and the dearest, and the two marked rows are the ones that decide most programs. An operation count assigns all of these the same weight, which is the same as pricing a journey by counting the steps without asking whether each step is a pace or a flight.

Two entries deserve a word. The cost of reaching main memory is not the

processor being slow, it is the processor waiting, with nothing to do, for

several hundred cycles while the request travels out and the data comes back.

In that time it could have performed several hundred additions.

And the mispredicted branch is a cost with nothing to show for it. The

processor guessed which way the code would go, started doing that work, found

out it guessed wrong, and discarded everything. The lesson on guessing which way

you will go takes that apart.

What to count instead

Operation counts are not replaced by nothing. They are replaced by three

quantities that are just as countable on paper and actually predict the result.

FIG 4Two quantities as the stride through memory grows

arithmetic operations performedcache lines the hardware must fetch

The flat line is what an operation count measures and it never moves, because the program really is doing the same arithmetic throughout. The rising line is what the hardware is charged for. Everything interesting about the performance of this program lives in the gap between the two lines, and the count cannot see any of it.

The first quantity is cache lines touched. Work out how many distinct

sixty-four byte regions your loop will ask for, which is a matter of looking at

the access pattern and the layout. Version A touches one line per eight

elements, version B touches one per element.

The second is the length of the longest chain of steps where each has to wait

for the one before. Independent work overlaps and is close to free; a chain

does not overlap and its length is a floor on the time. The next lesson is

entirely about this.

The third is how many branches the processor will guess wrong. A loop condition

that is true a thousand times and false once is guessed right almost always. A

comparison against data that is effectively random is guessed right half the

time and each mistake costs the equivalent of twenty additions.

All three can be estimated before writing the code, which is the practical

value. You do not need a profiler to know that version B touches eight times as

many lines. You need to be in the habit of asking.

One honest caveat to end on. These estimates tell you which of two designs to

prefer and roughly by how much. They do not tell you where the time in an

existing program is going, because programs spend their time in places nobody

predicts. That is a measurement problem rather than an estimation problem, and

it is the subject of the companion course on reading a profile. The two skills

are complementary: estimate before you build, measure before you optimise, and

never swap the order.

Recap

Operation counts predicted speed on machines where every operation took the same time and memory was as fast as the processor. Neither has been true since about 1990.
Write the two versions, time them, and the gap is the lesson: identical arithmetic, different access order, and the hardware charges for the order rather than the arithmetic.
The useful replacement for counting operations is counting the things that actually cost: cache lines touched, dependent steps in a chain, and branches the processor cannot guess.

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

NextMore Than One Instruction at a Time →