Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

How does caching effect the performance of a running program? From my understanding, the assumption that each instruction always takes the same amount of time is not always correct, because of the effects of caching. How does caching affect algorithmic performance? Thanks in advance.

EDIT 1: To further elaborate, lets say I'm running this Java program that's reading one million integers. From what I understand about this program, it's order of growth is cubic and will take a while to finish running. How would caching improve the performance of this program while it is running?

share|improve this question
3  
Depends a bit on what kind of cache you are talking about? For CPU chache: Have a look here. The question and Mystical's answer give a good example of effects you may get from CPU cache and branche prediction. Similar here –  thorsten müller Aug 17 '12 at 7:08
1  
+1. Wow. That branch prediction question and answer was awesome –  Anthony Aug 17 '12 at 7:29
1  
By "caching" do you mean "memoization"? """Memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs.""" –  Mike Samuel Aug 17 '12 at 18:11
    
@Mike The book that I'm reading, Algorithms, just mentioned caching. –  Anthony Aug 18 '12 at 4:15
    
@Anthony, I don't have my copy of CLR handy, but did it mention it in the context of "dynamic programming"? –  Mike Samuel Aug 18 '12 at 13:51

7 Answers 7

up vote 5 down vote accepted

Cache allows you to "cheat" an algorithm in its pure form and just look up a value instead of calculating it. There are less instructions to execute and therefore caching speeds up the performance.

http://qntm.org/fib

share|improve this answer
    
+1 Thanks for the concise answer and interesting and helpful link. I have a lot to learn about caching! –  Anthony Aug 17 '12 at 7:36
6  
This particular instance of caching is called memoization. –  AlexWebr Aug 17 '12 at 14:02
    
+1 Thanks Alex and @karl, I've learned something new (memoization) –  Anthony Aug 18 '12 at 4:32

Modern processors have lots of caching features that are intended to improve the performance of "normal" programs like this. If you want to study the effect of this caching, you could set about creating an abnormal program that computes the same result.

For example, instead of ramping through the indexes of the arrays serially, go through them in pseudo-random order. (it will take a little thought to do this without a lot of overhead, but the simple way is to allocate a permutation table the same size as the array).

Another example which can provide an "aha" moment is to unroll the inner loop. At some size, unrolling the loop will start to produce worse results.

share|improve this answer
    
+1 I'll try that, thanks –  Anthony Aug 18 '12 at 4:17

Caching is a simple trade off. You save the time needed to compute a result at the expense of having to allocate memory for a lookup table that holds all the results you're likely to need. Whether or not the trade off is worth it depends on how expensive computing the result is and how much memory a lookup table with all the results you're likely to need will consume.

EDIT: I was of course talking about lookup tables rather than pure caching, while they're closely related concepts they're not quite the same. Chalk that one up to the morning coffee not being in full effect yet.

Caching is not just computing a result, but also storing it in a lookup table for future use as well, so a subsequent request for the same value returns the cached version instead of running the computation again. Lookup tables is precomputing a large collection of values, or loading them from a data file, and putting them in a lookup table before any calls to the method are ever made. the former will result in methods that are slower to execute the first time, but are faster on subsequent calls, but which cause memory usage to steadily increase. The latter means paying a large cost in computing all the values up front and allocating a large chunk of memory for the lookup table, but pays off in always getting consistently fast results when the method is actually called and constant memory usage.

share|improve this answer
    
+1 Thanks for still mentioning lookup tables, all of which I have to learn as well. So as long as the original data has not changed, its ok to just use the lookup table instead? Cool, great answer, thanks –  Anthony Aug 18 '12 at 4:27

There are really two different definitions of caching. The first is what the operating system does, moving blocks of storage that are slow to access into blocks that are much faster to access. If you write your algorithm to take advantage of this kind of caching, your program will run faster, sometimes a lot faster, but the algorithmic complexity remains O(n3).

Sometimes when people say caching, they mean memoization. This means you do the calculation the hard way the first time, but you store it in memory for the second and subsequent times you need it. Effectively, the first time you run it for given data, your algorithm is O(n3), but after that it is O(1).

share|improve this answer
    
+1 Nice explanation. I'm sure memoization is what the book I'm reading meant. Thanks for the helpful link! Now I understand that performance gains cannot be achieved while the program is running, only after, thanks –  Anthony Aug 18 '12 at 4:19

Caching is a technique that exploits the distance data is away from the requester. In a modern computer system architecture there are several levels of data layers. All of these layers appear are at varying distances from the requester (the CPU).

It is usually the case that the closest data layers have a higher cost per gigabyte. A higher cost per gigabyte means that there is almost always less available space in a closer data layer than a further away data layer. This difference in space is why we employ caching techniques in our computer systems and in our software. Techniques that try to bring most likely required items closer to the requester and push stale items away so that cache memory is not exhausted.

In order to take advantage of caches you have to be aware of two terms: spatial locality and temporal locality.

Spatial locality is a term used with addressing systems like computer memory. Modern processor caches pull data down in blocks of adjacent memory (memory 'near' another). Algorithms can take advantage of this by accessing memory sequentially in addresses that differ by small units (1 being optimum). An example of good spatial locality is the following:

int sum = 0;
int[] array = { /* Some massive array with data */ };

for (int i = 0; i < ARRAY_SIZE; i++) {
    sum += array[i]; // Access elements with an address difference of 1.
}

Temporal locality is a term used to describe using something in cache frequently. Use of a cache item (i.e. a variable) over and over again results in less fetches from a further away data layer. Algorithms can exploit temporal locality by re-using variables frequently. An example of good temporal locality is the following:

int sum = 0;

for (int i = 0; i < 32; i++) {
    sum += i; // Frequent access of variables sum and i.
}

It is worth checking out this link to see the differences in time of common places that data is stored in computing.

share|improve this answer
    
+1 Thank you very much Simon. This is a great answer. Thanks for the code snippet and link. Those numbers were interesting, I need to do more research on these. –  Anthony Aug 17 '12 at 7:56

Caching is a very wide topic, but ultimately the goal is the same : to improve performance and reduce the load of IO, CPU or memory intensive operations. If you can elaborate on which type of 'algorithmic caching' you are referring to, we can answer more specifically.

Examples of types of caching:

In an application:

  • Data Caching - e.g. caching values, entities, graphs etc without needing to go back to the database, disk to fetch data.
  • Page Caching (Web Apps) - caching all or just part of a web page means that the server doesn't need to render the page again.

Specific to the Web, browser caches, and network caching devices like proxies, save load on a server entirely, with static files like .js, .css, images, etc.

And at a hardware level:

  • Compilers can use registers to cache memory
  • CPU's have caches to save time retrieving data from RAM (e.g. L1 and L2 cache)
share|improve this answer
    
+1. Lets say I'm running this java program that's reading one million integers. From what I understand about this program, it's order of growth is cubic and will take a while to finish running. How would caching improve the performance of this program while it is running? –  Anthony Aug 17 '12 at 7:22

When any kind of caching is in effect, there's a "best case" performance with 100% hits and a "worst case" performance with 0% hits. A well designed scheme with a suitable program will get close to the best case performance. The difference between best an worst cases can be enormous, 10x, even 100x.

Unfortunately, there's no guarantee or simple formula that will guarantee caches effectiveness. A small change in the size of a program, or the size of it's data set, can result in huge and largely mysterious changes in performance.

share|improve this answer
    
+1 Thank you for the explanation –  Anthony Aug 17 '12 at 7:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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