Еще один динамический массив против std :: vector, но

Question

... ну, я получил странные результаты!

Мне было интересно узнать производительность std::vector по сравнению с динамическим массивом. Поскольку уже есть много вопросов на эту тему, я бы не упомянул об этом, если бы не постоянно получал эти «противоречивые» результаты: vector<int> как-то быстрее, чем new int[]! Я всегда думал, что если бы была какая-то разница в производительности, это всегда было бы в пользу динамического массива. Как этот результат возможен?

Код ниже:

int numElements = 10000000;
 long j = 0;
 long k = 0;

 vector<int> intVector(numElements);
 int* intArray = new int[numElements]; 

 clock_t start, finish;
 start = clock();

 for (int i = 0; i < numElements; ++i)
  intVector[i] = i;
 for (int i = 0; i < numElements; ++i)
  j += intVector[i];

 finish = clock();
 cout << "j: " << j << endl;
 cout << "Total duration: " << (double) finish - start << " ms." << endl;

 // Test Control.
 start = clock();

 for (int i = 0; i < numElements; ++i)
  intArray[i] = i;
 for (int i = 0; i < numElements; ++i)
  k += intArray[i];

 finish = clock();
 cout << "k: " << k << endl;
 cout << "Total duration: " << (double) finish - start << " ms." << endl;

Оптимизации были включены, и я разделил циклы for в каждом блоке начала / окончания, чтобы можно было отдельно рассчитать время инициализации массива / вектора (в этом случае std::vector<int> и new int[] выполняются одинаково ).

Однако с помощью приведенного выше кода я постоянно получаю std::vector<int> выигрыш при 26-30 ms против 36-45 ms за new int[].

Кто-нибудь хочет объяснить, почему вектор работает лучше, чем динамический массив? Оба были объявлены до циклов синхронизации, поэтому я ожидал, что производительность будет примерно одинаковой. Кроме того, я попробовал ту же идею, вместо этого используя std::vector<int*> и new int*[], и получил аналогичные результаты, с классом vector, превосходящим динамический массив, поэтому то же самое справедливо для указателей на указатели.

Спасибо за помощь.

Приложение: без оптимизации std::vector теряет большое время на динамический массив (~ 1,400 ms против ~ 80 ms), чтобы дать ожидаемую разницу в производительности, но это не значит, что векторный класс может каким-то образом оптимизироваться, чтобы дать лучшую производительность, чем стандартный динамический массив?

Answer 1

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

Попробуйте изменить инициализацию массива на int* intArray = new int[numElements]();, чтобы инициализировать значения его элементов, и посмотрите, изменит ли это результаты.

Answer 2

Для всех практических целей, при использовании таким образом, они имеют ту же скорость. Оператор вектора [] обычно реализован так [версия MSVC]:

const_reference operator[](size_type _Pos) const
{   // subscript nonmutable sequence
    return (*(_Myfirst + _Pos));
}

... что совпадает с:

const_reference operator[](size_type _Pos) const
{   // subscript nonmutable sequence
    return _Myfirst[_Pos];
}

Ваш тест в основном просто проверяет способность вашего компилятора встроить код, и, похоже, он делает это хорошо здесь.

Что касается объяснения различий, то любые ответы, которые вы получите, как правило, будут гипотетическими, не видя разборки. Это может быть связано с улучшенным кэшированием, регистры лучше используются в первом случае (попробуйте поменять местами порядок тестов и посмотрите, что произойдет) и т. Д. Стоит отметить, что доступ к памяти вектора будет осуществляться до того, как тест начнется с как он инициализирует все в T () в ctor.

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

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

Answer 3

Я только что провел этот эксперимент. Действительно странное поведение, хотя я думаю, что я понял это.

Повторите ваш код еще раз. То есть ...

benchmark vector
benchmark array

benchmark vector
benchmark array

Вы заметите, что вы получите другие номера во второй раз. Моя догадка? Ошибки страницы. Вектор по какой-то причине не вызывает ошибку страницы, а метод массива -. После загрузки страниц обе будут работать примерно с одинаковой скоростью (то есть: что происходит во второй раз). Кто-нибудь знает, как напечатать количество ошибок страниц в процессе до сих пор?