Почему std :: vector может быть быстрее, чем необработанный динамически размещенный массив?

Question

В результате обсуждения с коллегой я написал тесты для тестирования std::vector по сравнению с необработанными динамически распределенными массивами, и в итоге получил сюрприз.

Мои тесты следующие:

#include "testconsts.h" // defines NUM_INTS across all tests
#include <vector>

int main()
{
    const int numInts = NUM_INTS;
    std::vector<int>                     intVector( numInts );
    int * const                          intArray       = new int[ numInts ];

    ++intVector[0]; // force access to affect optimization
    ++intArray[0];  // force access to affect optimization

    for( int i = 0; i < numInts; ++i )
    {
        ++intArray[i];
    }

    delete[] intArray;
    return 0;
}

и:

#include "testconsts.h" // defines NUM_INTS across all tests
#include <vector>

int main()
{
    const int numInts = NUM_INTS;
    std::vector<int>                     intVector( numInts );
    int *                                intArray       = new int[ numInts ];

    ++intArray[0];  // force access to affect optimization
    ++intVector[0]; // force access to affect optimization

    for( int i = 0; i < numInts; ++i )
    {
        ++intVector[i];
    }

    delete[] intArray;
    return 0;
}

Они скомпилированы с g ++ -O3 с gcc 4.4.3

Результаты нескольких прогонов бенчмаркинга с использованием time похожи на:

Массив:

real    0m0.757s
user    0m0.176s
sys     0m0.588s

Vector:

real    0m0.572s
user    0m0.268s
sys     0m0.304s

Понятны три вещи:

1. Массив быстрее во время пользователя
2. Вектор быстрее, меньше системного времени
3. За весь вектор выиграл этот бой

Вопрос «почему?».

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

Что касается вопроса о времени пользователя, он менее интересен для меня, но мне все еще любопытны мнения по этому поводу. Я предполагал, что это как-то связано с инициализацией, хотя я не передаю значение инициализации в векторный конструктор, поэтому я не знаю.

Answer 1

Разница не в производительности вектора по сравнению с динамическим массивом, а в количестве обращений к памяти, которые вы выполняете.

По сути, в векторном тесте вы снова получаете доступ к кэшированной памяти, а в версии массива - нет. Вы платите цену за кеширование векторной версии в любом случае.

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

С другой стороны, при тестировании массива векторный конструктор инициализирует элементов, и это означает, что в случае, если вы пытаетесь профилировать поведение массива, содержимое вектора перебирается и элементы массива пройдены. Удвойте количество обращений к памяти, ошибок страниц и памяти, используемой приложением.

Вы можете попробовать изменить код так, чтобы динамическое распределение выполнялось так:

int * intArray = new int[ numInts ](); // note extra ()

Который инициализирует значение всего массива, или вы инициализируете содержимое массива иначе. Результаты запуска этой модифицированной версии теста должны быть похожими.

Answer 2

Вы проводили тест более одного раза?Бенчмаркинг - сложный процесс, и для получения какого-либо значимого результата приходится полагаться на средние значения;Вполне возможно, что в то время, когда вы выполняли тестирование массива, несколько циклов ЦП были посвящены чему-то другому, что замедляло его.Я ожидаю, что при достаточном количестве результатов они будут похожи, так как std::vector написан с массивом в стиле C в его ядре.