I recently became interested in the general problem of optimizing memory usage in a situation where there is more than one kind of memory available, and there is a trade-off between the capacity of a given memory segment and the speed of accessing it.

The familiar example is a program deciding when to read from / write to the processor cache, RAM and hard drive (via virtual memory).

I am particularly interested in the special case where the amount of data (including the program itself) that needs to be loaded significantly exceeds the capacity of the fastest storage available (i.e. the trivial solution of "just load up everything" is inapplicable).

I found that a Wikipedia page describing some common cache algorithms, which is almost what I want. Unfortunately, these are a bit low-level:

  • Many, such as LRU or MRU only make sense if you have subroutines that get accessed many times. If I have a program with a large number of subroutines, some of which are never accessed in a given run, and some of them are accessed one or two times, this strategy will never work because it can't build up enough data on what is commonly used and what is not.
  • Others, such as CLOCK, seem to deal with the peculiarities of implementation, rather than actually attacking the root of the problem.
  • I know there is a strategy where one first profiles a program during a test run, then provides the profile for the operating system to optimize accordingly. However, we must still solve the problem of providing a truly representative "example usage" while building the profile.

What I really want to learn about is this:When we abstract away all the technicalities of hardware and software, and speak in a purely theoretical context, is it possible to somehow analyze the structure of an algorithm, to work out an effective cache strategy for it based on high-level comprehension of what the algorithm is doing?


I don't know about a method for analyzing an arbitrary given algorithm to come up with a cache policy in general (this sounds quite hard), but this is essentially what's been done (optimally, in an asymptotic sense) on a case-by-case basis for most known cache-oblivious algorithms, by analyzing their divide-and-conquer structure. Cache-oblivious algorithms are known for FFT, matrix multiplication, sorting, and a few others. See the Wikipedia page and references therein.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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