Почему вектор (размер) медленнее, чем новый []?

Question

Я тестировал некоторые алгоритмы STL, и меня удивило время, затраченное на выполнение следующего кода: (я измерил скомпилированный код g ++ [без оптимизации] с помощью команды time)

#include <vector>
struct vec2{
    int x, y;
    vec2():x(0), y(0) {}
};
int main(int argc, char* argv[]){
    const int size = 200000000;
    std::vector<vec2> tab(size); //2.26s
//  vec2* tab = new vec2[size]; //1.29s
//  tab[0].x = 0;
//  delete[] tab;
    return 0;
}

Время, затрачиваемое на векторную инициализацию, составляет 2,26 с, тогда как new (и delete) - 1,29 с. Что делает вектор ctor, который займет намного больше времени? new[] вызывает конструктор для каждого элемента, так же как и vector ctor, верно?

Затем я скомпилировал с -O3, все прошло быстрее, но между двумя кодами все еще был разрыв. (У меня соответственно 0,83 и 0,75)

Есть идеи?

Answer 1

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

std::vector<vec2> tab(size);

в действительности интерпретируется как

std::vector<vec2> tab(size, vec2());

, т. Е. Второй аргумент получает значение из аргумента по умолчанию.Затем вектор выделяет необработанную память и копирует этот сконструированный по умолчанию элемент, передаваемый извне в каждый элемент нового вектора (с помощью конструктора копирования).Как правило, это может быть медленнее, чем создание по умолчанию каждого элемента напрямую (как это делает new[]).

Чтобы проиллюстрировать разницу с помощью эскиза кода, new vec2[size] примерно эквивалентно

vec2 *v = (vec2 *) malloc(size * sizeof(vec2));

for (size_t i = 0; i < size; ++i)
  // Default-construct `v[i]` in place
  new (&v[i]) vec2();

return v;

в то время как vector<vec2>(size) приблизительно эквивалентен

vec2 source; // Default-constructed "original" element

vec2 *v = (vec2 *) malloc(size * sizeof(vec2));

for (size_t i = 0; i < size; ++i)
  // Copy-construct `v[i]` in place
  new (&v[i]) vec2(source);

return v;

В зависимости от реализации, второй подход может оказаться медленнее.

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

Answer 2

Обе версии инициализируют память.

Как отметили несколько человек, вектор использует конструкцию копирования, а массив использует конструктор по умолчанию. Ваш компилятор, кажется, оптимизирует последний лучше, чем первый.

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

Вместо этого вы бы написали что-то вроде:

const int size = 200000000;
std::vector<vec2> v;
v.reserve(size);

Затем, когда вы будете готовы поместить реальный элемент в вектор, вы используете v.push_back(element). reserve() выделяет память без ее инициализации; push_back() копирует конструкции в зарезервированное пространство.

В качестве альтернативы, если вы хотите поместить новый элемент в вектор, вы можете использовать v.resize(v.size()+1), а затем изменить элемент v.back(). (Вот как может работать «распределитель пула».) Хотя эта последовательность инициализирует элемент, а затем перезаписывает его, все это произойдет в кэше L1, который почти так же быстр, как и его вообще не инициализирует.

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

Answer 3

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

013E3FC0  test        eax,eax  
013E3FC2  je          std::_Uninit_def_fill_n<vec2 *,unsigned int,vec2,std::allocator<vec2>,vec2>+19h (13E3FC9h)  
013E3FC4  mov         dword ptr [eax],edx  
013E3FC6  mov         dword ptr [eax+4],esi  
013E3FC9  add         eax,8  
013E3FCC  dec         ecx  
013E3FCD  jne         std::_Uninit_def_fill_n<vec2 *,unsigned int,vec2,std::allocator<vec2>,vec2>+10h (13E3FC0h)  

где регистры edx и esi были обнулены вне цикла:

00013FB5  xor         edx,edx  
00013FB7  xor         esi,esi  
00013FB9  lea         esp,[esp]  

В случае new[] внутренний цикл выглядит следующим образом:

009F1800  mov         dword ptr [ecx],0  
009F1806  mov         dword ptr [ecx+4],0  
009F180D  add         ecx,8  
009F1810  dec         edx  
009F1811  jns         main+30h (9F1800h)  

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