Forwards vs Backwards array walking

Question

Let me first preface this with the fact that I know these kind of micro-optimisations are rarely cost-effective. I'm curious about how stuff works though. For all cacheline numbers etc, I am thinking in terms of an x86-64 i5 Intel CPU. The numbers would obviously differ for different CPUs.

I've often been under the impression that walking an array forwards is faster than walking it backwards. This is, I believed, due to the fact that pulling in large amounts of data is done in a forward-facing manner - that is, if I read byte 0x128, then the cacheline (assuming 64bytes in length) will read in bytes 0x128-0x191 inclusive. Consequently, if the next byte I wanted to access was at 0x129, it would already be in the cache.

However, after reading a bit, I'm now under the impression that it actually wouldn't matter? Because cache line alignment will pick the starting point at the closest 64-divisible boundary, then if I pick byte 0x127 to start with, I will load 0x64-0x127 inclusive, and consequently will have the data in the cache for my backwards walk. I will suffer a cachemiss when transitioning from 0x128 to 0x127, but that's a consequence of where I've picked the addresses for this example more than any real-world consideration.

I am aware that the cachelines are read in as 8-byte chunks, and as such the full cacheline would have to be loaded before the first operation could begin if we were walking backwards, but I doubt it would make a hugely significant difference.

Could somebody clear up if I'm right here, and old me is wrong? I've searched for a full day and still not been able to get a final answer on this.

tl;dr : Is the direction in which we walk an array really that important? Does it actually make a difference? Did it make a difference in the past? (To 15 years back or so)

I have tested with the following basic code, and see the same results forwards and backwards:

#include <windows.h>
#include <iostream>
// Size of dataset
#define SIZE_OF_ARRAY 1024*1024*256
// Are we walking forwards or backwards?
#define FORWARDS 1

int main()
{
    // Timer setup
   LARGE_INTEGER StartingTime, EndingTime, ElapsedMicroseconds;
   LARGE_INTEGER Frequency;

   int* intArray = new int[SIZE_OF_ARRAY];
    // Memset - shouldn't affect the test because my cache isn't 256MB!
   memset(intArray, 0, SIZE_OF_ARRAY);

    // Arbitrary numbers for break points
   intArray[SIZE_OF_ARRAY - 1] = 55;
   intArray[0] = 15;

   int* backwardsPtr = &intArray[SIZE_OF_ARRAY - 1];

   QueryPerformanceFrequency(&Frequency); 
   QueryPerformanceCounter(&StartingTime);

    // Actual code
   if (FORWARDS)
   {
    while (true)
    {
        if (*(intArray++) == 55)
            break;
    }
   }
   else
   {
    while (true)
    {
        if (*(backwardsPtr--) == 15)
            break;
    }
   }

    // Cleanup
   QueryPerformanceCounter(&EndingTime);
   ElapsedMicroseconds.QuadPart = EndingTime.QuadPart - StartingTime.QuadPart;
   ElapsedMicroseconds.QuadPart *= 1000000;
   ElapsedMicroseconds.QuadPart /= Frequency.QuadPart;

   std::cout << ElapsedMicroseconds.QuadPart << std::endl;

    // So I can read the output
   char a;
   std::cin >> a;
   return 0;
}

I apologise for A) Windows code, and B) Hacky implementation. It's thrown together to test a hypothesis, but doesn't prove the reasoning.

Any information about how the walking direction could make a difference, not just with cache but also other aspects, would be greatly appreciated!

Answer 1

Just as your experimentation shows, there is no difference. Unlike the interface between the processor and L1 cache, the memory system transacts on full cachelines, not bytes. As @user657267 pointed out, processor specific prefetchers exist. These might preference forward vs. backward, but I heavily doubt it. All modern prefetchers detect direction rather than assuming them. Furthermore, they detect stride as well. They involve incredibly complex logic and something as easy as direction isn't going to be their downfall.

Short answer: go in either direction you want and enjoy the same performance for both!