asm - compiler explorer

¿Por qué memcmp(a, b, 4) solo a veces está optimizado para una comparación uint32?

Question

Dado este código:

#include <string.h>

int equal4(const char* a, const char* b)
{
    return memcmp(a, b, 4) == 0;
}

int less4(const char* a, const char* b)
{
    return memcmp(a, b, 4) < 0;
}

GCC 7 en x86_64 introdujo una optimización para el primer caso (Clang lo ha hecho durante mucho tiempo):

    mov     eax, DWORD PTR [rsi]
    cmp     DWORD PTR [rdi], eax
    sete    al
    movzx   eax, al

Pero el segundo caso todavía llama a memcmp() :

    sub     rsp, 8
    mov     edx, 4
    call    memcmp
    add     rsp, 8
    shr     eax, 31

¿Se podría aplicar una optimización similar al segundo caso? ¿Cuál es el mejor ensamblaje para esto, y hay alguna razón clara por la que no se está haciendo (por GCC o Clang)?

Véalo en el Explorador de compiladores de Godbolt: https://godbolt.org/g/jv8fcf

Answer 1

Como se discutió en otras respuestas / comentarios, usar memcmp(a,b,4) < 0 es equivalente a una comparación unsigned entre enteros big-endian. No podría en línea tan eficientemente como == 0 en little-endian x86.

Más importante aún, la versión actual de este comportamiento en gcc7 / 8 solo busca memcmp() == 0 o != 0 . Incluso en un objetivo big-endian donde esto podría alinearse con la misma eficacia para < o > , gcc no lo hará. (Los compiladores big endian más nuevos de Godbolt son PowerPC 64 gcc6.3 y MIPS / MIPS64 gcc5.4. Mips es MIPS big endian, mientras que mipsel es MIPS little endian). Si prueba esto con gcc futuro, use a = __builtin_assume_align(a, 4) para asegurarse de que gcc no tenga que preocuparse por el rendimiento / corrección de carga no alineada en no x86. (O simplemente use const int32_t* lugar de const char* .)

Si / cuando gcc aprende a memcmp línea para casos que no sean EQ / NE, tal vez gcc lo haga en little endian x86 cuando sus heurísticas le indiquen que el tamaño de código adicional valdrá la pena. por ejemplo, en un bucle -fprofile-use cuando se compila con -fprofile-use (optimización guiada por perfil).

Si desea que los compiladores hagan un buen trabajo para este caso , probablemente debería asignar a uint32_t y usar una función de conversión ntohl como ntohl . Pero asegúrese de elegir uno que realmente pueda estar en línea; aparentemente Windows tiene un ntohl que se compila en una llamada DLL . Vea otras respuestas sobre esa pregunta para algunas cosas de endian portable, y también el intento imperfecto de alguien en un portable_endian.h , y esta bifurcación . Estuve trabajando en una versión por un tiempo, pero nunca la terminé / probé ni la publiqué.

La conversión del puntero puede ser Comportamiento indefinido, según cómo haya escrito los bytes y a qué apunta el char* . Si no está seguro sobre el alias estricto y / o la alineación, memcpy en abytes . La mayoría de los compiladores son buenos para optimizar la memcpy pequeña de tamaño memcpy .

// I know the question just wonders why gcc does what it does,
// not asking for how to write it differently.
// Beware of alignment performance or even fault issues outside of x86.

#include <endian.h>
#include <stdint.h>

int equal4_optim(const char* a, const char* b) {
    uint32_t abytes = *(const uint32_t*)a;
    uint32_t bbytes = *(const uint32_t*)b;

    return abytes == bbytes;
}


int less4_optim(const char* a, const char* b) {
    uint32_t a_native = be32toh(*(const uint32_t*)a);
    uint32_t b_native = be32toh(*(const uint32_t*)b);

    return a_native < b_native;
}

Revisé Godbolt , y eso se compila en un código eficiente (básicamente idéntico a lo que escribí en el Asm a continuación), especialmente en plataformas big-endian, incluso con el antiguo gcc. También hace un código mucho mejor que ICC17, que integra memcmp pero solo en un bucle de comparación de bytes (incluso para el caso == 0 .

Creo que esta secuencia hecha a mano es una implementación óptima de less4() (para la convención de llamadas x86-64 SystemV, como se usa en la pregunta, con const char *a en rdi y b en rsi ).

less4:
    mov   edi, [rdi]
    mov   esi, [rsi]
    bswap edi
    bswap esi
    # data loaded and byte-swapped to native unsigned integers
    xor   eax,eax    # solves the same problem as gcc''s movzx, see below
    cmp   edi, esi
    setb  al         # eax=1 if *a was Below(unsigned) *b, else 0
    ret

Esas son todas instrucciones de un solo paso en CPU Intel y AMD desde K8 y Core2 ( agner.org/optimize ).

Tener que bswap ambos operandos tiene un costo de tamaño de código adicional frente al caso == 0 : no podemos plegar una de las cargas en un operando de memoria para cmp . (Eso ahorra tamaño de código y uops gracias a la micro fusión.) Esta es la parte superior de las dos instrucciones adicionales de bswap .

En las CPU que admiten movbe , puede guardar el tamaño del código: movbe ecx, [rsi] es load + bswap. En Haswell, son 2 uops, por lo que presumiblemente decodifica a los mismos uops que mov ecx, [rsi] / bswap ecx . En Atom / Silvermont, se maneja directamente en los puertos de carga, por lo que tiene menos uops y un tamaño de código más pequeño.

Vea la parte de setcc de mi respuesta xor-zeroing para obtener más información sobre por qué xor / cmp / setcc (que utiliza clang) es mejor que cmp / setcc / movzx (típico para gcc).

En el caso habitual donde esto se alinea en el código que se bifurca en el resultado, el setcc + zero-extend se reemplaza con un jcc ; el compilador se optimiza creando un valor de retorno booleano en un registro. Esta es otra ventaja de la memcmp : la biblioteca memcmp tiene que crear un valor de retorno booleano entero que el llamante prueba , porque ninguna convención memcmp ABI / llamada permite devolver condiciones booleanas en banderas. (No conozco ninguna convención de llamadas que no sea x86 que haga eso tampoco). Para la mayoría de las implementaciones de memcmp biblioteca, también hay una sobrecarga significativa al elegir una estrategia dependiendo de la longitud, y tal vez la verificación de alineación. Eso puede ser bastante barato, pero para el tamaño 4 será más que el costo de todo el trabajo real.

Answer 2

Endianness es el problema aquí. Considere esta entrada:

a = 01 00 00 03
b = 02 00 00 02

Si compara estas dos matrices tratándolas como enteros de 32 bits, encontrará que a es más grande (porque 0x03000001> 0x02000002). En una máquina big endian, esta prueba probablemente funcionaría como se esperaba.

Answer 3

La resistencia es un problema, pero el carácter firmado es otro. Por ejemplo, considere que los cuatro bytes que compara son 0x207f2020 y 0x20802020. El 80 como personaje firmado es -128, el 7f como personaje firmado es +127. Pero si compara los cuatro bytes, ninguna comparación le dará el orden correcto.

Por supuesto, puede hacer un xor con 0x80808080 y luego puede usar una comparación sin firmar.

Answer 4

Si genera código para una plataforma little-endian, la optimización de memcmp cuatro bytes para la desigualdad en una sola comparación DWORD no es válida.

Cuando memcmp compara bytes individuales, pasa de bytes con direcciones bajas a bytes con direcciones altas, independientemente de la plataforma.

Para que memcmp devuelva cero, los cuatro bytes deben ser idénticos. Por lo tanto, el orden de comparación no importa. Por lo tanto, la optimización DWORD es válida porque ignora el signo del resultado.

Sin embargo, cuando memcmp devuelve un número positivo, el orden de bytes es importante. Por lo tanto, implementar la misma comparación usando la comparación DWORD de 32 bits requiere una capacidad específica: la plataforma debe ser big-endian, de lo contrario, el resultado de la comparación sería incorrecto.