12 cache problems solving tips and tricks guide. A cache is a type of memory that is small yet very fast and it is used to store memory locations that have been accessed most recently. This is the simplest description that can be used but the detailed description may come in handy if one is trying to understand the performance of the program.
The best way to solve cache problems is by going step by step. The first problem that can be solved is that of memory access. This involves the comparison of two items for example, loop 1 and loop 2. One may be asked how much faster is loop 1 compared to 2.
- int arr = new int[64 * 1024 * 1024];
- // Loop 1for (int i = 0; i < arr.Length; i++) arr[i] *= 3;
- // Loop 2for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;
As shown above, Loop 1 multiplies values in the third array by 3, but looped to only each 16th. Loop 2 does only 6% work of loop 1 but on the modern machines, the two loops take the same time.
They take the same time because of the memories. The loops' running time is not dominated by integer multiplications but by the memory accesses. The impact of cache lines usually also are a problem solved by running different values against time.
For example, at the beginning like between 1 and 16 units time is constant but as the units increase beyond that, time is halved as steps are doubled.
This is because, CPU's today, don't usually access memory by each byte but rather in big chunks known as cache lines. When one reads a certain memory location, the whole cache line is picked from the very main memory and put into the cache.
However, it is cheaper to access other values from a common cache line. Also, one could want to solve the cache sizes because there are three levels. L1, L2 and L3. One may solve the different sizes by using a Sys Internals tool.
Both these methods help one to identify the sizes of the cache lines as well as the sizes of the cache. Cache associativity is also another important element.
In cache design, it should be confirmed that each chunk of main memory should be able to be stored in any slot or most of them.
Examples of the different approaches people may use to map the slots into the memory chunks are, fully associative, n-way set and direct mapped cache.