Разница в эффективности между оператором if и модом (SIZE) - PullRequest
Новая
       31

Разница в эффективности между оператором if и модом (SIZE)

1 голос
/ 13 июня 2019

Изучение Я нашел использование (i+1)mod(SIZE) для выполнения цикла в массиве элементов. Поэтому я подумал, был ли этот метод более эффективным, чем оператор if ...

Например: 

#define SIZE 15

int main(int argc, char *argv[]) {
    int items[SIZE];

    for(int i = 0; items[0] < 5; i = (i + 1) % SIZE) items[i] += 1;

    return 0;
}

Это более эффективно, чем (?): 

#define SIZE 15

int main(int argc, char *argv[]) {
    int items[SIZE];

    for(int i = 0; items[0] < 5; i++) {
        if(i == SIZE) i = 0;
        items[i] += 1;
    }

    return 0;
}

Спасибо за ответы и ваше время.

Ответы [ 2 ]

3 голосов
/ 13 июня 2019

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

Пример 1: 

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-68], edi
        mov     QWORD PTR [rbp-80], rsi
        mov     DWORD PTR [rbp-4], 0
.L3:
        mov     eax, DWORD PTR [rbp-64]
        cmp     eax, 4
        jg      .L2
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        mov     eax, DWORD PTR [rbp-64+rax*4]
        lea     edx, [rax+1]
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        mov     DWORD PTR [rbp-64+rax*4], edx
        mov     eax, DWORD PTR [rbp-4]
        add     eax, 1
        movsx   rdx, eax
        imul    rdx, rdx, -2004318071
        shr     rdx, 32
        add     edx, eax
        mov     ecx, edx
        sar     ecx, 3
        cdq
        sub     ecx, edx
        mov     edx, ecx
        mov     DWORD PTR [rbp-4], edx
        mov     ecx, DWORD PTR [rbp-4]
        mov     edx, ecx
        sal     edx, 4
        sub     edx, ecx
        sub     eax, edx
        mov     DWORD PTR [rbp-4], eax
        jmp     .L3
.L2:
        mov     eax, 0
        pop     rbp
        ret

Пример 2: 

main:
        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-68], edi
        mov     QWORD PTR [rbp-80], rsi
        mov     DWORD PTR [rbp-4], 0
.L4:
        mov     eax, DWORD PTR [rbp-64]
        cmp     eax, 4
        jg      .L2
        cmp     DWORD PTR [rbp-4], 15
        jne     .L3
        mov     DWORD PTR [rbp-4], 0
.L3:
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        mov     eax, DWORD PTR [rbp-64+rax*4]
        lea     edx, [rax+1]
        mov     eax, DWORD PTR [rbp-4]
        cdqe
        mov     DWORD PTR [rbp-64+rax*4], edx
        add     DWORD PTR [rbp-4], 1
        jmp     .L4
.L2:
        mov     eax, 0
        pop     rbp
        ret

Вы видите, что для конкретного случая с x86 решение без модуля значительно короче.

1 голос
/ 13 июня 2019

Несмотря на то, что вы спрашиваете только о mod против branch, в зависимости от фактической реализации mod и ответвления, вероятно, более чем пять случаев:

На основе модуля

Power-of-two

Если значение SIZE известно компилятору и равно степени 2, mod скомпилируется в один and , как это и будет очень эффективным по производительности и размеру кода.and по-прежнему является частью цепочки зависимостей приращения цикла, хотя ограничение скорости накладывается на производительность, равную 2 циклам на итерацию, если только компилятор не достаточно умен, чтобы развернуть его и не дать and выйти изпереносимая цепь (gcc и clang не были).

Известно, но не как двойная степень

С другой стороны, если значение SIZE известно, но не является степеньюиз двух, вы, вероятно, получите основанную на умножении реализацию фиксированного значения модуля, , например, .Обычно это занимает что-то вроде 4-6 инструкций, которые заканчиваются частью цепочки зависимостей.Таким образом, это ограничит вашу производительность чем-то вроде 1 итерации каждые 5-8 циклов, точно в зависимости от задержки цепочки зависимостей.

Неизвестно

В вашем примере SIZE - известная константа, но в более общем случае, когда он не известен во время компиляции, вы получите инструкцию деления на платформах, которые его поддерживают.Что-то вроде как это .

Это хорошо для размера кода, так как это одна инструкция, но, вероятно, катастрофически для производительности, потому что теперь у вас есть медленная инструкция деления как часть переносимой зависимости дляпетля.В зависимости от вашего оборудования и типа переменной SIZE, вы смотрите 20-100 циклов на итерацию.

На основе ветвления

Вы добавляете ветку в свой код, но переходитекомпилятор решил реализовать это как условный переход или как условный переход.В -O2, gcc выбирает прыжок и звенит условным ходом .

Условный переход

Это прямая интерпретация вашего кода: используйте условную ветвьдля реализации условия i == SIZE.

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

Однако производительность может серьезно пострадать, если ветка часто ошибается.Это сильно зависит от значения SIZE и от вашего оборудования.Современный Intel должен иметь возможность прогнозировать вложенные циклы до 20 с чем-то итераций, но помимо этого он будет ошибочно прогнозировать каждый раз при выходе из внутреннего цикла.Конечно, если SIZE очень велико, то единственный неверный прогноз в любом случае не будет иметь большого значения, поэтому наихудший случай - SIZE, достаточно большой, чтобы неверно прогнозировать.

Условное движение

clangиспользует условный ход для обновления i.Это разумный вариант, но он означает переносимую зависимость потока данных в 3-4 цикла.

1 Либо на самом деле константа, как в вашем примереили фактически постоянная из-за встраивания и постоянного распространения.

...