Noté algo curioso en mi computadora. * La prueba de divisibilidad escrita a mano es significativamente más rápida que el 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 a impar y m > 0 . Sin embargo, se puede generalizar fácilmente a todo a y m . El código simplemente convierte la división en una serie de sumas.
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: ¿Puede decirme cómo se comporta el código en su máquina? ¿Es una oportunidad de optimización perdida en GCC? ¿Puedes hacer esta prueba aún más rápido?
ACTUALIZACIÓN: según lo solicitado, aquí hay un ejemplo reproducible mínimo:
#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 -DNDEBUG en AMD Ryzen Threadripper 2990WX con
gcc --version gcc (Gentoo 9.2.0-r2 p3) 9.2.0 ACTUALIZACIÓN 2: según lo solicitado, la versión que puede manejar cualquier a y m (si también desea evitar el desbordamiento de enteros, la prueba debe implementarse con el tipo de entero dos veces más largo 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; }Lo que estás haciendo se llama reducción de fuerza: reemplazar una operación costosa con una serie de operaciones baratas.
La instrucción de 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 en su lugar. 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).
Responderé mi pregunta yo mismo. Parece que me convertí en una víctima de la predicción de ramas. 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 barajan o no se barajan con la función de barajar .
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 |