Concept

Pointer chasing — where it appears

Reaching data by following a stored address to an arbitrary place in memory, as a linked list or a tree of separate nodes does. Each hop is likely a cache miss, so a structure that reads few entries can still be slow if every entry is a pointer away.

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

A list and a block of memory

The same traversal, over the same graph, examining the same edges in the same order, laid out two ways. Twelve thousand two hundred and eighty-eight edge slots either way; 11,812 modelled cache misses against 3,258. This is the site's largest gap between two counts of one run, and it exists because one of the layouts is a pointer chase and the other is a sweep.

graphs · Graph

Two probes are two misses

Cuckoo hashing's lookup reads at most two slots, and at a load of 0.45 it reads 1.27 on average where linear probing reads 1.39. Replayed through a cache, it misses 1.18 times a lookup where linear probing misses 0.98. The table that wins the count the analysis uses loses the count the machine charges, because two slots in unrelated places are two cache lines, and a run of adjacent slots is usually one.

machine · Machine

Named alongside it

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

Cache Locality Memory layout Miss rate Adjacency Adjacency list Chained hashing CSR (compressed sparse row)Cuckoo hashing Hash table Linear probing Load factor

All concepts