Эффективный путь к OR соседним битам в 64-битном целочисленном

Ответ 1

Вот портативная реализация на С++. Кажется, это работает во время моего краткого тестирования. Код обращенного перемежения основан на этом вопросе 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 и msvc все скомпилируют это примерно до 30 инструкций.

Из комментариев, есть модификация, которая может быть сделана.

• Измените первую строку, чтобы использовать одну операцию битмаски, чтобы выбрать только "нечетные" биты.

Возможно, улучшенный код (?):

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;
}

Ответ 2

Возможно быстрое решение для архитектуры x86 с набором инструкций BMI2:

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

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

Это скомпилируется до 5 инструкций.

Ответ 3

Если у вас нет pext, и вы все же хотите сделать это лучше, чем тривиальный путь, то это извлечение может быть выражено как логарифмическое число (если вы обобщили его по длине) перемещений бит:

// 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

С

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

repk - это просто, чтобы я мог писать короткие константы. rep8(0x44) = 0x4444444444444444 и т.д.

Также, если у вас есть pext, вы можете сделать это только с одним из них, что, вероятно, быстрее и хотя бы короче:

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

Ответ 4

Хорошо, пусть делает это более взломанным тогда (может быть, глючит):

uint64_t x;

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

Теперь мое оригинальное решение сделало это:

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

Однако, как отметил ДжекАйдли, в то время как это выравнивает биты вместе, оно не удаляет пробелы из середины!

К счастью, мы можем использовать очень полезную инструкцию _pext из набора инструкций BMI2.

u64 _pext_u64(u64 a, u64 m) - Извлечь биты из a в соответствующие местоположения бит, заданные маской m, в смежные низкие биты в dst; остальные верхние биты в dst устанавливаются на ноль.

solution = _pext_u64(solution, odd_bits);

В качестве альтернативы вместо использования & и >> для выделения битов вы можете просто использовать _pext дважды на исходном номере с предоставленными масками (что разделило бы его на два смежных 32-битных номера), а затем просто or результаты.

Если у вас нет доступа к BMI2, я уверен, что удаление пробелов по-прежнему будет включать цикл; немного проще, чем ваша оригинальная идея.

Ответ 5

Небольшое улучшение по сравнению с подходом LUT (4 поисковых запроса вместо 8):

Вычислить поразрядный или очистить каждый бит. Затем переплетайте биты пар байтов, чтобы получить четыре байта. Наконец, измените порядок бит в четырех байтах (отображается на квадрат) с помощью 256-разрядной таблицы поиска:

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

Ответ 6

Жесткая часть, похоже, состоит в том, чтобы упаковать бит после обработки. Орнирование осуществляется с помощью:

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

(при условии, что достаточно большой int, поэтому нам не нужно использовать суффиксы). Затем мы можем упаковать их по этапам, сначала упаковывая их по два на четыре, четыре на четыре и т.д.:

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...)

Вещь, которая происходит в упаковке, заключается в том, что путем умножения мы объединяем данные со сдвинутыми данными. В вашем примере у нас было бы первое умножение (я обозначаю нули из маскировки в ored как o, а другой 0 (из исходных данных)):

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

Мы могли бы сделать это и с помощью oring:

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

Ответ 7

Я сделал несколько векторизованных версий (ссылка godbolt по-прежнему с некоторыми замечаниями по дизайну заметок) и сделала некоторые тесты, когда этот вопрос был новым. Я собирался потратить на это больше времени, но так и не вернулся. Отправляя то, что у меня есть, я могу закрыть эту вкладку браузера. > & Л.; Усовершенствования приветствуются.

У меня нет Haswell, на который я мог протестировать, поэтому я не мог сравнить версию pextr с этим. Однако я уверен, что это быстрее, поскольку это всего лишь 4 быстрых инструкций.

 *** 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 not written

Почти наверняка лучшая версия (с BMI2):

#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);
}

Скомпилируется для:

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

Таким образом, это всего 4 uops, а задержка критического пути - 5c = 3 (pext) + 1 (или) + 1 (lea). (Intel Haswell). Пропускная способность должна быть одним результатом за цикл (без накладных расходов на цикл или загрузки/хранения). mov imm для константы может быть выведен из цикла, хотя, поскольку он не разрушен. Это означает пропускную способность, что нам нужен только 3 процессора с плавным доменом за результат.

mov r, imm64 не является идеальным. (A 1uop broadcast - немедленный 32 или 8 бит в 64-битный регистр будет идеальным, но нет такой инструкции). Наличие константы в памяти данных является опцией, но встроенный в поток команд хорош. Постоянная 64b занимает много места в кеш-кеш, что делает версию, которая делает pext с двумя разными масками еще хуже. Создание одной маски из другой с помощью not могло бы помочь с этим: movabs/pext/not/pext/or, но это все еще 5 insns по сравнению с 4, включенными lea трюк.

Лучшая версия (с AVX):

#include <immintrin.h>

/* Yves Daoust 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.
}

Лучшая версия без AVX - небольшая модификация, которая работает только с одним входом за раз, только используя SIMD для перетасовки. Теоретически использование MMX вместо SSE будет иметь больше смысла, особенно. если мы заботимся о первом процессоре Core2, где 64b pshufb работает быстро, но 128b pshufb не является одиночным циклом. Во всяком случае, компиляторы плохо работали с встроенными MMX. Кроме того, EMMS работает медленно.

// 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
}

Извините за ответ в основном ответом на код. На данный момент я не чувствовал, что стоит потратить огромное количество времени на обсуждение вещей больше, чем уже есть комментарии. См. http://agner.org/optimize/ для руководства по оптимизации для конкретных микроархитектур. Кроме того, x86 для других ресурсов.