Почему групповое суммирование медленнее с отсортированными группами, чем с несортированными группами?

Question

У меня есть 2 столбца целых чисел с разделителями табуляции, первый из которых является случайным целым числом, второй - целым числом, идентифицирующим группу, которая может быть сгенерирована этой программой. (generate_groups.cc)

#include <cstdlib>
#include <iostream>
#include <ctime>

int main(int argc, char* argv[]) {
  int num_values = atoi(argv[1]);
  int num_groups = atoi(argv[2]);

  int group_size = num_values / num_groups;
  int group = -1;

  std::srand(42);

  for (int i = 0; i < num_values; ++i) {
    if (i % group_size == 0) {
      ++group;
    }
    std::cout << std::rand() << '\t' << group << '\n';
  }

  return 0;
}

Затем я использую вторую программу (sum_groups.cc) для расчета сумм по группам.

#include <iostream>
#include <chrono>
#include <vector>

// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
  for (size_t i = 0; i < n; ++i) {
    p_out[p_g[i]] += p_x[i];
  }
}

int main() {
  std::vector<int> values;
  std::vector<int> groups;
  std::vector<int> sums;

  int n_groups = 0;

  // Read in the values and calculate the max number of groups
  while(std::cin) {
    int value, group;
    std::cin >> value >> group;
    values.push_back(value);
    groups.push_back(group);
    if (group > n_groups) {
      n_groups = group;
    }
  }
  sums.resize(n_groups);

  // Time grouped sums
  std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
  for (int i = 0; i < 10; ++i) {
    grouped_sum(values.data(), groups.data(), values.size(), sums.data());
  }
  std::chrono::system_clock::time_point end = std::chrono::system_clock::now();

  std::cout << (end - start).count() << std::endl;

  return 0;
}

Если я затем запускаю эти программы в наборе данныхзаданного размера, а затем перемешать порядок строк в одном и том же наборе данных, когда перемешанные данные вычисляют суммы в ~ 2 раза или более быстрее, чем упорядоченные данные.

g++ -O3 generate_groups.cc -o generate_groups
g++ -O3 sum_groups.cc -o sum_groups
generate_groups 1000000 100 > groups
shuf groups > groups2
sum_groups < groups
sum_groups < groups2
sum_groups < groups2
sum_groups < groups
20784
8854
8220
21006

Я бы ожидал, что исходные данныеотсортированы по группам, чтобы иметь лучшую локальность данных и быть быстрее, но я наблюдаю противоположное поведение. Мне было интересно, если кто-нибудь может предположить причину?