While trying to solve a problem on CodeChef, I discovered that the order in which you loop over multi-dimensional arrays matters a lot and can make the difference between an AC and a TLE*. The order of loops matters because of the way data is cached in the judging server, and doing something like accessing the third dimension before the second or first will result in fewer cache hits.
I have never encountered this problem before, does CP really involve cache optimization too?
* Compare this and this (the part that says “extra addition”).
The idea of caching the useful data centers around a fundamental property of computer programs known as locality . Programs with good locality tend to access the same set of data items over and over again from the upper levels of the memory hierarchy (i.e. cache) and thus run faster.
Example: The run time of different matrix multiplication kernels that perform the same number of arithmetic operations, but have different degrees of locality, can vary by a factor of 20!
Cache Friendly Code –
Programs with good locality generally run faster as they have lower cache miss rate in comparison with the ones with bad locality. In a good programming practice, cache performance is always counted as one of the important factor when it comes to the analysis of the performance of a program. The basic approach on how a code can be cache friendly is:
Frequently used cases need to be faster: Programs often invest most of the time in a few core functions and these functions in return have most to do with the loops. So, these loops should be designed in a way that they possess a good locality.
Multiple loops: If a program constitutes of multiple loops then minimize the cache misses in the inner loop to alleviate the performance of the code.
so as to summarize, you must write a cache friendly code because it does play a significant role in reducing the execution
time (doesn’t really matters for cakewalk, easy or medium problems)