Как используется странная инструкция popcount в современных процессорах

Автор оригинала: Vaibhav Sagar
  • Перевод
Это псевдорасшифровка моей презентации на !!Con 2019.

В большинстве используемых сегодня процессорных архитектур есть инструкция под названием popcount, сокращённо от 'population count'. Она делает следующее: подсчитывает количество установленных битов в машинном слове. Например (возьмём 8-битные слова для простоты), popcount(00100110) равно 3, а popcount(01100000) равно 2.

Вас это может сильно удивить, как и меня, но это всё, что она делает! Кажется не очень полезным, правда?

Я думал, что это какое-то недавнее дополнение для некоторых гиперспециализированных вариантов использования, но на самом деле она присутствует в архитектурах процессоров, по крайней мере, с 1961 года:


Так что же происходит?

Инструкция АНБ


popcount также известна как «инструкция АНБ», и в очень интересном треде на comp.arch обсуждается её использование в криптографии. Ходят слухи, что её первоначально добавили в набор инструкций CPU по просьбе АНБ. Как сказано в этом архивированном почтовом треде:

Было почти традицией одну из каждой партии более быстрых машин CDC отправлять «хорошему клиенту» — приезжал неизвестный грузовик, и больше о ней никогда не слышали.

Отличная легенда, но для чего они её использовали?

Один из показателей информационного содержания — вес Хэмминга, который представляет собой количество ненулевых символов в строке. Для двоичной строки это именно popcount!

Как объяснялось здесь, АНБ требовалось проводить криптоанализ перехваченных сообщений, а поскольку CDC 6000 работала с 60-битными словами, одного слова было достаточно для хранения большинства алфавитов, которые их интересовали. Они были в состоянии:

  1. Разбить сообщение на строки
  2. Установить бит для каждого уникального символа в строке
  3. Использовать popcount для подсчёта числа разных символов
  4. Использовать счётчик в качестве хэша для дальнейшего криптоанализа

Любопытно, что popcount, похоже, исчез из наборов инструкций между серединой 1970-х и серединой 2000-х годов, поэтому возвращение должно объясняться чем-то ещё, кроме криптографических приложений. Для чего ещё её можно использовать?

Исправление ошибок


С понятием веса Хэмминга связано расстояние Хэмминга, которое представляет собой количество различных позиций между двумя строками одинаковой длины. Для двух двоичных строк x и y, это просто popcount после XOR. Например:

00100110
01100000 ^
--------
01000110

popcount(01000110) = 3

В телекоммуникационных приложениях это помогает вычислить расстояние сигнала, где по проводу передаётся известное слово и подсчитывается количество изменённых битов, чтобы оценить ошибку передачи.

Затем мы можем спроектировать соответствующий код исправления ошибок. Например, если передача должна выдерживать до двух изменённых битов, то кодовые слова должны отличаться по расстоянию Хэмминга по крайней мере на 5.

Бинарные свёрточные нейросети


А теперь нечто совсем иное: двоичные свёрточные нейронные сети! Но сначала, что это такое?

  • Бинарность означает, что мы используем матрицы только из значений +1 (кодируется как 1) и -1 (кодируется как 0), в отличие от 32-разрядных значений с плавающей запятой.
  • Свёртка означает умножение матриц?
  • Нейронные сети — это системы, вдохновлённые мозгом животных (здесь я немного плаваю).

Таким образом, мы должны выполнить умножение бинарных матриц. Но что особенного в бинарных матрицах?

Обычное умножение матриц на 32-битные значения хорошо подходит для настольных компьютеров с мощными CPU и GPU, но всё чаще мы хотим выполнять полезную работу на небольших и простых устройствах, таких как смартфоны, маршрутизаторы, умные часы и т. д. Мы можем разложить эти более сложные матрицы на слои бинарных матриц, а с ними настолько легче работать и хранить их, что мы в выигрыше даже несмотря на увеличение количества слоёв.

Тут вступает в игру popcount. Он используется для вычисления скалярного произведения двух бинарных матриц:

a = xnor(x, y)
b = popcount(a)
c = len(a)
dot(x, y) = 2 × b − c

Более подробно см. здесь и здесь.

Шахматное программирование


Многие шахматные программы хранят данные в представлении bitboard, которое удобно вписывается в 64-битное слово. Операция Population Count использовалась для значимых операций с этим представлением, таких как вычисление подвижности фигуры.

Молекулярный фингерпринтинг


Это тоже связано с расстоянием Хэмминга: молекулы каким-то образом хэшируются и сравниваются (с помощью popcount), чтобы определить степень их похожести. Подробнее см. здесь.

Hash array mapped tries (HAMT)


Вот где я впервые узнал о popcount! HAMT — это структура данных (впервые созданная Филом Бэгвеллом), которая может хранить очень большое количество значений (обычно 32 или 64) в массиве на каждом узле trie. Однако выделение памяти для 32 или 64-элементного массива каждый раз может быть невероятно расточительным, особенно если массив на самом деле содержит всего несколько элементов. Решение состоит в том, чтобы добавить битовую маску, в которой количество установленных бит соответствует количеству элементов в массиве, что позволяет массиву расти и сжиматься по мере необходимости. Вычисление индекса для данного элемента эффективно может быть сделано с помощью popcount. В моём блог-посте с реализацией структур HAMT можете узнать больше, как они работают.

Сжатые структуры данных


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

  • rank(i) подсчитывает количество бит, заданных до i-го индекса в бит-векторе
  • select(i) находит индекс, в котором установлен i-й бит

Чтобы сделать эти операции эффективными на больших бит-векторах, требуется построить индекс и эффективно его использовать, в обоих случаях с участием popcount. Вот здесь есть хороший обзор индекса RRR. И, насколько я могу судить, самый передовой современный подход описан в статье Space-Efficient, High-Performance Rank & Select Structures on Uncompressed Bit Sequences.

Оптимизации компиляторов


popcount стала настолько распространённой, что и GCC, и Clang способны её обнаружить и заменить встроенной инструкцией. Представьте такого Клиппи: «О, я вижу, что вы пытаетесь реализовать popcount, позвольте мне выйти и исправить это для вас»! Соответствующий код LLVM находится здесь. Даниэль Лемир приводит его как пример удивительного ума современных компиляторов.

Вывод


Окутанная тайной в начале своей истории, инструкция popcount стала повсеместно использоваться, хотя и осталась немного необычной инструкцией CPU. Мне нравится, как она связывает такие разные области информатики, и мне интересно, сколько ещё существует других таких же странных инструкций. Если у вас есть своя любимая, хотелось бы услышать о ней!
Поддержать автора
Поделиться публикацией
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама

Комментарии 19

    +2
    Есть две отличные статьи на хабре на этот счёт: раз и два.

    В общем-то, чем больше машинных инструкций имеет вычислительное устройство, тем лучше пользователю этого устройства.
    Однако редкий реальный продукт (даже числомолотилка) будет действительно интенсивно использовать popcnt.
    По сути, хороший алгоритм позволяет заменить эту инструкцию очень небольшим количеством базовых инструкций.
    Выигрыш в несколько тактов при подсчёте единиц — хорошо. Если на 10 инструкций приходится один вызов popcnt, то его замена базовыми инструкциями снизит производительность очень значительно.
    А вот если один popcnt на 100 инструкций — то уже всего 10%.
    И требовать наличия особенной инструкции, особенно когда у тебя в коде подсчёт выполняется два с половиной раза, не очень-то разумно.
    В одном случае (вторая из ссылок выше) людям поломали драйвер.
    Другой пример — в Quantum Break было требование по наличию popcnt, и Remedy с честными глазами заявляли «Нет, нам это действительно нужно для рендера. Не перекомпилим». А по факту замена двух байт в библиотеке рендера на NOPы делало игру полностью работоспособной без popcnt. И притом с хорошей производительностью.

    Поэтому выигрывая несколько тактов на редких инструкциях, не стоит забывать о совместимости.
      +1
      Ага хорошая инструкция, выполняется за один такт, если конечно не реализована микрокодом, процессор может как правило выполнить несколько таких инструкций за такт(AMD Athlon II X4 640). Лично я её использовал в решении шахматной задачи «Надо расставить19 ферзей так, чтобы группа белых ферзей, не били группу черных ферзей, и на оборот». У меня на одно ядро, задача решалась за 20-25 миллисек для доски 8х8. Частота процессора 3ГГц. В общем можно хорошо ускорить код, если выполняется массированный подсчёт бит.
      ЗЫ
      В gcc не правильная реализация этой функции, т.е. интринстика, надо чтобы было dword ...(dword) а не byte ...(dword), из-за этого компилятор вставляет совершенно лишнею команду преобразования movzx.
        +2
        В Паскале множество
        S : set of 1..8;
        занимало байт и значение
        S :=[1,8];
        представлялось единичным младшим и старшим битами, остальные нули. С помощью popcount легко и быстро посчитать мощность такого множества.
          +1

          С использованием как раз все понятно, но почему она называется не bitcount, например?

            +1

            Видимо потому что считает не сами биты а только количество единиц в данном массиве бит (те что pops out?). Интерпретации названия в документации к команде не припомню. Также беглый гуглеж выдал что-то про population count, что тоже может быть притянуто.

              0

              Кстати, в Java она как раз таки называется bitCount.

              0

              На Hacker News недавно обсуждалось это (наверное та же статья, т.к. очень часто переводы статей с HN появляются здесь), и кто-то писал что современные наборы инструкций (какие-то там из AVX) позволяют считать быстрее, чем popcnt. Кто-то там приводил ссылку на конкретную реализацию. Посколько я уже лет 30 не брал в руки ассемблер, то в подробности не вчитывался и не запомнил, но думаю, желающие смогут быстро найти.

                0

                Мы как-то сравнивали разные подходы в разрезе типовой задачи на собеседовании "посчитать количество бит". Сильно отличается от процессора к процессору, на x64 интелах лучше всех векторизовался вот этот подход, но я не уверен что он будет быстрее современных же popcnt. Ссылку на все битхаки уже приводили ниже.


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

                  Я в этом ничего не понимаю, мое понимание ассемблера заканчивается на уровне Intel 8086. Возможно 80286. Но одну из ссылок нашел:
                  http://0x80.pl/articles/sse-popcount.html

                    +1

                    А кстати да, я нашёл свой тестовый код. Компилятор достаточно умный чтобы свернуть натуральный подсчёт битов в popcnt. Результаты с AVX (magic) действительно быстрее:
                    Собирается через


                    $ gcc -O3 -mavx bitcount.c

                    Number of bits (natural): 3100008771 in 160 ms
                    Number of bits (lookup) : 3100008771 in 297 ms
                    Number of bits (magic)  : 3100008771 in 134 ms

                    Пробуйте добавлять свои эксперименты, узнаем кто самый быстрый :) Кстати на АРМ ситуация в корне другая, так как нет AVX.


                    Исходный код

                    Писался на перерыве на коленке, так что не придираться.


                    #include <stdio.h>
                    #include <stdlib.h>
                    #include <stdint.h>
                    #include <time.h>
                    
                    #define ARR_SIZE (200 * 1000 * 1000)
                    #define LOOKUP_TABLE_SIZE 256
                    #define CLOCKS_PER_MS (CLOCKS_PER_SEC / 1000)
                    
                    static uint8_t _bits_lookup_table[LOOKUP_TABLE_SIZE];
                    
                    void initLookupTable() {
                        _bits_lookup_table[0] = 0;
                        for (int i = 1; i < LOOKUP_TABLE_SIZE; i++) {
                        _bits_lookup_table[i] = _bits_lookup_table[i / 2] + (i & 1);
                        }
                    }
                    
                    uint32_t countBitsLookup(uint32_t *arr, uint32_t size) {
                        uint32_t counter = 0;
                        for (uint32_t i = 0; i < size; i++) {
                            uint8_t *bytearr = (uint8_t*)(arr++);
                    
                            counter += _bits_lookup_table[*bytearr++];
                            counter += _bits_lookup_table[*bytearr++];
                            counter += _bits_lookup_table[*bytearr++];
                            counter += _bits_lookup_table[*bytearr];
                        }
                        return counter;
                    }
                    
                    uint32_t countBitsNatural(uint32_t *arr, uint32_t size) {
                        uint32_t counter = 0;
                        for (uint32_t i = 0; i < size; i++) {
                        for (uint32_t val = arr[i]; val > 0; val &= val - 1) {
                            counter++;
                        }
                        }
                        return counter;
                    }
                    
                    uint32_t countBitsMagic(uint32_t *arr, uint32_t size) {
                        uint32_t counter = 0;
                        for (uint32_t i = 0; i < size; i++) {
                        uint32_t val = arr[i];
                            val = val - ((val >> 1) & 0x55555555);                      // reuse input as temporary
                            val = (val & 0x33333333) + ((val >> 2) & 0x33333333);       // temp
                            counter += ((val + (val >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;// count
                        }
                        return counter;
                    }
                    
                    uint32_t *randomArray(uint32_t size) {
                        uint32_t *arr = (uint32_t*) malloc(size * sizeof(uint32_t));
                        for (uint32_t i = 0; i < size; i++) {
                        arr[i] = rand();
                        }
                        return arr;
                    }
                    
                    int main(void) {
                        srand(clock());
                        initLookupTable();
                        uint32_t *array = randomArray(ARR_SIZE);
                    
                        clock_t ts = clock();
                    
                        uint64_t bits_1 = countBitsNatural(array, ARR_SIZE);
                        ts = clock() - ts;
                        printf("Number of bits (natural): %zu in %zu ms\n", bits_1, ts / CLOCKS_PER_MS);
                    
                        ts = clock();
                        uint64_t bits_2 = countBitsLookup(array, ARR_SIZE);
                        ts = clock() - ts;
                        printf("Number of bits (lookup) : %zu in %zu ms\n", bits_2, ts / CLOCKS_PER_MS);
                    
                        ts = clock();
                        uint64_t bits_3 = countBitsMagic(array, ARR_SIZE);
                        ts = clock() - ts;
                        printf("Number of bits (magic)  : %zu in %zu ms\n", bits_3, ts / CLOCKS_PER_MS);
                    }
                    

                    Ассемблер

                    Видно как раз мощную векторизацию в случае подсчёта формулой из битхаков.


                      401440:       c5 f9 72 d1 01          vpsrld $0x1,%xmm1,%xmm0
                      401445:       c5 f9 db c5             vpand  %xmm5,%xmm0,%xmm0
                      401449:       c5 f1 fa c8             vpsubd %xmm0,%xmm1,%xmm1
                      40144d:       c5 f9 72 d1 02          vpsrld $0x2,%xmm1,%xmm0
                      401452:       c5 f1 db cb             vpand  %xmm3,%xmm1,%xmm1
                      401456:       c5 f9 db c3             vpand  %xmm3,%xmm0,%xmm0
                      40145a:       c5 f9 fe c1             vpaddd %xmm1,%xmm0,%xmm0
                      40145e:       c5 f1 72 d0 04          vpsrld $0x4,%xmm0,%xmm1
                      401463:       c5 f1 fe c8             vpaddd %xmm0,%xmm1,%xmm1
                      401467:       c5 f1 db cc             vpand  %xmm4,%xmm1,%xmm1
                      40146b:       c5 f9 72 f1 08          vpslld $0x8,%xmm1,%xmm0
                      401470:       c5 f9 fe c1             vpaddd %xmm1,%xmm0,%xmm0
                      401474:       c5 f1 72 f0 10          vpslld $0x10,%xmm0,%xmm1
                      401479:       c5 f9 fe c1             vpaddd %xmm1,%xmm0,%xmm0
                      40147d:       c5 f9 72 d0 18          vpsrld $0x18,%xmm0,%xmm0
                      401482:       c5 e9 fe d0             vpaddd %xmm0,%xmm2,%xmm2

                    А это как компилятор оптимизировал подсчёт бит в цикле:


                    00000000004013b0 <countBitsNatural>:
                      4013b0:       85 f6                   test   %esi,%esi
                      4013b2:       74 2a                   je     4013de <countBitsNatural+0x2e>
                      4013b4:       8d 46 ff                lea    -0x1(%rsi),%eax
                      4013b7:       45 31 c0                xor    %r8d,%r8d
                      4013ba:       48 8d 4c 87 04          lea    0x4(%rdi,%rax,4),%rcx
                      4013bf:       90                      nop
                      4013c0:       8b 17                   mov    (%rdi),%edx
                      4013c2:       31 c0                   xor    %eax,%eax
                      4013c4:       f3 0f b8 c2             popcnt %edx,%eax
                      4013c8:       44 01 c0                add    %r8d,%eax
                      4013cb:       85 d2                   test   %edx,%edx
                      4013cd:       44 0f 45 c0             cmovne %eax,%r8d
                      4013d1:       48 83 c7 04             add    $0x4,%rdi
                      4013d5:       48 39 f9                cmp    %rdi,%rcx
                      4013d8:       75 e6                   jne    4013c0 <countBitsNatural+0x10>
                      4013da:       44 89 c0                mov    %r8d,%eax
                      4013dd:       c3                      retq
                      4013de:       45 31 c0                xor    %r8d,%r8d
                      4013e1:       44 89 c0                mov    %r8d,%eax
                      4013e4:       c3                      retq
                      4013e5:       66 66 2e 0f 1f 84 00    data16 nopw %cs:0x0(%rax,%rax,1)
                      4013ec:       00 00 00 00
                      0
                      если перевести в биты и подумать, то там достаточно просто:

                      первая строка:
                      (посмотрите на пары бит: 0b00 — это 0, 0b01 — 1 бит, 0b10 — 1 бит, 0b11 — это 2 бита) или если переводить в двоичные числа 0b00->0b00, 0b01->0b01, 0b10->0b01, 0b11->0b10. 0x5 в битах — это 0b0101, так что после первой строки у вас уже не биты числа — а массив сумм пар бит;

                      вторая строка:
                      v & 0b0011......0011 + (v & 1100...1100) >> 2
                      т.е. суммируем пары бит между собой, и теперь у нас массив сумм бит по четыре бита;

                      третья строка:
                      сначала v + ( v & 0b11110000....1111000 ) >> 4 — получаем из массива бит по 4бита, массив по сумм по 8 бит (обозначим его как s), а потом умножение на 0x1010101 — это на самом деле сумма умножений
                      s* 0x01000000 + s * 0x00010000 +… + s* 0x00000001 или если учитывать, что при переполнении старшие биты отбрасываются — это будет эквивалентно сумме сдвигов
                      s << 24 + s << 16 + s << 8 + s — так что в старшем байте будет сумма их всех, и сдвигом вправо на 24 вы получаете ответ.
                  +2
                  Математический трюк, считаем единички в x за линейное от числа единичек время:
                  cnt=0;
                  while (x>0) {
                  x = (x-1) & x;
                  cnt++;
                  }
                      0
                      Алгоритм, конечно, очень красивый и элегантный, но не вполне дружественный к предсказателю ветвлений. На не слишком разреженных данных будет много непредсказуемых проверок.
                      +2
                      Почему это инструкция странная? Когда работаешь с битовыми массивами/картами, подсчет количества бит очень популярная задача. Конечно использование 8-битных lookup таблиц или RLE кодирование с использованием intrinsic'ов __builtin_ctz()/_BitScanForward() (для разреженных данных) не сильно медленнее, но все равно инструкция полезная.
                        +1
                        У меня была похожая задача. Делал моно-синтезатор. Там нужно выводить ноту нажатой клавиши. Но если нажато несколько, то брать ту, что выше остальных. Делал на ПЛИСе чисто аппаратно (а не программно). Все клавиши были одним битовым словом. Но как выбрать номер самого старшего бита? Сначала пробовал циклы какие-то. Не то, чтобы мне было принципиально сделать за 1 такт. Но в итоге пришел к Priority Encoder. Находил много разных реализаций, громоздких в основном, или табличных. Но картинки из советских книжек натолкнули на решение на обычной асинхронной логике. Все получилось и я даже закинул его на всякий случай на OpenCores. Конечно, количество установленных бит могло пригодиться, но не в этом варианте, тк был всего один голос. Для меня было важно, чтобы битов было установлено больше нуля (а это попроще, чем посчитать количество).
                          0
                          В структуре данных Roaring bitmaps очень активно применяется эта инструкция и не только она.
                            0
                            В машине «Маршрут-1» была такая инструкция для вычисления количества занятых мест в вагоне.
                              0
                              Кому интересно, GEMM_BIN функция перемножения бинарных матриц для бинарных нейронных сетей (Например, Yolov3 xnor net) — используют POPCNT инструкцию:


                              На Low-power devices работает до 30 раз быстрее, чем с Float-32-bit.
                              Высокая точность достигается с применением обучения с online-SVR.

                              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                              Самое читаемое