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

Совет «на 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. Я проверил её на замерах с кристалла: из тактов каждого теста вычел число единиц в аккумуляторе и поправку за нулевую старшую половину. Если формула верна, остаток должен быть одинаковым во всех тестах.

Форма формулы держится в 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 для регистровых форм:

Из полной очереди всё совпадает с таблицей Intel. Из пустой каждая двухбайтовая инструкция таблицы, кроме сдвига на CL, стоит 8 тактов, сколько бы ни занимала её работа: 2 байта по 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 тактов. По таблице выгоднее шесть shl ax, 1 вместо mov cl и сдвига на CL, и получается 21. MUL с той же константой, если во втором множителе 8 единиц и старшая половина результата ненулевая, — 129 по таблице и 140 с выборкой.

Столбцы MUL ниже — для mov cx, k / mul cx при 8 единицах во втором множителе и ненулевом DX.

По таблице цепочка стоит от 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 тактов. Её цепочка состоит только из однобитных сдвигов и сложений, для которых счёт с выборкой сходится с таймером Абраша с точностью до регенерации DRAM. 12345 дороже всего на 3 такта, но в её цепочке есть сдвиг на CL, где счёт завышен (см. «Границы»), так что для неё вывод не надёжен. Во втором варианте MUL константа лежит в AX, и время зависит уже от битов k. В счёте с выборкой для всех k из таблицы выше он дороже первого на 1–16 тактов. Пороги и доли в списке выше посчитаны против более быстрого из двух вариантов.

Что это значит

Для констант, которые реально попадались в коде под DOS, совет верен. Степени двойки — это один-два сдвига, и там выигрыш огромный. Для 10, 80 и 320 цепочка в 1,9–3,5 раза быстрее MUL, но не в 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.