¿Cómo se ve un branchless en C++?

Question

Me doy cuenta de que tengo una gran falta de conocimiento en esa área (una manera elegante de decir que no sé nada sobre esto).

¿Hay alguna documentación sobre cómo y cuándo usarlos?

Answer 1

Aparte de todo el código sin sucursales basado haciendo girar (que no cubre todo, como FP), se obtiene instrucciones específicamente destinado a la creación de códigos sin sucursales, estos serían SETcc, FCMOVcc y CMOVcc bajo x86, que realizan operaciones basadas en las banderas de condición de una comparación.

un ejemplo muy simple sería (sí, el ejemplo es tan simple que uno probablemente no escribir algo como esto, es sólo para demostrar un punto de claridad):

bool CheckZero(int x) 
{ 
    if(x == 0) 
     return true; 

    return false; 
    //OR we can use: return (x == 0) ? true : false; 
} 

ahora un simple compilador x86 pueden compilar que reduce a:

MOV EAX,[ESP + 4] 
    TEXT EAX,EAX 
    JE _TRUE 
    XOR EAX,EAX 
    RETN 4 

_TRUE: 
    MOV EAX,1 
    RETN 4 

un compilador de optimización x86 tomaría abajo en el siguiente código de sucursales (o similar):

MOV ECX,[ESP + 4] 
XOR EAX,EAX 
TEST ECX,ECX 
SETE AL 
RETN 4 

Se puede encontrar un ejemplo un poco más complejo here.

Sin embargo, esto es algo que un compilador llevará a cabo, y no algunos de los que debería preocuparse (al menos no sin analizar el resultado de su compilador). pero si se requiere que el código sea sin sucursales, C++ no proporciona el control suficiente para hacerlo, por lo que debe usar el ensamblado (en línea).

Answer 2

http://hbfs.wordpress.com/2008/08/05/branchless-equivalents-of-simple-functions/

creo (aunque no sé más de lo que he leído en la página) es una manera de conseguir si la funcionalidad sin la ramificación (lo cual tiene sentido en base a la palabra sin sucursales si;)) No sé más

Gracias Sr. Google.

Answer 3

Escribí el simulador de lógica ternaria no hace mucho, y esta pregunta me resultó viable, ya que afecta directamente a la velocidad de ejecución de mi interpretador; Debía simular toneladas y toneladas de compuertas lógicas ternarias lo más rápido posible.

En un sistema ternario codificado en binario, un trit se empaqueta en dos bits. El bit más significativo significa negativo y menos significativo significa positivo. El caso "11" no debería ocurrir, pero debe manejarse correctamente y amenazarse como 0.

Considere la función inline int bct_decoder(unsigned bctData), que debe devolver nuestro trit formateado como entero regular -1, 0 o 1; Como observé, hay 4 enfoques: los llamé "cond", "mod", "math" y "lut"; Vamos a investigarlos

Primero se basa en jz | jnz y jl | jb saltos condicionales, por lo tanto cond. Su rendimiento no es bueno en absoluto, porque depende de un pronosticador de bifurcación. Y lo que es peor, varía, porque se desconoce si habrá una rama o dos a priori. Y aquí está un ejemplo:

inline int bct_decoder_cond(unsigned bctData) { 
    unsigned lsB = bctData & 1; 
    unsigned msB = bctData >> 1; 
    return 
     (lsB == msB) ? 0 : // most possible -> make zero fastest branch 
     (lsB > msB) ? 1 : -1; 
} 

Esta es la versión más lento, podría involucrar a 2 sucursales en peor de los casos y esto es algo en lo que falla lógica binaria. En mi 3770k, produce alrededor de 200MIPS en promedio en datos aleatorios.(Aquí y después de - cada prueba es la media a partir de 1000 se prueba el conjunto de datos de 2 MB lleno al azar)

A continuación se basa en operador de módulo y su velocidad está en algún lugar entre la primera y la tercera, pero es definitivamente más rápido - 600 MIPS:

inline int bct_decoder_mod(unsigned bctData) { 
    return (int)((bctData + 1) % 3) - 1; 
} 

El siguiente es un enfoque sin sucursales, que involucra solo las matemáticas, por lo tanto, las matemáticas; no asume instrunciones de salto en absoluto:

inline int bct_decoder_math(unsigned bctData) { 
    return (int)(bctData & 1) - (int)(bctData >> 1); 
} 

Esto hace lo que debería, y se comporta muy bien. Para comparar, el rendimiento estimado es 1000 MIPS, y es 5 veces más rápido que la versión ramificada. Probablemente, la versión ramificada se ralentiza debido a la falta de soporte nativo firmado de 2 bits. Pero en mi aplicación es una versión bastante buena en sí misma.

Si esto no es suficiente, podemos ir más lejos, tener algo especial. A continuación se denomina enfoque de búsqueda de tabla:

inline int bct_decoder_lut(unsigned bctData) { 
    static const int decoderLUT[] = { 0, 1, -1, 0 }; 
    return decoderLUT[ bctData & 0x3 ]; 
} 

En mi caso, uno TRIT ocuparon sólo 2 bits, por lo tabla LUT era sólo 2b * 4 = 8 bytes, y valía la pena probar. Se adapta a la caché y funciona a una velocidad increíble de 1400-1600 MIPS, aquí es donde la precisión de mi medición está bajando. Y eso es una aceleración de 1.5 veces desde el enfoque matemático rápido. Esto se debe a que acaba de obtener el resultado precalculado y la instrucción única AND. Lamentablemente, los cachés son pequeños y (si la longitud de su índice es mayor que varios bits) simplemente no puede usarlos.

Así que creo que he respondido a su pregunta sobre cómo podría ser el código ramificado/sin sucursales. La respuesta es mucho mejor y con muestras detalladas, la aplicación en el mundo real y los resultados de las mediciones de rendimiento real.