   L1/L2 cache optimization
  Hi guys.  I am starting to hear a lot of buzz about optimizing code so that l1/l2 cache misses are low.  Not sure at all how to do that really in c++ or any language for that matter.  Can't seem to find any good tutorials on google either.  Can anyone point me in the right direction?  Thanks!   
  Perhaps you can search for "locality of reference".   ;  Im not sure how well cache optimizations work on PC environment though.Surely there are situtations where you could get some significant performance increase in your application.This would be thanks to less memory accessing but with all the junk that goes about on a regular pc like context switching between processes that is dictated solely by OS, your cache optimizations might end up with little actual gain.As whenever the execution turn changes you might as well flush the L1 cache as far as your application is concerned as it will most likely be filled with whatever the next process in turn was viewing.Infuluencing or predicting the feelings of L2 seems to be exercise in futility as well. Given the fact that the thing at least used to be shared by all the cores, containing data as well as instructions in a hideous mishmash that could cause lines to be filled and stored with data in most erratic patterns that depend on whats running on your computer.If there is something to be gained with caches, it would seem to be related to L1.I would reckon that isolated environments such as gaming consoles could potentially see very good results from cache friendly approach.Ultimately you could query the processor with "CPUID" to milk various parameters from cache line sizes to the particular set associativeness of the implementation.That knowledge might allow doing some "cache-line aligning" on data, if you overrode the new and delete to do your bidding by implementing a memory pooling system. ( I do know that Boos library has memorypools covered, but since I have never used em, cant say if this is exactly what they are going for as well )   ;  Thanks for the tips.  I guess what I am getting at is what does it mean to be cache friendly?  Furthermore,  what are a few common techniques used in being cache friendly?  Thanks!   ;  If some set of data is going to be used together, you should allocate it in a simmilar part of memory.e.g. iterating through a std::vector is more "cache freindly" than iterating through a std::list, because in a vector each item is stored next to each other in RAM, whereas in a list each item could be anywhere in RAM.The smallest block of data that the cache deals with is a "line", whose size depends on the CPU. Cache lines can range in size from 32 bytes to 256 bytes (or anything else). Seeing as an int is 4 bytes, then on a 32-byte cache-line CPU, when you fetch a single int from RAM, you're actually downloading 8 ints worth of data into the CPU.This is why iterating a vector is cache friendly -- on the first iteration you might get a cache miss. When this happens, the cache downloads a whole line, which could include the int you wanted, plus the next 7 ints in the array (meaning that only every 8th iteration causes a cache miss).You can use this knowledge when designing your classes too. If you've got a big class, who's instances will be spread over multiple cache lines, then rearranging the order of the members can be useful to reduce the number of cache misses. E.g. if you've a group of members that are usually accessed together, then they should be stored next to each other to increase the chance they're both loaded in the same line (instead of spread over multiple lines).Also, if your classes contain some data that is accessed all the time (hot data) and some data that is accessed very rarely (cold data), then it can be beneficial to put the cold data into a seperate structure and just have a pointer to it from the hot data. This stops this 'unused' cold data from being pulled into the cache for no reason whenever you want to to use the hot data.   ;Quote:Original post by akaitoraThanks for the tips.  I guess what I am getting at is what does it mean to be cache friendly?  Furthermore,  what are a few common techniques used in being cache friendly?  Thanks!There are two principles the cache works with. Temporal and Spatial locality.According to temporal locality, any data that is being accessed right now, is likely to be accessed again soon, so it is good to be cached.According to spatial locality, any data that is nearby the currently accessed data is likely to be accessed soon.The cache is organized into discreet components called "lines". Currently defacto L1 size would seem to be 64 Bytes.The whole L1 memory consists of bunch of those lines. ( L1 size being sum of(line0,line1...lineN) ).Every byte in computers memory maps to some byte in some cache line. However, as it is apparent, there are not enough cache lines to privide every single byte in the memory an unique byte. So, there must be sharing. There are some schemes that determine how exactly the bytes in memory are mapped on the cache lines such as Direct mapping, Fully associative and Set associative mapping.The whole issue with cache-friendliness comes down with the fact that memory access is relatively expensive operation. Whenever you load data from memory, that particular adress maps into some cacheline. Now the whole cacheline is filled with those bytes in memory that belong to that same cache line. This causes the spatial locality principle to work so well.  Assuming that you load Byte "B" from memory that happens to map as the first byte of cache line 4, with cacheline size being 64,  you can access all those 63 following bytes "free of charge", as they are already in cache memory. Of course there is cache-fetch time, but compared to memory access, its as "free" as it gets, as you don't have to access usually highly stressed bus to get your requested data through.Temporal locality comes as more of a nice side-effect, as the data that is once loaded into cache is likely to be adressed soon as well, hopefully before the cache line contents are replaced by some other memory location that also is adressed that happens to map onto the very same line.At the end of the day, being cache friendly at very basic level involves you to avoid doing needless memory accesses by aligning data in a way, it has a good chance of using as little cache lines as possible.If you can align data in a fashion that anything that is smaller than 64 (or whatever the size is at the time) fits on a single line, you can avoid a single memory access that would otherwise be needed to fetch the "rest of the data" as half of it might be located on line 1, and the rest on line 2.This practically wastes a single cache line and risks that some important data gets kicked out as result ( Which needs to be reloaded again from the memory when its needed).<Darn. Long posts take time to write and ignore preceeding answers. ^^>[Edited by - rmed002 on May 24, 2010 4:18:14 AM];Gallery of processor cache effectsBe nice to your cacheBoth these, I think, should help answer your questions.   