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

Question

Сегодня я решил сравнить и сравнить некоторые различия в 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 также должен привести к этой загадке). Сроки были вычислены с использованием команды 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,000 с, 0,000 с и 0,004 с соответственно.

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

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

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

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

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

Answer 1

Одна вещь, которая приходит мне на ум, заключается в том, что такой большой объект в стеке за один раз может вызвать перераспределение пространства стека с помощью ОС. Попробуйте сбросить/proc/self/maps в конце основного

Answer 2

Рассмотрите второй и третий тесты. Понятно, что они идентичны: выделите K * N * sizeof(double) байтов с кучи, а затем получите доступ к ним точно так же. Так почему разные времена?

Все ваши «более быстрые» тесты имеют одну общую черту: new[]. Все более медленные тесты выделяются new или в стеке. vector, вероятно, использует new[] Under the Hood ™. Единственная очевидная причина этого в том, что new[] и new имеют значительно более разнообразные реализации, чем ожидалось.

Что я собираюсь предложить, так это то, что new[] вернется к mmap и выделит непосредственно на границе страницы, что даст вам ускорение выравнивания, тогда как другие два метода не будут выделяться на границе страницы.

Рассмотрите возможность использования функции выделения ОС, чтобы непосредственно отображать фиксированные страницы, а затем поместить в нее std::array<std::array<double, N>, K>.

Answer 3

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

Answer 4

Единственное большое различие, которое я вижу, заключается в том, что ваши данные хранятся по-разному. В первых двух случаях ваши данные хранятся в одном огромном куске. Все остальные случаи хранят указатели на строки в вашей матрице. Я не совсем понимаю, почему это делает ваш код быстрее, но он может быть связан с поиском и предварительной выборкой процессора. Попробуйте кэшировать строку матрицы, прежде чем перебирать ее, поэтому вам не нужно искать mat[k] для каждой записи. Это может сделать его быстрее и даже ускорить. Может быть, ваш компилятор может сделать это в случае vector<array<T>>, но не в случае array<array<T>>.

Answer 5

Я только что попробовал это на своем рабочем столе с MSVC++ 2010, и я получил то же время (1,6 секунды) для всех тестов, кроме vector из vectors, которое составляло 5,0 секунд.

Я рассмотрел бы фактическую реализацию ваших библиотек array и vector, чтобы узнать, имеются ли какие-либо очевидные отличия.

Попробуйте заменить циклы индексного стиля на циклы итераторного типа и посмотреть, влияет ли это на производительность.

Кроме того, попробуйте использовать clock(), чтобы запустить программу из программы: среди прочего, это позволит вам определить, какая часть кода действует по-разному. Возможно, даже стоит добавить вложенную область, чтобы вы могли также время разрушать объекты.

Answer 6

Я подозреваю, что при выделении array в стеке или кучи компилятора просто должно выровнять для array времени при использовании vector «s аллокатора это, вероятно, с помощью operator new, который должен возвращать память надлежащим образом выровненную для любого типа.Если бы выделенная память оказалась лучше выровненной, что позволило увеличить количество обращений к кешу/больших чтений, то похоже, что это может легко объяснить разницу в производительности.