Постановка задачи
Нас интересует скорость различных стандартных инструментов 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 Но это — тема отдельной статьи… (За рамки статьи также вышли оптимизации компилятора, мы их не используем.)
Вывод
Скорость работы нашего цикла увеличилась на порядок! При этом мы даже не думали о многопоточных алгоритмах (и алгоритмах вообще). Мы также не использовали ничего, кроме родного C++: действовали строго по стандарту и не использовали никаких сторонних библиотек.
Итак, если нам важна скорость нашего цикла — алгоритмы STL не подходят. Итераторы гибки, но не слишком быстры — быстрее всего доступ осуществляется через обычные указатели.
ссылка на оригинал статьи http://habrahabr.ru/post/260025/
Добавить комментарий