What is the essence of the concept of cache conscious?

Question

Algorithms

In articles related to algorithms, I came across such a concept as cache conscious , but unfortunately I can’t understand what it means and its translation does not add understanding.
It seems like the essence is related to the convenience of the algorithm for caching, but I would like more details and possible translation options for the concept.

Answer 1

Cache is a tool for speeding up algorithms with high data locality. Simply put, if the algorithm at some point in time reads data from a memory location N, then very soon it will need to read from some location very close to N.
Another important point is the high cost of cache memory. This means that the algorithm should use the cache very rationally.
Thus, cache conscious algorithms:
- access data in an easily predictable manner (eg, strictly sequentially)
- store data in a compact manner (ie, the minimum required data set of optimal type with proper alignment).
Usually, when people talk about cache conscious algorithms, they mean the processor cache (and even all levels of processor caches, each of which is larger, but also slower than the previous one). Although this also applies to distributed computing, when the algorithm must take into account that accessing data located on another computer can be very long and expensive.

Answer 2

There are two things: cache conscious and cache oblivious. Both refer to the refined memory model.
In conventional algorithms, we have one RAM memory to which there is equal access. In the refined one, there is a cache between the processor and the main memory, access to which is much faster than to the main memory. The theoretical cache model usually looks like this: these are H lines of W bytes each. Algorithms request to read a piece of memory into the cache, and then operate on what is in the cache. The efficiency of the algorithm is determined by the number of main memory reads into the cache (+ standard characteristics).
Actually, the algorithms are divided into those for which the cache parameters W and H are important - cache concious, and those for which they are not important - cache oblivious.
PS Here on Habré they customize a binary search, taking into account the cache, and in update they also make a hint on how to make cache oblivious.