В большинстве используемых сегодня процессорных архитектур есть инструкция под названием
popcount, сокращённо от 'population count'. Она делает следующее: подсчитывает количество установленных битов в машинном слове. Например (возьмём 8-битные слова для простоты), popcount(00100110) равно 3, а popcount(01100000) равно 2.Вас это может сильно удивить, как и меня, но это всё, что она делает! Кажется не очень полезным, правда?
Я думал, что это какое-то недавнее дополнение для некоторых гиперспециализированных вариантов использования, но на самом деле она присутствует в архитектурах процессоров, по крайней мере, с 1961 года:
- 1961: IBM Stretch
- 1964: CDC 6000
- 1975: Cray-1
- 2005: SPARC
- 2005: ARM NEON
- 2007: AMD K10
- 2008: Intel Nehalem
Так что же происходит?
Инструкция АНБ
popcount также известна как «инструкция АНБ», и в очень интересном треде на comp.arch обсуждается её использование в криптографии. Ходят слухи, что её первоначально добавили в набор инструкций CPU по просьбе АНБ. Как сказано в этом архивированном почтовом треде:Было почти традицией одну из каждой партии более быстрых машин CDC отправлять «хорошему клиенту» — приезжал неизвестный грузовик, и больше о ней никогда не слышали.
Отличная легенда, но для чего они её использовали?
Один из показателей информационного содержания — вес Хэмминга, который представляет собой количество ненулевых символов в строке. Для двоичной строки это именно
popcount!Как объяснялось здесь, АНБ требовалось проводить криптоанализ перехваченных сообщений, а поскольку CDC 6000 работала с 60-битными словами, одного слова было достаточно для хранения большинства алфавитов, которые их интересовали. Они были в состоянии:
- Разбить сообщение на строки
- Установить бит для каждого уникального символа в строке
- Использовать
popcountдля подсчёта числа разных символов
- Использовать счётчик в качестве хэша для дальнейшего криптоанализа
Любопытно, что
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. Мне нравится, как она связывает такие разные области информатики, и мне интересно, сколько ещё существует других таких же странных инструкций. Если у вас есть своя любимая, хотелось бы услышать о ней! Комментарии (18)
DeuterideLitium6
12.09.2019 00:55Ага хорошая инструкция, выполняется за один такт, если конечно не реализована микрокодом, процессор может как правило выполнить несколько таких инструкций за такт(AMD Athlon II X4 640). Лично я её использовал в решении шахматной задачи «Надо расставить19 ферзей так, чтобы группа белых ферзей, не били группу черных ферзей, и на оборот». У меня на одно ядро, задача решалась за 20-25 миллисек для доски 8х8. Частота процессора 3ГГц. В общем можно хорошо ускорить код, если выполняется массированный подсчёт бит.
ЗЫ
В gcc не правильная реализация этой функции, т.е. интринстика, надо чтобы было dword ...(dword) а не byte ...(dword), из-за этого компилятор вставляет совершенно лишнею команду преобразования movzx.
third112
12.09.2019 03:53В Паскале множество
занимало байт и значениеS : set of 1..8;
представлялось единичным младшим и старшим битами, остальные нули. С помощью popcount легко и быстро посчитать мощность такого множества.S :=[1,8];
pronvit
12.09.2019 04:37С использованием как раз все понятно, но почему она называется не bitcount, например?
Cenzo
12.09.2019 05:10Видимо потому что считает не сами биты а только количество единиц в данном массиве бит (те что pops out?). Интерпретации названия в документации к команде не припомню. Также беглый гуглеж выдал что-то про population count, что тоже может быть притянуто.
eumorozov
12.09.2019 07:47На Hacker News недавно обсуждалось это (наверное та же статья, т.к. очень часто переводы статей с HN появляются здесь), и кто-то писал что современные наборы инструкций (какие-то там из AVX) позволяют считать быстрее, чем
popcnt. Кто-то там приводил ссылку на конкретную реализацию. Посколько я уже лет 30 не брал в руки ассемблер, то в подробности не вчитывался и не запомнил, но думаю, желающие смогут быстро найти.Cenzo
12.09.2019 21:43Мы как-то сравнивали разные подходы в разрезе типовой задачи на собеседовании "посчитать количество бит". Сильно отличается от процессора к процессору, на 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; // counteumorozov
12.09.2019 21:48Я в этом ничего не понимаю, мое понимание ассемблера заканчивается на уровне Intel 8086. Возможно 80286. Но одну из ссылок нашел:
http://0x80.pl/articles/sse-popcount.htmlCenzo
12.09.2019 21:58+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); }vassabi
13.09.2019 00:08если перевести в биты и подумать, то там достаточно просто:
первая строка:
(посмотрите на пары бит: 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 вы получаете ответ.
ofmetal
12.09.2019 10:18Математический трюк, считаем единички в x за линейное от числа единичек время:
cnt=0;
while (x>0) {
x = (x-1) & x;
cnt++;
}WinPooh73
12.09.2019 12:43Алгоритм, конечно, очень красивый и элегантный, но не вполне дружественный к предсказателю ветвлений. На не слишком разреженных данных будет много непредсказуемых проверок.
avdx
12.09.2019 11:59Почему это инструкция странная? Когда работаешь с битовыми массивами/картами, подсчет количества бит очень популярная задача. Конечно использование 8-битных lookup таблиц или RLE кодирование с использованием intrinsic'ов __builtin_ctz()/_BitScanForward() (для разреженных данных) не сильно медленнее, но все равно инструкция полезная.
UA3MQJ
12.09.2019 12:46У меня была похожая задача. Делал моно-синтезатор. Там нужно выводить ноту нажатой клавиши. Но если нажато несколько, то брать ту, что выше остальных. Делал на ПЛИСе чисто аппаратно (а не программно). Все клавиши были одним битовым словом. Но как выбрать номер самого старшего бита? Сначала пробовал циклы какие-то. Не то, чтобы мне было принципиально сделать за 1 такт. Но в итоге пришел к Priority Encoder. Находил много разных реализаций, громоздких в основном, или табличных. Но картинки из советских книжек натолкнули на решение на обычной асинхронной логике. Все получилось и я даже закинул его на всякий случай на OpenCores. Конечно, количество установленных бит могло пригодиться, но не в этом варианте, тк был всего один голос. Для меня было важно, чтобы битов было установлено больше нуля (а это попроще, чем посчитать количество).
Dimchansky
12.09.2019 15:05В структуре данных Roaring bitmaps очень активно применяется эта инструкция и не только она.
SourenTopchian
12.09.2019 16:50В машине «Маршрут-1» была такая инструкция для вычисления количества занятых мест в вагоне.
Boroda1
Есть две отличные статьи на хабре на этот счёт: раз и два.
В общем-то, чем больше машинных инструкций имеет вычислительное устройство, тем лучше пользователю этого устройства.
Однако редкий реальный продукт (даже числомолотилка) будет действительно интенсивно использовать popcnt.
По сути, хороший алгоритм позволяет заменить эту инструкцию очень небольшим количеством базовых инструкций.
Выигрыш в несколько тактов при подсчёте единиц — хорошо. Если на 10 инструкций приходится один вызов popcnt, то его замена базовыми инструкциями снизит производительность очень значительно.
А вот если один popcnt на 100 инструкций — то уже всего 10%.
И требовать наличия особенной инструкции, особенно когда у тебя в коде подсчёт выполняется два с половиной раза, не очень-то разумно.
В одном случае (вторая из ссылок выше) людям поломали драйвер.
Другой пример — в Quantum Break было требование по наличию popcnt, и Remedy с честными глазами заявляли «Нет, нам это действительно нужно для рендера. Не перекомпилим». А по факту замена двух байт в библиотеке рендера на NOPы делало игру полностью работоспособной без popcnt. И притом с хорошей производительностью.
Поэтому выигрывая несколько тактов на редких инструкциях, не стоит забывать о совместимости.