Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Compulsory miss — where it appears

A cache miss on the first touch of a line, which no cache of that line size can avoid however large it is. Its count is the floor a trace's misses fall to as the cache grows, so what lies above it is the price of the access pattern rather than of the data's size.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

0%25%50%75%100%645124,09665,536cache holds 512array size n (elements)miss ratefully associative · 64 lines × 8 elements · LRU20,000 random accesses per point

The cliff where the data stops fitting

Below the cache's capacity, almost every access hits. A factor of eight above it, almost every access misses. The transition is not gradual and it is not a property of any algorithm — it is a property of how much data there is, and an algorithm's complexity class says nothing about which side of it a program is working on.

machine · Machine rounds, if every ready cell ran at oncerow order, stored by rows65,793anti-diagonal order, stored by rows513anti-diagonal order, stored by diagonals513reads that miss the cacherow order, stored by rows6.3%anti-diagonal order, stored by rows31.1%anti-diagonal order, stored by diagonals8.7%fully associative · 32 lines × 8 elements · LRU263,169 reads and writes per order

The table stored the way it is filled

Store an edit-distance table by anti-diagonals instead of by rows, and the anti-diagonal fill keeps its 513 rounds while its cache misses fall from 31.1% of reads to 8.7%. It does not fall to row order's 6.3%, and the gap is not noise — on caches of four and eight lines the two rates are 9.4% and 6.3%, exactly three to two, because a cell reads from two earlier diagonals and only one earlier row. The same layout turns row order into the order that strides, at 28.3%. How a table is stored and the order it is filled in are one decision, and its price is the number of earlier fronts the recurrence reads.

machine · Machine

Named alongside it

The objects these essays reach for when they reach for this one.

Access patternCacheLocalityMiss rateWorking setCache capacityDepthEdit distanceEvaluation orderMemory layoutOperation countParallelism

All concepts