c++ - Truco de bits para detectar si alguno de algunos enteros tiene un valor específico

performance optimization

Question

¿Hay algún truco de bits inteligente para detectar si alguno de los pocos números enteros (por ejemplo, 3 o 4) tiene un valor específico?

El sencillo

bool test(int a, int b, int c, int d)
{
    // The compiler will pretty likely optimize it to (a == d | b == d | c == d)
    return (a == d || b == d || c == d);
}

en GCC compila a

test(int, int, int, int):
        cmp     ecx, esi
        sete    al
        cmp     ecx, edx
        sete    dl
        or      eax, edx
        cmp     edi, ecx
        sete    dl
        or      eax, edx
        ret

Esas instrucciones de sete tienen una latencia más alta de la que quiero tolerar, por lo que preferiría usar algo a modo de bit ( & , | , ^ , ~ ) y una única comparación.

Answer 1

La única solución que he encontrado hasta ahora es:

int s1 = ((a-d) >> 31) | ((d-a) >> 31);
int s2 = ((b-d) >> 31) | ((d-b) >> 31);
int s3 = ((c-d) >> 31) | ((d-c) >> 31);

int s = s1 & s2 & s3;
return (s & 1) == 0;

variante alternativa:

int s1 = (a-d) | (d-a);
int s2 = (b-d) | (d-b);
int s3 = (c-d) | (d-c);

int s = (s1 & s2 & s3);
return (s & 0x80000000) == 0;

ambos se traducen a:

mov     eax, ecx
sub     eax, edi
sub     edi, ecx
or      edi, eax
mov     eax, ecx
sub     eax, esi
sub     esi, ecx
or      esi, eax
and     esi, edi
mov     eax, edx
sub     eax, ecx
sub     ecx, edx
or      ecx, eax
test    esi, ecx
setns   al
ret

que tiene menos instrucciones de configuración, pero obviamente más mov / sub.

Actualización: como sugirió BeeOnRope @: tiene sentido convertir las variables de entrada a unsigned

Answer 2

No es un truco completo. Cualquier cero produce un producto cero, lo que da un resultado cero. Negar 0 produce un 1. No se ocupa del desbordamiento.

bool test(int a, int b, int c, int d)
{
    return !((a^d)*(b^d)*(c^d));
}

Salida gcc 7.1 -O3 . ( d está en ecx , las otras entradas comienzan en otros registros enteros).

    xor     edi, ecx
    xor     esi, ecx
    xor     edx, ecx
    imul    edi, esi
    imul    edx, edi
    test    edx, edx
    sete    al
    ret

Puede ser más rápido que el original en Core2 o Nehalem donde los bloqueos de registros parciales son un problema. imul r32,r32 tiene una latencia de 3c en Core2 / Nehalem (y posteriores CPU de Intel) y 1 por rendimiento de reloj, por lo que esta secuencia tiene una latencia de 7 ciclos desde las entradas hasta el segundo resultado, y otros 2 ciclos de latencia para test / sete . El rendimiento debe ser bastante bueno si esta secuencia se ejecuta en múltiples entradas independientes.

Usar una multiplicación de 64 bits evitaría el problema de desbordamiento en la primera multiplicación, pero la segunda podría desbordarse si el total es >= 2**64 . Seguiría siendo el mismo rendimiento en Intel Nehalem y Sandybridge-family, y AMD Ryzen. Pero sería más lento en las CPU más antiguas.

En x86 asm, al hacer la segunda multiplicación con una instrucción mul un solo operando y multiplicación completa (64x64b => 128b) se evitaría el desbordamiento, y se podría verificar que el resultado sea todo cero o no con or rax,rdx . Podemos escribir eso en GNU C para objetivos de 64 bits (donde __int128 está disponible)

bool test_mulwide(unsigned a, unsigned b, unsigned c, unsigned d)
{
    unsigned __int128 mul1 = (a^d)*(unsigned long long)(b^d);
    return !(mul1*(c^d));
}

y gcc / clang realmente emiten el asm que esperábamos (cada uno con algunas instrucciones de mov inútiles):

   # gcc -O3 for x86-64 SysV ABI
    mov     eax, esi
    xor     edi, ecx
    xor     eax, ecx
    xor     ecx, edx   # zero-extends
    imul    rax, rdi
    mul     rcx        # 64 bit inputs (rax implicit), 128b output in rdx:rax
    mov     rsi, rax   # this is useless
    or      rsi, rdx
    sete    al
    ret

Esto debería ser casi tan rápido como la versión simple que puede desbordarse, en el moderno x86-64. ( mul r64 sigue teniendo solo 3c de latencia, pero 2 uops en lugar de 1 para imul r64,r64 que no produce la mitad alta), en Intel Sandybridge-family.

Es probable que sea aún peor que el setcc / or salida de la versión original, que usa 8 bits or instrucciones para evitar leer registros de 32 bits después de escribir el byte bajo (es decir, no hay bloqueos de registros parciales).

Vea ambas fuentes con ambos compiladores en el explorador del compilador Godbolt . (También se incluye: la versión ^ / & @ BeeOnRope que corre el riesgo de falsos positivos , con y sin un retroceso a un control completo).