Дополнение до двух длинных целых чисел

Я хочу выполнить длинную целочисленную математику (128 бит) с помощью Intel I64 Assembler, и мне нужно создать дополнение до 2. Допустим, моя положительная ценность выражена в RDX: RAX.

Дополнение до 2 выполняется «перевернуть биты и добавить 1». Итак, самая наивная реализация (4 инструкции и 14 байтов кода):

  NOT RAX
  NOT RDX
  ADD RAX,1   ; Can't use INC, it doesn't set Carry
  ADC RDX,0

Когда я использую инструкцию NEG для RAX вместо NOT, она дает мне «+1», но перенос неверен, NEG RAX очищает перенос, когда RAX был равен нулю, но мне нужно переносить ТОЛЬКО В ЭТОМ СЛУЧАЕ. Итак, следующий лучший подход может быть (4 инструкции и 11 байтов кода):

  NOT RDX
  NEG RAX
  CMC
  ADC RDX,0                  ; fixed, thanks lurker

Еще 4 инструкции. Но вместо добавления +1 я могу вычесть -1, и поскольку SBB добавляет бит переноса к вычитаемому, я добавлю +1, когда переносимость ясна. Итак, моя следующая лучшая попытка - это с 3 инструкциями и 10 байтами кода:

   NOT RDX
   NEG RAX
   SBB RDX,-1

Как вы можете видеть из моего длинного текста, это не очевидно для понимания. Есть ли лучший и более понятный способ сделать каскадное дополнение 2 на ассемблере?


person Rolf    schedule 03.04.2015    source источник
comment
Вы, кажется, полагаете, что лучше означает более короткий код, и это то, что не должно применяться к мультискалярному процессору, работающему вне очереди, как x86-64. Я бы сказал, что самая нестабильная из ваших реализаций - первая, и я не удивлюсь, если все они будут выполняться одновременно.   -  person mcleod_ideafix    schedule 03.04.2015
comment
Кстати: вы рассматривали возможность использования регистров XMM? Они достаточно широки, чтобы вместить 128-битное число, и (я не проверял) у них могут быть целочисленные инструкции для работы с целым числом.   -  person mcleod_ideafix    schedule 03.04.2015
comment
@mcleod_ideafix они не делают, поэтому у вас все еще остается проблема переноса переноски вручную.   -  person harold    schedule 03.04.2015
comment
Я думаю, вы имеете в виду ADC RDX,0 как последнюю инструкцию во втором примере.   -  person lurker    schedule 04.04.2015
comment
Спасибо @ lurker, я исправил. И да, я рассмотрел регистры XMM. Они созданы для векторов целых чисел, где распространение переноса невозможно. Таким образом, они дают вам выбор между необнаруженным переполнением или целочисленным насыщением. Не подходит для моей цели.   -  person Rolf    schedule 04.04.2015
comment
Мне ДЕЙСТВИТЕЛЬНО приходило в голову, что моя проблема может быть неуместной из-за оптимизирующего оборудования. Но я парень, родился в 1960-х и вырос, считая байты и циклы. Я думаю, это вошло в привычку :)   -  person Rolf    schedule 04.04.2015
comment
Глядя на таблицы инструкций Агнера Фога, удивительно CMC - низкая задержка, высокая пропускная способность на современных микроархитектурах, поэтому вторая версия, вероятно, конкурентоспособна. С другой стороны, рассмотрим цепочки зависимостей: 1: ADC зависит от _3 _ / _ 4_ через флаги, зависит от NOT. 2: ADC зависит от _7 _ / _ 8_ зависит от NEG. 3: SBB зависит от _11 _ / _ 12_. Я бы сказал, что с последней версией вы нашли очень хитрый способ.   -  person EOF    schedule 04.04.2015
comment
Регистры SIMD, такие как XMM / YMM / ZMM, предназначены для одновременного использования нескольких значений не для целых чисел с высокой точностью   -  person phuclv    schedule 04.04.2015
comment
Спасибо EOF за подсказку Агнеру Фогу. Я займусь этим.   -  person Rolf    schedule 05.04.2015


Ответы (2)


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

Например, устаревшие инструкции, такие как enter, dad, _ 3_ ... будут очень медленными и предназначены только для обратной совместимости. Даже inc иногда работает медленнее, чем add. То же, что cmc, которое вы использовали выше на некоторых μархах

В результате более длинные серии инструкций с низкой задержкой, которые могут выполняться параллельно, будут работать намного быстрее. Некоторые общие группы инструкций можно даже объединить в одну макрооперацию. Оптимизаторы компилятора всегда знают об этом и выберут наиболее подходящие инструкции для выдачи.

Для этого фрагмента

__int128 negate(__int128 x)
{
    return -x;
}

ICC 19.0.1 mov также может быть «бесплатным»

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

Быстрее это или нет, нужен микробенчмаркинг. Но на процессорах Intel компилятор Intel (ICC) часто обеспечивает более высокую производительность, чем другие, потому что он лучше понимает архитектуру.

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

person phuclv    schedule 04.04.2015
comment
dad не является мнемоникой x86, aam и т.п. недопустимы в x86-64. Согласно таблицам инструкций Ager Fog, cmc работает быстро на каждой микроархитектуре Intel / AMD, начиная с P4. - person EOF; 04.04.2015
comment
Возможно, мне стоит иногда попробовать GCC, по крайней мере, чтобы посмотреть на код, который он генерирует. Я использовал Visual Studio 2013. - person Rolf; 05.04.2015
comment
gcc.godbolt.org поможет вам увидеть вывод сборки нескольких наиболее распространенных компиляторов. - person phuclv; 07.04.2015

Кстати, отрицание 2-регистрового числа одинаково в 32-битном или 16-битном режиме с EDX: EAX или DX: AX. Используйте ту же последовательность инструкций.


Чтобы копировать и отрицать, ответ @phuclv показывает эффективный вывод компилятора. Лучше всего обнулить место назначения с помощью xor и затем использовать sub / sbb.

Это 4 мупа для интерфейса на AMD, а также на Intel Broadwell и более поздних версиях. На Intel до Broadwell sbb reg,reg составляет 2 мопса. Обнуление xor находится вне критического пути (может произойти до того, как данные, которые нужно инвертировать, будут готовы), поэтому общая задержка составляет 2 или 3 цикла для высокой половины. Младшая половина, конечно, готова с задержкой в ​​1 цикл.

Clang mov/neg для младшей половины, возможно, лучше на Ryzen, у которого есть mov-elimination для целого числа GP, но по-прежнему требуется исполнительный блок ALU для обнуления xor. Но для старых процессоров это ставит mov на критический путь задержки. Но обычно внутреннее давление ALU не так важно, как узкие места внешнего интерфейса, для инструкций, которые могут использовать любой порт ALU.


Чтобы отрицать на месте, используйте neg для вычитания из 0

neg   rdx              ; high half first
neg   rax             ; subtract RDX:RAX from 0
sbb   rdx, 0          ; with carry from low to high half

neg в точности эквивалентен sub от 0, что касается установки флагов и производительности.

АЦП / SBB с немедленный 0 - это всего лишь 1 мкоп на Intel SnB / IvB / Haswell, как особый случай. Тем не менее, на Nehalem и ранее это по-прежнему 2 мупа. Но без исключения перемещения mov в другой регистр и затем sbb обратно в RDX было бы медленнее.

Младшая половина (в RAX) готова в первом цикле после того, как она готова в качестве входа для neg. (Таким образом, выполнение более позднего кода вне очереди может начаться с младшей половины.)

Верхняя половина neg rdx может работать параллельно с нижней половиной. Затем sbb rdx,0 должен ждать rdx от neg rdx и CF от neg rax. Таким образом, он готов позже, чем через 1 цикл после нижней половины или через 2 цикла после того, как будет готова входная высокая половина.


Вышеупомянутая последовательность лучше, чем любая в вопросе, поскольку на очень распространенных процессорах Intel меньше ошибок. На Бродвелле и более поздних версиях (однократный SBB, а не только для немедленного 0)

;; equally good on Broadwell/Skylake, and AMD.  But worse on Intel SnB through HSW
NOT RDX
NEG RAX
SBB RDX,-1     ; can't use the imm=0 special case

Очевидно, что любая из 4-командных последовательностей неоптимальна, а скорее всего. И некоторые из них имеют худшие ILP / цепочки зависимостей / задержку, например, 2 инструкции на критическом пути для нижней половины или цепочка из 3 циклов для верхней половины.

person Peter Cordes    schedule 04.04.2019
comment
Некоторое время я не смотрел этот вопрос. отличные идеи, большое спасибо - person Rolf; 07.08.2020