¿Módulo más rápido en C/C#?

math optimization

Question

¿Hay algún truco para crear un módulo de enteros más rápido que el operador% estándar para bases particulares?

Para mi programa, estaría buscando alrededor de 1000-4000 (por ejemplo, n% 2048). ¿Hay una forma más rápida de realizar n módulo 2048 que simplemente: n%2048 ?

Answer 1

El módulo sin potencia de dos sin ramificación es posible al calcular previamente las constantes mágicas en tiempo de ejecución, para implementar la división utilizando un cambio de suma-suma.

Esto es aproximadamente 2 veces más rápido que el operador de módulo incorporado % en mi Intel Core i5.

Me sorprende que no sea más dramático, ya que las instrucciones div CPU x86 pueden tener latencias tan altas como 80-90 ciclos para la división de 64 bits en algunas CPU, en comparación con mul en 3 ciclos y operaciones bitwise en 1 ciclo cada una.

Prueba de concepto y tiempos que se muestran a continuación. series_len refiere al número de operaciones de módulo realizadas en serie en una sola var. Eso es para evitar que la CPU oculte las latencias a través de la paralelización.

#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);
}

Resultados

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

Answer 2

La forma más rápida de multiplicar / dividir números enteros sin signo es desplazándolos a la izquierda oa la derecha. Las operaciones de cambio coinciden directamente con los comandos de la CPU. Por ejemplo, 3 << 2 = 6, mientras que 4 >> 1 = 2.

Puede usar el mismo truco para calcular el módulo: desplace un entero lo suficiente hacia la izquierda para que solo queden los bits restantes, y luego vuelva a desplazarlo hacia la derecha para que pueda verificar el valor del resto.

Por otro lado, el módulo entero también existe como un comando de CPU. Si el operador de módulo entero se asigna a este comando en compilaciones optimizadas, no verá ninguna mejora al usar el truco de cambio de bits.

El siguiente código calcula 7% 4 desplazándose lo suficiente para que solo queden los 2 últimos bits (ya que 4 = 2 ^ 2). Esto significa que necesitamos cambiar 30 bits:

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

El resultado es 3

EDITAR:

Acabo de leer todas las soluciones que proponen simplemente borrar los bits de orden superior. Tiene el mismo efecto, pero mucho más simple y directo.

Answer 3

Para potencias de dos 2^n , todo lo que tienes que hacer es poner a cero todos los bits excepto los últimos n bits.

Por ejemplo (asumiendo enteros de 32 bits):

x%2 es equivalente a x & 0x00000001

x%4 es equivalente a x & 0x00000003

En general, x % (2^n) es igual a x & (2^n-1) . Escrito en C, esto sería x & ((1<<n)-1) .

Esto se debe a que 2^n le da un 1 en el n+1 bit (desde la derecha). Entonces 2^n-1 te dará n unidades a la derecha y ceros a la izquierda.

Answer 4

Si está dividiendo por literales que son potencias de dos, entonces la respuesta es probablemente No: cualquier compilador decente convertirá automáticamente tales expresiones en una variación de una operación AND, que está bastante cerca de ser óptima.

Answer 5

Si se sabe que el denominador en tiempo de compilación es una potencia de 2, como su ejemplo de 2048, podría restar 1 y hacer un bit-y.

Es decir:

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

... donde m es una potencia de 2.

Por ejemplo:

22 % 8 == 22 - 16 == 6

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

Tenga en cuenta que un buen compilador tendrá sus propias optimizaciones para % , tal vez lo suficiente como para ser tan rápido como la técnica anterior. Los operadores aritméticos tienden a ser bastante fuertemente optimizados.

Answer 6

Usted podría poner a cero los bits de orden alto, es decir

x = 11 = 1011
x% 4 = 3 = 0011

así que para x% 4 solo puedes tomar los últimos 2 bits. No estoy seguro de qué pasaría si se usaran números negativos.

Answer 7

Aquí hay algunas técnicas que replican la operación de módulo.

De los evaluados, este fue el más rápido (modificado para adaptarse a su escenario 2048). Siempre que su "máximo" no sea millones y en el rango 1000-4000 que mencionó, también puede funcionar más rápido para usted:

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;

Darle una oportunidad. Se realizó más rápido en la máquina del autor en varias configuraciones, por lo que también debería funcionar admirablemente bien para usted.