En C, ¿existe una técnica sin ramas para calcular la diferencia absoluta entre dos enteros sin signo? Por ejemplo, dadas las variables a y b, me gustaría el valor 2 para los casos cuando a = 3, b = 5 o b = 3, a = 5. Idealmente, también me gustaría poder vectorizar el cálculo utilizando los registros SSE.Calcule la diferencia absoluta entre enteros sin signo utilizando SSE
max(i,j) - min(i,j)
(i>j)*(i-j) + (j>i)*(j-i)
que sin duda puede utilizar SSE registra, pero el compilador puede hacer esto para usted de todos modos
Hay varias maneras de hacerlo, sólo voy a mencionar una:
SSE4
PMINUD y PMAXUD para separar el valor más grande en el registro n. ° 1, y el valor más pequeño en el registro n. ° 2.MMX/SSE2
PCMPGTD. Usa este resultado como una máscara.(a-b) y (b-a)POR (PAND (mask, a-b), PANDN (mask, b-a)) para seleccionar el valor correcto para la diferencia absoluta.Prueba esto (2ª asume complementos, lo cual está bien judgning por el hecho de que usted está pidiendo SSE):
int d = a-b;
int ad = ((d >> 30) | 1) * d;
Explicación: firmar bits (bit 31) obtiene propagado a primera poco. el | 1 parte asegura que el multiplicador es 1 o -1. Las multiplicaciones son rápidas en las CPU modernas.
calcular la diferencia y regresar el valor absoluto
__m128i diff = _mm_sub_epi32(a, b);
__m128i mask = _mm_xor_si128(diff, a);
mask = _mm_xor_si128(mask, b);
mask = _mm_srai_epi32(mask, 31);
diff = _mm_xor_si128(diff, mask);
mask = _mm_srli_epi32(mask, 31);
diff = _mm_add_epi32(diff, mask);
Esto requiere una operación menor que el uso de la firma comparar op, y produce menos presión en el registro.
La misma cantidad de presión de registro que antes, 2 operaciones más, mejor bifurcación y combinación de cadenas de dependencia, emparejamiento de instrucciones para la decodificación uops y utilización de unidades por separado. Aunque esto requiere una carga, que puede estar fuera de la memoria caché. Me he quedado sin ideas después de este.
__m128i mask, diff;
diff = _mm_set1_epi32(-1<<31); // dependency branch after
a = _mm_add_epi32(a, diff); // arithmetic sign flip
b = _mm_xor_si128(b, diff); // bitwise sign flip parallel with 'add' unit
diff = _mm_xor_si128(a, b); // reduce uops, instruction already decoded
mask = _mm_cmpgt_epi32(b, a); // parallel with xor
mask = _mm_and_si128(mask, diff); // dependency merge, branch after
a = _mm_xor_si128(a, mask); // if 2 'bit' units in CPU, parallel with next
b = _mm_xor_si128(b, mask); // reduce uops, instruction already decoded
diff = _mm_sub_epi32(a, b); // result
Después de temporización de cada versión con 2 millones de iteraciones en un Core2Duo, las diferencias son inconmensurables. Así que elige lo que sea más fácil de entender.
¿Se supone que 'sum' es' diff'? Bah, ahora que leí el tuyo atentamente, es bastante similar al mío. Pero es más inteligente y agradable al usar la diferencia firmada como una comparación firmada. Sin embargo, la comparación con cero generalmente es más ligera que la de desplazamiento a la derecha. – Potatoswatter
En realidad, ambos cometimos un error: en la primera función, se necesita una función de consenso de tres entradas, no XOR de tres vías. – Potatoswatter
SSE2:
parece ser aproximadamente la misma velocidad que la segunda función de Phernost. A veces, GCC programa que sea un ciclo completo más rápido, otras veces un poco más lento.
__m128i big = _mm_set_epi32(INT_MIN, INT_MIN, INT_MIN, INT_MIN);
a = _mm_add_epi32(a, big); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32(b, big); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32(a, b); // get signed difference
__m128i mask = _mm_cmpgt_epi32(b, a); // mask: need to negate difference?
mask = _mm_andnot_si128(big, mask); // mask = 0x7ffff... if negating
diff = _mm_xor_si128(diff, mask); // 1's complement except MSB
diff = _mm_sub_epi32(diff, mask); // add 1 and restore MSB
SSSE3:
muy ligeramente más rápido que el anterior. Hay mucha variación dependiendo de cómo se declaran las cosas fuera del ciclo. (Por ejemplo, hacer a y bvolatile hace las cosas más rápidas! Parece ser un efecto aleatorio en la programación.) Pero esto es consistentemente más rápido en un ciclo más o menos.
__m128i big = _mm_set_epi32(INT_MIN, INT_MIN, INT_MIN, INT_MIN);
a = _mm_add_epi32(a, big); // re-center the variables: send 0 to INT_MIN,
b = _mm_add_epi32(b, big); // INT_MAX to -1, etc.
__m128i diff = _mm_sub_epi32(b, a); // get reverse signed difference
__m128i mask = _mm_cmpgt_epi32(b, a); // mask: need to negate difference?
mask = _mm_xor_si128(mask, big); // mask cannot be 0 for PSIGND insn
diff = _mm_sign_epi32(diff, mask); // negate diff if needed
SSE4 (rwong THX):
No se puede probar esto.
__m128i diff = _mm_sub_epi32(_mm_max_epu32(a, b), _mm_min_epu32(a, b));
Eh ... es bastante fácil ...
int diff = abs(a - b);
fácilmente vectorisable (Utilizando como SSE3):
__m128i sseDiff = _mm_abs_epi32(_mm_sub_epi32(a, b));
a y b son enteros sin signo. Considere a = 0 y b = 0xffffffff. La diferencia absoluta correcta es 0xffffffff, pero su solución dará 1.
Como se explicó la edición extraña, esto está mal. Otro ejemplo para enteros sin signo de 8 bits: para '4 - 255', la diferencia absoluta correcta es 251.Pero tratarlo como firmado -5 y tomar el valor absoluto te da 5, que es la misma respuesta que obtienes para 255 - 250. El sub –
A partir del tommesani.com, una solución para este problema es utilizar resta cero sin signo dos veces.
Como la sustracción de saturación nunca pasa por debajo de 0, a calcular: r1 = (ab) .saturating r2 = (ba) .saturating
Si a es mayor que b, R1 contendrá la respuesta, y r2 será 0 y viceversa para b> a. ORing los dos resultados parciales juntos producirán el resultado deseado.
De acuerdo con the VTUNE users manual, PSUBUSB/PSUBUSW está disponible para registros de 128 bits, por lo que debería poder obtener una tonelada de paralelización de esta manera.
con saturación sin firmar parece estar solo disponible para palabras o bytes, pero afortunadamente eso es lo que estaba buscando para. Esta respuesta es ligeramente mejor que la respuesta más votada usando SSE4.1 PMINU/PMAXU/PSUB, porque 'POR' se puede ejecutar en más puertos que' PSUB' en algunas CPU (Intel Haswell, por ejemplo). –
Uno o más de los siguientes probablemente dará como resultado un código sin sucursales, dependiendo de la máquina y el compilador, ya que las expresiones condicionales son todas muy simples.
No he pasado por todas las respuestas sse pero posiblemente algunas de las siguientes están representadas en el código vectorial; Ciertamente, todos los siguientes son vectorizables (si tiene la comparación sin signo para comenzar, o fingir al alternar primero el msb). Pensé que sería útil tener algunas respuestas escalares prácticas a la pregunta.
unsigned udiff(unsigned a, unsigned b)
{
unsigned result = a-b; // ok if a<b;
if(a <b) result = -result;
return result;
}
unsigned udiff(unsigned a, unsigned b)
{
unsigned n =(a<b)? (unsigned)-1 : 0u;
unsigned result = a-b;
return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}
unsigned udiff(unsigned a, unsigned b)
{
unsigned axb = a^b;
if(a < b) axb = 0;
return (axb^b) - (axb^a); // a-b, or b-a
}
Esto funcionará en x86_64 (o cualquier cosa donde las temperaturas de 64 bits son básicamente libres)
unsigned udiff(unsigned a, unsigned b)
{
unsigned n= (unsigned)(
(long long)((unsigned long long)a - (unsigned long long)b)>>32
); // same n as 2nd example
unsigned result = a-b;
return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF
}
Pero el bit de signo de un-b no es una indicación de que a
greggo