I get about 3* faster with the simpleStride. Seems like a compiler optimization.

weirdbehavior.ino

unsigned long time;

const unsigned long N = 999;
const unsigned long N_sq = N * N;
unsigned long bigArr[N] = {0};
unsigned long sum;
unsigned long Cache = 128;
const unsigned long NumIter = 10000;

void init_arr() {
  for ( unsigned long i = 0; i < N; ++i) {
    bigArr[i] = i;
  }
}

unsigned long simpleStride( unsigned long iter ) {
  const unsigned long ret = ( 1000 * 1000 ) % N;
  iter = iter + ret - ret;
  return iter;
}

unsigned long cacheStride( unsigned long iter ) {
  unsigned long ret = ( iter * Cache ) % N;
  ret = ret + ret - ret;
  return ret;
}

void timerFunction( unsigned long (*f)(unsigned long) , const char* strideFunName) {
  sum = 0;
  time = millis();
  for ( unsigned long iter = 0; iter < NumIter; ++iter ) {
    for ( unsigned long i = 0; i < N; ++i ) {
      sum += bigArr[f(i)];
    }
  }
  time = millis() - time;
  Serial.print( strideFunName );
  Serial.print( " : " );
  Serial.print( time );
  Serial.print( " sum: " );
  Serial.print( sum );
  Serial.print( "\n" );
}

void setup() {
  Serial.begin( 9600 );
  init_arr();
}

void loop() {
  timerFunction( simpleStride, "stride of 1  " );
  timerFunction( cacheStride,  "stride of 128" );
}