Exploring Data in the CPU Cache

[fluidistic]

Hello,
I wonder what kind of data usually go into the CPU cache. Generally the size of the cache is in kB or MB in contrast with RAM which is in GB.
I understand that the cpu accesses the RAM much slower than the cache so it's better for it to find the data in the cache instead of in the RAM. But the cache is so small in size I wonder how it can be that useful.
Is it possible to store a small .txt file into the cache? If so, accessing the .txt should be much faster than accessing it if it was into the RAM; is there an easy way to benchmark the time it takes to "read" this .txt file and thus determine whether the file is indeed into the cache?
Thank you.

 

[phinds]

One of the main speed advantages of cache is for programs with loops. If you are executing the same few or few dozens of instructions over and over in a loop, your program executes noticeably faster if the instructions are in the cache than if they are in main store.

 

[rootone]

The CPU cache is used for holding variables that the CPU requires access to very frequently.
As Phinds said this would typically be things such loop counters, or constant pointers to frequently addressed items in main memory.
At the level of files there is a different kind of cache, whereby some or even all of a file held on disk is copied into RAM.
Accessing the data that way is significantly faster than continually reading from the disk.

 

[phinds]

The CPU cache is used for holding variables that the CPU requires access to very frequently.
As Phinds said this would typically be things such loop counters, or constant pointers to frequently addressed items in main memory.
At the level of files there is a different kind of cache, whereby some or even all of a file held on disk is copied into RAM.
Accessing the data that way is significantly faster than continually reading from the disk.

But it is NOT just data. Not just things like loop counters, it is the program code as well as data. It does no good to keep a loop counter in cache if you have to fetch all of the instructions in the loop out of main store every time through the loop.

 

[StoneTemplePython]

I wonder what kind of data usually go into the CPU cache.

A special case answer, albeit a very important one, involves how people optimize matrix multiplication. E.g. look at blocked matrix multiplication. You might enjoy these slides (from 1999 apparently but still quite relevant).

https://people.eecs.berkeley.edu/~demmel/cs267_Spr99/Lectures/Lect_02_1999b.pdf

 

[EngWiPy]

There is something called memory hierarchy in computer architecture. You have the hard drive, the RAM, then the cache. As you go up, the memory level gets smaller, but faster and cost more per storage unit. But with the proper use of these different levels, you will have something called virtual memory, which will be the size of the hard drive, but it's accessed faster than if the CPU would access the hard drive directly. The CPU accesses the cache faster than the RAM, and accesses the RAM faster than the hard drive. There are different algorithms what data to fetch and put in each upper level of this hierarchy. For example, one method says that any given instruction is likely to be executed more than once, so, it will be kept in the cache. Another method says that it's likely that adjacent instructions will be executed, so a block of instruction will be fetch from the RAM to the cache. I vaguely remember this stuff from my bachelor's degree. But I believe the concepts I described is somewhat correct.

 

[FactChecker]

It should be mentioned that cache is generally for temporary storage. There are different levels of cache, L3, L2, L1 of increasing speeds. L3 feeds L2 feeds L1. L1 is on the microprocessor chip. L2 and L3 can be in the CPU module or on the motherboard. The computer can look ahead and start pulling data in from the slower memory to faster memory before it is needed. So the contents of the different levels of cache are always changing. This is all carefully thought out. Messing with it can cause unexpected and counter-intuitive results.

EDIT: Changed all misspelled "cash" to "cache"

 

[phinds]

It should be mentioned that cash is generally for temporary storage.

Well, I don't know about that. I NEVER use MY money for temporary storage.

 

[FactChecker]

Well, I don't know about that. I NEVER use MY money for temporary storage.

AAARRRRRGGGGGHHHHH! Ok. I'm a moron at spelling. I'll correct it.

 

[rootone]

Messing with it can cause unexpected and counter-intuitive results.

I bet it can. I doubt if anyone other than an OS developer could do much about it anyway though.

 

[phinds]

I bet it can. I doubt if anyone other than an OS developer could do much about it anyway though.

I don't think cache management is part of the O.S. it is part of the on-board processing, the "computer within the computer" as it were. I'm not 100% sure that that's always the case.

 

[phinds]

AAARRRRRGGGGGHHHHH! Ok. I'm a moron at spelling. I'll correct it.

I, of course, niver misspolle anythung.

 

[EngWiPy]

I think cache management is part of the architecture of the CPU.

 

[Rive]

I think cache management is part of the architecture of the CPU.

The/most CPU provides basic cache management, but also there are instructions for cache management (so the code can fetch data into the cache which will be needed in the future) and also: by organizing the data usage to fit with the cache structure the programmer and the compiler (maybe even the OS) can affect the cache efficiency.

 

[DrClaude]

Most of the posts here appear to be from computer scientists, focussing on the caching of instructions. As someone who has simulated big systems, let me tell you that proper cache management is also very important for data. For instance, accessing arrays following their storage order in memory is very important to avoid cache misses, where the data needed is not in cache and must be fetched from main RAM. This is because, as previously said, one of the main assumption for caching algorithms is that the next requested part of memory is most likely near the previously accessed part of memory. Cache misses can severely affect a program efficiency!

 

[DrClaude]

http://computer.howstuffworks.com/cache.htm

 

[FactChecker]

Most of the posts here appear to be from computer scientists, focussing on the caching of instructions. I someone who has simulated big systems, let me tell you that proper cache management is also very important for data. For instance, accessing arrays following their storage order in memory is very important to avoid cache misses, where the data needed is not in cache and must be fetched from main RAM. This is because, as previously said, one of the main assumption for caching algorithms is that the next requested part of memory is most likely near the previously accessed part of memory. Cache misses can severely affect a program efficiency!

I have seen work in time-critical applications where the cache activity was monitored and successfully optimized. My only first-hand attempt was when I naively tried to optimize and got bad results. In that effort, a large amount of data was being looped through repeatedly. Trying to be smart, I alternated looping forward and backward so that the data last looped through would be the first looped through in the next iteration. To my surprise, that was significantly slower. It taught me a lesson and after that I left it to the compiler.

 

[Rive]

I have seen work in time-critical applications where the cache activity was monitored and successfully optimized.

Called 'code profiling'. There are various tools to monitor cache usage, branch prediction and many other things.
Also, many CPUs (and: GPUs also) has HW support for this.

 

[jbriggs444]

Well, I don't know about that. I NEVER use MY money for temporary storage.

I've been known to temporarily transcribe a phone number to cache on a dollar bill. There is also a cache of cash in my car for tolls, parking, burgers and such.

 

[phinds]

I think cache management is part of the architecture of the CPU.

Yes, that is exactly what I had just said.

The/most CPU provides basic cache management, but also there are instructions for cache management (so the code can fetch data into the cache which will be needed in the future) and also: by organizing the data usage to fit with the cache structure the programmer and the compiler (maybe even the OS) can affect the cache efficiency.

Ah, good to know. I was not aware of that but it makes sense.

 

[Mark44]

Somewhat OT, but I once worked with a guy who pronounced cache as "caché" (i.e., as two syllables, with the accent on the second syllable). He most likely was confusing the pronunciation of this French word with another French word, cachet, which is pronounced the way he was pronouncing cache.

 

[phinds]

Somewhat OT, but I once worked with a guy who pronounced cache as "caché" (i.e., as two syllables, with the accent on the second syllable). He most likely was confusing the pronunciation of this French word with another French word, cachet, which is pronounced the way he was pronouncing cache.

Yes, he had to have been. Cachet has been absorbed into, and is used in, English, but I can't see it ever being confused with cache by anyone who understands the two words.

 

[Mark44]

Well, I don't know about that. I NEVER use MY money for temporary storage.

But if you cache money, is that the same as "cash money"?

 

[phinds]

But if you cache money, is that the same as "cash money"?

Nah, if you cache money, it's then called "dormant assests"

 

[FactChecker]

I'm afraid that my spelling error has hijacked this thread.

 

[phinds]

I'm afraid that my spelling error has hijacked this thread.

Oh ... what were we talking about? [/QUOTE]

 

[DrClaude]

To bring things back on track, here is a figure from C. W. Ueberhuber, Numerical Computation: Methods, Software, and Analysis (Springer, Berlin, 1997):

There is significant increase in computing time when the data no longer fit in the cache.

 

[newjerseyrunner]

You should never worry about the cache as a programmer. Do that once you start profiling your software and update your algorithm if there are problems.

You can not access the cache in any language other than assembly, and even then, you have no assurance of what actually happens. CPUs may not even have certain caches, so usually even the operating system is agnostic to the on-chip cache. The only way I know to even hint to the computer that you want something stored in cache is to use the PREFETCH assembly command in IA-32. But again, it's only a hint, not an instruction.

Storing a small text file would likely not be very useful, unless you plan on accessing the parts of it trillions of times, in which case your hardware will have likely already placed it in cache for you.

 

[nsaspook]

You should never worry about the cache as a programmer. Do that once you start profiling your software and update your algorithm if there are problems.

It depends on what type of programmer you are. Embedded/systems programming in C at the kernel/driver level even on devices like the 4 core RPi3 ARM8 with cache requires very close attention to cache issues that affect processor pipeline, branch execution times, memory barriers for cache coherency and such.

http://www.geeksforgeeks.org/branch-prediction-macros-in-gcc/
https://www.kernel.org/doc/Documentation/memory-barriers.txt

 

[Rive]

You should never worry about the cache as a programmer.

Except when it becomes problematic to tell your customers to buy bigger/stronger HW...

 

[EngWiPy]

I don't remember studying anything about cache in the OS course. It was taught in the computer architecture course.

 

[nsaspook]

Cache in the news, in a bad way. While the effects of caching are usually transparent at the user level and higher OS levels it's possible to exploit cache operation in computer attacks even from JavaScript.
https://www.vusec.net/projects/anc/

 

[FactChecker]

It depends on what type of programmer you are. Embedded/systems programming in C at the kernel/driver level even on devices like the 4 core RPi3 ARM8 with cache requires very close attention to cache issues that affect processor pipeline, branch execution times, memory barriers for cache coherency and such.

I agree. But that being said, I think that it is a subject for an advanced, specialized programmer. A typical programmer would have a long time to learn about cache before anyone expects him to deal with these issues. And they would probably do it with frequent consultation with the manufacturer.

 

[Mark44]

A typical programmer would have a long time to learn about cash before anyone expects him to deal with these issues.

Here we go again...

 

[phinds]

Here we go again...