I've been reading about implementing dense matrix multiplication when the matrix doesn't fit in cache. One of the graphs I've seen (slide 9 from these slides) shows sudden drops in performance using the naive algorithm. This drops are to around 50% of the speed, occur while the matrix still fits in cache, and only occur for one or two sizes. I'm not planning on using the naive algorithm, but I would like to know where the sudden drops in performance come from. (The drops also occur with blocked algorithms, but are much smaller.)


1 Answer 1


That is a classic example of cache associativity. The stride associated with that problem size is filling up certain sets causing cache eviction despite there being lots of space in other sets.

Cache associativity

Figure from Gustavo Duarte's excellent blog post on the topic

See also Drepper's What every programmer should know about memory.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.