So I'm familiar with loop interchange for read optimization because of the ways that arrays are laid out in memory.
I'm a little unfamiliar with how caches work. I understand disk I/O techniques like read-ahead and wait to write, but I'm not sure about other cache optimizations for writing.
Will loop order matter when writing to an array or a vector? If so, can you explain why and how the cache mechanism works, please?
Thanks!
Generally, caches are sequential locations in memory to temporary hold values while other operations are occurring. You could consider them as a 1 dimensional array.
Caches may also be different structures as well. For example, a Disk Drive cache may be a Trie, using the sector as the index. A processor may have an array of cache's, using a hash of the memory address as the index.
In general, reading from a cache has the same performance whether it is incremental, decremental or random access, as long as the accesses are withing the same cache row. Some processors may have pointers to cache values that get incremented after a read or decremented.
The optimization trick for caches is to have your frequently accessed data fit inside the cache row. For example, if you have a 2 dimensional array, each row should be a cache row. Any access within the row (e.g. column within the row) is optimal. However, iterating over rows, keeping the column the same, is not optimal because the processor must load (or search for) another row and put that into it's cache.
With a hard drive, the cache serves two purposes: 1) Contain frequently access data; and 2) Buffer data from the processor while the data is written to the drive. In case 2), the processor doesn't have to wait for the transaction to finish; it dumps the data then continues with other operations while the drive transfers data from its cache to the platters.