Department of Energy Argonne National Laboratory Office of Science NEWTON's Homepage NEWTON's Homepage
NEWTON, Ask A Scientist!
NEWTON Home Page NEWTON Teachers Visit Our Archives Ask A Question How To Ask A Question Question of the Week Our Expert Scientists Volunteer at NEWTON! Frequently Asked Questions Referencing NEWTON About NEWTON About Ask A Scientist Education At Argonne Cache Memory
Name: Ben
Status: Student
Age: 19
Location: N/A
Country: N/A
Date: Around 1999


Question:
A question regarding Cache memory.

Can you please explain to be how data structures are used in Cache memory? i.e. how they are stored, and how they are processed.



Replies:
The kind of data structures im interested in are Stacks, Queues, and Lists.

Cache memory doesn't know anything about data structures at all, so the simple and not very useful answer to your question is that data structures are treated by the cache memory the same as everything else.

So, perhaps some slightly different but related questions might be more useful:
1. What is cache memory and what is its purpose?
2. How does cache memory work?
3. What does this mean for different types of data structures?

1. First of all cache memory is very fast memory that the processor can access much more quickly than main memory or RAM. Currently processors can operate at speeds much greater than affordable, reliable memory can supply the necessary data. Cache memory, is much like other memory, except it can operate much faster, and much more expensive.

Cache memory attempts to bridge the gap between fast, expensive memory that can be made in limited quantities, and the large amounts of RAM needed for modern applications. By giving the processor a small amount of fast memory to used, and then having that memory read in and write to main memory in "spare" time, the processor can operate at full speed much of the time.

2. The details of how cache memory works vary depending on the different cache controllers and processors, so I won't describe the exact details. In general, though, cache memory works by attempting to predict which memory the processor is going to need next, and loading that memory before the processor needs it, and saving the results after the processor is done with it.

Whenever the byte at a given memory address is needed to be read, the processor attempts to get the data from the cache memory. If the cache doesn't have that data, the processor is halted while it is loaded from main memory into the cache. At that time memory around the required data is also loaded into the cache.

When data is loaded from main memory to the cache, it will have to replace something that is already in the cache. So, when this happens, the cache determines if the memory that is going to be replaced has changed. If it has, it first saves the changes to main memory, and then loads the new data.

The cache system doesn't worry about data structures at all, but rather whether a given address in main memory is in the cache or not. In fact, if you are familiar with virtual memory where the hard drive is used to make it appear like a computer has more RAM than it really does, the cache memory is similar.

3. So, cache memory doesn't know anything about data structures, and instead only knows whether a given memory address is present in the cache or not. For most programs this doesn't matter at all. Programmers don't have to do anything and everything works just fine, and the actual details of how the cache work don't matter too much.

However, if a given process is absolutely time critical, knowing a little about the cache can help you improve the performance of the program. Most of the time, however, this is wasted effort since modern operating systems are multi-tasking, and any time the OS takes over the cache is pretty much blown away.

But, in general, to optimize for the cache:
1. Keep loops small, don't make them take up large amounts of memory for the code, this is so all the code for the loop will fit into the cache. Generally the amount that will fit into the cache is small 2-4K.

2. Try not to call functions that are outside the current area of code.

3. Try to access memory in the same areas. For example, classes where each fields are accessed together are good. Arrays that are small and accessed sequentially are good.

This implies some types of data structures aren't great for caches:

1. Large arrays that are iterated from start to finish are bad. If you go through the entire array several times, and the array doesn't fit, this is not good. It would be better to process portions of the array completely before moving to the next section.

2. Linked lists where one piece of data in each node is accessed for each record is not good. It would be better to completely process each node, and be completely done with a node before moving on.

3. Stacks are generally fairly good as they access the most recently loaded memory.

4. Queues can be really bad if they are a first-in-first-out type of queue. This is because many cache systems, when they have to discard memory, discard the oldest memory, and this is the memory the queue needs to access, since the first-in node is the oldest one.

But, as I said, it is generally good to know how cache works and be aware of it. It is really bad to spend extra time programming for the cache unless you know--absolutely--that optimizing for the cache is the best way to get your results. Personally, I have been programming time- critical code for seven years, and have found that a better algorithm will improve performance much more than tweaking for the cache.

I hope this helps.
--Eric Tolman


Click here to return to the Computer Science Archives

NEWTON is an electronic community for Science, Math, and Computer Science K-12 Educators, sponsored and operated by Argonne National Laboratory's Educational Programs, Andrew Skipor, Ph.D., Head of Educational Programs.

For assistance with NEWTON contact a System Operator (help@newton.dep.anl.gov), or at Argonne's Educational Programs

NEWTON AND ASK A SCIENTIST
Educational Programs
Building 360
9700 S. Cass Ave.
Argonne, Illinois
60439-4845, USA
Update: June 2012
Weclome To Newton

Argonne National Laboratory