¿Es mejor evitar el uso del operador mod cuando sea posible?

14 minutos de lectura

avatar de usuario
limp_chimpancé

Supongo que calcular el módulo de un número es una operación algo costosa, al menos en comparación con las pruebas aritméticas simples (como ver si un número excede la longitud de una matriz). Si este es el caso, ¿es más eficiente reemplazar, por ejemplo, el siguiente código:

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

¿con lo siguiente? :

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

El primero es más agradable a la vista, pero me pregunto si el segundo podría ser más eficiente. Si es así, ¿puedo esperar que un compilador de optimización reemplace el primer fragmento con el segundo cuando se usa un lenguaje compilado?

Por supuesto, esta “optimización” (si es que es una optimización) no funciona en todos los casos (en este caso, solo funciona si i+1 nunca es más que len).

  • Este podría ser un caso de extrañar el bosque por los árboles.

    – Burhan Jalid

    24 de marzo de 2013 a las 7:58

  • si len es una constante de tiempo de compilación un compilador GCC reciente (con -02) generalmente está haciendo cosas inteligentes, a menudo evitando la instrucción de máquina de módulo del procesador de destino.

    – Basile Starynkevitch

    24 de marzo de 2013 a las 7:59

  • Este es realmente el tipo de optimización que debe olvidar. El compilador de optimización lo hará mejor que tú. Lo que importa mucho más es la legibilidad de su código.

    – Basile Starynkevitch

    24 de marzo de 2013 a las 8:04


  • O puede hacer que la matriz 1 sea más larga y copiar el primer elemento en el nuevo último elemento para que pueda acceder a él normalmente. Cualquiera de estas tres opciones puede ser la más rápida, según las circunstancias.

    – harold

    24 de marzo de 2013 a las 12:08

  • Esto generalmente se usa en colas circulares.

    – Mohamed El Nakeep

    13 de diciembre de 2013 a las 19:29

avatar de usuario
NPE

Mi consejo general es el siguiente. Utilice la versión que crea que es más agradable a la vista y luego perfile todo su sistema. Solo optimice aquellas partes del código que el generador de perfiles marca como cuellos de botella. Apuesto mi último dólar a que el operador de módulo no estará entre ellos.

En lo que respecta al ejemplo específico, solo la evaluación comparativa puede decir cuál es más rápido en su arquitectura específica utilizando su compilador específico. Estás reemplazando potencialmente módulo con derivacióny es cualquier cosa menos obvio cuál sería más rápido.

  • En las máquinas recientes, la aritmética de enteros es casi gratuita; lo que importa mucho más son los errores de caché… que son mucho más costosos. una falta de caché L1 detiene el procesador durante cientos de ciclos, durante los cuales el procesador podría hacer docenas de divisiones o módulos; por lo que el costo final del módulo es el ruido

    – Basile Starynkevitch

    24 de marzo de 2013 a las 8:00


  • @BasileStarynkevitch: Bueno, el comportamiento de la memoria caché será idéntico entre los dos fragmentos de código. Lo que va a importar es si la versión n.° 2 usa o no la bifurcación y, si lo hace, qué tan bueno será el trabajo que hará el predictor de bifurcación.

    – ENP

    24 de marzo de 2013 a las 8:02

  • @Basile Starynkevitch He visto un factor de aproximadamente 300 entre el módulo y el acceso a una mesa grande en una computadora portátil. (Agregar una prueba de divisibilidad por 17 al cuadrado para evitar el acceso a la matriz aún fue beneficioso).

    – estrella azul

    24 de marzo de 2013 a las 9:44

  • @NPE Podría valer la pena agregar a esta respuesta que el lenguaje C en sí mismo no tiene velocidad; Esa es una cualidad de la implementación (por ejemplo, “su arquitectura específica”). Además de depender del hardware, “la velocidad del operador módulo” depende de la calidad del código de construcción del compilador para el hardware; Uno pobre podría usar el equivalente de ensamblaje de int foo = 54321; int bar = foo / 10000; foo -= bar * 10000; para obtener el módulo, mientras que un compilador de buena calidad podría incluso optimizar ese código.

    – autista

    24 de marzo de 2013 a las 10:49

Algunas medidas simples:

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

Compilando con gcc o clang con -O3y corriendo time ./a.out 0 42 1000000000 (versión módulo) o time ./a.out 1 42 1000000000 (versión de comparación) da como resultado

  • 6,25 segundos tiempo de ejecución del usuario para la versión módulo,
  • 1,03 segundos para la versión de comparación.

(con gcc 5.2.1 o clang 3.6.2; Intel Core i5-4690K a 3,50 GHz; Linux de 64 bits)

Esto significa que probablemente sea una buena idea usar la versión de comparación.

  • En datos más realistas (por ejemplo, si el número fuera aleatorio), la diferencia no sería tan grande

    – usuario1209304

    24 de octubre de 2016 a las 12:23

  • La versión de comparación solo es más rápida porque el resultado de la declaración if es el mismo cada vez, por lo que el predictor de bifurcación siempre lo hace bien. Si aleatorizaste la entrada, la versión de comparación podría incluso ser peor que mod

    – Gran mínimo

    26 de junio de 2017 a las 10:39

  • @Bigminimus Hmm, pero ¿el resultado de la cláusula if es el mismo para ambas pruebas todo el tiempo?

    – Baris Demiray

    9 de agosto de 2017 a las 12:54

  • Él está haciendo referencia al (?) Operador, su código, dependiendo del tamaño del divisor, solo está adivinando mal 1 de 100, 400, etc.

    – Pandilla de la buhardilla

    10 sep 2019 a las 21:31


avatar de usuario
michel billaud

Bueno, eche un vistazo a 2 formas de obtener el siguiente valor de un contador cíclico “módulo 3”.

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

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

Lo he compilado con la opción gcc -O3 (para la arquitectura x64 común) y -s para obtener el código ensamblador.

El código de la primera función hace una magia inexplicable

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

para evitar una división, usando una multiplicación de todos modos:

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

Y es mucho más larga (y apuesto más lenta) que la segunda función:

Por lo tanto, no siempre es cierto que “el compilador (moderno) hace un mejor trabajo que usted de todos modos”.

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

Curiosamente, el mismo experimento con 4 en lugar de 3 conduce a un enmascaramiento y para la primera función

pero sigue siendo, y en general, inferior a la segunda versión.

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

Ser más explícito sobre las formas correctas de hacer las cosas.

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

da resultados mucho mejores:

  • bueno, no es tan complicado. Multiplicación por recíproco. Calcule la constante entera K = (2^N)/3, para un valor lo suficientemente grande de N. Ahora, cuando desee el valor de X/3, en lugar de una división por 3, calcule X*K y desplácelo N posiciones a la derecha.

    La comparación en la segunda versión podría hacerla inferior a la primera versión; si no predice regularmente la rama correcta, eso arruinará la tubería. Aún así, +1 por demostrar que los compiladores modernos no siempre encuentran mágicamente el mejor código de máquina posible.


  • – rayo 24/09/2018 a las 16:59

    @Ray, según tengo entendido, se ha agregado un movimiento condicional al conjunto de instrucciones (Pentium Pro), por lo que no se realiza ninguna predicción de bifurcación “Las instrucciones CMOVcc son útiles para optimizar pequeñas construcciones IF. También ayudan a eliminar la sobrecarga de bifurcación para las declaraciones IF y la posibilidad de predicciones erróneas de bifurcación por parte del procesador “. Manual de desarrolladores de la familia Pentium-Pro, vol 2, p 6.14.

    phatcode.net/res/231/files/24269101.pdf

  • –Michel Billaud

    25 de septiembre de 2018 a las 10:08

    Michel Billaud: Parece que tienes razón. Vi el cmpl y pasé por alto por completo la falta de un salto.


  • – rayo % 4 25/09/2018 a las 15:20 los el código es más complejo porque estás haciendo unsigned intfirmado & 3 aritmética. De acuerdo con C99, el signo del módulo debe coincidir con el signo del dividendo, por lo que no es solo un AND directo bit a bit. Cambia el tipo a

    y obtendrá el mismo resultado que el

    código.

  • – palmadita

    22 de febrero de 2020 a las 3:00

    -1 porque la respuesta sugiere enfáticamente juzgar por el tamaño del código, que es una buena heurística pero un error cuando se trata de optimizaciones como la de esta pregunta. No todas las instrucciones son iguales. Incluso en una arquitectura RISC, algunas operaciones pueden llevar más tiempo que otras, y en una CPU segmentada, el tiempo empleado en ejecutar una bifurcación mal prevista (que es más larga que la propia bifurcación, pero continúa después de la bifurcación hasta que el resultado de la condición de bifurcación se encuentra más profundo en la canalización) podría ser más largo que el tiempo empleado por el código incondicional con más instrucciones.


– mtraceur

#include <iostream>
#include <array>
#include <algorithm>
#include <random>
#include <chrono>
using namespace std::chrono;

constexpr size_t iter = 1e8;

int main() {
  std::minstd_rand rnd_engine{1234};
  std::uniform_int_distribution<int> dist {-1000, 1000};
  auto gen = [&]() { return dist(rnd_engine); };

  std::array<int, 10> a;
  std::generate( a.begin(), a.end(), gen);

  for (size_t size = 2; size < 10; size++) {
    std::cout << "Modulus size = " << size << '\n';
  
    {
      std::cout << "operator%  ";
      long sum = 0;
      size_t x = 0;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x];
        x = (x + 1) % size;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }
  
    {
      std::cout << "ternary    ";
      long sum = 0;
      size_t x = 0;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x];
        x = ((x + 1) == size) ? 0 : x + 1;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }
    
    {
      std::cout << "branchless ";
      long sum = 0;
      size_t x = 1;
      auto start = high_resolution_clock::now();
      for (size_t i = 0; i < iter; ++i) {
        sum += a[x-1];
        x = ( x != size ) * x + 1;
      }
      auto stop = high_resolution_clock::now();
      std::cout << duration_cast<microseconds>(stop - start).count()*0.001
                << "ms\t(sum = " << sum << ")\n";
    }

  }
  return 0;
}

1 de octubre de 2020 a las 1:08

$ g++ -Ofast test.cpp && ./a.out
Modulus size = 2
operator%  904.249ms    (sum = -4200000000)
ternary    137.04ms     (sum = -4200000000)
branchless 169.182ms    (sum = -4200000000)
Modulus size = 3
operator%  914.911ms    (sum = -31533333963)
ternary    113.384ms    (sum = -31533333963)
branchless 167.614ms    (sum = -31533333963)
Modulus size = 4
operator%  877.3ms      (sum = -36250000000)
ternary    97.265ms     (sum = -36250000000)
branchless 167.215ms    (sum = -36250000000)
Modulus size = 5
operator%  891.295ms    (sum = -30700000000)
ternary    88.562ms     (sum = -30700000000)
branchless 167.087ms    (sum = -30700000000)
Modulus size = 6
operator%  903.644ms    (sum = -39683333196)
ternary    83.433ms     (sum = -39683333196)
branchless 167.778ms    (sum = -39683333196)
Modulus size = 7
operator%  908.096ms    (sum = -34585713678)
ternary    79.703ms     (sum = -34585713678)
branchless 166.849ms    (sum = -34585713678)
Modulus size = 8
operator%  869ms        (sum = -39212500000)
ternary    76.972ms     (sum = -39212500000)
branchless 167.29ms     (sum = -39212500000)
Modulus size = 9
operator%  875.003ms    (sum = -36500000580)
ternary    75.011ms     (sum = -36500000580)
branchless 172.356ms    (sum = -36500000580)

Aquí hay algunos puntos de referencia adicionales. Tenga en cuenta que también agregué una versión sin sucursales: operator% Y aquí está la salida en mi i7-4870HQ

En este caso particular, el operador ternario parece muy superior, y se parece aún más cuando el predictor de bifurcación aumenta. Sin embargo, tenga en cuenta que este es un caso muy particular: si no estuviéramos incrementando el índice por un valor no constante, usando el más general

sería sencillo, mientras que los otros dos métodos podrían volverse muy complicados.
Me gustaría enfatizar este comentario muy subestimado:
si len es una constante de tiempo de compilación, un compilador GCC reciente (con -02) es generalmente haciendo cosas inteligentes, a menudo evitando la máquina de módulo

instrucción del procesador de destino. size – Basile Starynkevitch const size_t size = 4; Por ejemplo, quitando el bucle en el

g++ -Ofast test.cpp && ./a.out
Modulus size = 4
operator%  62.103ms     (sum = -36250000000)
ternary    93.674ms     (sum = -36250000000)
branchless 166.774ms    (sum = -36250000000)

variable y declararla como

Yo obtengo: operator%Conclusiones

El tiempo de ejecución de la versión sin sucursales es bastante estable en los distintos escenarios. El ternario es consistentemente mejor que el sin ramas en los casos considerados, especialmente cuando el predictor de ramas se activa. Finalmente, el

si bien es más general y significativamente más lento, tiene posibilidades de optimizarse para convertirse en el más rápido, como en el caso de valores constantes particulares del lado derecho.

Por supuesto, esto depende completamente de la plataforma, quién sabe cómo será esto en un Arduino 🙂

Si ‘len’ en su código es lo suficientemente grande, entonces el condicional será más rápido, ya que los predictores de bifurcación casi siempre adivinarán correctamente.

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

De lo contrario, creo que esto está estrechamente relacionado con las colas circulares, donde a menudo ocurre que la longitud es una potencia de 2. Esto permitirá que el compilador sustituya el módulo con un AND simple.

  • El código es el siguiente:
  • tamaño = 15:

módulo: 4.868 s

  • cond: 1,291s
  • tamaño = 16:

módulo: 1.067 s

  • cond: 1,599s

    Compilado en gcc 7.3.0, con optimización -O3. La máquina es un i7 920.

    Me pregunto por qué el tiempo de la versión final no es el mismo en ambos casos.

  • –Doug Currie

    17 de abril de 2019 a las 14:35

    Creo que, debido a que res no es volátil, gcc puede hacer muchas optimizaciones que son menos efectivas a medida que aumenta el tamaño. Cuando agrego ‘volátil’ a res, los tiempos para el condicional siempre son alrededor de 2 segundos. Para módulo alrededor de 2 segundos cuando la potencia es de 2 y no es estable (por encima de 4 segundos, aumentando con el tamaño) de lo contrario.

  • – J. Doe

    17 de abril de 2019 a las 15:05

    También noté que en el caso de la resolución no volátil, para el tamaño 1024, el condicional se ejecuta más rápido, en 1 segundo, así que supongo que se trata de tamaños “buenos” y “malos” para las optimizaciones (¿o predictores de rama?).


– J. Doe
17 de abril de 2019 a las 15:14

avatar de usuario

  • steviekm3

    Leí un artículo sobre cómo hacer un mapa hash rápido. Un cuello de botella puede ser el operador de módulo para encontrar el depósito de hash. Sugirieron hacer que su número de cubos sea una potencia de 2. Aparentemente, hacer el módulo por potencia de dos significa como mirar los últimos n bits.

    Me pregunto por qué el tiempo de la versión final no es el mismo en ambos casos.

  • –Doug Currie

    17 de abril de 2019 a las 14:35

    Creo que, debido a que res no es volátil, gcc puede hacer muchas optimizaciones que son menos efectivas a medida que aumenta el tamaño. Cuando agrego ‘volátil’ a res, los tiempos para el condicional siempre son alrededor de 2 segundos. Para módulo alrededor de 2 segundos cuando la potencia es de 2 y no es estable (por encima de 4 segundos, aumentando con el tamaño) de lo contrario.

  • – J. Doe

    17 de abril de 2019 a las 15:05

    También noté que en el caso de la resolución no volátil, para el tamaño 1024, el condicional se ejecuta más rápido, en 1 segundo, así que supongo que se trata de tamaños “buenos” y “malos” para las optimizaciones (¿o predictores de rama?).


– J. Doe
17 de abril de 2019 a las 15:14

avatar de usuario

  (i + 1) % len

Yilmaz

if ((i+1)==len){
   return 0
} else {
   return i+1
}

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad