Pull to refresh

Веселые старты или C++ и STL: кто быстрее?

C++ *
Sandbox

Постановка задачи


Нас интересует скорость различных стандартных инструментов C++ для выполнения однотипных операций над большим количеством элементов (циклы, алгоритмы STL, итераторы, указатели и т.д.). Для упрощения будем считать исходной задачу вычисления суммы большого количества целых чисел. (Ссылка для тех, кто не любит читать, а любит смотреть.)

Prepare


Для начала напишем код, который будет оценивать быстродействие цикла:

#include <iostream>
#include <sys/time.h>
#include <iomanip>

using namespace std;

const int COUNT = 1000 * 1000 * 1000;

int main () {
       struct timespec tm1, tm2;
       clock_gettime(CLOCK_REALTIME, &tm1);

 // Our code to estimate

       clock_gettime(CLOCK_REALTIME, &tm2);

       double t1 = 1000.0 * tm1.tv_sec + tm1.tv_nsec / (1000.0 * 1000);
       double t2 = 1000.0 * tm2.tv_sec + tm2.tv_nsec / (1000.0 * 1000);
       cout << "t=" << setprecision(5) << t2 -t1 << " ms" << endl;
       return 0;
};


Не очень точно, но зато просто и понятно.

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


#include <vector>
#include <algorithm>
…
int RandomNumber () {
       static int s = 0;
       return (s++ % 100);
}
int main () {
       vector<int> vec(COUNT);
       generate(vec.begin(), vec.end(), RandomNumber);
       ...
       // Our code to estimate


Accumulate


Самым кошерным способом решения нашей задачи является использование функции accumulate:

#include <numeric>
       …
       // Our code to estimate
       accumulate(vec.begin(), vec.end(), 0, [](int sum, int i) {
               return sum + i;
       });


Компилируем и запускаем:

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 349.29 mseconds

Не мало…

for_each


Попробуем for_each?

// Our code to estimate
int sum = 0;
for_each(vec.begin(), vec.end(), [&sum](int i) {
       sum += i;
});

Смотрим:

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 417.64 mseconds

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

class Sum {
       int sum;
public:
       Sum() : sum(0) {}
       inline void operator()(int i) {
               sum += i;
       }
       inline operator int() {
               return sum;
       }
};
…
       // Our code to estimate
       for_each(vec.begin(), vec.end(), Sum());


Барабанная дробь…

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 371.64 mseconds

Еще можно сделать лямбду с состоянием и получить результат, сравнимый с accumulate, но игра не стоит свеч: результат все равно нас не устроит.

for


Вернемся к старым добрым циклам:

// Our code to estimate
int sum = 0;
for(auto i = vec.begin(); i != vec.end(); i++) {
       sum += *i;
};

Ну и что?

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 520.66 mseconds

Ну, это понятно, почему, меняем немного код:

auto end = vec.end();
for(auto i = vec.begin(); i != end; i++) {

Снова компилируем и запускаем:

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 403.68 mseconds

Уже лучше! Еще мы знаем, что префиксный инкремент чуть быстрее чем постфиксный:

for(auto i = vec.begin(); i != end; ++i) {

Это потому, что в операции постфиксного инткремента используется временный объект + копирование.

Компилируем и запускаем:

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 327.05 mseconds

Лучший результат на сегодня! Но еще не вечер…
Почему цикл оказался чуть быстрее? В основном потому, что тут нет вызова функций, а также нет лишних копирований объекта (в нашем случае — целочисленного) суммы.

iterator or not


Откажемся от итераторов вообще:

for(int i = 0; i < COUNT; ++i) {
   sum += vec[i];
};

Компилируем и запускаем:

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 110.52 mseconds

Вот это уже — результат.

Тут мы выиграли сразу на двух операциях — инкремент инта быстрее, чем оператор инкремента у итератора, а оператор разыменовывания медленнее, чем доступ по индексу.

Arrays


А что будет, если мы используем обычный массив? Точнее, будем брать элементы по смещению указателя, а не по индексу (замена вектора на массив бессмыслена — вектор хранит свои данные в массиве):

int *array = &vec[0];
for(int i = 0; i < COUNT; ++i) {
       sum += array[i];
};

И оно того стоило:

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 81.219 mseconds

Доступ по указателю намного быстрее!
А если итерировать сразу по указателю, без индексов, выйдет значительно быстрее:

auto end = &vec[vec.size () - 1];
for(int *i = &vec[0]; i != end; ++i) {
   sum += *i;
};

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 24.494 mseconds


Хардкор


Что еще мы можем сделать с циклом? Точно — «зарегистрировать»:

register int *array = &vec[0];
register int sum = 0;
for(register int i = 0; i != COUNT; ++i) {
       sum += array[i];
};

И что мы получаем?

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 10.456 mseconds

Результат радует, однако следует помнить, что злоупотребление модификатором register сводит его на нет: компилятор перестает обращать на него внимание когда регистров не хватает, а их всегда не хватает) Так что вышеприведенный результат представляет скорее академический интерес, чем практический.

Можно по-эксперементировать с алгоритмами, например, такое изменение:

sum += array[i] + array[++i];

Ускорит наш код еще в двое:

$ g++ -std=c++11 main.cpp -o test && ./test 
$ duration 4.8562 mseconds

UPDATE: и приведет к неопределенному поведению! Спасибо alexac за замечание.
За рамки статьи также вышли оптимизации компилятора, мы их не используем. Но это — тема отдельной статьи

Вывод


Скорость работы нашего цикла увеличилась на порядок! При этом мы даже не думали о многопоточных алгоритмах (и алгоритмах вообще). Мы также не использовали ничего, кроме родного C++: действовали строго по стандарту и не использовали никаких сторонних библиотек.

image

Итак, если нам важна скорость нашего цикла — алгоритмы STL не подходят. Итераторы гибки, но не слишком быстры — быстрее всего доступ осуществляется через обычные указатели.
Tags:
Hubs:
Total votes 49: ↑20 and ↓29 -9
Views 19K
Comments 43
Comments Comments 43