# Algorithm Space and Time Complexity with Consideration for I/O (eg cache)

Is there an expression of performance for an algorithm or data structure that attempts to consider cache and other hardware concerns?

Context: in my class we're looking at binary trees and it seems like it would be extremely difficult to optimize data retrieval with the structure. I know B-Trees address this problem, but I haven't seen a formal analysis of how much speed is improved considering some amount of cache.

I've never applied it to rigorously prove the cost of some algorithm or data structure but I believe what you're looking for is the Idealized-cache model. The idea is to do Big O analysis where the cost is the number of cache block transfers instead of atomic machine instructions. E.g. Traversing an array under that model is `O(n/B)` where `n` is the number of elements and `B` is the cache block size. (Technically `n` is the number of bytes the array elements take up, but the difference between that and the number of elements is a constant factor, which Big O notation ignores.)

You might want to read the paper Cache Efficient Functional Algorithms, which applies this kind of analysis in the context of a purely functional language. I'm sure there's plenty of other papers as well; cache-efficient and cache-oblivious data structures and algorithms are an active research topic.

In a language with a generational garbage collector you make use of the heuristic that things that are allocated sequentially in time will generally end up adjacent in memory. The reason for this is that generational garbage collectors usually allocate sequentially in the youngest generation, and when a collection happens the live objects will be compacted and possibly moved to an older generation as well. When this happens the object graph will generally be traversed in depth-first or breadth-first order, but either way objects end up adjacent to other objects they point to.

If your language's garbage collector is non-generational and also non-moving/copying/compacting I don't know what you'd do, but then your performance is probably screwed either way since your memory is fragmented.

On the subject cache-efficient trees, you might want to read Improving RRB-Tree Performance through Transience which talks about a vector/list implementation using trees whose nodes have 31 or 32 children each.

What kind of formal analysis do you mean? If you look at Big O notation, the complexity does not change when you change a constant factor. What I mean is: a cache may be faster than RAM, but that does not change your complexity from O(n) to O(log n).

I think the problem is that things like cache optimization are so much dependent on the specific hardware that a formal analysis is not really useful.

• I suppose I was hoping for bounds on cache misses and ram misses given some value of cache size and ram size. Feb 25, 2015 at 18:22
• Ah, I see. I think the problem is that modern compilers as well as modern CPUs both optimize and change your programs so heavily that you are unable to come to any good analytical conclusions about things like cache misses. Even if you were able to make a statement, it would only be valid for a single program compiled with a specific compiler and running on a specific CPU with specific RAM, etc. - it is just not worth the effort. Feb 26, 2015 at 1:27
• A formal analysis is useful when you're analyzing the output of a compiler. A CPU can only optimize and execute OOO as long as it has space in its instruction cache, it doesn't do another optimization sweep of the entire program. Analysis of data structure and algorithm performance w.r. to cache does exist. IMHO this post reads more like a comment than an answer. Mar 27, 2015 at 16:08
• @TheBrain He's effectively looking for a different cost model; you'd still be doing Big O analysis but the unit cost becomes the number of cache misses and hand-wave away the actual machine instructions as "much, much faster than a cache miss". Mar 27, 2015 at 16:20