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)dentroif (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