If the following code is executed:
int *array = new int[1000];
for (int i = 0; i < 1000; i++)
array[i] = i * 2;
The CPU stores the array in cache. But, if the following code is executed:
int *array = new int[1000];
for (int i = 1000-1; i >= 0; i--)
array[i] = i * 2;
I'm wondering if the CPU can also cache the array, or if it only assumes it exists in the "forward" direction.
There's far too many CPUs out there to make a general assumption about this, but:
If you're, let's say, on a common x86 architecture, then what the cache will contain are always multiples of a cache line size, containing the first address you accessed that led to a cache miss;that is the same for forward access.
Depending on how complicated memory access prediction is, the backward access might also be prefetched; who does that prediction depends on your CPU architecture, your actual CPU implementation, and your compiler. It's not uncommon for compilers to "know" which memory access patterns work well for a given CPU generation and make sure that memory access happens in that order.
For your very arithmetic case, there might even be e.g. automatic detection of four consecutive, aligned addresses being accessed, and automatic vectorization with the SIMD instructions your CPU support. That also has an effect on the alignment with with the RAM is accessed, which might have even further influence on cache behaviour..
Furthermore, since you seem to care about speed, you'd typically allow your compiler to optimize. In very many cases, this would lead to such loops becoming "reversed", and SIMD'ed, even.
Note that for other architectures, this might work differently: For example, there's an infamous family of motorola DSPs of the mid-90s that had a relatively simple address generation unit, and things like accessing memory backwards was possible fast if you (or your C compiler) knew how to tell it to work backwards; then, there was the option to "fuse" a memory load or store with any other CPU instruction, so here your whole caching would effectively be dominated by how you manually specified the memory access patterns.
I'm wondering if the CPU can also cache the array, or if it only assumes it exists in the "forward" direction.
The CPU cache works in unit of cache lines (e.g. 32 words or bytes). See this. The order in which you access your array (increasing or decreasing addresses) does not matter much. The first access into a cache line would be some cache miss (both in your forward and backward scenarii), but not the next ones.
The compiler might optimize and unroll the loop, and/or emit PREFETCH machine instructions. You might perhaps use carefully (with GCC) its __builtin_prefetch (see this) but that might even slow down your code if you use it wrongly.
Yes, the array will be cached. Data is taken to cache as a multiple of a cache line size. So for example if the cache line size is 8 bytes then when you access a memory location for the first time irrespective of whether you are trying to access byte 0 or byte 7 all the memory locations from 0-8 will be taken into the cache.
Cache work with lines 32 or 64 etc... (hardware dependent) bytes. and possible with memory granularity, so first acess to any byte load full (n-bytes) memory block into cache line
