Почему массив <T, N> был бы медленнее, чем вектор <T>?

Сегодня я решил сравнить и сравнить некоторые различия в gcc оптимизируемости std::vector и std::array. Как правило, я нашел то, что ожидал: выполнение задачи для каждого из набора коротких массивов намного быстрее, чем выполнение задач в эквивалентных векторах коллекции.

Однако я обнаружил что-то неожиданное: использование std::vector для хранения коллекции массивов происходит быстрее, чем при использовании std::array. На всякий случай, это было результатом некоторого артефакта большого количества данных в стеке, я также попытался выделить его как массив в куче и в массиве C-стиля в куче (но результаты по-прежнему напоминают массив массивы в стеке и вектор массивов).

Любая идея, почему std::vector когда-либо превзойдет std::array (на котором компилятор имеет больше информации о времени компиляции)?

Я скомпилировал с использованием gcc-4.7 -std=c++11 -O3 (gcc-4.6 -std=c++0x -O3 также должен привести к этой загадке). Runtimes вычислялись с помощью команды bash -native time (пользовательское время).

Код:

#include <array>
#include <vector>
#include <iostream>
#include <assert.h>
#include <algorithm>

template <typename VEC>
double fast_sq_dist(const VEC & lhs, const VEC & rhs) {
  assert(lhs.size() == rhs.size());
  double result = 0.0;
  for (int k=0; k<lhs.size(); ++k) {
    double tmp = lhs[k] - rhs[k];
    result += tmp * tmp;
  }
  return result;
}

int main() {
  const std::size_t K = 20000;
  const std::size_t N = 4;

  // declare the data structure for the collection
  // (uncomment exactly one of these to time it)

  // array of arrays
  // runtime: 1.32s
  std::array<std::array<double, N>, K > mat;

  // array of arrays (allocated on the heap)
  // runtime: 1.33s
  //  std::array<std::array<double, N>, K > & mat = *new std::array<std::array<double, N>, K >;

  // C-style heap array of arrays
  // runtime: 0.93s
  //  std::array<double, N> * mat = new std::array<double, N>[K];

  // vector of arrays
  // runtime: 0.93
  //  std::vector<std::array<double, N> > mat(K);

  // vector of vectors
  // runtime: 2.16s
  //  std::vector<std::vector<double> > mat(K, std::vector<double>(N));

  // fill the collection with some arbitrary values
  for (std::size_t k=0; k<K; ++k) {
    for (std::size_t j=0; j<N; ++j)
      mat[k][j] = k*N+j;
  }

  std::cerr << "constructed" << std::endl;

  // compute the sum of all pairwise distances in the collection
  double tot = 0.0;
   for (std::size_t j=0; j<K; ++j) {
     for (std::size_t k=0; k<K; ++k)
       tot += fast_sq_dist(mat[j], mat[k]);
   }

   std::cout << tot << std::endl;

  return 0;
}

NB 1: Все версии печатают один и тот же результат.

NB 2: И просто чтобы продемонстрировать, что разницы во времени между std::array<std::array<double, N>, K>, std::vector<std::array<double, N> > и std::vector<std::vector<double> > были не просто из присваивания/инициализации при распределении, то время выполнения простого выделения коллекция (т.е. комментирование вычисления и печати tot) составляла 0.000s, 0.000s и 0.004s, соответственно.

NB 3:. Каждый метод компилируется и запускается отдельно (не синхронизируется по времени в одном и том же исполняемом файле), чтобы предотвратить несправедливые различия в кешировании.

NB 4:
Сборка для массива массивов: http://ideone.com/SM8dB
Сборка для вектора массивов: http://ideone.com/vhpJv
Сборка для вектора векторов: http://ideone.com/RZTNE

NB 5: Чтобы быть абсолютно ясным, я никоим образом не собираюсь критиковать STL. Абсолютно люблю STL и, не только часто использую его, детали эффективного использования научили меня множеству тонких и замечательных особенностей С++. Напротив, это интеллектуальное преследование: я просто задумывался над тем, чтобы изучить принципы эффективного дизайна на С++.

Кроме того, было бы необоснованным обвинять STL, потому что трудно деконвертировать этиологию дифференциала времени выполнения: при включении оптимизаций это может быть из оптимизаций компилятора, которые замедляют работу кода, а не ускоряют его. При отключении оптимизаций это может быть из ненужных операций копирования (которые будут оптимизированы и никогда не будут выполняться в производственном коде), которые могут быть предвзяты к некоторым типам данных больше, чем другие.

Если вам любопытно, как я, я бы с удовольствием подумал об этом.