x86 Проверка и сброс битов btr eax, 7 делает именно то, что вы просили: сбросить бит 7 и установить CF = исходное значение этого бита.
btr reg, imm или reg, reg составляет 1 моп для Intel, 2 моп для AMD. Когда за ним следует инструкция jcc, он не может слиться макросом в одну операцию сравнения и ветвления, как это делает test al, 1<<7 / jnz. (https://agner.org/optimize/). Количество команд - не единственный фактор производительности . Хорошие ILP и короткие критические задержки, особенно во избежание ненужных цепочек зависимостей, переносимых l oop, также важны. Но подсчет входных мопов для быстрого пути в вашем коде, безусловно, стоит учесть.
x86 сдвиги (как и большинство ISA) помещают последний сдвинутый бит в флаг переноса. Так shr al, 1 устанавливает CF = orig & 1 и обновляет AL = orig >> 1. Возможно, есть способ объединить это со сдвигом битов в байтах, чтобы объединить их, как с shrd, или с помощью трюков с частичной регистрацией ...
Поскольку вы манипулируете байтами, Почему нет G CC использовать частичные регистры? - это то, что вы, возможно, захотите понять, если задумаетесь о способах объединения нескольких битовых полей в одно непрерывное большее целое число в регистре.
Я хочу хранить большие числа в последовательности 8-битных значений
Я надеюсь, что вы не планируете вычислять напрямую с числами в этом формате. Это звучит разумно в качестве компактного формата / кодирования сериализации переменной длины, который может быть меньше int для небольших значений, но при этом содержать до uint64_t или даже больше, если необходимо.
Если общая скорость больше важно, работать как минимум 32-битными блоками, так что вы получаете гораздо больше битов результата за операцию ЦП. Или так меньше шагов распаковки для объединения в одно смежное двоичное целое число. (например, переменное смещение AVX2 vpsrlvd, чтобы поместить вершину одного меча рядом с нижней частью меча в следующем более высоком элементе, затем используйте сдвиги переменных qword, чтобы сделать то же самое в середине 128 -битная полоса. Затем сдвиг байтов или случайное перемешивание.
(Однако вы можете сделать это для 16-разрядных элементов с 16-разрядным pmullw, умножив его на степень 2 (или 1), если вы используйте 16-битные порции, либо AVX512BW с переменным числом или 16-битные сдвиги с маской слияния, либо 8-битные порции с pmaddubsw, чтобы даже объединить в нижней части элементы SIMD с правильными множителями: 1 и 1<<7 для младших и старших байтов каждой пары после маскировки сигнальных битов.)
Байты обычно являются ошибкой для материала BigInteger в целом . См. этот обзор обзора кода на BigInt класс в C ++ (который неразумно планировал хранить числа в массивах десятичных цифр ASCII). 30 битов значения в 32-битном блоке могут быть полезны для переносимых вещей (например, Python использует внутренне). Вы можете работать в база л ike 10 ^ 9, если вы выполняете много преобразований в / из десятичных строк, или 2 ^ 30, если нет.
Не использование всех битов на ветку позволяет отложить перенос (не нормализацию) для SIMD: Могут ли длинные целочисленные подпрограммы получить пользу от SSE? . Это может работать с 1 резервным битом для переноса и верхним битом, предназначенным для вашей стратегии сигнализации для неявной длины вместо хранения длины. (Многие инструкции x86 SIMD, такие как blendvps или movmskps, делают верхний бит SIMD-элемента dword особенным или каждого байта для целочисленного SIMD, например pmovmskb, pshufb и pblendvb. Таким образом, вы можете получить битовая маска старших битов, которые можно отсканировать с помощью bsf или bsr, чтобы найти первый установленный бит.)
Распаковка идей:
Если вы выберете старшую биту бит каждого байта = 0 в пределах целого числа, и 1 для обозначения конца, что позволяет избежать битовых наборов битов, которые необходимо очистить.
Как упоминалось ранее, pmaddubsw является хорошей идеей для SIMD объединять байты в 16-битные слова, с правильными множителями 1 и 1<<7.
Затем еще один шаг с pmaddwd может объединить слова в слова с 1, 1<<14, тогда вы настроены для AVX2 vpsrlv или просто сдвинуть и смешать. Все это затем принимает log2 (vector_length) число шагов вместо vector_length steps.
Без SIMD вы можете использовать x += x в качестве сдвига влево, но сделать это только сдвигом некоторых бит делая x += x & mask. Это работает для скаляра или с paddb, если у вас нет SSSE3 pmaddubsw. (Или с AVX512BW с байтовой маской vpaddb для меньшей задержки, чем у pmadd.)
x = ... (bits) 0abcdefg 0ABCDEFG
+ (hex) x & 0x...00FF00FF
0abcdefg ABCDEFG0
Это дает вам смежные 16-битные блоки, содержащие 14 битов значения. Однако на этот раз каждый блок разделяется двумя 0 битами, поэтому маскированное добавление - не самый эффективный способ продолжения. Вероятно, оттуда И с 0xFFFF0000FFFF0000 и смещением вправо на 2, затем маскируем оригинал другим способом и смешиваем с ИЛИ.
Десериализация этого формата с BMI2 pext Параллельный бит EXTract
pext медленный на AMD (микрокодированный, не выделенный HW, даже на Zen2), а BMI2 не везде доступен. Но на процессорах Intel это 1 моп, 3 такта, 1 тактовая частота. https://uops.info/
Обратите внимание, что вы можете сделать это в C со встроенными функциями : интерактивное руководство Intel по поиску / поиск . (Переносимость скалярных встроенных функций не SIMD между компиляторами может быть нечеткой, но для новых инструкций, таких как popcnt и BMI, в целом все в порядке.) Компиляторы могут не очень хорошо использовать btr для CSE x&(1<<7) и x &= ~(1<<7) в одной операции , но они должны обрабатывать этот код, даже если вы пишете что-то вроде (~mask) & x вместо встроенных. Хотя, вероятно, компиляторы будут выполнять постоянное распространение и материализовать инвертированную константу для and вместо andn.
Учитывая указатель на число неизвестной длины в этом формате, загрузите до 8 байтов и извлеките до 56 бит значения из них. (Предполагается, что загрузка qword безопасна: может загружать мусор, но не переходить на неотображенную страницу и ошибка: Безопасно ли читать после конца буфера в пределах одной и той же страницы на x86 и x64? )
; input pointer in RDI: a set bit 7 indicates end of number
; clobbers RCX, RDX
; result in RAX
;; great on Intel, probably can do better on AMD one byte at a time or with SIMD pmaddubsw
mov rcx, [rdi] ; 8 bytes, including possible trailing garbage
mov rdx, 0x7F7F7F7F7F7F7F7F
andn rsi, rdx, rcx ; isolate high bits: (~rdx) & rcx
blsmsk rax, rsi ; get mask up to lowest set bit: (rsi-1) XOR rsi = mask up to (and including) the first signal bit
and rax, rcx ; clear high garbage
; RAX = 0 above the number. The end-of-number flag is still set but pext only grabs bits 6:0 from each byte.
pext rax, rax, rdx ; rax = 8x 7-bit fields packed down to low 56
; uint64_t result in RAX, from the first 1 to 8 bytes of [rdi],
; depending on where the first number-end flag was
Если ни один байт не имеет своего старшего установленного бита, blsmsk со входом «все ноль» создает выход «все единицы». Таким образом, мы извлекаем все 8 байтов для случая бесконечного числа, а также для случая, когда установлен верхний бит ввода.
andn и blsmsk - задержка одного цикла за один цикл , но они находятся в цепочке зависимостей, ведущей к pext, поскольку в этом одном блоке нет параллелизма на уровне команд за одну итерацию. Он довольно короткий, поэтому, если бы мы делали еще одну итерацию для 8-байтовых данных, OoO exe c могло бы хорошо перекрываться.
Было бы здорово, если бы мы могли запустить pext параллельно с вычислением маска, которую мы могли бы использовать на выводе вместо ввода. Но это соотношение 7: 8 является проблемой. Мы могли бы запустить pext дважды параллельно (с другой маской), чтобы выровнять старшие биты каждого байта там, где они необходимы для blsmsk. Или мы могли бы tzcnt найти позицию младшего установленного бита, а затем как-то умножить на 7/8. Позиция кратна 8, поэтому мы могли бы tzcnt и сделать x - (x>>3) или что-то еще, а затем использовать этот битовый индекс для BMI2 bzhi.
Если у вас есть упакованный поток чисел в этом формате , вы захотите найти, где начинается следующий. Из rsi изолированного шаблона конечного флага вы можете rsi = tzcnt(rsi) затем rsi >>= 3 найти индекс байта первого бита конца номера.
Вам нужно добавить еще 1 к этому go мимо этого. Вы можете сделать lea rdi, [rdi + rsi + 1], но это имеет дополнительную задержку по сравнению с inc rdi / add rdi, rsi из-за 3-компонентного LEA (две операции +).
Или если вы сместили маску влево до tzcnt, вы можете сделать это напрямую, и в качестве бонуса он будет трактовать без терминатора как 8 вместо 9.
add rsi, rsi ; left-shift the end-of-number flags to the bottom of the next byte (or out)
tzcnt rsi, rsi ; rsi = bit-index of first bit of next number, 64 if RSI=0
; shrx rcx, rcx, rsi ; shift to the bottom and restart instead of reloading
shr esi, 3 ; bit index -> byte index. We know it's a small integer so 32-bit operand-size is fine and more saves code-size
add rdi, rsi ; advance the pointer
Эта работа может выполняться параллельно с blsmsk и pext. Хотя, если мы все равно выполняем эту tzcnt работу, возможно, нам следует использовать bzhi вместо blsmsk / and. Это может быть лучше для пропускной способности, но хуже для задержки: add -> tzcnt - это 4 цикла задержки от готовности RSI до того, как вход готов к bzhi, и все это находится на критическом пути, ведущем к pext. против blsmsk / and только 2 цикла.
Или если мы хотим l oop, пока не найдем конец одного числа (более 8 байтов) , RSI по-прежнему содержит изолированные биты сигнала. Вот почему я сделал andn в RSI, а не в RAX.
... continuing from above to keep going until the end of large number
... do something with the 56-bit RAX chunks, like overlapping stores into memory?
; rsi still holds the isolated signal bits
add rdi, 8
test rsi, rsi
jnz .loop ; }while(end of number not found)
Или blsmsk устанавливает CF, если его вход был нулевым, поэтому, если бы мы могли структурировать наш l oop с помощью blsmsk внизу мы можем использовать это как ветвь l oop. Он также устанавливает флаги, так что, возможно, с l oop вращением и отслаиванием первых / последующих итераций
Секция BMI2 PEXT представляет собой несколько случайных идей, перемешанных вместе, а не одну согласованную полностью оптимизированную реализацию. Приспособьтесь по мере необходимости в зависимости от любых гарантий, которые вы можете сделать. например, будет полезна верхняя граница в 8 байтов на число.
Одна важная вещь, на которую следует обратить внимание, - это задержка l-1214 * -переданной цепи dep, включающей приращение указателя. Если для начала следующего числа задано большое время ожидания, exe c не по порядку не сможет чередовать работу многих итераций.
Полусвязанный, еще один бит проблема с упаковкой / распаковкой: Упаковка BCD в DPD: как улучшить эту процедуру сборки amd64?