poner - set border java

¿Cómo puedo hacer código sin sucursales?

Question

Relacionado con esta respuesta: https://stackoverflow.com/a/11227902/4714970

En la respuesta anterior, se menciona cómo evitar fallas en la predicción de sucursales al evitar las sucursales.

El usuario demuestra esto reemplazando:

if (data[c] >= 128)
{
sum += data[c];
}

Con:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

¿Cómo son estos dos equivalentes (para el conjunto de datos específicos, no estrictamente equivalentes)?

¿Cuáles son algunas maneras generales en que puedo hacer cosas similares en situaciones similares? ¿Sería siempre usando >> y ~ ?

Answer 1

Código sin ramificación significa que típicamente se evalúan todos los resultados posibles de una declaración condicional con un peso del conjunto [0, 1], de modo que la Suma {peso_i} = 1. La mayoría de los cálculos se descartan esencialmente. Se puede obtener una optimización del hecho de que E_i no tiene que ser correcta cuando el peso correspondiente w_i (o la máscara m_i ) sea cero.

 result = (w_0 * E_0) + (w_1 * E_1) + ... + (w_n * E_n) ;; or
result = (m_0 & E_0) | (m_1 & E_1) | ... | (m_n * E_n)

donde m_i representa una máscara de bits.

La velocidad también se puede lograr a través del procesamiento paralelo de E_i con un colapso horizontal.

Esto es contradictorio con la semántica de if (a) b; else c; if (a) b; else c; o es a ? b : c taquigrafía ternaria a ? b : c a ? b : c , donde solo se evalúa una expresión de [b, c].

Por lo tanto, la operación ternaria no es una solución mágica para el código sin sucursales. Un compilador decente produce código sin sucursales por igual para

t = data[n];
if (t >= 128) sum+=t;

contra

 movl -4(%rdi,%rdx), %ecx
leal (%rax,%rcx), %esi
addl $-128, %ecx
cmovge %esi, %eax

Las variaciones del código sin sucursales incluyen presentar el problema a través de otras funciones no lineales sin sucursales, como el ABS, si está presente en la máquina de destino.

p.ej

 2 * min(a,b) = a + b - ABS(a - b),
2 * max(a,b) = a + b + ABS(a - b)

o incluso:

 ABS(x) = sqrt(x*x) ;; caveat -- this is "probably" not efficient

Además de << y ~ , puede ser igualmente beneficioso usar bool y !bool lugar de (posiblemente no definido) (int >> 31). Del mismo modo, si la condición se evalúa como [0, 1], se puede generar una máscara de trabajo con negación:

-[0, 1] = [0, 0xffffffff] in 2''s complement representation

Answer 2

Si bien la respuesta de Louis Wasserman es correcta, quiero mostrarle una forma más general (y mucho más clara) de escribir código sin sucursales. Usted puede simplemente usar ? : ? : operador:

 int t = data[c];
sum += (t >= 128 ? t : 0);

El compilador JIT ve en el perfil de ejecución que la condición se predice mal aquí. En tales casos, el compilador es lo suficientemente inteligente como para reemplazar una rama condicional con una instrucción de movimiento condicional:

 mov 0x10(%r14,%rbp,4),%r9d ; load R9d from array
cmp $0x80,%r9d ; compare with 128
cmovl %r8d,%r9d ; if less, move R8d (which is 0) to R9d

Puede verificar que esta versión funciona igual de rápido para la matriz ordenada y no ordenada.

Answer 3

int t = (data[c] - 128) >> 31;

El truco aquí es que si los data[c] >= 128 , entonces los data[c] - 128 no son negativos, de lo contrario son negativos. El bit más alto en un int , el bit de signo, es 1 si y solo si ese número es negativo. >> es un desplazamiento que extiende el bit de signo, por lo que si se desplaza hacia la derecha en 31, el resultado completo es 0 si solía ser no negativo, y todos los 1 bits (lo que representa -1) si solía ser negativo. Entonces t es 0 si los data[c] >= 128 , y -1 caso contrario. ~t cambia estas posibilidades, por lo que ~t es -1 si los data[c] >= 128 , y 0 caso contrario.

x & (-1) siempre es igual a x , y x & 0 siempre es igual a 0 . Entonces sum += ~t & data[c] incrementa la sum en 0 si data[c] < 128 , y por data[c] caso contrario.

Muchos de estos trucos pueden ser aplicados en otros lugares. Este truco puede aplicarse generalmente para que un número sea 0 si y solo si un valor es mayor o igual que otro valor, y -1 contrario, y puedes jugar con él un poco más para obtener <= , < , y así en. La combinación de bits como esta es un enfoque común para hacer que las operaciones matemáticas no se ramifiquen, aunque ciertamente no siempre se construirá a partir de las mismas operaciones; ^ (xor) y | (o) también entran en juego a veces.