Статьи / dotNET / Производительность dotNET / Performance
Давно я сюда не писал, обходился Telegram и Twitter, но поля их слишком малы, чтобы вместить эту статью :)
Для небольшого исследования в области упаковки чисел мне понадобилось получить минимальное количество бит, требуемое для записи числа.
Его, конечно, математически можно получить с помощью двоичного логарифма “округлённого к большему целому” (буду использовать обозначение lg n).
Как вы, вероятно, знаете, в .NET Core 3.0 появились intrinsic’и[1], в частности, LZCNT. Она, конечно, возвращает leading zeroes,
но вычесть-то из 31 (для индекса в каком-нибудь массиве) или из 32 (для количества бит на число) недолго.
Однако, мне было интересно узнать и универсальное решение. В .NET Core 3.0, к счастью, добавили для этого класс BitOperations[2].
А мне, конечно же, захотелось посмотреть его исходники…
Ожидаемо, используются статические методы с AggressiveInlining, которые проверяют доступность intrinsic’ов и, если их нет, пользуются софтовой реализацией.
А вот здесь начинается интересное. Есть семейство алгоритмов, основанных на последовательностях де Брёйна (de Bruijn), которые позволяют делать оптимизации для некоторых битовых операций.
Есть статья 1998 года[3], хорошо описывающая алгоритм поиска установленных битов в числе. Далее будет краткий пересказ, но с пояснениями для тех, кто, как и я, не особо плотно занимается подобными алгоритмами (они, обычно, используются в компьютерной графике или шахматных программах).
Это можно сделать за счёт того, что отрицательные числа (почти на всех процессорах) хранятся как «дополнительный код»[4].
Например, если сложить два 32-битных int’a x и -x (x > 0), как без-знаковые 64-битные целые, то получим число с нулями в младших 32-х битах, а в 33-ем будет 1.
Понятно, что для 32-битных операций 33 бит просто отбрасывается и получаем, внезапно, 0 :)
Из этого следует, что у -x, по сравнению с x, все биты должны быть «перевёрнуты», кроме самой младшей единички (тогда сложение и даст все нули).
Например, если x = 01101000, то -x = 10011000.
Поэтому для получения самого младшего бита достаточно просто сделать так: y = x & (-x).
А для получения следующего установленного бита достаточно посчитать x-y и, если получился не ноль, повторить алгоритм.
Очевидно, что для n-битного целого есть ровно n чисел с единственным установленным битом. N маленькое (32, ну, максимум, 64), поэтому напрашивается вариант использовать хеш-функцию, но не простую, а идеальную (без коллизий). Да, я уже немного спойлернул, что для этого будут использоваться…
Не буду выпендриваться и говорить, что они всем известны — лично я про них узнал из этой статьи.
Если совсем кратко и для алфавита из 0 и 1, то это последовательность из n символов, каждая подстрока длины lg n которой уникальна.
Подробнее можно прочитать в википедии[5]. Максимальная последовательность, содержащая все возможные подстроки, называется циклом де Брёйна.
Например, для n = 8 это могут быть 00011101 или 00010111, для которых окно из 3 символов даёт уникальные значения (в т.ч. со сдвигом за границы).
За счёт их свойств, циклы де Брёйна идеально подходят для нашей хеш-функции — нужно всего лишь умножить на целочисленную константу и сдвинуть биты на константу,
чтобы получить хеш-таблицу размера n без коллизий:
h(x) = (x * deBruijn) >> (n - lg n)
За счёт чего работает магия? Спрятал под спойлер, чтобы была возможность сначала ответить самостоятельно.
Напоминаю, x — это число с единственным установленным битом (допустим, на k-ом месте). Значит, умножив его на цикл де Брёйна,
мы сдвигаем последовательность де Брёйна на k влево. Теперь, раз уж мы взяли цикл де Брёйна с lg n лидирующими нулями, сдвигаем его вправо на (n - lg n) бит.
Вуаля! Мы получили гарантированно уникальное число размером lg n бит (в случае с байтами — число от 0 до 7).
В статье делаются выводы о том, что алгоритм весьма хорош для софтовых реализаций и, разумеется, немного проигрывает нативной реализации (когда она есть в процессоре). На всякий случай, напоминаю — статья 1998 года.
Если вы посмотрите на исходный код BitOperations.Log2(uint)[2], то увидите, что:
Lzcnt и ArmBase.Log2SoftwareFallback.Давайте немного посмотрим на Log2SoftwareFallback. Сначала, изящным хаком, все биты справа от лидирующих нулей заполняются единицами
(если нулей слева нет вообще, получим 0xFFFFFFFF):
Если вдруг этот хак не очень понятен, попробуйте нарисовать в уме или на бумаге какую-нибудь строку из рандомных 0 и 1, а на второй строке сдвинуть её вправо (для начала, на 1 бит) и применить битовый OR.
Если вы помните, раньше речь шла о точной степени двойки, а теперь мы получили число 2k-1, для которого некий Марк Дикинсон
придумал специальный цикл де Брёйна, чтобы не делать лишних операций по получению 2k (value-- в начале и value++ в конце).
Как работает этот хак я уже сходу не смог разобраться (да и не только я[7]). Если кто-то разберётся — прошу поделиться в твиттере.
Хотя, конечно, всегда есть вариант, что это число найдено брутфорсом…
Для моей конкретной задачи получение lg n пока не очень критично по скорости, а сильно заранее экономить на спичках неохота,
поэтому я просто возьму BitOperations.Log2. Если когда-то придётся разворошить этот спичечный коробок, я учту, в том числе, что мне не нужно проверять на 0
(особенность распределения) и можно сделать отдельный класс (или сборку), заточенный под поддерживаемые процессоры.
Я же не MS, мне не надо поддерживать все возможные конфигурации :)
Спасибо за внимание!
Статьи / dotNET / Производительность dotNET / Performance