Почему вычитание быстрее сложения?

183
30 марта 2018, 13:06

Написал несколько бенчмарков для вектора (использовал библиотеку гугла 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, инициализацию полностью выносил за цикл бенчмарка. Потому проблема не в тестах, они корректны.

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

Answer 1

Есть один тонкий момент - при использовании в качестве ограничителя вызова функции.

Тут

for(int = func(); i >= 0; --i)

func() вызывается один раз, а тут -

for(int = 0; i < func(); ++i)

много раз (если оптимизатор не выпилит этот вызов, чего он может и не делать, если для него не очевидно, что этот вызов всегда дает одинаковый результат и не выполняет никаких побочных действий).

Update после возражения автора вопроса

Еще - вот такой код

int main()
{
    const int N = 1000000000;
    {
        muTimer mt;
        for(int i = 0; i < N; ++i);
        cout << mt.stop().duration() << endl;
    }
    {
        muTimer mt;
        for(int i = N; i > 0; --i);
        cout << mt.stop().duration() << endl;
    }
}

(полностью - см. https://ideone.com/9WYPGW (на нулевое время не смотрите - понятно, что на Ideone оптимизатор циклы вообще выбросил))

дает при компиляции VC++ 2017 с отключенной оптимизацией на моей машине

1591801
1537876

т.е. одинаковое время в пределах погрешности.

Так что... а был ли мальчик? :)

Answer 2

Потому, что проверка данных из точек памяти вытягивает время. Это по-сути БАГ программиста, что он вызывает функцию постоянно. Представьте, что у вас отключены оптимизации. for.cpp: // > g++ -O0 -mtune=native -S -masm=intel -fverbose-asm for.cpp

    int const n(10);
    int f(){return n;}
/*
_Z1fv:
.LFB0:
    .cfi_startproc
    push    rbp #
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    mov rbp, rsp    #,
    .cfi_def_cfa_register 6
    mov eax, 10 # D.2224,
    pop rbp #
    .cfi_def_cfa 7, 8
    ret
*/
    int main(){
    for(int i=0;i<f();++i);
    /*
        jmp .L4 #
    .L5:
        inc DWORD PTR [rbp-4]   # i
    .L4:
        call    _Z1fv   #
        cmp eax, DWORD PTR [rbp-4]  # D.2225, i
        setg    al  #, retval.0
        test    al, al  # retval.0
        jne .L5 #, 
     */
    for(int i=f();i>0;)--i;
    /*
        call    _Z1fv   #
        mov DWORD PTR [rbp-8], eax  # i, tmp63
        jmp .L6 #
    .L7:
        dec DWORD PTR [rbp-8]   # i
    .L6:
        cmp DWORD PTR [rbp-8], 0    # i,
        jg  .L7 #,  
     */  
    }

В первом цикле постоянно вызывается функция f(); А она постоянно дёргает стек и регистры, возвращая 10.

READ ALSO
compareTo, как исправить ошибку

compareTo, как исправить ошибку

Здравствуйте, столкнулся с такой проблемой, что compareTo закидывает самую первую строчку из файла в конец после сортировкиТак выглядит код

210
Вопрос по ООП. Конкретный пример

Вопрос по ООП. Конкретный пример

Класс - реализация интерфейса, описывающего работникаУ каждого работника может быть менеджер, у каждого менеджера может быть менеджер итд

172
Проектирование и многопоточность Java

Проектирование и многопоточность Java

Существует кусками реализованная структура проектаБез многопоточности

254
GridView in LinearLayout

GridView in LinearLayout

Можно ли использовать gridview в linearlayout/ Ставлю, вроде отображает,а содержимого нету!

202