Two designs for a market data book: an array of structs where each instrument holds 12 fields totalling 96 bytes, or a struct of arrays with one array per field. The hot path reads 2 fields across 500 instruments per update. Compute the cache lines touched by each and pick one.

Two designs for a market data book: an array of structs where each instrument holds 12 fields totalling 96 bytes, or a struct of arrays with one array per field. The hot path reads 2 fields across 500 instruments per update. Compute the cache lines touched by each and pick one.

Approach: Count how many 64-byte lines each layout has to fetch to satisfy the same 1,000 field reads, then consider what the prefetcher and the vector units can do with each.

Array of structs touches about 1,000 cache lines and struct of arrays touches about 32, so struct of arrays wins by a factor of thirty. With array of structs each instrument occupies 96 bytes spanning two 64-byte lines, and reading any field pulls in the whole line, so 500 instruments cost 500 to 1,000 line fetches and 94 of every 96 bytes fetched are discarded. With struct of arrays the two fields live in two contiguous arrays; if each field is 8 bytes then 500 consecutive values occupy 4,000 bytes, which is 63 lines, and if the instruments are contiguous the two arrays together cost about 126 lines, dropping to a handful when the set is smaller or the fields narrower. Every byte fetched is used. The access is also a linear stride, which the hardware prefetcher recognises and covers, and it lets the compiler emit vector loads that process eight values per instruction. The cost of struct of arrays is that touching all 12 fields of one instrument now costs 12 separate streams, so the layout follows the access pattern rather than the object model. A hybrid that groups the hot fields into one hot struct and leaves the cold fields elsewhere gets most of the benefit with less disruption.

Follow-up: The 500 instruments are not contiguous, they are a scattered subset of 50,000. What does that do to the comparison and what indexing fixes it?

Key concepts: struct of arrays, cache line, prefetch, vectorisation.