Вопрос по math, optimization, c#, modulus – Более быстрый модуль в C / C #?

19

Есть ли хитрость для создания более быстрого целочисленного модуля, чем стандартный оператор% для конкретных базисов?

Для моей программы я бы искал около 1000-4000 (например, n% 2048). Есть ли более быстрый способ выполнить n модуля 2048, чем просто:n%2048?

...... Точно так же. Dan W
Хороший выбор имени пользователя. Dan W
2048 звучит подозрительно, как будто вы собираетесь использовать это в контексте RSA, может быть? Если это так, то лучше рассмотреть модульное возведение в степень напрямую. emboss
Нет, это для более быстрой функции синуса / косинуса (см.here). 2048 представляет размер таблицы. Dan W

Ваш Ответ

7   ответов
0

которые имеют степень двойки, то ответ, вероятно, нет: любой порядочный компилятор автоматически превратит такие выражения в вариацию операции AND, которая довольно близка к оптимальной.

Integer. Выпуск сборки без отладки. Он был использован для дальнейшего увеличения скорости вычисления быстрой синусоидальной функции по Чарльзу. ответhere, Увидетьindex %= TABLE_SIZE; немного. Dan W
Из любопытства, какой тип данных, и вы измеряете сборку отдельного релиза?
В C # я получаю увеличение скорости, см. Выше. Dan W
0

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

Это примерно в 2 раза быстрее, чем встроенный оператор по модулю% на моем Intel Core i5.

Я удивлен, что это не так драматично, как процессор x86div инструкции могут иметьзадержки до 80-90 циклов для 64-битного деления на некоторых процессорах, по сравнению сmul при 3 циклах и побитовых операциях по 1 циклу каждый.

Подтверждение концепции и сроков показано ниже.series_len относится к числу модульных операций, выполняемых последовательно на одной переменной. Это препятствует тому, чтобы ЦП скрывал задержки через распараллеливание.

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

typedef int32_t s32;
typedef uint32_t u32;
typedef uint64_t u64;

#define NUM_NUMS 1024
#define NUM_RUNS 500
#define MAX_NUM UINT32_MAX
#define MAX_DEN 1024

struct fastdiv {
    u32 mul;
    u32 add;
    s32 shift;
    u32 _odiv;  /* save original divisor for modulo calc */
};

static u32 num[NUM_NUMS];
static u32 den[NUM_NUMS];
static struct fastdiv fd[NUM_NUMS];

/* hash of results to prevent gcc from optimizing out our ops */
static u32 cookie = 0;

/* required for magic constant generation */
u32 ulog2(u32 v) {
    u32 r, shift;
    r =     (v > 0xFFFF) << 4; v >>= r;
    shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
    shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
    shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
                                            r |= (v >> 1);
    return r;
}

/* generate constants for implementing a division with multiply-add-shift */
void fastdiv_make(struct fastdiv *d, u32 divisor) {
    u32 l, r, e;
    u64 m;

    d->_odiv = divisor;
    l = ulog2(divisor);
    if (divisor & (divisor - 1)) {
        m = 1ULL << (l + 32);
        d->mul = (u32)(m / divisor);
        r = (u32)m - d->mul * divisor;
        e = divisor - r;
        if (e < (1UL << l)) {
            ++d->mul;
            d->add = 0;
        } else {
            d->add = d->mul;
        }
        d->shift = l;
    } else {
        if (divisor == 1) {
            d->mul = 0xffffffff;
            d->add = 0xffffffff;
            d->shift = 0;
        } else {
            d->mul = 0x80000000;
            d->add = 0;
            d->shift = l-1;
        }
    }
}

/* 0: use function that checks for a power-of-2 modulus (speedup for POTs)
 * 1: use inline macro */
#define FASTMOD_BRANCHLESS 0

#define fastdiv(v,d) ((u32)(((u64)(v)*(d)->mul + (d)->add) >> 32) >> (d)->shift)
#define _fastmod(v,d) ((v) - fastdiv((v),(d)) * (d)->_odiv)

#if FASTMOD_BRANCHLESS
#define fastmod(v,d) _fastmod((v),(d))
#else
u32 fastmod(u32 v, struct fastdiv *d) {
    if (d->mul == 0x80000000) {
        return (v & ((1 << d->shift) - 1));
    }
    return _fastmod(v,d);
}
#endif

u32 random32(u32 upper_bound) {
    return arc4random_uniform(upper_bound);
}

u32 random32_range(u32 lower_bound, u32 upper_bound) {
    return random32(upper_bound - lower_bound) + lower_bound;
}

void fill_arrays() {
    int i;
    for (i = 0; i < NUM_NUMS; ++i) {
        num[i] = random32_range(MAX_DEN, MAX_NUM);
        den[i] = random32_range(1, MAX_DEN);
        fastdiv_make(&fd[i], den[i]);
    }
}

void fill_arrays_pot() {
    u32 log_bound, rand_log;
    int i;

    log_bound = ulog2(MAX_DEN);
    for (i = 0; i < NUM_NUMS; ++i) {
        num[i] = random32_range(MAX_DEN, MAX_NUM);
        rand_log = random32(log_bound) + 1;
        den[i] = 1 << rand_log;
        fastdiv_make(&fd[i], den[i]);
    }
}

u64 clock_ns() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return tv.tv_sec*1000000000 + tv.tv_usec*1000;
}

void use_value(u32 v) {
    cookie += v;
}

int main(int argc, char **arg) {
    u64 builtin_npot_ns;
    u64 builtin_pot_ns;
    u64 branching_npot_ns;
    u64 branching_pot_ns;
    u64 branchless_npot_ns;
    u64 branchless_pot_ns;
    u64 t0, t1;
    u32 v;
    int s, r, i, j;
    int series_len;

    builtin_npot_ns = builtin_pot_ns = 0;
    branching_npot_ns = branching_pot_ns = 0;
    branchless_npot_ns = branchless_pot_ns = 0;

    for (s = 5; s >= 0; --s) {
        series_len = 1 << s;
        for (r = 0; r < NUM_RUNS; ++r) {
            /* built-in NPOT */
            fill_arrays();
            t0 = clock_ns();
            for (i = 0; i < NUM_NUMS; ++i) {
                v = num[i];
                for (j = 0; j < series_len; ++j) {
                    v /= den[i];
                }
                use_value(v);
            }
            t1 = clock_ns();
            builtin_npot_ns += (t1 - t0) / NUM_NUMS;

            /* built-in POT */
            fill_arrays_pot();
            t0 = clock_ns();
            for (i = 0; i < NUM_NUMS; ++i) {
                v = num[i];
                for (j = 0; j < series_len; ++j) {
                    v /= den[i];
                }
                use_value(v);
            }
            t1 = clock_ns();
            builtin_pot_ns += (t1 - t0) / NUM_NUMS;

            /* branching NPOT */
            fill_arrays();
            t0 = clock_ns();
            for (i = 0; i < NUM_NUMS; ++i) {
                v = num[i];
                for (j = 0; j < series_len; ++j) {
                    v = fastmod(v, fd+i);
                }
                use_value(v);
            }
            t1 = clock_ns();
            branching_npot_ns += (t1 - t0) / NUM_NUMS;

            /* branching POT */
            fill_arrays_pot();
            t0 = clock_ns();
            for (i = 0; i < NUM_NUMS; ++i) {
                v = num[i];
                for (j = 0; j < series_len; ++j) {
                    v = fastmod(v, fd+i);
                }
                use_value(v);
            }
            t1 = clock_ns();
            branching_pot_ns += (t1 - t0) / NUM_NUMS;

            /* branchless NPOT */
            fill_arrays();
            t0 = clock_ns();
            for (i = 0; i < NUM_NUMS; ++i) {
                v = num[i];
                for (j = 0; j < series_len; ++j) {
                    v = _fastmod(v, fd+i);
                }
                use_value(v);
            }
            t1 = clock_ns();
            branchless_npot_ns += (t1 - t0) / NUM_NUMS;

            /* branchless POT */
            fill_arrays_pot();
            t0 = clock_ns();
            for (i = 0; i < NUM_NUMS; ++i) {
                v = num[i];
                for (j = 0; j < series_len; ++j) {
                    v = _fastmod(v, fd+i);
                }
                use_value(v);
            }
            t1 = clock_ns();
            branchless_pot_ns += (t1 - t0) / NUM_NUMS;
        }

        builtin_npot_ns /= NUM_RUNS;
        builtin_pot_ns /= NUM_RUNS;
        branching_npot_ns /= NUM_RUNS;
        branching_pot_ns /= NUM_RUNS;
        branchless_npot_ns /= NUM_RUNS;
        branchless_pot_ns /= NUM_RUNS;

        printf("series_len = %d\n", series_len);
        printf("----------------------------\n");
        printf("builtin_npot_ns    : %llu ns\n", builtin_npot_ns);
        printf("builtin_pot_ns     : %llu ns\n", builtin_pot_ns);
        printf("branching_npot_ns  : %llu ns\n", branching_npot_ns);
        printf("branching_pot_ns   : %llu ns\n", branching_pot_ns);
        printf("branchless_npot_ns : %llu ns\n", branchless_npot_ns);
        printf("branchless_pot_ns  : %llu ns\n\n", branchless_pot_ns);
    }
    printf("cookie=%u\n", cookie);
}
Results

Intel Core i5 (MacBookAir7,2), macOS 10.11.6, clang 8.0.0

series_len = 32
----------------------------
builtin_npot_ns    : 218 ns
builtin_pot_ns     : 225 ns
branching_npot_ns  : 115 ns
branching_pot_ns   : 42 ns
branchless_npot_ns : 110 ns
branchless_pot_ns  : 110 ns

series_len = 16
----------------------------
builtin_npot_ns    : 87 ns
builtin_pot_ns     : 89 ns
branching_npot_ns  : 47 ns
branching_pot_ns   : 19 ns
branchless_npot_ns : 45 ns
branchless_pot_ns  : 45 ns

series_len = 8
----------------------------
builtin_npot_ns    : 32 ns
builtin_pot_ns     : 34 ns
branching_npot_ns  : 18 ns
branching_pot_ns   : 10 ns
branchless_npot_ns : 17 ns
branchless_pot_ns  : 17 ns

series_len = 4
----------------------------
builtin_npot_ns    : 15 ns
builtin_pot_ns     : 16 ns
branching_npot_ns  : 8 ns
branching_pot_ns   : 3 ns
branchless_npot_ns : 7 ns
branchless_pot_ns  : 7 ns

series_len = 2
----------------------------
builtin_npot_ns    : 8 ns
builtin_pot_ns     : 7 ns
branching_npot_ns  : 4 ns
branching_pot_ns   : 2 ns
branchless_npot_ns : 2 ns
branchless_pot_ns  : 2 ns
Как скорость вашего ответа сравнивается с двумя верхними? Dan W
2

х = 11 = 1011
х% 4 = 3 = 0011

так что для x% 4 вы могли бы просто взять последние 2 бита - я не уверен, что произойдет, если будут использованы отрицательные числа

33

что знаменатель во время компиляции имеет степень 2, как, например, ваш пример 2048 года, вы можете вычесть 1 и сделать побитовое и.

То есть:

n % m == n & (m - 1) 

...гдеm это степень 2.

Например:

22 % 8 == 22 - 16 == 6

         Dec   Bin
       -----   -----
          22 = 10110
           8 = 01000  
       8 - 1 = 00111 
22 & (8 - 1) =   10110 
               & 00111 
               -------
           6 =   00110

Имейте в виду, что хороший компилятор будет иметь свои собственные оптимизации для%Может быть, даже достаточно, чтобы быть таким же быстрым, как описанная выше техника Арифметические операторы, как правило, довольно сильно оптимизированы.

И если вы знаете заранее, чтоm будет точно, а не только то, что это сила2Вы можете предварительно вычесть. Чтобы получитьmod из16использоватьn & 15.
Остерегайтесь того, как определяется модуль (или делитель): C # / RuyJIT / VS2015, например. оптимизировал мой модуль и деление до 10times быстрее с модулем / делителем, указанным в том же методе или как const против переданного в качестве параметров, поэтому предварительно определите их, если возможно.
@DanW: имейте в виду, это также работает дляnegative значенияn, в то время как% не. Для негативаn и положительныйm, % дает отрицательный остаток.
@DanW - Рад слышать. Я сам человек на C #, поэтому мне было интересно, как будет выглядеть производительность в .NET.
Возможно, в C / C ++, но в C # я нахожу увеличение скорости по крайней мере в 1,25 раза быстрее (и, вероятно, намного выше, так как происходит и другие вещи - это код реального мира). Dan W
13

2^nвсе, что вам нужно сделать, это обнулить все биты, кроме последнегоn биты.

Например (предполагая 32-битные целые числа):

x%2 эквивалентноx & 0x00000001

x%4 эквивалентноx & 0x00000003

В общемx % (2^n) равноx & (2^n-1), Написано на С, это будетx & ((1<<n)-1).

Это потому что2^n дает вам 1 вn+1бит (справа). Так2^n-1 дам тебеn те, что справа, и нули слева.

Да, конечно. Dan W
Это не дает модуль, это только говорит, равен ли модуль 0.
Разве это не так?x & (n-1) вместоx & ((1<<n)-1) как сказал Джастин? Dan W
В моем примереn не номер, который вы изменяете,2^n является.
@JustinMorgan: Woops неправильно прочитал вопрос, отредактировал.
2

Вот несколько методик которые повторяют операцию модуля.

Это был самый быстрый тест (с учетом сценария 2048). Пока ваш & quot; max & quot; это не миллионы, и в диапазоне 1000-4000, который вы упомянули, он также может работать быстрее для вас:

int threshold = 2048; //the number to mod by
int max = 1000; //the number on the left. Ex: 1000 % 2048
int total = 0;
int y = 0;
for (int x = 0; x < max; x++)
{
    if (y > (threshold - 1))
    {
        y = 0;
        total += x;
    }
    y += 1;
}
return total;

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

0

Самый быстрый способ умножить / разделить числа без знака на целые числа - сдвинуть их влево или вправо. Операции сдвига соответствуют непосредственно командам процессора. Например, 3 & lt; & lt; 2 = 6, а 4 = 1.

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

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

Следующий код рассчитывает 7% 4 путем смещения достаточно далеко, чтобы остались только 2 последних бита (так как 4 = 2 ^ 2). Это означает, что нам нужно сдвинуть 30 бит:

uint i=7;
var modulo=((i<<30)>>30);

Результат 3

EDIT:

Я просто прочитал все решения, предлагающие просто стереть биты более высокого порядка. Это имеет тот же эффект, но намного проще и прямолинейнее.

@jrodatus Вы можете также прочитать другие вопросы и комментарии - это вопрос C #, а не вопрос сборки. Сгенерированный IL и сборка могут отличаться от одного процессора к другому и от одного процессора до следующего. Как упомянул Кристиан Ведберг в комментарии, теперь с модом вы можете получить в 10 раз лучшую производительность. Если компилятор обнаруживает, что делитель имеет степень 2, он вполне может использовать один из многих побитовых методов здесь
@jrodatus, и это связано с этим ответом, как? Не берите в голову, что говорить о циклах без упоминания процессора бессмысленно. Раньше мул занимал 90 или более инструкций. И указание на чью-то домашнюю работу на старых процессорах ничего не доказывает. Поведение каждой инструкции ЦПУ задокументировано, вам не нужно измерять их косвенно. PS: а затем есть команды SIMD, AVX и SSE4, которые делаютflotating указать как быстро или быстрее, если у вас есть достаточно данных
2 (C против C #). Название вопроса говоритC / C #. C отображается на сборку, поэтому время команд процессораare актуально (как вы сами заявили). (Продолжение & APOS; д)
Это & APOS; snot at all правда, что процессорdiv/mod инструкции так же быстры, как побитовые инструкции. Они намного, намного медленнее. Вокруг80-90 cycles для 64-битнойdiv по сравнению с 3 циклами дляmul и 1 цикл дляand.
1 (Актуальность). Вы неправильно указали"If the integer modulo operator maps to this [integer modulo CPU] command in optimized builds, you will not see any improvement by using the bit shift trick." Вопреки этому утверждению, сдвиг немногоis быстрее, чем команды процессора div / mod на современных процессорах. Обратите внимание на код теста и результаты измерения времени в моем ответе. (Продолжение & APOS; д)

Похожие вопросы