¿Prueba de divisibilidad más rápida que% operador?

23

Noté algo curioso en mi computadora. * La prueba de divisibilidad escrita a mano es significativamente más rápida que la del %operador. Considere el ejemplo mínimo:

* AMD Ryzen Threadripper 2990WX, GCC 9.2.0

static int divisible_ui_p(unsigned int m, unsigned int a)
{
    if (m <= a) {
        if (m == a) {
            return 1;
        }

        return 0;
    }

    m += a;

    m >>= __builtin_ctz(m);

    return divisible_ui_p(m, a);
}

El ejemplo está limitado por impar ay m > 0. Sin embargo, se puede generalizar fácilmente a todos ay m. El código simplemente convierte la división en una serie de adiciones.

Ahora considere el programa de prueba compilado con -std=c99 -march=native -O3:

    for (unsigned int a = 1; a < 100000; a += 2) {
        for (unsigned int m = 1; m < 100000; m += 1) {
#if 1
            volatile int r = divisible_ui_p(m, a);
#else
            volatile int r = (m % a == 0);
#endif
        }
    }

... y los resultados en mi computadora:

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |    8.52user |
| builtin % operator |   17.61user |

Por lo tanto, más de 2 veces más rápido.

La pregunta: ¿Me puede decir cómo se comporta el código en su máquina? ¿Se pierde la oportunidad de optimización en GCC? ¿Puedes hacer esta prueba aún más rápido?


ACTUALIZACIÓN: según lo solicitado, aquí hay un ejemplo mínimo reproducible:

#include <assert.h>

static int divisible_ui_p(unsigned int m, unsigned int a)
{
    if (m <= a) {
        if (m == a) {
            return 1;
        }

        return 0;
    }

    m += a;

    m >>= __builtin_ctz(m);

    return divisible_ui_p(m, a);
}

int main()
{
    for (unsigned int a = 1; a < 100000; a += 2) {
        for (unsigned int m = 1; m < 100000; m += 1) {
            assert(divisible_ui_p(m, a) == (m % a == 0));
#if 1
            volatile int r = divisible_ui_p(m, a);
#else
            volatile int r = (m % a == 0);
#endif
        }
    }

    return 0;
}

compilado con gcc -std=c99 -march=native -O3 -DNDEBUGAMD Ryzen Threadripper 2990WX con

gcc --version
gcc (Gentoo 9.2.0-r2 p3) 9.2.0

ACTUALIZACIÓN2: según lo solicitado, la versión que puede manejar cualquiera ay m(si también desea evitar el desbordamiento de enteros, la prueba debe implementarse con un tipo de entero dos veces mayor que los enteros de entrada):

int divisible_ui_p(unsigned int m, unsigned int a)
{
#if 1
    /* handles even a */
    int alpha = __builtin_ctz(a);

    if (alpha) {
        if (__builtin_ctz(m) < alpha) {
            return 0;
        }

        a >>= alpha;
    }
#endif

    while (m > a) {
        m += a;
        m >>= __builtin_ctz(m);
    }

    if (m == a) {
        return 1;
    }

#if 1
    /* ensures that 0 is divisible by anything */
    if (m == 0) {
        return 1;
    }
#endif

    return 0;
}
DaBler
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
Samuel Liew
También me gustaría ver una prueba en la que realmente afirmes que esos dos rs que calculas son iguales entre sí.
Mike Nakis
@ MikeNakis Acabo de agregar eso.
DaBler
2
La mayoría de los usos de la vida real a % bson bmucho más pequeños que a. A través de la mayoría de las iteraciones en su caso de prueba, son de tamaño similar o bmás grande, y su versión puede ser más rápida en muchas CPU en esas situaciones.
Matt Timmermans

Respuestas:

11

Lo que estás haciendo se llama reducción de fuerza: reemplazar una operación costosa por una serie de operaciones baratas.

La instrucción mod en muchas CPU es lenta, porque históricamente no se probó en varios puntos de referencia comunes y, por lo tanto, los diseñadores optimizaron otras instrucciones. Este algoritmo funcionará peor si tiene que hacer muchas iteraciones, y %funcionará mejor en una CPU donde solo necesita dos ciclos de reloj.

Finalmente, tenga en cuenta que hay muchos atajos para tomar el resto de la división por constantes específicas. (Aunque los compiladores generalmente se encargarán de esto por usted).

Davislor
fuente
históricamente no se probó en varios puntos de referencia comunes , ¡también porque la división es inherentemente iterativa y difícil de hacer rápido! x86, al menos, permanece como parte de div/ idivque han recibido algo de amor en Intel Penryn, Broadwell y IceLake (divisores de hardware de radix más altos)
Peter Cordes
1
Entiendo que la "reducción de fuerza" es que reemplaza una operación pesada en un bucle con una sola operación más ligera, por ejemplo, en lugar de x = i * constcada iteración, realiza x += constcada iteración. No creo que reemplazar una sola multiplicación con un bucle shift / add se llame reducción de fuerza. en.wikipedia.org/wiki/… dice que el término puede usarse de esta manera, pero con una nota "Este material está en disputa. Se describe mejor como optimización de mirilla y asignación de instrucciones".
Peter Cordes
9

Contestaré mi pregunta yo mismo. Parece que me convertí en una víctima de la predicción de rama. El tamaño mutuo de los operandos no parece importar, solo su orden.

Considere la siguiente implementación

int divisible_ui_p(unsigned int m, unsigned int a)
{
    while (m > a) {
        m += a;
        m >>= __builtin_ctz(m);
    }

    if (m == a) {
        return 1;
    }

    return 0;
}

y las matrices

unsigned int A[100000/2];
unsigned int M[100000-1];

for (unsigned int a = 1; a < 100000; a += 2) {
    A[a/2] = a;
}
for (unsigned int m = 1; m < 100000; m += 1) {
    M[m-1] = m;
}

que se mezclan / no se mezclan utilizando la función de reproducción aleatoria .

Sin barajar, los resultados siguen siendo

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |    8.56user |
| builtin % operator |   17.59user |

Sin embargo, una vez que barajo estas matrices, los resultados son diferentes.

| implementation     | time [secs] |
|--------------------|-------------|
| divisible_ui_p     |   31.34user |
| builtin % operator |   17.53user |
DaBler
fuente