Сдвиги вместо MUL на 8088: по таблице выигрывают все константы, с учётом выборки байтов — только 9–21%

38 минут назад Прокомментировать Просмотры: 7

Совет «на 8088 умножай на константу сдвигами: MUL медленный» знаком даже тем, кто никогда не писал программы под DOS. Его основание — таблица тактов Intel: MUL с 16-битным регистром занимает 118–133 такта, сдвиг на один бит — 2, сложение — 3. Согласно этой таблице, последовательность сдвигов и сложений быстрее MUL для любой 16-битной константы: я проверил все 65 534. Но у 8088 восьмибитная шина, и чтение каждого байта инструкции из памяти занимает 4 такта, которые в таблице не учтены. Я взял опубликованные замеры настоящего 8088 1982 года и на их основе рассчитал время MUL и последовательностей. Для MUL таблица совпала с результатами измерений с точностью до такта. Время последовательностей я оценивал по замерам отдельных инструкций. Если предположить, что каждую инструкцию процессору сначала приходится считывать по шине, последовательность оказывается быстрее MUL для всех констант ниже определённого порога. Он зависит от второго множителя и находится в пределах от 1367 до 4779. Выше порога преимущество сохраняется лишь для части констант, а среди всех 16-битных констант — для 9–21%. Это расчёт: последовательности целиком на процессоре я не запускал. Почему такая оценка, скорее всего, завышает их время, объясняется в разделе «Границы».

Источник замеров

Собственного 8088 у меня нет. Данные взяты из набора SingleStepTests/8088 Дэниела Балсома: по 10 000 тестов на каждый опкод, выполненных на AMD D8088 1982 года выпуска — лицензионной копии Intel 8088 — с помощью платы Arduino8088. В каждом тесте состояние шины записано для каждого такта. Половина тестов начинается с полной очередью предвыборки, когда 4 байта уже прочитаны, другая половина — с пустой.

Началом инструкции Балсом считает такт, на котором процессор сообщает о чтении первого байта опкода из очереди, а концом — чтение первого байта следующей инструкции. Я скачал файлы в одноразовом контейнере, обработал их собственным скриптом на Python и исключил тесты с префиксами. Всё остальное — арифметические расчёты по этим данным.

MUL: замеры подтвердили таблицу Intel

Работу внутреннего механизма умножения Кен Ширрифф разобрал по фотографиям кристалла 8086. У 8088 такой же исполнительный блок, отличается только шина. Микрокод 16 раз проверяет младший бит AX: если он равен единице, прибавляет второй множитель, после чего выполняет сдвиг. Если бит нулевой, сложение пропускается. В конце отдельная подпрограмма проверяет, равна ли нулю старшая половина результата. Следовательно, время зависит от битов AX и от значения старшей половины произведения. Второй множитель влияет на него только через эту половину.

Ещё в 2012 году Эндрю Дженнер вывел по собственным измерениям формулу для 8088: умножение слова занимает 123 такта плюс 1 за каждый единичный бит AX и ещё 1, если старшее слово результата равно нулю; умножение байта — 69 тактов с аналогичными поправками для AL и AH. Я проверил формулу на замерах реального процессора: из числа тактов каждого теста вычел количество единичных битов аккумулятора и поправку за нулевую старшую половину. Если формула верна, во всех тестах должен остаться один и тот же результат.

Инструкция, очередь	Тестов	Такты	Остаток
MUL r16, полная	630	119–130	117 во всех 630
MUL r16, пустая	585	122–134	120 во всех 585
MUL r8, полная	636	70–77	69 во всех 636
MUL r8, пустая	622	73–80	72 во всех 622

Структура формулы подтверждается в 100% тестов с регистровыми операндами. Константа для байта, 69, совпала с результатом Дженнера. Для слова совпадения нет: замеры процессора дают 117, а у Дженнера указано 123 — на 6 тактов больше. Причина расхождения в его заметке не объясняется.

С константой 117 формула воспроизводит таблицу Intel: при AX = 0 получаем 117 + 0 + 1 = 118. Именно столько намерил Майкл Абраш в «Zen of Assembly Language», выполнив серию mul ax с нулевым значением. При AX = FFFFh и ненулевом DX получается 133. С таблицей есть лишь одно расхождение: если AX = FFFFh, а второй множитель равен 0 или 1, старшая половина результата нулевая и формула даёт 134 — на такт больше табличного максимума. Для байта аналогичный расчёт даёт 70–77 тактов и 78 в том же крайнем случае. Значение AX = FFFFh в тестах не встретилось ни разу, максимум составил 14 единичных битов, поэтому 134 такта получены только из формулы и измерением не подтверждены. Весь разброс объясняется битами AX и ветвлением по условию «DX = 0». Пустая очередь добавляет ровно 3 такта: процессору приходится ждать поступления байтов инструкции по шине. Для операнда в памяти таблица Абраша даёт на 10 тактов больше, не считая вычисления адреса.

Сколько тактов действительно занимает сдвиг

Для инструкций, из которых строятся последовательности, картина иная. Вот данные тех же файлов SingleStepTests для регистровых форм:

Инструкция	Байт	Тактов из полной очереди	Тактов из пустой
`mov bx, ax`	2	2	8
`add ax, bx`, `sub ax, bx`	2	3	8
`shl ax, 1`	2	2	8
`mov cl, n`	2	4	8
`shl ax, cl`	2	8 + 4·CL	11 + 4·CL
`mov cx, imm16`	3	4	12

При полной очереди результаты полностью совпадают с таблицей Intel. При пустой каждая двухбайтовая инструкция из таблицы, кроме сдвига на CL, занимает 8 тактов независимо от времени её выполнения: два байта по 4 такта. Трёхбайтовый mov cx, imm16 занимает 12 тактов. Абраш получил аналогичный результат с помощью таймера: серия shr на IBM PC выполнялась со скоростью 8,64 такта на инструкцию при табличных 2, а дополнительные 0,64 такта он отнёс на счёт регенерации DRAM. После MUL очередь полна: за сотню тактов процессор успевает её заполнить. В серии коротких инструкций она быстро опустошается, поскольку двухтактная инструкция завершается раньше, чем процессор успевает прочитать два байта следующей.

При каких константах последовательность быстрее MUL

Затем я перебрал все k от 2 до 65535. Для каждого значения построил последовательности по двоичной записи k и по записи со знаковыми разрядами, где одно вычитание может оказаться выгоднее нескольких сложений. Более дешёвый вариант я сравнил с более быстрым из двух способов применения MUL: mov cx, k и mul cx либо mov cx, ax, mov ax, k, mul cx. Стоимость каждой инструкции скрипт заново извлекает из файлов SingleStepTests; вручную в него ничего не внесено. Время последовательности я рассчитывал двумя способами: «по таблице», когда каждая инструкция уже находится в очереди, и «с выборкой», когда каждая считывается по 8-битной шине. Сравниваются младшие 16 бит результата: последовательность не выдаёт старшее слово произведения, которое MUL помещает в DX. Если оно необходимо, такое сравнение неприменимо.

Так выглядит умножение на 320 — длину строки в режиме 13h:

mov bx, ax      ; по таблице 2, с выборкой 8
shl ax, 1       ; 2 / 8
shl ax, 1       ; 2 / 8
add ax, bx      ; 3 / 8, теперь ax = 5x
mov cl, 6       ; 4 / 8
shl ax, cl      ; 32 / 35, ax = 320x

С учётом выборки получается 75 тактов. При расчёте по таблице выгоднее заменить mov cl и сдвиг на CL шестью инструкциями shl ax, 1: тогда выходит 21 такт. MUL с той же константой при восьми единичных битах второго множителя и ненулевой старшей половине результата занимает 129 тактов по таблице и 140 с выборкой.

В столбцах MUL ниже приведены значения для mov cx, k / mul cx при восьми единичных битах второго множителя и ненулевом DX.

k	Последовательность по таблице	Последовательность с выборкой	MUL по таблице	MUL с выборкой
10	11	40	129	140
320	21	75	129	140
1000	28	103	129	140
1024	20	59	129	140
12345	42	143	129	140
21845 (5555h)	51	176	129	140
65535	37	99	129	140

По таблице последовательность занимает от 2 до 56 тактов и опережает MUL для всех 65 534 констант: именно на этом основано правило «умножай сдвигами». С учётом выборки получается от 8 до 192 тактов, медиана — 163. При этом время MUL зависит от второго множителя x, а значит, от него зависит и порог:

x = 0, самый быстрый MUL — 133 такта с выборкой: последовательность быстрее для всех k < 1367 и в общей сложности для 8,6% констант;
8 единичных битов в x — 140 тактов: последовательность быстрее для всех k < 2731 и в общей сложности для 14,1% констант;
x = FFFFh, самый медленный MUL — 148 тактов: последовательность быстрее для всех k < 4779 и в общей сложности для 21,3% констант.

Выше порога результат зависит от расположения единичных битов в k и возможности заменить сложения вычитанием. Для 1024 и 65535 последовательность со сдвигом и одним вычитанием по-прежнему дешевле MUL, а для 5555h — дороже на 36 тактов. Последовательность для 5555h состоит только из однобитных сдвигов и сложений, для которых расчёт с выборкой совпадает с измерениями таймера Абраша с точностью до времени регенерации DRAM. Для 12345 расчётное время больше всего на 3 такта, но в последовательности есть сдвиг на CL, стоимость которого в этом расчёте завышена (см. «Границы»). Поэтому вывод для этой константы ненадёжен. Во втором варианте MUL константа находится в AX, и время уже зависит от битов k. В расчёте с выборкой для всех k из таблицы выше он обходится на 1–16 тактов дороже первого. Пороги и доли в списке рассчитаны относительно более быстрого из двух вариантов.

Практический смысл результатов

Для констант, которые действительно встречались в DOS-программах, совет работает. Степени двойки требуют одного-двух сдвигов, и выигрыш здесь огромен. Для 10, 80 и 320 последовательность быстрее MUL в 1,9–3,5 раза, хотя таблица обещает преимущество в 6–12 раз. Для 5555h, где единицы чередуются с нулями и вычитание не сокращает последовательность, в этом расчёте быстрее оказывается MUL, хотя по таблице он проигрывает всегда. Сама таблица для MUL верна. Совет подводит другое обстоятельство: таблица не учитывает время, которое 8088 тратит на чтение байтов коротких инструкций из памяти.

По замерам Абраша, регенерация DRAM на IBM PC занимает 7,4% времени серии shr — 8,64 такта вместо 8, — но совсем не замедляет серию MUL без обращений к памяти. Следовательно, на настоящем PC порог, вероятно, ниже полученных мной значений. Однако это вывод из его измерений: самостоятельно я его не проверял.

Границы

Измерения выполнены на одном экземпляре AMD D8088, без тактов ожидания памяти и регенерации DRAM. Для Intel 8088 результаты, вероятно, будут такими же, а для 8086 с 16-битной шиной порог окажется другим.
Последовательность целиком на процессоре не запускалась: её стоимость рассчитана как сумма замеров отдельных инструкций. Для однобитных сдвигов и сложений расчёт «с выборкой» даёт 8 тактов на инструкцию, тогда как таймер Абраша показал 8,64 с учётом регенерации DRAM. Для сдвига на CL эта оценка завышена: за время его выполнения очередь успевает заполниться. Она завышена и для первых инструкций после долгой операции, пока в очереди ещё остаются байты. Реальное время находится между двумя расчётными значениями.
Последовательности не являются оптимальными. Более удачная цепочка сложений может быть короче, и тогда порог повысится.

Скрипты обработки написаны на Python 3.15 и запускаются в контейнере python:3.15-slim. Источник данных — github.com/SingleStepTests/8088, каталог v2, лицензия MIT.

Источник