Написал несколько бенчмарков для вектора (использовал библиотеку гугла https://github.com/google/benchmark) и получил странный результат: обход с циклом от size
до нуля работает в два-три раза быстрее, чем от нуля до size
.
Подумал, это может быть связано с кешированием и прочими оптимизациями процессора, потому написал такие тесты
#define ARGS Arg(10000)
static void BM_Minus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = state.range(0); i > 0; i = i - 1) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_Minus)->ARGS;
static void BM_PlusMinus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); i = i + (-1)) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PlusMinus)->ARGS;
static void BM_PreMinus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = state.range(0); i > 0; --i) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PreMinus)->ARGS;
static void BM_PostMinus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = state.range(0); i > 0; i--) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PostMinus)->ARGS;
// -------------------------------------------------
static void BM_Plus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); i = i + 1) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_Plus)->ARGS;
static void BM_MinusMinus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); i = i - (-1)) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_MinusMinus)->ARGS;
static void BM_PrePlus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); ++i) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PrePlus)->ARGS;
static void BM_PostPlus(benchmark::State& state) {
for (auto _ : state) {
for (size_t i = 0; i < state.range(0); i++) {
benchmark::DoNotOptimize(i);
}
}
}
BENCHMARK(BM_PostPlus)->ARGS;
И получил следующие результаты:
Benchmark Time CPU Iterations
----------------------------------------------------------------
BM_Minus/10000 16202 ns 16186 ns 43230
BM_PlusMinus/10000 9 ns 9 ns 76223137
BM_PreMinus/10000 16200 ns 16187 ns 43200
BM_PostMinus/10000 16207 ns 16193 ns 43089
BM_Plus/10000 42778 ns 42739 ns 16415
BM_MinusMinus/10000 42734 ns 42696 ns 16392
BM_PrePlus/10000 42783 ns 42745 ns 16361
BM_PostPlus/10000 42965 ns 42926 ns 16378
Посмотрел на ассемблер (предварительно выпилив код гугловской библиотеки), в сложении используется инструкция ja
, в вычитании je
, что, очевидно, не может давать такой разницы. В остальном отличие только в том, с каким числом сравнивается, что, опять же, повлиять не может, и сложение меняется на вычитание. Даже адрес переменной i
тот же.
Разница остается вне зависимости от того, включены ли оптимизации (проверял от O0
до O4
) и сколько элементов создается (проверял на малых, средних и больших значениях).
Вопрос:
1) Верны ли эти результаты для всех/большинства процессоров?
2) Почему такое происходит?
3) Возможно, кому-то известны случаи использования этой особенности?
4) Еще интересно, почему компилятор так оптимизировал BM_PlusMinus()
. Вернее, почему только ее. Но тема не об этом, это просто замечание.
Компилятор: g++ 7.3.1
Процессор: Intel Core i7
P.S. В комментариях заметили, что возможно, проблема в том, что state.range(0) вызывается несколько раз. Я не акцентировал на этом внимания, но написал, что ассемблерный код одинаковый. Более того, изначально я проверял с константами на месте state.range(0), также менял цикл на while, инициализацию полностью выносил за цикл бенчмарка. Потому проблема не в тестах, они корректны.
Сейчас я склоняюсь к версии, что процессору проще сравнивать с нулм, чем с большими числами, но тогда возникает вопрос, почему не уменьшаетя разница на малых числах.
bm_plusminus()
начальное значение и условие как минимум неправильно описаныi = i - 1
можно записать на ассемблере по-разному. PrePlus и PostPlus должны дать одинаковый результат - поскольку промежуточное значение PostPlus - не используется.for (size_t i = var1; i < var2; ...) {}
.