Address models before cache predictions

What this concept is

A locality model starts with actual access order and explicit assumptions about element width, alignment, line size and cache organization. An ISA contract and a particular processor’s performance are different layers.

Why it matters here

Both matrix traversals perform quadratic work and return the same sum, yet they visit addresses in different orders. That gives a testable hypothesis, not a promised speedup.

Concrete example

For a row-major four-by-four matrix of four-byte elements at base B, the address of element (r,c) is B + 4*(4*r+c). Row traversal begins B, B+4, B+8, B+12. Column traversal begins B, B+16, B+32, B+48. If a model has sixteen-byte aligned lines, the first sequence stays within one line while the second visits four. A real target can have different line size, prefetch and residency.

Common confusion / misconception

Big-O is not a latency model. A cache-line prediction is not a hardware counter reading. RISC versus CISC labels do not by themselves predict the winner of this experiment, nor does an x86 example describe an ARM host.

How to use it

Derive addresses first. State model assumptions, predict what should improve and name a condition under which the prediction weakens. Then identify the actual target and compare source with generated assembly. Keep model-derived counts separate from observations.

Check yourself

Which assumptions were needed to say four accesses hit one line? What changes if the base crosses a line boundary? Why might a tiny matrix show little timing difference?

Mini drill or application

Write the first eight addresses for both traversals of a three-by-three matrix. Change only the assumed line size and explain the prediction change before measuring.

Read this only if stuck

Computer Organization and Design for memory hierarchy; MIT 6.004 sections on performance and caches offer optional exercises.