Лучше ли избегать использования оператора мод, когда это возможно?

Я предполагаю, что вычисление модуля числа является несколько дорогостоящей операцией, по крайней мере, по сравнению с простыми арифметическими тестами (например, если число превышает длину массива). Если это действительно так, эффективнее ли заменить, например, следующий код:

res = array[(i + 1) % len];

со следующим?

res = array[(i + 1 == len) ? 0 : i + 1];

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

Конечно, эта "оптимизация" (если это действительно оптимизация) не работает во всех случаях (в этом случае она работает только в том случае, если i+1 не больше, чем len).

Ответ 1

Мой общий совет таков. Используйте ту версию, которая, по вашему мнению, проще на глазу, а затем профилируйте всю вашу систему. Только оптимизируйте те части кода, которые профайлер торчит как узкие места. Я поставил свой нижний доллар, что оператор modulo не будет среди них.

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

Ответ 2

Некоторые простые измерения:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    int test = atoi(argv[1]);
    int divisor = atoi(argv[2]);
    int iterations = atoi(argv[3]);

    int a = 0;

    if (test == 0) {
        for (int i = 0; i < iterations; i++)
            a = (a + 1) % divisor;
    } else if (test == 1) {
        for (int i = 0; i < iterations; i++)
            a = a + 1 == divisor ? 0 : a + 1;
    }

    printf("%d\n", a);
}

Компиляция с помощью gcc или clang с -O3, а запуск time ./a.out 0 42 1000000000 (версия по модулю) или time ./a.out 1 42 1000000000 (сравнительная версия) приводит к

6.25 секунд пользовательская версия для версии modulo,
1,03 секунды для версии сравнения.

(с использованием gcc 5.2.1 или clang 3.6.2, Intel Core i5-4690K @3,50 ГГц, 64-разрядной Linux)

Это означает, что, вероятно, неплохо использовать версию сравнения.

Ответ 3

Советы, чтобы избежать оператора% (модуля), http://embeddedgurus.com/stack-overflow/2011/02/efficient-c-tip-13-use-the-modulus-operator-with-caution

Ответ 4

Итак, рассмотрим 2 способа получить следующее значение циклического счетчика по модулю 3.

int next1(int n) {
    return (n + 1) % 3;
}

int next2(int n) {
    return n == 2 ? 0 : n + 1;
}

Я скомпилировал его с опцией gcc -O3 (для общей архитектуры x64) и -s, чтобы получить код сборки.

Код первой функции выполняет необъяснимую магию (*), чтобы избежать деления, в любом случае, используя умножение:

addl    $1, %edi
movl    $1431655766, %edx
movl    %edi, %eax
imull   %edx
movl    %edi, %eax
sarl    $31, %eax
subl    %eax, %edx
leal    (%rdx,%rdx,2), %eax
subl    %eax, %edi
movl    %edi, %eax
ret

И намного дольше (и я ставлю медленнее), чем вторая функция:

leal    1(%rdi), %eax
cmpl    $2, %edi
movl    $0, %edx
cmove   %edx, %eax
ret

Так что не всегда верно, что "(современный) компилятор работает лучше, чем вы".

Интересно, что тот же эксперимент с 4 вместо 3 приводит к маскировке первой функции

addl    $1, %edi
movl    %edi, %edx
sarl    $31, %edx
shrl    $30, %edx
leal    (%rdi,%rdx), %eax
andl    $3, %eax
subl    %edx, %eax
ret

но все же, по большому счету, уступает второй версии.

Быть более явным о правильных способах делать вещи

int next3(int n) {
    return (n + 1) & 3;;
}

дает гораздо лучшие результаты:

leal    1(%rdi), %eax
andl    $3, %eax
ret

(*) ну, не так сложно. Умножение на взаимное. Вычислите целочисленную константу K = (2 ^ N)/3 для достаточно большого значения N. Теперь, когда вы хотите получить значение X/3 вместо деления на 3, вычислите X * K и сдвиньте его N позиции справа.

Ответ 5

Если 'len' в вашем коде достаточно велико, условное выражение будет быстрее, поскольку предикторы ветвления почти всегда будут правильно угадывать.

Если нет, то я считаю, что это тесно связано с циклическими очередями, где часто случается, что длина является степенью 2. Это позволит компилятору заменить по модулю простое И.

Код следующий:

#include <stdio.h>
#include <stdlib.h>

#define modulo

int main()
{
    int iterations = 1000000000;
    int size = 16;
    int a[size];
    unsigned long long res = 0;
    int i, j;

    for (i=0;i<size;i++)
        a[i] = i;

    for (i=0,j=0;i<iterations;i++)
    {
        j++;
        #ifdef modulo
            j %= size;
        #else
            if (j >= size)
                j = 0;
        #endif
        res += a[j];
    }

    printf("%llu\n", res);
}

Размер = 15:

по модулю: 4868 с
конд: 1,291 с

размер = 16:

по модулю: 1,067 с
конд: 1,599 с

Скомпилировано в gcc 7.3.0 с оптимизацией -O3. Машина i7 920.

Ответ 6

Modulo может выполняться с помощью одной процессорной команды на большинстве архитектур (например, DIV на x86). Однако это, вероятно, преждевременная оптимизация для того, что вам нужно.