Я хочу показать вам, как одна буква в ассемблере может стоить 3× производительности. Не в теории — на живых замерах. По дороге мы заглянем внутрь процессора: Register Alias Table, partial register merge, scheduler, latency vs throughput, и даже обнаружим, что делитель выдаёт остаток раньше частного.
Но начнём с основ. Приготовьтесь: кроличья нора окажется глубже, чем кажется.
Немного контекста
Процессор x86-64 работает с регистрами — быстрыми ячейками прямо внутри CPU. Их немного (16 основных), зато доступ к ним — за доли такта, в отличие от оперативной памяти, где задержка может достигать сотен тактов.
Главный нюанс: у каждого регистра есть части разного размера, унаследованные от предыдущих поколений архитектуры:
┌───────────────────────────────────────────────────────────────┐│ rax (64 бит) │├───────────────────────────────┬───────────────────────────────┤│ (верхние 32) │ eax (32 бит) ││ ├───────────────┬───────────────┤│ │ │ ax (16 бит) ││ │ ├───────┬───────┤│ │ │ah (8) │al (8) │└───────────────────────────────┴───────────────┴───────┴───────┘
rax, eax, ax — это не разные регистры. Это один и тот же регистр, просто вы указываете, какую часть хотите использовать. Запись в eax меняет нижние 32 бита rax. Запись в ax — нижние 16. Это важно — и именно здесь спрятана ловушка, о которой пойдёт речь.
Таких регистров 16: rax, rbx, rcx, rdx, rsi, rdi, rbp, rsp, r8–r15. Для нашей истории важны два: rax и rdx — потому что именно их использует инструкция деления.
Целочисленное деление на x86
Инструкция div (беззнаковое деление) и idiv (знаковое) работают так: делимое берётся из пары регистров, делитель — из операнда, результат раскладывается обратно:
┌──────────┬────────────────┬──────────────┬─────────────────────┐│ Размер │ Делимое │ Частное в │ Остаток в │├──────────┼────────────────┼──────────────┼─────────────────────┤│ 16-бит │ dx:ax │ ax │ dx │├──────────┼────────────────┼──────────────┼─────────────────────┤│ 32-бит │ edx:eax │ eax │ edx │├──────────┼────────────────┼──────────────┼─────────────────────┤│ 64-бит │ rdx:rax │ rax │ rdx │└──────────┴────────────────┴──────────────┴─────────────────────┘
Перед делением нужно подготовить делимое в паре rdx:rax (или edx:eax, или dx:ax). Верхнюю часть обычно обнуляют через mov или xor.
Как работает цикл
В ассемблере нет for и while. Цикл — это метка, тело и условный переход:
mov ecx, 100 ; счётчик = 100.loop: ; ... тело цикла ... dec ecx ; счётчик -= 1 jnz .loop ; если не ноль — прыгаем назад
dec ecx уменьшает счётчик на 1 и выставляет флаги. jnz (jump if not zero) проверяет флаг и прыгает, если результат не ноль. Процессор умеет сливать эти две инструкции в одну операцию (macro-fusion), поэтому пара dec+jnz стоит всего 1 такт.
Эксперимент
Вопрос: сколько тактов процессора стоит одна инструкция div?
Контекст может сильно влиять на результат — кэш, предсказание переходов, другие инструкции рядом. Чтобы измерить стоимость деления в чистом виде, напишем плоский цикл на 1920×1080 = 2 073 600 итераций. Почему такое число? Представьте рендер: 1920×1080 пикселей, на каждый — деление.
Тело цикла: два mov для подготовки делимого + инструкция деления. Все делят одно и то же: 536700 / 2700. Подготовка регистров — стандартная для каждого размера:
; 16-бит unsigned ; 16-бит signedmov dx, 0x0008 mov dx, 0x0008mov ax, 0x2B7C mov ax, 0x2B7Cdiv word [best_den] idiv word [best_den]; 32-бит unsigned ; 32-бит signedmov edx, 0 mov edx, 0mov eax, 536700 mov eax, 536700div dword [best_den] idiv dword [best_den]; 64-бит unsigned ; 64-бит signedmov rdx, 0 mov rdx, 0mov rax, 536700 mov rax, 536700div qword [best_den] idiv qword [best_den]
Но сначала проверим, сколько стоит сам цикл без деления — только setup:
┌────────────────────────────────┬──────────┐│ Setup (без div) │ cpr │├────────────────────────────────┼──────────┤│ 16-бит (mov dx + mov ax) │ 1924 │├────────────────────────────────┼──────────┤│ 32-бит (mov edx + mov eax) │ 1928 │├────────────────────────────────┼──────────┤│ 64-бит (mov rdx + mov rax) │ 1924 │└────────────────────────────────┴──────────┘ (cpr = cycles per row = total / 1080)
Все setup-ы дают ~1920 cpr — 1 такт на итерацию. Мувы бесплатны: они уходят на свободные ALU-порты параллельно с dec/jnz. Значит, всё что мы замерим дальше — это чистая стоимость деления.
Глава 1. Странная таблица
Результаты:
┌────────┬───────────────┬────────────────┐│ │ signed (idiv) │ unsigned (div) │├────────┼───────────────┼────────────────┤│ 16-bit │ 44 447 │ 44 457 │├────────┼───────────────┼────────────────┤│ 32-bit │ 13 445 │ 13 445 │├────────┼───────────────┼────────────────┤│ 64-bit │ 52 289 │ 48 160 │└────────┴───────────────┴────────────────┘ (cycles per row, 1920 итераций на строку)
Переведём в такты на одну итерацию (cpr / 1920) и вычтем стоимость цикла без инструкции деления (1 такт):
┌────────┬──────────────┬──────────────┬──────────────┬──────────────┐│ │ idiv (полн.) │ idiv (чист.) │ div (полн.) │ div (чист.) │├────────┼──────────────┼──────────────┼──────────────┼──────────────┤│ 16-bit │ 23.2 │ 22.2 │ 23.2 │ 22.2 │├────────┼──────────────┼──────────────┼──────────────┼──────────────┤│ 32-bit │ 7.0 │ 6.0 │ 7.0 │ 6.0 │├────────┼──────────────┼──────────────┼──────────────┼──────────────┤│ 64-bit │ 27.2 │ 26.2 │ 25.1 │ 24.1 │└────────┴──────────────┴──────────────┴──────────────┴──────────────┘ (тактов на итерацию; чист. = минус стоимость цикла без деления)
16-бит — ~22 такта на деление. 64-бит — ~24–26 тактов. Примерно один порядок.
А 32-бит — ~6 тактов. Почти в 3 раза быстрее.
Если бы время росло с увеличением битности — 16 < 32 < 64 — это было бы логично: больше бит, сложнее операция. Но здесь именно 32-бит выбиваются вниз. Код одинаковый по структуре: два mov, один div. Числа одни и те же. Единственная разница — размер регистров. Почему 32-бит настолько быстрее?
Глава 2. Что происходит внутри процессора
Чтобы понять, откуда разница, нужно заглянуть под капот.
Регистр rax, который вы видите в коде — это не физический регистр. Это имя. Псевдоним.
Внутри процессора есть register file — массив из ~180 безымянных физических регистров. И таблица переназначений — Register Alias Table (RAT) — которая в каждый момент говорит: «rax — это сейчас физический регистр №47».
Когда вы пишете mov rax, 10, процессор берёт из пула новый физический регистр — скажем, №112 — записывает туда 10 и обновляет RAT: rax → №112. Старый №47 живёт, пока все инструкции, которые его читают, не завершатся. Это основа out-of-order execution — параллельного исполнения инструкций.
Теперь ключевой момент. В x86-64 есть правило:
-
Запись в 32-битный регистр (
mov edx, ...) обнуляет верхние 32 бита. Полная перезапись. Процессор создаёт новый физический регистр, старая версия не нужна. Зависимости нет. -
Запись в 16-битный регистр (
mov dx, ...) верхние 48 бит не трогает. Процессор должен создать новыйrdx, где нижние 16 бит — новые, а верхние 48 — из предыдущей версии. Для этого нужно дождаться готовности предыдущегоrdx. Это создаёт зависимость, которая нам не нужна — верхние 48 бит мы не используем, и они пролетают над гнездом кукушки каждый раз в неизменном виде.
В нашем 16-битном цикле это катастрофа. div word записывает результат в ax и dx — тоже 16-битные записи. А div word при этом тоже должен склеить свой результат с верхними 48 битами предыдущего rax и rdx — это ещё один merge. Получается, верхние 48 бит никому не нужны — ни div, ни mov dx — но они протаскиваются через каждую итерацию, создавая цепочку зависимостей: div → merge → mov dx → merge → div → .... Каждая итерация ждёт предыдущую.
В 32-битном варианте mov edx, 0 обнуляет верхние 32 бита — цепочка разрывается. Итерации становятся независимыми, и процессор может перекрывать их.
Здесь нужно ввести два понятия:
Latency — сколько тактов от начала div до готовности результата. Для 16-битного div на Coffee Lake: 21–22 такта (данные uops.info).
Throughput — через сколько тактов делитель может принять следующую операцию. Для 16-битного div: 6 тактов (данные uops.info).
Делитель частично конвейеризирован: через ~6 тактов вход свободен, хотя предыдущее деление ещё не закончило.
16-бит с mov dx (ненужная зависимость): каждая итерация ждёт предыдущую → bottleneck = latency = ~22 такта.
32-бит с mov edx (нет зависимости): итерации перекрываются → bottleneck = throughput = ~6 тактов.
22 / 6 = ~3.7×. Вот почему 32-бит так выбивается в нашей таблице.
Если теория верна, то и 16-битный div word должен ускориться, если мы уберём ненужную зависимость — заменим mov dx на mov edx. Проверим.
Глава 3. Проверяем теорию
Заменяем 16-битные mov на 32-битные в обоих вариантах:
; div word — было: ; div word — стало:mov dx, 0x0008 mov edx, 8mov ax, 0x2B7C mov eax, 0x2B7Cdiv word [best_den] div word [best_den]; idiv word — было: ; idiv word — стало:mov dx, 0x0008 mov edx, 8mov ax, 0x2B7C mov eax, 0x2B7Cidiv word [best_den] idiv word [best_den]
Одна буква e. Тот же div word, те же числа. Сначала проверим, что сам setup по-прежнему бесплатен:
┌──────────────────────────────────┬──────┐│ Setup (без div) │ cpr │├──────────────────────────────────┼──────┤│ 32-бит для word (mov edx/eax) │ 1925 │└──────────────────────────────────┴──────┘
1 такт — как и все остальные setup-ы. Теперь запускаем с делением:
┌───────────────────────┬───────────────┬────────────────┐│ │ signed (idiv) │ unsigned (div) │├───────────────────────┼───────────────┼────────────────┤│ 16-bit (mov dx) │ 44 447 │ 44 457 │├───────────────────────┼───────────────┼────────────────┤│ 16-bit (mov edx) │ 15 368 │ 15 368 │├───────────────────────┼───────────────┼────────────────┤│ 32-bit │ 13 445 │ 13 445 │├───────────────────────┼───────────────┼────────────────┤│ 64-bit │ 52 289 │ 48 160 │└───────────────────────┴───────────────┴────────────────┘
В тактах (чистая стоимость деления):
┌───────────────────────┬──────────────┬──────────────┐│ │ idiv (чист.) │ div (чист.) │├───────────────────────┼──────────────┼──────────────┤│ 16-bit (mov dx) │ 22.2 │ 22.2 │├───────────────────────┼──────────────┼──────────────┤│ 16-bit (mov edx) │ 7.0 │ 7.0 │├───────────────────────┼──────────────┼──────────────┤│ 32-bit │ 6.0 │ 6.0 │├───────────────────────┼──────────────┼──────────────┤│ 64-bit │ 26.2 │ 24.1 │└───────────────────────┴──────────────┴──────────────┘
16-бит с mov edx — 15 368 cpr (7.0 тактов чистых). С mov dx было 44 447 cpr (22.2 такта). Втрое быстрее. Теория подтверждена.
Мы уже знаем из наших замеров, что сами mov-ы бесплатны — все setup-ы стоят 1 такт. Значит, вся разница — в зависимостях, которые 16-битные записи создают внутри цикла с div.
Глава 4. А что с 64-битным делением?
С 16-бит разобрались. Но в таблице осталась странность: 64-бит div qword — ~48 160 cpr, это ~25 тактов на итерацию. При этом зависимостей нет: mov rdx, 0 и mov rax, 536700 — полные 64-битные перезаписи, цепочка разорвана.
Значит, ~25 тактов — это не latency, а throughput 64-битного делителя. Он просто не может быстрее. Данные uops.info подтверждают: throughput div r64 на Coffee Lake = ~21 такт. На 64-битном делении CPU тратит 33 µops (32 из микрокода!) вместо 10 для 16/32-бит. Совершенно другая реализация.
Но если ~21 такт — это throughput, то latency должна быть больше. uops.info говорит: latency от 32 тактов. Значит, если создать зависимость между итерациями, время должно вырасти.
Глава 5. Где зависимость?
Создадим зависимость. После div qword (536700 / 2700): rax = 198, rdx = 2100. Мы знаем результат — значит, через вычитание можно вернуть rdx к нулю, сохранив зависимость:
mov rax, 536700sub rdx, 2100 ; 2100 - 2100 = 0, зависит от rdxdiv qword [best_den]
Запускаем: ~46 300 cpr. Столько же, сколько без зависимости. Время не выросло.
Странно. Зависимость div → sub → div точно есть. sub читает rdx, который записал div. Почему это не замедляет?
Глава 6. Ищу latency
Может, ~21 такт — это и есть latency, а не throughput? Может, для маленьких чисел делитель просто быстрее, чем обещает uops.info?
Попробуем увеличить число: 536700000, потом 5367000000000. Результат — тот же: ~46 000–48 000 cpr. Размер числа не влияет.
Глава 7. Две зависимости
div qword читает два входных регистра: rdx:rax. До сих пор мы создавали зависимость только по rdx. А что, если нужна зависимость по обоим?
После div: rax = 198, rdx = 2100. Через сложение возвращаем оба к исходным значениям:
add rax, 536502 ; 198 + 536502 = 536700, зависит от raxadd rdx, -2100 ; 2100 - 2100 = 0, зависит от rdxdiv qword [best_den]
Те же числа. Тот же результат. Запускаем: ~67 050 cpr = 34 такта на итерацию!
Было 24 такта без зависимости. Стало 34 с зависимостью. Разница 10 тактов. Вот настоящая latency. И ~34 — это как раз в диапазоне 32+, который указывает uops.info.
Глава 8. Какой именно регистр?
Но подождите. Зависимость по одному rdx (глава 5) не замедлила цикл, а зависимость по обоим — замедлила. Значит, дело конкретно в rax?
Проверяем три варианта:
; Вариант 1: зависимость только по raxadd rax, 536502 ; зависит от raxxor edx, edx ; НЕ зависит от rdxdiv qword [best_den]; Вариант 2: зависимость только по rdxmov rax, 536700 ; НЕ зависит от raxadd rdx, -2100 ; зависит от rdxdiv qword [best_den]; Вариант 3: обаadd rax, 536502add rdx, -2100div qword [best_den]
Результаты:
┌────────────────┬─────────┬───────────────────┐│ Зависимость │ cpr │ Такты/итерацию │├────────────────┼─────────┼───────────────────┤│ нет │ ~48 000 │ ~24 (throughput) │├────────────────┼─────────┼───────────────────┤│ только rax │ 67 800 │ 34.3 │├────────────────┼─────────┼───────────────────┤│ только rdx │ 46 250 │ 23.1 │├────────────────┼─────────┼───────────────────┤│ оба │ 67 050 │ 34.0 │└────────────────┴─────────┴───────────────────┘
Зависимость по rax → 34 такта. Зависимость по rdx → 23 такта. Как будто зависимости нет.
Глава 9. Остаток приходит раньше частного
Делитель выдаёт результаты не одновременно.
Остаток (rdx) готов через ~23 такта — раньше, чем throughput делителя (~21). Поэтому зависимость по rdx ничего не стоит: к моменту, когда делитель готов принять следующую операцию, rdx уже давно посчитан.
Частное (rax) готов через ~34 такта — позже, чем throughput. Делитель свободен, add rax, 536502 готова к выполнению, но ей нужен rax, которого ещё нет. 10 тактов простоя.
Данные uops.info подтверждают: на Coffee Lake для DIV R64 latency до rax (частное) начинается от 32 тактов, а до rdx (остаток) — от 5 тактов.
Полная карта делителя
Данные uops.info для Coffee Lake:
┌────────────┬──────────────┬──────────────┬────────────┬───────┬─────────────┐│ Инструкция │ Lat →rax │ Lat →rdx │ Throughput │ µops │ Из микрокода│├────────────┼──────────────┼──────────────┼────────────┼───────┼─────────────┤│ div r16 │ 21 │ 22 │ 6 │ 10 │ 7 │├────────────┼──────────────┼──────────────┼────────────┼───────┼─────────────┤│ idiv r16 │ 21 │ 22 │ 6 │ 10 │ 7 │├────────────┼──────────────┼──────────────┼────────────┼───────┼─────────────┤│ div r32 │ 24–26 │ 24–26 │ 6 │ 10 │ 7 │├────────────┼──────────────┼──────────────┼────────────┼───────┼─────────────┤│ idiv r32 │ 24–26 │ 24–26 │ 6 │ 10 │ 7 │├────────────┼──────────────┼──────────────┼────────────┼───────┼─────────────┤│ div r64 │ 32–87 │ 5–75 │ 21 │ 33 │ 32 │├────────────┼──────────────┼──────────────┼────────────┼───────┼─────────────┤│ idiv r64 │ 38–94 │ 39–95 │ 24 │ 56 │ 53 │└────────────┴──────────────┴──────────────┴────────────┴───────┴─────────────┘
16/32-бит: 10 µops, throughput 6. Зазор latency/throughput — ~3.7×. Partial register merge не даёт попасть в throughput, и мы видим latency.
64-бит div: 33 µops (32 из микрокода!), throughput 21. Другая реализация.
64-бит idiv: 56 µops. Знаковое 64-битное деление — самая тяжёлая целочисленная операция на Skylake.
Итоги
-
Регистры — это псевдонимы. Физические регистры выделяются динамически через RAT. Это основа OoO-execution.
-
16-битные записи ядовиты. Они создают ложные зависимости через partial register merge. 32-битные записи обнуляют верх и разрывают цепочку. Причём никакой экономии нет:
mov dx, imm16всё равно занимает целый 64-битный физический регистр и добавляет merge µop сверху. -
Latency ≠ throughput. Делитель может принять новую операцию задолго до выдачи результата предыдущей. Но только если зависимости не блокируют подачу операндов.
-
Разные выходы одной инструкции имеют разную latency. Остаток готов раньше частного. Зависимость от «быстрого» выхода может быть бесплатной.
-
Размер операнда определяет реализацию. 16/32-бит
div— 10 µops. 64-бит — 33 µops из микрокода. Это не масштабирование, это другой алгоритм.
Наверное вы успели заметить, что в одном случае 6 тактов, а в другом 7 тактов, хотя throughput — 6. Кто украл такт? И как вообще так получилось, что все, что вокруг деления на в одном случае ничего не стоит, а в другом случае обходится лишь в 1 такт. Если это будет интересно, то я обязательно освещу это в другой статье. Всем спасибо, что дочитали до конца!
Замеры выполнены на Intel Core i7-10510U (Comet Lake, 14nm, микроархитектура Skylake). Данные о latency и throughput — uops.info. Все эксперименты — чистый NASM x86-64, Linux/X11.
ссылка на оригинал статьи https://habr.com/ru/articles/1024862/