c++ - tipo - Manera eficiente de OR bits adyacentes en un entero de 64 bits

unsigned int para que sirve

Question

Lo que quiero hacer es tomar un número entero sin signo de 64 bits que consiste en pares de bits y crear un número entero de 32 bits que contenga 0 si ambos bits en el par correspondiente son 0 y 1 de lo contrario. En otras palabras, convierta algo que se vea así:

01 00 10 11

en algo que se parece a esto

1 0 1 1

Las dos soluciones obvias son el bucle de fuerza bruta o una tabla de búsqueda para cada byte y luego hacer ocho búsquedas y combinarlas en un resultado final con OR y desplazamiento de bits, pero estoy seguro de que debería haber un medio eficiente para revertir esto . Haré esto para enteros de 64 bits en C ++, pero si alguien conoce formas eficientes de hacerlo para enteros más cortos, estoy seguro de que puedo descubrir cómo escalarlo.

Answer 1

Aquí hay una implementación portátil de C ++. Parece funcionar durante mi breve prueba. El código de desentrelazado se basa en esta pregunta SO .

uint64_t calc(uint64_t n)
{
    // (odd | even)
    uint64_t x = (n & 0x5555555555555555ull) | ((n & 0xAAAAAAAAAAAAAAAAull) >> 1);

    // deinterleave
    x = (x | (x >> 1)) & 0x3333333333333333ull;
    x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full;
    x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull;
    x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull;
    x = (x | (x >> 16)) & 0x00000000FFFFFFFFull;

    return x;
}

gcc, clang y msvc compilan todo esto en aproximadamente 30 instrucciones.

De los comentarios , hay una modificación que se puede hacer.

• Cambie la primera línea para usar una sola operación de máscara de bits para seleccionar solo los bits "impares".

El código posiblemente (?) Mejorado es:

uint64_t calc(uint64_t n)
{
    // (odd | even)
    uint64_t x = (n | (n >> 1)) & 0x5555555555555555ull; // single bits

    // ... the restdeinterleave
    x = (x | (x >> 1)) & 0x3333333333333333ull; // bit pairs
    x = (x | (x >> 2)) & 0x0F0F0F0F0F0F0F0Full; // nibbles
    x = (x | (x >> 4)) & 0x00FF00FF00FF00FFull; // octets
    x = (x | (x >> 8)) & 0x0000FFFF0000FFFFull; // halfwords
    x = (x | (x >> 16)) & 0x00000000FFFFFFFFull; // words

    return x;
}

Answer 2

Bien, hagamos esto más hacky entonces (podría ser defectuoso):

uint64_t x;

uint64_t even_bits = x & 0xAAAAAAAAAAAAAAAAull;
uint64_t odd_bits  = x & 0x5555555555555555ull;

Ahora, mi solución original hizo esto:

// wrong
even_bits >> 1;
unsigned int solution = even_bits | odd_bits;

Sin embargo, como señaló JackAidley, si bien esto alinea los bits, ¡no elimina los espacios del medio!

Afortunadamente, podemos usar una instrucción _pext muy útil del _pext instrucciones BMI2 .

u64 _pext_u64(u64 a, u64 m) - Extrae bits de a en las ubicaciones de bits correspondientes especificadas por la máscara m a bits bajos contiguos en dst; los bits superiores restantes en dst se ponen a cero.

solution = _pext_u64(solution, odd_bits);

Alternativamente, en lugar de usar & y >> para separar los bits, puede usar _pext dos veces en el número original con las máscaras proporcionadas (que lo dividirían en dos números contiguos de 32 bits), y luego simplemente or los resultados .

Sin embargo, si no tiene acceso a BMI2, estoy bastante seguro de que la eliminación de la brecha aún implicaría un bucle; un poco más simple que su idea original, tal vez.

Answer 3

Hice algunas versiones vectorizadas (el enlace de Godbolt todavía con algunos comentarios de notas de diseño) e hice algunos puntos de referencia cuando esta pregunta era nueva. Iba a pasar más tiempo en eso, pero nunca volví a hacerlo. Publicar lo que tengo para poder cerrar esta pestaña del navegador. >. <Mejoras bienvenidas.

No tengo un Haswell en el que pueda probar, por lo que no pude comparar la versión pextr con esto. Sin embargo, estoy seguro de que es más rápido, ya que solo son 4 instrucciones rápidas.

 *** Sandybridge (i5-2500k, so no hyperthreading)
 *** 64bit, gcc 5.2 with -O3 -fno-tree-vectorize results:
 TODO: update benchmarks for latest code changes

   total cycles, and insn/clock, for the test-loop
   This measures only throughput, not latency,
   and a bottleneck on one execution port might make a function look worse in a microbench
   than it will do when mixed with other code that can keep the other ports busy.

Lower numbers in the first column are better: 
these are total cycle counts in Megacycles, and correspond to execution time 
but they take frequency scaling / turbo out of the mix.
(We''re not cache / memory bound at all, so low core clock = fewer cycles for cache miss doesn''t matter).

     AVX                  no AVX
887.519Mc  2.70Ipc      887.758Mc  2.70Ipc    use_orbits_shift_right
1140.68Mc  2.45Ipc      1140.47Mc  2.46Ipc    use_orbits_mul  (old version that right-shifted after each)
718.038Mc  2.79Ipc      716.452Mc  2.79Ipc    use_orbits_x86_lea
767.836Mc  2.74Ipc      1027.96Mc  2.53Ipc    use_orbits_sse2_shift
619.466Mc  2.90Ipc      816.698Mc  2.69Ipc    use_orbits_ssse3_shift
845.988Mc  2.72Ipc      845.537Mc  2.72Ipc    use_orbits_ssse3_shift_scalar_mmx (gimped by stupid compiler)
583.239Mc  2.92Ipc      686.792Mc  2.91Ipc    use_orbits_ssse3_interleave_scalar
547.386Mc  2.92Ipc      730.259Mc  2.88Ipc    use_orbits_ssse3_interleave

The fastest (for throughput in a loop) with    AVX is orbits_ssse3_interleave
The fastest (for throughput in a loop) without AVX is orbits_ssse3_interleave_scalar
but obits_x86_lea comes very close.

AVX for non-destructive 3-operand vector insns helps a lot
Maybe a bit less important on IvB and later, where mov-elimination handles mov uops at register-rename time

// Tables generated with the following commands:
// for i in avx.perf{{2..4},{6..10}};do awk ''/cycles   / {c=$1; gsub(",", "", c); }  /insns per cy/ {print c / 1000000 "Mc  " $4"Ipc"}'' *"$i"*;done | column -c 50 -x
//  Include 0 and 1 for hosts with pextr
// 5 is omitted because it''s not written

La mejor versión casi segura (con BMI2) es:

#include <stdint.h>
#define LOBITS64 0x5555555555555555ull
#define HIBITS64 0xaaaaaaaaaaaaaaaaull

uint32_t orbits_1pext (uint64_t a) {
    // a|a<<1 compiles more efficiently on x86 than a|a>>1, because of LEA for non-destructive left-shift
    return _pext_u64( a | a<<1, HIBITS64);
}

Esto compila a:

    lea     rax, [rdi+rdi]
    or      rdi, rax
    movabs  rax, -6148914691236517206
    pext    rax, rdi, rax
    ret

Por lo tanto, solo son 4 uops, y la latencia de ruta crítica es 5c = 3 (pext) + 1 (o) + 1 (lea). (Intel Haswell). El rendimiento debe ser un resultado por ciclo (sin sobrecarga de bucle o carga / almacenamiento). Sin embargo, el mov imm para la constante se puede levantar de un bucle, ya que no se destruye. Esto significa que, en cuanto al rendimiento, solo necesitamos 3 uops de dominio fusionado por resultado.

El mov r, imm64 no es ideal. (Una transmisión de 1uop inmediata de 32 u 8 bits a un registro de 64 bits sería ideal, pero no existe tal instrucción). Tener la constante en la memoria de datos es una opción, pero en línea en el flujo de instrucciones es bueno. Una constante de 64b ocupa mucho espacio uop-cache, lo que hace que la versión que pext con dos máscaras diferentes sea aún peor. Sin embargo, generar una máscara de la otra con un not podría ayudar con eso: movabs / pext / not / pext / or , pero eso sigue siendo 5 insns en comparación con los 4 habilitados por el truco de lea .

La mejor versión (con AVX) es:

#include <immintrin.h>

/* Yves Daoust''s idea, operating on nibbles instead of bytes:
   original:
   Q= (Q | (Q << 1)) & 0xAAAAAAAAAAAAL // OR in pairs
   Q|= Q >> 9; // Intertwine 4 words into 4 bytes
   B0= LUT[B0]; B1= LUT[B2]; B2= LUT[B4]; B3= LUT[B6]; // Rearrange bits in bytes

   To operate on nibbles,
   Q= (Q | (Q << 1)) & 0xAAAAAAAAAAAAL // OR in pairs, same as before
   Q|= Q>>5  // Intertwine 8 nibbles into 8 bytes
   // pshufb as a LUT to re-order the bits within each nibble (to undo the interleave)
   // right-shift and OR to combine nibbles
   // pshufb as a byte-shuffle to put the 4 bytes we want into the low 4
*/
uint32_t orbits_ssse3_interleave(uint64_t scalar_a)
{
    // do some of this in GP regs if not doing two 64b elements in parallel.
    // esp. beneficial for AMD Bulldozer-family, where integer and vector ops don''t share execution ports
    // but VEX-encoded SSE saves mov instructions

    __m128i a = _mm_cvtsi64_si128(scalar_a);
    // element size doesn''t matter, any bits shifted out of element boundaries would have been masked off anyway.
    __m128i lshift = _mm_slli_epi64(a, 1);
    lshift = _mm_or_si128(lshift, a);
    lshift = _mm_and_si128(lshift, _mm_set1_epi32(0xaaaaaaaaUL));
    // a = bits:   h  g  f  e  d  c  b  a  (same thing in other bytes)
    // lshift =    hg 0 fe  0  dc 0  ba 0
    // lshift =    s  0  r  0  q  0  p  0

    // lshift =    s 0 r 0 q 0 p 0
    __m128i rshift = _mm_srli_epi64(lshift, 5);  // again, element size doesn''t matter, we''re keeping only the low nibbles
    // rshift =              s 0 r 0 q 0 p 0  (the last zero ORs with the top bit of the low nibble in the next byte over)
    __m128i nibbles = _mm_or_si128(rshift, lshift);
    nibbles = _mm_and_si128(nibbles, _mm_set1_epi8(0x0f) );  // have to zero the high nibbles: the sign bit affects pshufb

    // nibbles =   0 0 0 0 q s p r
    // pshufb ->   0 0 0 0 s r q p
    const __m128i BITORDER_NIBBLE_LUT = _mm_setr_epi8( // setr: first arg goes in the low byte, indexed by 0b0000
    0b0000,
    0b0100,
    0b0001,
    0b0101,
    0b1000,
    0b1100,
    0b1001,
    0b1101,
    0b0010,
    0b0110,
    0b0011,
    0b0111,
    0b1010,
    0b1110,
    0b1011,
    0b1111 );
    __m128i ord_nibbles = _mm_shuffle_epi8(BITORDER_NIBBLE_LUT, nibbles);

    // want            00 00 00 00 AB CD EF GH from:

    // ord_nibbles   = 0A0B0C0D0E0F0G0H
    //                  0A0B0C0D0E0F0G0 H(shifted out)
    __m128i merged_nibbles = _mm_or_si128(ord_nibbles, _mm_srli_epi64(ord_nibbles, 4));
    // merged_nibbles= 0A AB BC CD DE EF FG GH.  We want every other byte of this.
    //                 7  6  5  4  3  2  1  0
    // pshufb is the most efficient way.  Mask and then packuswb would work, but uses the shuffle port just like pshufb
    __m128i ord_bytes = _mm_shuffle_epi8(merged_nibbles, _mm_set_epi8(-1,-1,-1,-1, 14,12,10,8,
                                      -1,-1,-1,-1,  6, 4, 2,0) );
    return _mm_cvtsi128_si32(ord_bytes); // movd the low32 of the vector
    // _mm_extract_epi32(ord_bytes, 2); // If operating on two inputs in parallel: SSE4.1 PEXTRD the result from the upper half of the reg.
}

La mejor versión sin AVX es una ligera modificación que solo funciona con una entrada a la vez, solo usando SIMD para barajar. En teoría, usar MMX en lugar de SSE tendría más sentido, especialmente. si nos preocupamos por Core2 de primera generación, donde 64b pshufb es rápido, pero 128b pshufb no es un ciclo único. De todos modos, los compiladores hicieron un mal trabajo con los intrínsecos MMX. Además, EMMS es lento.

// same as orbits_ssse3_interleave, but doing some of the math in integer regs. (non-vectorized)
// esp. beneficial for AMD Bulldozer-family, where integer and vector ops don''t share execution ports

// VEX-encoded SSE saves mov instructions, so full vector is preferable if building with VEX-encoding

// Use MMX for Silvermont/Atom/Merom(Core2): pshufb is slow for xmm, but fast for MMX.  Only 64b shuffle unit?
uint32_t orbits_ssse3_interleave_scalar(uint64_t scalar_a)
{
    uint64_t lshift = (scalar_a | scalar_a << 1);
    lshift &= HIBITS64;

    uint64_t rshift = lshift >> 5;
    // rshift =              s 0 r 0 q 0 p 0  (the last zero ORs with the top bit of the low nibble in the next byte over)
    uint64_t nibbles_scalar = (rshift | lshift) & 0x0f0f0f0f0f0f0f0fULL;
    // have to zero the high nibbles: the sign bit affects pshufb
    __m128i nibbles = _mm_cvtsi64_si128(nibbles_scalar);

    // nibbles =   0 0 0 0 q s p r
    // pshufb ->   0 0 0 0 s r q p

    const __m128i BITORDER_NIBBLE_LUT = _mm_setr_epi8( // setr: first arg goes in the low byte, indexed by 0b0000
    0b0000,
    0b0100,
    0b0001,
    0b0101,
    0b1000,
    0b1100,
    0b1001,
    0b1101,
    0b0010,
    0b0110,
    0b0011,
    0b0111,
    0b1010,
    0b1110,
    0b1011,
    0b1111 );
    __m128i ord_nibbles = _mm_shuffle_epi8(BITORDER_NIBBLE_LUT, nibbles);

    // want            00 00 00 00 AB CD EF GH from:

    // ord_nibbles   = 0A0B0C0D0E0F0G0H
    //                  0A0B0C0D0E0F0G0 H(shifted out)
    __m128i merged_nibbles = _mm_or_si128(ord_nibbles, _mm_srli_epi64(ord_nibbles, 4));
    // merged_nibbles= 0A AB BC CD DE EF FG GH.  We want every other byte of this.
    //                 7  6  5  4  3  2  1  0
    // pshufb is the most efficient way.  Mask and then packuswb would work, but uses the shuffle port just like pshufb
    __m128i ord_bytes = _mm_shuffle_epi8(merged_nibbles, _mm_set_epi8(0,0,0,0, 0,0,0,0, 0,0,0,0, 6,4,2,0));
    return _mm_cvtsi128_si32(ord_bytes); // movd the low32 of the vector
}

Perdón por la respuesta de volcado de código. En este punto, no sentía que valiera la pena dedicar una gran cantidad de tiempo a discutir cosas más de lo que los comentarios ya lo hacen. Consulte http://agner.org/optimize/ para obtener guías para la optimización de microarquitecturas específicas. También la wiki x86 para otros recursos.

Answer 4

La parte difícil parece ser empacar los pedazos después de oring. La oring se realiza mediante:

ored  = (x | (x>>1)) & 0x5555555555555555;

(suponiendo int suficientemente grandes para que no tengamos que usar sufijos). Luego podemos empacar, luego en pasos, primero empacarlos dos por dos, cuatro por cuatro, etc.

pack2 = ((ored*3) >> 1) & 0x333333333333;
pack4 = ((ored*5) >> 2) & 0x0F0F0F0F0F0F;
pack8 = ((ored*17) >> 4) & 0x00FF00FF00FF;
pac16 = ((ored*257) >> 8) & 0x0000FFFF0000FFFF;
pack32 = ((ored*65537) >> 16) & 0xFFFFFFFF;
// (or cast to uint32_t instead of the final & 0xFFF...)

Lo que sucede en el empaque es que al multiplicar combinamos los datos con los datos desplazados. En su ejemplo, tendríamos en la primera multiplicación ( ored ceros del enmascaramiento en ored como o y el otro 0 (de los datos originales)):

 o1o0o1o1
     x 11
----------
 o1o0o1o1
o1o0o1o1
----------
o11001111
  ^^  ^^ 
 o10oo11o < these are bits we want to keep.

Podríamos haber hecho eso oring también:

ored = (ored | (ored>>1)) & 0x3333333333333333;
ored = (ored | (ored>>2)) & 0x0F0F0F0F0F0F0F0F;
ored = (ored | (ored>>4)) & 0x00FF00FF00FF00FF;
ored = (ored | (ored>>8)) & 0x0000FFFF0000FFFF;
ored = (ored | (ored>>16)) & 0xFFFFFFFF;

// ored = ((uint32_t)ored | (uint32_t)(ored>>16));  // helps some compilers make better code, esp. on x86

Answer 5

Ligera mejora sobre el enfoque LUT (4 búsquedas en lugar de 8):

Calcule el bit a bit o borre cada dos bits. Luego entrelaza los bits de pares de bytes para obtener cuatro bytes. Finalmente, reordene los bits en los cuatro bytes (mapeados en la palabra cuádruple) por medio de una tabla de búsqueda de 256 entradas:

Q= (Q | (Q << 1)) & 0xAAAAAAAAAAAAL; // OR in pairs
Q|= Q >> 9; // Intertwine 4 words into 4 bytes
B0= LUT[B0]; B1= LUT[B2]; B2= LUT[B4]; B3= LUT[B6]; // Rearrange bits in bytes

Answer 6

Probablemente la solución más rápida para la arquitectura x86 con el conjunto de instrucciones BMI2 :

#include <stdint.h>
#include <x86intrin.h>

uint32_t calc (uint64_t a)
{
   return _pext_u64(a, 0x5555555555555555ull) |
          _pext_u64(a, 0xaaaaaaaaaaaaaaaaull);
}

Esto compila a 5 instrucciones en total.

Answer 7

Si no tiene pext y todavía quiere hacerlo mejor que de manera trivial, esta extracción puede expresarse como un número logarítmico (si lo generalizó en términos de longitud) de movimientos de bits:

// OR adjacent bits, destroys the odd bits but it doesn''t matter
x = (x | (x >> 1)) & rep8(0x55);
// gather the even bits with delta swaps
x = bitmove(x, rep8(0x44), 1);   // make pairs
x = bitmove(x, rep8(0x30), 2);   // make nibbles
x = bitmove(x, rep4(0x0F00), 4); // make bytes
x = bitmove(x, rep2(0x00FF0000), 8); // make words
res = (uint32_t)(x | (x >> 16)); // final step is simpler

Con:

bitmove(x, mask, step) {
    return x | ((x & mask) >> step);
}

repk es solo para poder escribir constantes más cortas. rep8(0x44) = 0x4444444444444444 etc.

Además, si tiene pext , puede hacerlo con solo uno de ellos, que probablemente sea más rápido y al menos más corto:

_pext_u64(x | (x >> 1), rep8(0x55));