Постановка задачи
Нас интересует скорость различных стандартных инструментов 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++: действовали строго по стандарту и не использовали никаких сторонних библиотек.
Итак, если нам важна скорость нашего цикла — алгоритмы STL не подходят. Итераторы гибки, но не слишком быстры — быстрее всего доступ осуществляется через обычные указатели.
Комментарии (43)
Gorthauer87
10.06.2015 18:38+20Только вот во всех этих сравнениях есть одна большая проблема: gcc по умолчанию не включает оптимизации, а если собирать с -O2, то всё становится совсем иначе:
Берем уровень -O3 и сравниваем accumulate с самым хардкорным вариантом:
aleksey@aleksey ~/d/p/bench> ./test t=0.00024414 ms aleksey@aleksey ~/d/p/bench> ./test2 t=0.00024414 ms
А если не видно разницы, то зачем платить больше?
GRascm
10.06.2015 18:39+1Даже при использовании -O1 у меня первый вариант работает с той же скоростью что и последний.
Gorthauer87
10.06.2015 18:41Кстати, clang тоже дают точно такую же скорость, хотя на -O1 он уже сливает.
QtRoS
10.06.2015 19:27-11Все равно хорошая статья, хоть и автор не включил оптимизации в компиляторе. Наглядность улучшений от элементарных изменений просто на шикарном уровне! Как будто «Жемчужины программирования» перечитал, где автор упорно «срезает жирок» с циклов.
AWE64
10.06.2015 21:00+1По-моему, все, что здесь описано, и так более-менее очевидно, без подробностей, конечно. На цифры взглянуть всегда интересно — за это плюс статье.
kashey
10.06.2015 19:51+4Можно еще префетча немного добавить и суммировать «рядком» в несколько переменных — быть может векторизация прилетит.
В свое время (ну лет 15 назад, когда DDR память появилась) AMD с Интелом выпускали километры документации о том как же быстро пройтись по массиву и получить весь заявленный в рекламе bandwidth. Ой не простое это было дело.
С тех пор подросло целое поколение…
Zordhauer
10.06.2015 20:07-6Мне кажется, для хорошего программиста должно быть очевидно, что за любой «сахар» (улучшение читабельности, возможность повторого использования, универсальность, дополнительную абстракцию и т.п.) требуется заплатить как раз-таки скоростью выполнения.
Хочешь скорости работы программы — пиши в машинных кодах, а если хочешь скорости своей работы (и тех, кто будет потом править твой код), то пиши на максимально высокоуровневом языке =)
И это все, как и в случае со статьей, не учитывает оптимизацию компилятора.MichaelBorisov
10.06.2015 20:14+14Отсутствие учета оптимизации компилятора вообще, на мой взгляд, сводит всю пользу статьи на нет.
Некоторый «сахар» C++ достается именно что бесплатно. При условии, что компилятор разберется, как перевести этот сахар в эффективный машинный код. Таких случаев немало, и особенно их немало с STL. В крайнем случае «платой за сахар» будет некоторое замедление компиляции.
И написание программы на ассемблере ничуть не уступает (по скорости ее работы) написанию ее в машинных кодах. Поэтому в машинных кодах никто не пишет еще с 50х-60х гг прошлого века.Zordhauer
10.06.2015 20:34-5польза статьи, скорее всего, в том, чтобы показать необходимость знать детали «работы» языка. Ведь не всегда есть возможность использовать оптимизацию компилятора (иначе эта опция был бы включена по умолчанию), да и не всегда стоит доверять компилятору (любое доверие потом может стать боком).
kmu1990
10.06.2015 20:46+10польза статьи, скорее всего, в том, чтобы показать необходимость знать детали «работы» языка.
Вероятно, я невнимательно прочитал, потому что я не заметил описания каких-то деталей работы языка.
иначе эта опция был бы включена по умолчанию
Я думал, что оптимизации не включены по-умолчанию, чтобы сделать отладку проще и компиляцию быстрее (gcc docs), или другими словами сделать процесс разработки более удобным, разве нет?
MichaelBorisov
10.06.2015 20:10+4Без включенной оптимизации компилятора все эти результаты несут информацию о скорости работы экзотически скомпилированных (без оптимизации) программ, то есть для практического применения пользы ноль.
Поначалу я удивился, почему помогает ключевое слово «register», ведь даже в VC5.0 компилятор разобрался бы, как оптимизировать такой простой цикл, и без «register». Сам бы на регистрах что надо разместил. Тем более регистров процессора более чем достаточно для такого простого цикла.
А еще автор не учел поведение кэша процессора. Измеренное быстродействие цикла может зависеть от того, что исполнял процессор перед этим циклом.
VioletGiraffe
10.06.2015 22:14+1Тот же тест, винда, MSVC 2013 (toolset v120) x86, vector(200 * 1000 * 1000). Релиз + /O2 (дефолтные релизные настройки):
accumulate: 46 ms
for_each: 118 ms
for(int i: vec): 118 ms // Обидно, да?
for (auto i = vec.begin(); i != vec.end(); i++): 47 ms
for (auto i = vec.begin(); i != end; ++i): 46 ms
for (size_t i = 0; i < vec.size(); ++i) sum += vec[i];: 118 ms
for (size_t i = 0; i < size; ++i) sum += vec[i];: 47 ms // Ага, понятно, почему range-based for медленный: компилятор, как и в этом случае, не кэширует" vec.size() и вычисляет его каждый раз.
int *array = &vec[0]; for(size_t i = 0; i < size; ++i) sum += array[i];: 47 ms
auto end = &vec[vec.size() — 1]; for (int *i = &vec[0]; i != end; ++i) sum += *i;: 47 ms
register: 47 ms // Ч. т. д.
sum += array[i] + array[++i]: 65 ms // Интересно…VioletGiraffe
10.06.2015 22:20+1P. S. Я расстроен, что компилятор не умеет оптимизировать вызов const-метода std::vector::size (ну или end). Неужели это так сложно — определить, что на векторе после generate не вызываются никакие не-const методы? И почему бы в векторе не сделать размер переменной, чтоб его просто вернуть, а не вычислять каждый раз?
MichaelBorisov
12.06.2015 13:28-1Я думаю, тут в первую очередь косяк разработчиков STL (P.J. Plauger). Реализация vector::size вычисляет разность между двумя переменными (this->_Mylast — this->Myfirst). Вероятно, время тратится на доступ к этим указателям в памяти.
ассемблерный код получается следующим (VS2013, Release, x86)
mov eax,dword ptr[esp+0Ch] mov esi,dword ptr[esp+8] sub eax,esi sar eax,2
Во как. 4 команды, 2 доступа к памяти, и кроме вычитания еще имеем сдвиг. Сейчас попробую сделать свой «вектор» и посмотреть, что накомпилирует компилятор при простом возврате члена данных класса.MichaelBorisov
12.06.2015 13:48+1Впрочем, к кэшированию все это не относится. Только что посмотрел, как компилятор компилирует цикл for(size_t i=0; i<v.size(); i++) a+=v[i]. Там что-то невообразимое получилось! Очень сложные конструкции, использование SSE и регистров xmm, явные попытки частично размотать цикл. Еще надо поразбираться.
MichaelBorisov
12.06.2015 13:39-1Только что попробовал сделать свой «вектор», у которого размер хранился бы в переменной-члене класса. Компилятор прекрасно кэширует значение этой переменной на регистре. Вот пример кода:
#include <iostream> #include <vector> class kektor { public: kektor(size_t nsize) : m_size(nsize) {} size_t size(void) const throw() { return m_size; } private: size_t m_size; }; void print_kek(const kektor& v) { for (size_t i = 0; i < v.size(); i++) { std::cout << i<<'\n'; } } void main(void) { std::cout << "Hello World!\n"; size_t sz; std::cin >> sz; kektor v(sz); print_kek(v); }
Ассемблерный код для функции print_kek:
xor edi,edi test esi,esi je endloop loop: push edi call std::basic_ostream<char,std::char_traits<char> >::operator<< mov ecx,eax call std::operator<<<std::char_traits<char> > inc edi cmp edi,esi jb loop endloop: ...
Так что да. Неприятно. Недосмотр авторов STL. Оптимизации компилятора доверяй, но проверяй.
kmu1990
12.06.2015 13:40+1А почему вы уверены, что в строке sum += vec[i] вызывается const метод? Кажется, если сам vec не const, то из const и не const метода будет выбран как раз последний.
DaylightIsBurning
12.06.2015 23:08Это не так просто: нужно знать, что значение size() не меняется по ходу выполнения цикла, что далеко не факт, независимо от const, может size() текущее время возвращает — откуда компилятору знать. Короче значение size() может косвенно зависеть от операций в цикле и компилятору не так то просто убедиться в обратном.
0xd34df00d
15.06.2015 15:39Вообще, по идее, компилятору реализация
size()должна быть видна, и компилятор вывести чистоту этого метода может.
Ждём атрибут[[pure]]или рассчитываем на сознательность библиотек, поставляемых с компилятором.
Lol4t0
10.06.2015 22:33+1Поиграем в игру «найдите 5 отличий»
Возьмем код#include <vector> #include <algorithm> using namespace std; int foo (vector<int> vec) { return accumulate(vec.begin(), vec.end(), 0, [](int sum, int i) { return sum + i; }); } int bar (vector<int> vec) { const int COUNT = vec.size(); register int *array = &vec[0]; register int sum = 0; for(register int i = 0; i != COUNT; ++i) { sum += array[i]; }; return sum; }
ZyXI
10.06.2015 22:39+2Странно, что вас ругали за отсутствие оптимизаций, но пропустили
CLOCK_REALTIME. Эти часы нельзя использовать для любых измерений производительности: документация явно говорит, что они могут изменяться. Специально для измерения производительности есть CLOCK_MONOTONIC_RAW (CLOCK_MONOTONIC для не?linux) и CLOCK_PROCESS_CPUTIME_ID. На простоту кода изменение константы на правильную не влияет никак.
alexac
11.06.2015 00:36+6Мне одному кажется, что последний пример
sum += array[i] + array[++i];
Это явное UB? Я не удивляюсь, что там прирост скорости вдвое, там компилятор имел право вообще пол системы снести во время трансляции.
Упрощенный пример и предупреждение: codepad.org/U2jK5eIo
StrangerInRed
11.06.2015 09:02-3Какое UB? ++i? Ну мог выйти за границы массива, а так мы берем просто два элемента подряд и перескакиваем через один.
kmu1990
11.06.2015 09:37+5Нет, имеется ввиду, что i изменяется и читается в одном выражении. Например, порядок вычисления array[i] и array[++i] не определен, например, он может сначала посчитать array[++i] и тогда программа дважды обратится к одному и тому же элементу массива, что не правильно.
А вообще вот, что пишет стандарт:
If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined.
В данном случае, как я понимаю, сайд эффект от ++i «unsequenced» с использованием i в array[i].
Singerofthefall
11.06.2015 10:25+1Да, вы совершенно правы, так как (§1.9/15)
Except where noted, evaluations of operands of individual operators and of subexpressions of individual expressions are unsequenced
DaylightIsBurning
11.06.2015 17:11Решил проверить сам и заодно узнать, насколько хорошо работают оптимизации. Во-первых не сошлись времена даже близко — у меня «регистровая» версия выдаёт 660 ms (а не 10 как у автора). Во-вторых оптимизации всё уравнивают, что бы оптимизации цикл совсем не выкинули — добавил вывод суммы в консоль.
g++ --version cat /proc/cpuinfo | grep "model name" | head -n1 g++ -std=c++11 test_for.cpp -o test_for g++ -std=c++11 -O3 test_for.cpp -o test_forO3 g++ -std=c++11 test_acc.cpp -o test_acc g++ -std=c++11 -O3 test_acc.cpp -o test_accO3 g++ -std=c++11 test_reg.cpp -o test_reg g++ -std=c++11 -O3 test_reg.cpp -o test_regO3 echo "No O; for,acc,reg:" ./test_for ./test_acc ./test_reg echo "-O3; for,acc,reg:" ./test_forO3 ./test_accO3 ./test_regO3
Результат:
g++ (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2 Copyright (C) 2014 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. model name : Intel(R) Core(TM) i7-4930K CPU @ 3.40GHz No O; for,acc,reg: t=11341 ms, sum=-2039607552 t=8141.1 ms, sum=-2039607552 t=660.89 ms, sum=-2039607552 -O3; for,acc,reg: t=231.37 ms, sum=-2039607552 t=231.31 ms, sum=-2039607552 t=232.29 ms, sum=-2039607552
test_reg.cpp#include <iostream> #include <sys/time.h> #include <iomanip> #include <vector> #include <algorithm> #include <numeric> using namespace std; const int COUNT = 1000 * 1000 * 1000; int RandomNumber () { static int s = 0; return (s++ % 100); } int main () { vector<int> vec(COUNT); generate(vec.begin(), vec.end(), RandomNumber); struct timespec tm1, tm2; clock_gettime(CLOCK_REALTIME, &tm1); register int *array = &vec[0]; register int sum = 0; for(register int i = 0; i != COUNT; ++i) { sum += array[i]; }; 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, sum=" <<sum<< endl; return 0; };
AMDmi3
Сравнивать быстродействие кода без оптимизаций? Ну ок.
VioletGiraffe
+1. Тема интересна, результаты бесполезны. Пожалуй, повторю эксперимент сам. Один раз столкнулся при оптимизации хотспота с тем, что обход вектора с помощью итератора заметно медленнее, чем по индексу (в релизе со вмеми оптимизациями).
lexdevel
Скорее всего это связано с тем, что Вы использовали постинкремент, а надо — преинкремент. Пруф.
VioletGiraffe
Не-а, всегда пишу прединкремент. После проделанного вчера эксперимента (мой пост ниже) я понял, что дело всего-навсего было в том, что я не догадался предвычислить end() до начала цикла, а size() — догадался. Это единственный фактор, насколько я могу судить по результатам исследования.
А вот разницы между +it и it++ как раз и нет в этом конкретном тесте.
xiWera
Ага, автор узнает много нового когда скомпилит все варианты с -O2 и посмотрит на дизасм :)