c++ - Truco de bits para detectar si alguno de algunos enteros tiene un valor específico
performance optimization (2)
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
¿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);
}
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.
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).