Самый быстрый способ подсчета количества единиц в регистре, сборка ARM

Question

Так что у меня был вопрос на собеседовании, прежде чем касаться битовых манипуляций. Компания является известной компанией GPU. У меня было очень мало опыта в ассемблере (странно, несмотря на то, что я аспирант по компьютерной архитектуре), и, как показывает этот рассказ, я испортил его. Вопрос был простой:

"Напишите быстрый код, который будет считать количество единиц в 32-битном регистре".

Сейчас я нахожусь в процессе изучения сборки рук. Поэтому, естественно, я снова вернулся к этой проблеме и придумал этот код, просто изучая ISA.

Для вас, экспертов по вооружению, это правильно? Есть ли более быстрый способ сделать это? Будучи новичком, я, естественно, считаю, что это неполно. Инструкция AND в "xx" выглядит избыточной, но в ARM нет другого способа сдвинуть регистр...

R1 будет содержать количество бит в конце, а R2 - это регистр с битами, которые мы хотим считать. r6 - просто фиктивный регистр. Комментарии заключены в ()

    MOV   R1, #0                (initialize R1 and R6 to zero)
    MOV   R6, #0        
xx: AND   R6, R6, R2, LSR #1    (Right shift by 1, right most bit is in carry flag)
    ADDCS R1, #1                (Add #1 to R1 if carry  flag is set)
    CMP R2, #0                  (update the status flags if R2 == 0 or not)
    BEQ xx                      (branch back to xx until R2==0)

Answer 1

Вы можете использовать предварительно вычисленную справочную таблицу и сократить количество итераций до 2 или 4.

Вы также можете использовать логарифмический подход.

Для получения дополнительной информации см. Эту статью в Википедии.

Answer 2

Этот код быстрый или нет, зависит от процессора. Конечно, он будет не очень быстрым на Cortex-A8, но может работать очень быстро на Cortex-A9 и более новых процессорах.

Это, однако, очень короткое решение.

Ожидает ввод в r0 и возвращает вывод в r0

  vmov.32 d0[0], r0
  vcnt.8  d0, d0
  vmov.32 r0, d0[0]

  add r0, r0, r0, lsr #16
  add r0, r0, r0, lsr #8
  and r0, r0, #31

Основная работа выполняется в инструкции vcnt.8, которая подсчитывает биты каждого байта в регистре NEON и сохраняет количество бит обратно в байты D0.

Здесь нет vcnt.32 только форма .8так что вам нужно добавить 4 байта по горизонтали, что и делает остальная часть кода.

Answer 3

Лучшие ссылки на битовые хаки

• Восторг Хакера (печать)
• Бит Тиддлинг Хаки (онлайн)

Bit Twiddling Hacks страница говорит

The best method for counting bits in a 32-bit
integer v is the following:

v = v - ((v >> 1) & 0x55555555);                    // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

Тогда я бы предложил вам использовать gcc а также objdump (или этот замечательный онлайн-инструмент gcc), чтобы увидеть, как этот фрагмент высокого уровня будет выглядеть как инструкция для руки.

00000000 <popcount>:
 0: 1043        asrs    r3, r0, #1
 2: f003 3355   and.w   r3, r3, #1431655765 ; 0x55555555
 6: 1ac0        subs    r0, r0, r3
 8: 1083        asrs    r3, r0, #2
 a: f000 3033   and.w   r0, r0, #858993459  ; 0x33333333
 e: f003 3333   and.w   r3, r3, #858993459  ; 0x33333333
12: 18c0        adds    r0, r0, r3
14: eb00 1010   add.w   r0, r0, r0, lsr #4
18: f000 300f   and.w   r0, r0, #252645135  ; 0xf0f0f0f
1c: eb00 2000   add.w   r0, r0, r0, lsl #8
20: eb00 4000   add.w   r0, r0, r0, lsl #16
24: 1600        asrs    r0, r0, #24
26: 4770        bx  lr

Похоже, что это дает вам результат в 12 инструкции, которые примерно можно перевести на такое же количество циклов.

Сравнивая целочисленные твидлинги выше look up table подход, используемый libgcc, поиск таблицы должен быть еще медленнее, учитывая дополнительные обращения к памяти.

00000028 <__popcountSI2>:
28: b410        push    {r4}
2a: 2200        movs    r2, #0
2c: 4c06        ldr r4, [pc, #24]   ; (48 <__popcountSI2+0x20>)
2e: 4613        mov r3, r2
30: fa40 f103   asr.w   r1, r0, r3
34: 3308        adds    r3, #8
36: 2b20        cmp r3, #32
38: b2c9        uxtb    r1, r1
3a: 5c61        ldrb    r1, [r4, r1]
3c: 440a        add r2, r1
3e: d1f7        bne.n   30 <__popcountSI2+0x8>
40: 4610        mov r0, r2
42: bc10        pop {r4}
44: 4770        bx  lr
46: bf00        nop
48: 00000000    andeq   r0, r0, r0
<.. snipped ..>

Answer 4

Так как это помечено ARM, clzинструкция наиболее полезна. Проблема также описывается какподсчет населения. gccимеет __builtin_popcount() для этого. Как и инструменты ARM. Есть эта ссылка(не расстраивайтесь из-за вашего решения, кто-то сделал веб-страницу с почти такой же), а также есть версия Дейва Сила с шестью инструкциями для clzОружие.clz выгодно и может использоваться для создания более быстрого алгоритма, в зависимости от ввода.

auselen хорошим предложением auselen чтения, этот полезный блог ^{Hacker's Delight} может оказаться полезным, в котором рассказывается о таких вещах в графическом контексте. По крайней мере, я нашел полезным разобраться в блинтовом коде Qt. Тем не менее, он имеет некоторую полезность в кодировании процедурыподсчета населения.

carry add Блок полезен в смысле разделяй и властвуй, что делает проблему O(ln n),clz более полезно, если данные имеют ряды или нули.

В записи " Хакерское наслаждение " больше информации о коде ARM Дейва Сила.

Answer 5

long count_bits_long (long);

    vmov.32 d0[0], r0       // R0 --> SIMD

    vcnt.8  d0, d0          // count bits in bytes
    vpaddl.u8 d0, d0        // add adjacent pairs of bytes and put into 16b words
    vpaddl.u16 d0, d0       // add adjacent pairs of 16b words and put into 32b word

    vmov.32 r0, d0[0]       // SIMD --> R0

    mov pc, lr              // return

Answer 6

    LDR r0, = 0x000000FF;
    MOV r1, #0;
    MOV r3, #0; this will always be zero
    MOV r2,r0;
rep MOVS r2, r2, LSR #1;
    ADC r1,r1, r3;  this adds r1 with zero plus the carry bit
    CMP r2, #0;
    BNE rep

Это будет сделано, r3 - всего лишь фиктивный регистр с 0 для правильной работы АЦП.

Answer 7

В AArch64 расширение CSSC представляет скалярную форму инструкции popcount:

       cnt  w0, w0

Я не думаю, что это доступно в 32-битном режиме, поэтому этот ответ немного не по теме, толькоvcntкоторый требует копирования в регистр NEON и обратно. Это может привести к остановке конвейера на процессорах, которые не связывают их плотно, поэтому, возможно, в некоторых случаях было бы быстрее использовать скалярный битхак для popcount или даже цикл, если вы ожидаете, что обычно будет установлено только пара битов. (Я думаю, что процессоры AArch64 чаще всего не останавливаются или не так уж плохо при перемещении данных между целочисленными и векторными регистрами, но без CSSC они находятся в одной лодке; см. выходные данные компилятора.)

В GCC13 добавлена ​​поддержка CSSC, которую необходимо включить вручную с помощью-march=armv8-a+cssc. Даже-march=armv9.3-aне позволяет GCC или clang использовать его (Godbolt) для C++20std::popcount(т.е. для__builtin_popcount()) без+csscчасть.-mcpu=cortex-x3и-mcpu=cortex-a710не включайте его, поэтому я предполагаю, что у них его нет.

Answer 8

Если у вас нет инструкции popcnt, обычно это делается с помощью инструкции vperm/pshufb/vtbl для поиска количества битов в таблице с помощью инструкции перемешивания. Примерно в псевдокоде:

      ucharN someVector = …;
ucharN lowNibbles = someVector & 0xf;
ucharN highNibbles = someVector >> 4;

static const ucharN popcntTable = { 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4…}; // vector[i] = popcnt(i)
return vtblq_u8(lowNibbles, popcntTable) + 
       vtblq_u8(highNibbles, popcntTable);

В зависимости от векторной арки вам потребуется настроить размер таблицы и значения таблицы в соответствии с особенностями инструкции тасования, такими как барьер AVX2 в середине регистра или 8-байтовый блок тасования Arm32. Возможно, у меня также поменялись аргументы vtbl. Надеюсь, вы поняли идею.