Función de comparación de enteros eficiente

5 minutos de lectura

avatar de usuario
fredodesbordamiento

los compare función es una función que toma dos argumentos a y b y devuelve un número entero que describe su orden. Si a es más pequeño que b, el resultado es un entero negativo. Si a es mayor que b, el resultado es un entero positivo. De lo contrario, a y b son iguales y el resultado es cero.

Esta función se usa a menudo para parametrizar algoritmos de clasificación y búsqueda de bibliotecas estándar.

Implementando el compare la función para personajes es bastante fácil; simplemente restas los argumentos:

int compare_char(char a, char b)
{
    return a - b;
}

Esto funciona porque generalmente se supone que la diferencia entre dos caracteres se ajusta a un número entero. (Tenga en cuenta que esta suposición no es válida para los sistemas en los que sizeof(char) == sizeof(int).)

Este truco no puede funcionar para comparar números enteros, porque la diferencia entre dos números enteros generalmente no cabe en un número entero. Por ejemplo, INT_MAX - (-1) = INT_MIN sugiere que INT_MAX es más pequeño que -1 (técnicamente, el desbordamiento conduce a un comportamiento indefinido, pero supongamos aritmética de módulo).

Entonces, ¿cómo podemos implementar la función de comparación de manera eficiente para números enteros? Aqui esta mi primer intento:

int compare_int(int a, int b)
{
    int temp;
    int result;
    __asm__ __volatile__ (
        "cmp %3, %2 \n\t"
        "mov $0, %1 \n\t"

        "mov $1, %0 \n\t"
        "cmovg %0, %1 \n\t"

        "mov $-1, %0 \n\t"
        "cmovl %0, %1 \n\t"
    : "=r"(temp), "=r"(result)
    : "r"(a), "r"(b)
    : "cc");
    return result;
}

¿Se puede hacer en menos de 6 instrucciones? ¿Hay una forma menos directa que sea más eficiente?

  • ¿Has desmontado return (a<b)?-1:(a>b);?

    – jxh

    12 de junio de 2012 a las 12:16

  • @ user315052 ¡Solo cinco instrucciones, genial! Ahora me siento estúpido 🙂

    – fredo desbordamiento

    12 de junio de 2012 a las 12:19

  • Es casi seguro que se trata de una optimización sin sentido. Cualquier ahorro aquí es ruido en comparación con la sobrecarga de la llamada de función y los costos algorítmicos en la persona que llama.

    –Raymond Chen

    12 de junio de 2012 a las 13:49

  • @KonradRudolph Si esto está en línea, en realidad es peor porque el compilador no puede optimizar el ensamblaje en línea. Es mejor expresarlo en C para que el optimizador pueda optimizar en la función en línea. Por ejemplo, su ensamblaje en línea evita que el compilador optimice if (compare_int(a,b) < 0) dentro if (a < b).

    –Raymond Chen

    12 de junio de 2012 a las 16:10


  • Raymond Chen acaba de publicar un artículo interesante sobre la evaluación comparativa de esto y lo que los optimizadores pueden hacer con las comparaciones de enteros.

    – isanae

    17 de noviembre de 2017 a las 19:49

  • ¿Puede modificar el punto de referencia para generar el espectro completo de enteros? ¿Qué pasa si reemplazas rand() con rand() | rand() << 17?

    – fredo desbordamiento

    12 de junio de 2012 a las 18:45

  • @AmbrozBizjak: ¿Verificó que su compilador generó las mismas 5 instrucciones que se publicaron en mi respuesta? Tengo curiosidad.

    – jxh

    26 de abril de 2014 a las 2:25

  • @jxh En mi sistema actual, obtengo: compare2 0m0.488s, compare3 0m0.502s. El ensamblaje no es el mismo que el publicado pero similar: ideone.com/uhmIYt y ideone.com/cD9Zd2. El problema con estos puntos de referencia es que los resultados también dependen de cómo el compilador logra insertar el código en el bucle. Puede ser mejor si lo obligamos a no alinear la función de comparación.

    – Ambroz Bizjak

    27 de abril de 2014 a las 7:53


  • Tenga en cuenta que en gcc 7.x (pero no en 6.x ni en 8.x), compare3(...) { a < b ? -1 : (a > b); } usa una rama, por lo que podría llevarse una desagradable sorpresa si su comparación es impredecible.

    – BeeOnRope

    20 de enero de 2019 a las 18:13

  • +1; un beneficio adicional es que no depende de la asm palabra clave que, como estoy seguro de que sabe, no funcionará en todas las plataformas.

    – John Dibling

    12 de junio de 2012 a las 12:54

  • Esto funcionará solo en las familias i686 y posteriores de CPU x86, por ejemplo, las que tienen la instrucción CMOV disponible. Prácticamente, es cualquier CPU que se hizo después del Pentium Pro (excepto Pentium MMX), por lo que debería estar bien a menos que uno de sus usuarios tenga una máquina de más de 10 años.

    –Daniel Kamil Kozar

    12 de junio de 2012 a las 13:57


  • @Daniel: si solo usa la versión C, entonces debería obtener un código bastante óptimo independientemente (asumiendo un compilador medio decente)

    – Pablo R.

    12 de junio de 2012 a las 17:52

  • Por supuesto, tienes razón. Solo estaba señalando los hechos que provienen de este código en particular.

    –Daniel Kamil Kozar

    12 de junio de 2012 a las 20:52


  • @FredOverflow: ¿El cmovge realmente resultar en un estancamiento de la tubería? No parece haber un salto condicional en el resultado del ensamblaje que muestra. ¿Qué versión del compilador usaste?

    – jxh

    25/04/2014 a las 23:41

  • Aunque son 4 instrucciones, aún puede encontrar que una secuencia sin ramas de 5 o 6 instrucciones es más rápida.

    – Pablo R.

    12 de junio de 2012 a las 17:53

  • @mfontanini Espero que mi solución sea la más lenta con diferencia para entradas aleatorias. Si el desbordamiento rara vez ocurre, por otro lado, esperaría que funcione muy bien (predicción de ramificación). De todos modos, me resultó difícil encontrar una solución aún más corta 🙂

    – fredo desbordamiento

    12 de junio de 2012 a las 18:20

  • Verá que el acarreo invertido de hecho es igual al signo correcto en el desbordamiento con signo si escribe la tabla de verdad para un restador completo de un bit. En el proceso, tenga en cuenta que para el signo correcto y los cálculos de desbordamiento con signo minuend bit=1 y subtrahend bit=1 debe ser tratado como -1 aritméticamente y la suma no se desborda IFF es 0 o -1. Entonces, tu conjetura es correcta.

    – Alexei Frunze

    14 de junio de 2012 a las 9:26


  • Su paso alternativo 3 no funciona para compare_int(0, -2147483648).

    – fredo desbordamiento

    12 de junio de 2012 a las 14:49

  • De acuerdo, fue una mala optimización.

    – anatolyg

    12 de junio de 2012 a las 15:03

  • Su paso alternativo 3 no funciona para compare_int(0, -2147483648).

    – fredo desbordamiento

    12 de junio de 2012 a las 14:49

  • De acuerdo, fue una mala optimización.

    – anatolyg

    12 de junio de 2012 a las 15:03

¿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