La manera más rápida de hacer la suma horizontal del vector del flotador en x86

Aquí hay algunas versiones afinadas basadas en La guía de microarquías de Agner Fog y las tablas de instrucciones. Ver también el wiki de etiquetas x86. Deben ser eficientes en cualquier CPU, sin cuellos de botella importantes. (por ejemplo, evité cosas que ayudarían a un uarch un poco pero ser lento en otro uarch). El tamaño del código también se minimiza.

El modismo común 2x hadd solo es bueno para el tamaño del código, no para la velocidad en ninguna CPU existente. Hay casos de uso para ello (ver a continuación), pero esto no es uno de ellos.

También he incluido una versión AVX. Cualquier tipo de reducción horizontal con AVX / AVX2 debe comenzar con unvextractf128 y una operación "vertical" para reducir a un vector XMM (__m128).

Vea la salida asm de todo este código en el Explorador del compilador Godbolt. Vea también mis mejoras a La Biblioteca de Clases Vectoriales C++ de Agner Fog horizontal_add funciones. (hilo del tablero de mensajes, y código en github). He usado CPP macros para seleccionar combinaciones óptimas de tamaño de código para SSE2, SSE4 y AVX, y para evitar movdqa cuando AVX no está disponible.

Hay compensaciones a considerar: {[67]]}

• tamaño del código: más pequeño es mejor para razones de caché I L1, y para obtener código desde el disco (binarios más pequeños). El tamaño binario total importa principalmente para las decisiones del compilador tomadas repetidamente en todo un programa. Si se está molestando en codificar a mano algo con intrínsecos, vale la pena gastar algunos bytes de código si le da a cualquier speedup para todo el programa (tenga cuidado de microbenchmarks que hacer desenrollar ven bien).
• uop-tamaño de caché: A menudo más precioso que L1 I I. 4 instrucciones single-uop pueden ocupar menos espacio que 2 haddps, por lo que esto es muy relevante aquí.
• latencia: A veces relevante
• rendimiento: normalmente irrelevantes, las sumas horizontales no deberían estar en el bucle más interno.
• uops total de dominio fusionado: Si el código circundante no tiene un cuello de botella en el mismo puerto que el hsum utiliza, esto es un proxy para el impacto del hsum en el rendimiento de todo el asunto.

Cuando una suma horizontal es infrecuente :

Las CPU sin caché uop podrían favorecer a 2x haddps: Es lento cuando se ejecuta, pero eso no es frecuente. Al ser solo 2 instrucciones minimiza el impacto en el código circundante( I size size).

Las CPU con un caché uop probablemente favorecerán algo que tome menos uops, incluso si es más instrucciones / más tamaño de código x86. Caché total de uops-las líneas utilizadas es lo que queremos minimizar, que no es tan simple como minimizar uops totales (las ramas tomadas y los límites de 32B siempre comienzan una nueva línea de caché de uop).

De todos modos, dicho esto, las sumas horizontales vienen un lote, así que aquí está mi intento de elaborar cuidadosamente algunas versiones que compilan muy bien. No se compara con ningún hardware real, o incluso se prueba cuidadosamente. Puede haber errores en las constantes de barajado o algo.

Si está haciendo una versión alternativa / base de su código, recuerde que solo las CPU antiguas lo ejecutarán ; las CPU más nuevas ejecutarán su versión AVX, o SSE4.1 o lo que sea.

Las CPU antiguas como K8, y Core2(merom) y anteriores solo tienen unidades barajadas de 64 bits. Core2 tiene unidades de ejecución de 128 bits para la mayoría de las instrucciones, pero no para barajar. (Pentium M y K8 manejan todas las instrucciones vectoriales de 128b como dos mitades de 64 bits).

Baraja como movhlps que mover los datos en trozos de 64 bits (sin barajar dentro de mitades de 64 bits) son rápidos, también.

En CPU viejas con mezclas lentas :

• movhlps (Merom: 1uop) es significativamente más rápido que shufps (Merom: 3uops). En Pentium-M, más barato que movaps. Además, se ejecuta en el dominio FP en Core2, evitando los retrasos de bypass de otros shuffles.
• unpcklpd es más rápido que unpcklps.
• {[19] } es lento, pshuflw/pshufhw son rápidos (porque solo barajan un 64bit half)
• pshufb mm0 (MMX) es rápido, pshufb xmm0 es lento.
• haddps es muy lento (6uops en Merom y Pentium M)
• movshdup (Merom: 1uop) es interesante: Es el único insn 1uop que baraja dentro de los elementos 64b.

shufps en Core2 (incluyendo Penryn) trae datos al dominio entero, causando un retraso de bypass para volver a las unidades de ejecución FP para addps, pero movhlps está completamente en el dominio FP. shufpd también se ejecuta en el flotador dominio.

movshdup se ejecuta en el dominio entero, pero es solo un uop.

AMD K10, Intel Core2(Penryn/Wolfdale), y todas las CPU posteriores, ejecutan todos los xmm shuffles como un solo uop. (Pero tenga en cuenta el retraso de bypass con shufps en Penryn, evitado con movhlps)

Sin AVX, evitando el desperdicio movaps/movdqa las instrucciones requieren una cuidadosa selección de barajadas . Solo unos pocos shuffles funcionan como un copy-and-shuffle, en lugar de modificar el destino. Baraja que combinan los datos de dos entradas (como unpck* o movhlps) se pueden usar con una variable tmp que ya no se necesita en lugar de _mm_movehl_ps(same,same).

Algunos de estos se pueden hacer más rápido (guardar un MOVAPS) pero más feo / menos "limpio" tomando un arg ficticio para su uso como destino para un shuffle inicial. Por ejemplo:

// Use dummy = a recently-dead variable that vec depends on,
//  so it doesn't introduce a false dependency,
//  and the compiler probably still has it in a register
__m128d highhalf_pd(__m128d dummy, __m128d vec) {
#ifdef __AVX__
    // With 3-operand AVX instructions, don't create an extra dependency on something we don't need anymore.
    (void)dummy;
    return _mm_unpackhi_pd(vec, vec);
#else
    // Without AVX, we can save a MOVAPS with MOVHLPS into a dead register
    __m128 tmp = _mm_castpd_ps(dummy);
    __m128d high = _mm_castps_pd(_mm_movehl_ps(tmp, _mm_castpd_ps(vec)));
    return high;
#endif
}

SSE1 (alias SSE):

float hsum_ps_sse1(__m128 v) {                                  // v = [ D C | B A ]
    __m128 shuf   = _mm_shuffle_ps(v, v, _MM_SHUFFLE(2, 3, 0, 1));  // [ C D | A B ]
    __m128 sums   = _mm_add_ps(v, shuf);      // sums = [ D+C C+D | B+A A+B ]
    shuf          = _mm_movehl_ps(shuf, sums);      //  [   C   D | D+C C+D ]  // let the compiler avoid a mov by reusing shuf
    sums          = _mm_add_ss(sums, shuf);
    return    _mm_cvtss_f32(sums);
}
    # gcc 5.3 -O3:  looks optimal
    movaps  xmm1, xmm0     # I think one movaps is unavoidable, unless we have a 2nd register with known-safe floats in the upper 2 elements
    shufps  xmm1, xmm0, 177
    addps   xmm0, xmm1
    movhlps xmm1, xmm0     # note the reuse of shuf, avoiding a movaps
    addss   xmm0, xmm1

    # clang 3.7.1 -O3:  
    movaps  xmm1, xmm0
    shufps  xmm1, xmm1, 177
    addps   xmm1, xmm0
    movaps  xmm0, xmm1
    shufpd  xmm0, xmm0, 1
    addss   xmm0, xmm1

Reporté un error de clangsobre pesimizar las barajadas . Tiene su propia representación interna para barajar, y lo vuelve a mezclar. gcc más a menudo utiliza las instrucciones que coinciden directamente con el intrínseco que utilizó.

A menudo clang hace mejor que gcc, en código donde la opción de instrucción no está afinada a mano, o la propagación constante puede simplificar las cosas incluso cuando los intrínsecos son óptimos para el caso no constante. En general, es bueno que los compiladores funcionen como un compilador adecuado para intrínsecos, no solo como un ensamblador. Los compiladores a menudo pueden generar un buen asm a partir de C escalar que no incluso tratar de trabajar como lo haría el buen asm. Eventualmente los compiladores tratarán a los intrínsecos como otro operador C como entrada para el optimizador.

SSE3

float hsum_ps_sse3(__m128 v) {
    __m128 shuf = _mm_movehdup_ps(v);        // broadcast elements 3,1 to 2,0
    __m128 sums = _mm_add_ps(v, shuf);
    shuf        = _mm_movehl_ps(shuf, sums); // high half -> low half
    sums        = _mm_add_ss(sums, shuf);
    return        _mm_cvtss_f32(sums);
}

    # gcc 5.3 -O3: perfectly optimal code
    movshdup    xmm1, xmm0
    addps       xmm0, xmm1
    movhlps     xmm1, xmm0
    addss       xmm0, xmm1

Esto tiene varias ventajas:

• No requiere ninguna copia movaps para trabajar alrededor de shuffles destructivos (sin AVX): movshdup xmm1, xmm2 el destino es de solo escritura, por lo que crea tmp a partir de un registro muerto para nosotros. Esta es también la razón por la que usé movehl_ps(tmp, sums) en lugar de movehl_ps(sums, sums).

• Pequeño tamaño código. Las instrucciones de barajado son pequeñas: movhlps es de 3 bytes, movshdup es de 4 bytes (igual que shufps). No se requiere byte inmediato, por lo que con AVX, vshufps es 5 bytes pero vmovhlps y vmovshdup son ambos 4.

Podría guardar otro byte con addps en lugar de addss. Dado que esto no se utilizará dentro de bucles internos, la energía adicional para cambiar los transistores adicionales es probablemente insignificante. Las excepciones de FP de los 3 elementos superiores no son un riesgo, porque todos los elementos tienen FP válido datos. Sin embargo, clang/LLVM en realidad "entiende" los shuffles vectoriales, y emite mejor código si sabe que solo el elemento bajo importa.

Al igual que la versión SSE1, agregar los elementos impares a sí mismos puede causar excepciones FP (como desbordamiento) que no ocurrirían de otra manera, pero esto no debería ser un problema. Los desnormales son lentos, pero IIRC que produce un resultado +Inf no está en la mayoría de los uarches.

SSE3 optimizando para el tamaño del código

Si el tamaño del código es su mayor preocupación, dos haddps (_mm_hadd_ps) las instrucciones harán el truco (respuesta de Paul R). Este también es el más fácil de escribir y recordar. Es no rápido , sin embargo. Incluso Intel Skylake todavía decodifica cada haddps a 3 uops, con 6 ciclos de latencia. Así que a pesar de que ahorra bytes de código de máquina (L1 I-cache), ocupa más espacio en la caché uop más valiosa. Casos de uso reales para haddps: un problema de transposición y suma, o hacer alguna escala en un paso intermedio en este SSE atoi() aplicación .

AVX:

Esta versión guarda un byte de código vs. La respuesta de Marat a la pregunta de AVX.

#ifdef __AVX__
float hsum256_ps_avx(__m256 v) {
    __m128 vlow  = _mm256_castps256_ps128(v);
    __m128 vhigh = _mm256_extractf128_ps(v, 1); // high 128
           vlow  = _mm_add_ps(vlow, vhigh);     // add the low 128
    return hsum_ps_sse3(vlow);         // and inline the sse3 version, which is optimal for AVX
    // (no wasted instructions, and all of them are the 4B minimum)
}
#endif

 vmovaps xmm1,xmm0               # huh, what the heck gcc?  Just extract to xmm1
 vextractf128 xmm0,ymm0,0x1
 vaddps xmm0,xmm1,xmm0
 vmovshdup xmm1,xmm0
 vaddps xmm0,xmm1,xmm0
 vmovhlps xmm1,xmm1,xmm0
 vaddss xmm0,xmm0,xmm1
 vzeroupper 
 ret

Doble precisión:

double hsum_pd_sse2(__m128d vd) {                      // v = [ B | A ]
    __m128 undef  = _mm_undefined_ps();                       // don't worry, we only use addSD, never touching the garbage bits with an FP add
    __m128 shuftmp= _mm_movehl_ps(undef, _mm_castpd_ps(vd));  // there is no movhlpd
    __m128d shuf  = _mm_castps_pd(shuftmp);
    return  _mm_cvtsd_f64(_mm_add_sd(vd, shuf));
}

# gcc 5.3.0 -O3
    pxor    xmm1, xmm1          # hopefully when inlined, gcc could pick a register it knew wouldn't cause a false dep problem, and avoid the zeroing
    movhlps xmm1, xmm0
    addsd   xmm0, xmm1


# clang 3.7.1 -O3 again doesn't use movhlps:
    xorpd   xmm2, xmm2          # with  #define _mm_undefined_ps _mm_setzero_ps
    movapd  xmm1, xmm0
    unpckhpd        xmm1, xmm2
    addsd   xmm1, xmm0
    movapd  xmm0, xmm1    # another clang bug: wrong choice of operand order


// This doesn't compile the way it's written
double hsum_pd_scalar_sse2(__m128d vd) {
    double tmp;
    _mm_storeh_pd(&tmp, vd);       // store the high half
    double lo = _mm_cvtsd_f64(vd); // cast the low half
    return lo+tmp;
}

    # gcc 5.3 -O3
    haddpd  xmm0, xmm0   # Lower latency but less throughput than storing to memory

    # ICC13
    movhpd    QWORD PTR [-8+rsp], xmm0    # only needs the store port, not the shuffle unit
    addsd     xmm0, QWORD PTR [-8+rsp]

Almacenar en memoria y viceversa evita un ALU uop. Eso es bueno si la presión del puerto de shuffle, o ALU uops en general, son un cuello de botella. (Tenga en cuenta que no necesita sub rsp, 8 ni nada porque el x86-64 SysV ABI proporciona una zona roja que los manejadores de señales no pisarán.)

Algunos la gente almacena en una matriz y suma todos los elementos, pero los compiladores generalmente no se dan cuenta de que el elemento bajo de la matriz todavía está allí en un registro anterior a la tienda.

Entero:

pshufd es una práctica copia-y-barajar. Los cambios de bits y bytes están desafortunadamente en su lugar, y punpckhqdq coloca la mitad alta del destino en la mitad baja del resultado, opuesto a la forma en que movhlps puede extraer la mitad alta en un registro diferente.

Usando movhlps para el primer paso puede ser bueno en algunas CPU, pero solo si tenemos un scratch reg. pshufd es una opción segura, y rápido en todo después de Merom.

int hsum_epi32_sse2(__m128i x) {
#ifdef __AVX__
    __m128i hi64  = _mm_unpackhi_epi64(x, x);           // 3-operand non-destructive AVX lets us save a byte without needing a mov
#else
    __m128i hi64  = _mm_shuffle_epi32(x, _MM_SHUFFLE(1, 0, 3, 2));
#endif
    __m128i sum64 = _mm_add_epi32(hi64, x);
    __m128i hi32  = _mm_shufflelo_epi16(sum64, _MM_SHUFFLE(1, 0, 3, 2));    // Swap the low two elements
    __m128i sum32 = _mm_add_epi32(sum64, hi32);
    return _mm_cvtsi128_si32(sum32);       // SSE2 movd
    //return _mm_extract_epi32(hl, 0);     // SSE4, even though it compiles to movd instead of a literal pextrd r32,xmm,0
}

    # gcc 5.3 -O3
    pshufd xmm1,xmm0,0x4e
    paddd  xmm0,xmm1
    pshuflw xmm1,xmm0,0x4e
    paddd  xmm0,xmm1
    movd   eax,xmm0

int hsum_epi32_ssse3_slow_smallcode(__m128i x){
    x = _mm_hadd_epi32(x, x);
    x = _mm_hadd_epi32(x, x);
    return _mm_cvtsi128_si32(x);
}

En algunas CPU, es seguro usar mezclas FP en datos enteros. No hice esto, ya que en las CPU modernas que a lo sumo guardarán 1 o 2 bytes de código, sin ganancias de velocidad (aparte del tamaño del código/efectos de alineación).