Динамическое распределение и произвольный доступ: Raw, Smart, Deque, Vector. Почему сырье так быстро, и так медленно?

Question

Я создал небольшой тест производительности, сравнивающий время установки и доступа трех популярных методов динамического выделения: raw pointer, std :: unique_ptr и std :: deque.

РЕДАКТИРОВАТЬ: в @ NathanOliver, добавил std::vector: EDIT 2: в latedeveloper х, выделенных станд :: вектор (п) и Std :: Deque (п) конструкторы РЕДАКТИРОВАТЬ 3: в @BaummitAugen, переехал распределение внутри времени loop и скомпилировал оптимизированную версию. EDIT 4: за комментарии @ PaulMcKenzie, заданные пробеги до 2000.

Результаты: Эти изменения сильно затянули. Deque и векторные еще медленнее на выделении и передаче, в то время как Deque гораздо медленнее доступа:

pickledEgg $ г ++ -std = C++ 11 -o sp2 -O2 sp2.cpp

Average of 2000 runs: 
Method Assign   Access 
====== ======   ====== 
Raw: 0.0000085643 0.0000000724 
Smart: 0.0000085281 0.0000000732 
Deque: 0.0000205775 0.0000076908 
Vector: 0.0000163492 0.0000000760 

Только для весело, вот -Ofast результаты:
pickledEgg $ г ++ -std = C++ 11 -o sp2 -Ofast sp2.cpp

Average of 2000 runs: 
Method Assign   Access 
====== ======   ====== 
Raw: 0.0000045316 0.0000000893 
Smart: 0.0000038308 0.0000000730 
Deque: 0.0000165620 0.0000076475 
Vector: 0.0000063442 0.0000000699 

ORIGINAL: Для потомков; примечание отсутствие оптимизатора -O2 флаг:

pickledEgg $ г ++ -std = C++ 11 -o sp2 sp2.cpp

Average of 100 runs: 
Method Assign  Access 
====== ======  ====== 
Raw: 0.0000466522 0.0000468586 
Smart: 0.0004391623 0.0004406758 
Deque: 0.0003144142 0.0021758729 
Vector: 0.0004715145 0.0003829193 

Обновленный код:

#include <iostream> 
#include <iomanip> 
#include <vector> 
#include <deque> 
#include <chrono> 
#include <memory> 

const int NUM_RUNS(2000); 

int main() { 
    std::chrono::high_resolution_clock::time_point b, e; 
    std::chrono::duration<double> t, raw_assign(0), raw_access(0), smart_assign(0), smart_access(0), deque_assign(0), deque_access(0), vector_assign(0), vector_access(0); 
    int k, tmp, n(32768); 

    std::cout << "Average of " << NUM_RUNS << " runs:" << std::endl; 
    std::cout << "Method " << '\t' << "Assign" << "\t\t" << "Access" << std::endl; 
    std::cout << "====== " << '\t' << "======" << "\t\t" << "======" << std::endl; 

    // Raw 
    for (k=0; k<NUM_RUNS; ++k) { 
     b = std::chrono::high_resolution_clock::now(); 
     int* raw_p = new int[n]; // run-time allocation 
     for (int i=0; i<n; ++i) { //assign 
      raw_p[i] = i; 
     } 
     e = std::chrono::high_resolution_clock::now(); 
     t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b); 
     raw_assign+=t; 
     b = std::chrono::high_resolution_clock::now(); 
     for (int i=0; i<n; ++i) { //access 
      tmp = raw_p[i]; 
     } 
     e = std::chrono::high_resolution_clock::now(); 
     t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b); 
     raw_access+=t; 
     delete [] raw_p; // :^) 
    } 
    raw_assign /= NUM_RUNS; 
    raw_access /= NUM_RUNS; 
    std::cout << "Raw: " << '\t' << std::setprecision(10) << std::fixed << raw_assign.count() << '\t' << raw_access.count() << std::endl; 

    // Smart 
    for (k=0; k<NUM_RUNS; ++k) { 
     b = std::chrono::high_resolution_clock::now(); 
     std::unique_ptr<int []> smart_p(new int[n]); // run-time allocation 
     for (int i=0; i<n; ++i) { //assign 
      smart_p[i] = i; 
     } 
     e = std::chrono::high_resolution_clock::now(); 
     t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b); 
     smart_assign+=t; 
     b = std::chrono::high_resolution_clock::now(); 
     for (int i=0; i<n; ++i) { //access 
      tmp = smart_p[i]; 
     } 
     e = std::chrono::high_resolution_clock::now(); 
     t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b); 
     smart_access+=t; 
    } 
    smart_assign /= NUM_RUNS; 
    smart_access /= NUM_RUNS; 
    std::cout << "Smart: " << '\t' << std::setprecision(10) << std::fixed << smart_assign.count() << '\t' << smart_access.count() << std::endl; 

    // Deque 
    for (k=0; k<NUM_RUNS; ++k) { 
     b = std::chrono::high_resolution_clock::now(); 
     std::deque<int> myDeque(n); 
     for (int i=0; i<n; ++i) { //assign 
      myDeque[n] = i; 
//   myDeque.push_back(i); 
     } 
     e = std::chrono::high_resolution_clock::now(); 
     t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b); 
     deque_assign+=t; 
     b = std::chrono::high_resolution_clock::now(); 
     for (int i=0; i<n; ++i) { //access 
      tmp = myDeque[n]; 
     } 
     e = std::chrono::high_resolution_clock::now(); 
     t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b); 
     deque_access+=t; 
    } 
    deque_assign /= NUM_RUNS; 
    deque_access /= NUM_RUNS; 
    std::cout << "Deque: " << '\t' << std::setprecision(10) << std::fixed << deque_assign.count() << '\t' << deque_access.count() << std::endl; 

    // vector 
    for (k=0; k<NUM_RUNS; ++k) { 
     b = std::chrono::high_resolution_clock::now(); 
     std::vector<int> myVector(n); 
     for (int i=0; i<n; ++i) { //assign 
      myVector[i] = i; 
//   .push_back(i); 
     } 
     e = std::chrono::high_resolution_clock::now(); 
     t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b); 
     vector_assign+=t; 
     b = std::chrono::high_resolution_clock::now(); 
     for (int i=0; i<n; ++i) { //access 
      tmp = myVector[i]; 
//   tmp = *(myVector.begin() + i); 
     } 
     e = std::chrono::high_resolution_clock::now(); 
     t = std::chrono::duration_cast<std::chrono::duration<double> >(e - b); 
     vector_access+=t; 
    } 
    vector_assign /= NUM_RUNS; 
    vector_access /= NUM_RUNS; 
    std::cout << "Vector:" << '\t' << std::setprecision(10) << std::fixed << vector_assign.count() << '\t' << vector_access.count() << std::endl; 

    std::cout << std::endl; 
    return 0; 
} 

Answer 1

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

Потому что ...

g++ -std=c++11 -o sp2 sp2.cpp 

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

Вызов функции обычно медленнее, чем никакой вызов функции. В течение нескольких итераций увеличивается небольшая накладная часть вызова функции. Однако оптимизатор может расширять функциональные вызовы inline, тем самым делая недостаток не фундаментальных типов void. Но только если выполняется оптимизация.

---

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

Кроме того, вы использовали std::deque::at, что делает проверку границ. Оператор индекса не выполняет проверку границ. Проверка надбавок добавляет дополнительные затраты времени выполнения.

---

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

Answer 2

A std::deque является двунаправленным списком. myDeque.at(i) должен пройти через первые элементы i на каждом вызове. Вот почему доступ к deque настолько медленный.

Инициализация std::vector выполняется медленно, поскольку вы не выделяете достаточное количество памяти. std::vector затем начинается с небольшого количества элементов и обычно удваивается, как только вы пытаетесь вставить больше. Это перераспределение включает вызов конструктора перемещения для всех элементов. Попробуйте построить вектор, как это:

std::vector<int> myVector{n}; 

в доступе вектор Интересно, почему вы не использовали tmp = myVector[i]. Вместо вызова оператора индекса вы создаете экземпляр итератора, вызываете его оператор + и в результате вы вызываете оператор разыменования. Поскольку вы не оптимизируете, вызовы функций, вероятно, не будут встраиваться, поэтому это означает, что std :: vector доступ медленнее, чем исходный указатель.

Для std::uniqe_ptr Я полагаю, что он имеет аналогичные причины, как с std::vector. Вы всегда вызываете оператор индекса на уникальный указатель, который также является вызовом функции. Как эксперимент, попробуйте сразу же после выделения памяти для smart_p, вызовите smart_p.get() и используйте необработанный указатель для остальных операций. Я предполагаю, что он будет таким же быстрым, как исходный указатель. Это может подтвердить мое предположение, что это вызов функции. Тогда простой совет: включить оптимизацию и повторите попытку.

kmiklas редактировать:

Average of 2000 runs: 
Method Assign   Access 
====== ======   ====== 
Raw: 0.0000086415 0.0000000681 
Smart: 0.0000081824 0.0000000670 
Deque: 0.0000204542 0.0000076554 
Vector: 0.0000164252 0.0000000678