Comments 46
[понимаю, что разговариваю с переводом, но всё же]
Теперь каждый непрямой бранч получил своё собственное место в таблицах предсказателя переходов, поэтому наверное и стало быстрее по сравнению с единственным бранчем в единственном месте. Предсказывать переход после конкретного опкода железке стало проще.
Что касается раскладывания по 256 байт -- возможно, стоило бы попробовать раскладывать по величине, кратной нечётному числу размеров кешлинии например, чтобы альясинг в кеше стал меньше.
После таких конструкций:
match op {
0x00 => op::brk(self, dev, pc),
0x01 => op::inc::<0b000>(self, dev, pc),
0x02 => op::pop::<0b000>(self, dev, pc),на 256 позиций, как-то желание читать дальше пропадает.
А что вас смушает? Я Rust не знаю, но выглядит как оптимальный вариант с точки зрения компилятора. Все опкоды заинлайнены в один большой цикл (что и видно в дизасме). Хочешь таблицу адресов делай, хочешь таблицу переходов, ну или двоичный поиск. Собственно тут ручками и делается то, что должен был сделать компилятор.
Это индусский способ реализации массива функций.
А если автора так беспокоят микрооптимизации эффективности , что он взялся расписывать руками массив, то он бы лучше убрал здесь передачу параметров и использование объектов.
Массив указателей на функцию будет добавлять как минимум +1 операцию на разыменования. Учитывая, что это виртуальная машина и каждый опкод даёт этот оверхэд, то у вас будет константный прирост оного. Зачем иметь оверхэд, если можно не иметь?
В машинном коде нет никаких разыменований. Будет переход на адрес, загруженный из памяти в регистр ARM, как и в другом случае.
И всё это полная фигня по сравнению с той кучей операций, которую генерит автору компилятор на передачу параметров вместо использования глобальных переменных.
В машинном коде нет никаких разыменований.
окей, два перехода на адрес - один к элементу в массиве и один к функции. В случае автора велик шанс, что код просто заинлайнится (ибо врядли опкоды делают что-то тяжёлое) и никакого второго перехода к функции не случится и код тела функции просто продлжит исполнятся.
использования глобальных переменных.
тут согласен и не согласен. Да передача параметров имеет шанс добавить накладных расходов, но опять же - инлайнинг функции с большой вероятностью это всё митигирует. Да и параметры там кучка интов. Ну и если уж хранить некое состояние, то в пределах некоторой структуры, а не глобальной переменной.
окей, два перехода на адрес - один к элементу в массиве и один к функции. В случае автора велик шанс, что код просто заинлайнится (ибо врядли опкоды делают что-то тяжёлое) и никакого второго перехода к функции не случится и код тела функции просто продлжит исполнятся.
В том и другом случае будет выборка по индексу из таблицы вариантов (или массива указателей) и переход по адресу кода тела функции, инлайновый он там или нет. Это в том случае, если компилятор достаточно умный и в варианте автора просечёт сам сделать таблицу адресов (массив) вместо долгих и нудных проверок на сравнения с номерами вариантов.
тут согласен и не согласен. Да передача параметров имеет шанс добавить накладных расходов, но опять же - инлайнинг функции с большой вероятностью это всё митигирует. Да и параметры там кучка интов.
Реальный код, сгенерированный компилятором у автора, приведён выше. Видно, что там до 10 команд и более расходуется на выборку параметров. Даже простейшие операции ADD и SUB реализуются 7 машинными командами, из которых 1 по сути делает полезную работу, а 6 представляют собой оверхед на связывание.
Конечно, автору надо как-то разбираться в том числе и со стеком эмулируемой машины, но и это можно сделать гораздо эффективнее. Например, верхушку эмулируемого стека хранить в регистрах (благо, основная масса команд в стековой архитектуре глубоко в стек не погружаются).
можно сделать гораздо эффективнее. Например, верхушку эмулируемого стека хранить в регистрах
Сильно усложнит логику каждой операции.
Или я что-то не понимаю. Например, опкод ADD, который берёт 2 аргумента из стека и кладёт результат обратно, на псевдокоде как должен быть реализован?
Что будет делать интерпретатор, если встретит 5 раз подряд опкод ADD? Этот случай, согласен, редкий, но предложенная оптимизация будет ему мешать, т.к. больше времени потратит на менеджмент, что у нас в стеке, а что в регистрах.
В архитектуре ARM пользователю доступны 17 регистров из 32 в качестве регистров общего назначения. Допутим, мы выделим под верхушку стека 12 из них. Тогда у нас будет, если не напутал в подсчёте, 13 различных вариантов команды ADD:
add x2, x1, x2
add x3, x2, x3
...
add x12, x11, x12
add [sp], x12, [sp]
add [sp+1], [sp], [sp+1]
и дальше inc sp
где sp – это регистр, содержащий эмулируемый указатель стека (например, пусть это будет x13).
Для оптимизации в последнем варианте можно добавить перезагрузку новой верхушки стека в регистры.
А сама команда в том или ином варианте будет выбираться индексированием по opcode+sp из таблицы переходов. То есть у нас не будет одной эмулируемой команды add, а будет 13 разных команд в зависимости от состояния стека.
Отвечая на вопрос, команда ADD 5 раз подряд содержательно исполнится так:
add x2, x1, x2
add x13, x13, #1
add x3, x2, x3
add x13, x13, #1
add x4, x3, x4
add x13, x13, #1
add x5, x4, x5
add x13, x13, #1
add x6, x5, x6
add x13, x13, #1
(каждая из этих команд выполняется за 1 такт)
плюс сама логика выборки виртуальных команд интерпретатора.
Это вы предлагаете компилятор, который преобразует 5 подряд инструкций ADD виртуальной машины в соответствующие инструкции на целевой архитектуре.
Автор, как я понимаю, пишет классическую FORTH-систему, и ему нужен интепретатор.
Если мы переходим от интерпретатора к компилятору, например к JIT, полностью исчезает проблема цикла fetch-decode-execute, которой посвящена статья (но появляются более сложные проблемы).
Не-не-не. Я, может, не очень правильно выразил свою мысль. Тут будет так:
; тут инструкции декодирования кода команды и выборки следующих двух инструкций по коду команды ADD и значению SP=1
add x2, x1, x2
add x13, x13, #1
; тут повторение цикла декодирования, то есть опять те же инструкции декодирования кода команды и выборки следующих двух инструкций по коду команды ADD и значению SP=2
add x3, x2, x3
add x13, x13, #1
и т.д. Я просто декодер опкодов не хочу пытаться писать, потому что он одинаков везде.
Но определённый элемент jit в этом, конечно, есть.
Снова не понял идею. Сегмент кода read-only или вы в него пишете?
Если r/o, вы хотите вместо декодирования одной команды ADD декодировать сразу две ADD, идущие подряд, и переходить на соответствующий кусок кода, который выполняет две ADD? Но количество вариантов растёт экспоненциальным взрывом, это будет непрактично.
Сегмент кода r/o. Команды интерпретируются и выполняются строго по одной. Но поскольку у нас интерпретатор, то мы знаем текущее конкретное состояние указателя стека (относительно регистрового пула и памяти) к моменту декодирования виртуальной команды ADD. Поэтому мы виртуальную команду ADD с указателем стека, равным 1, можем декодировать в реальную команду add x2, x1, x2, а виртуальную команду ADD с указателем стека, равным 2 – в реальную команду add x3, x2, x3(*)
А дальше после любой из этих команд мы выполняем реальную команду add x13, x13, #1, являющуюся просто инкрементом указателя виртуального стека, так как виртуальная команда ADD уменьшает на 1 количество элементов в виртуальном стеке, а стек у нас, допустим, растёт вниз.
После чего прокручиваемся в цикле интерпретации на декодирование и исполнение следующего виртуального опкода.
(*) у нас будет двухмерный массив адресов обработчиков виртуальных инструкций, индексируемый по первому измерению опкодом, а по второму – значением min(sp, 14). И если мы не выскочим за значения sp больше 12, то нам и не придётся лезть в оперативную память за данными. На практике, конечно, тут надо время от времени корректировать положение верхушки стека, как я написал выше, но это несущественно усложнит вычисления с sp, так как они всё равно будут в регистрах.
На самом деле, можно даже и массив адресов обработчиков не делать, а зарезервировать на каждый обработчик сколько-то байтов, и адрес обработчика получать просто умножением его номера на длину.
Теперь понял. На игрушечных примерах это нормально, на реальных программах, когда мы входим из функции в функцию, стек растёт довольно прилично, и придётся часто корректировать отображение стека на регистры.
Это затратная операция. Если сдвигать на 1, это 12 копирований по регистрам и 1 копирование (вытеснение) в память, но сдвиг будет довольно часто, когда вычисления прыгают около границы. Можно сдвигать на 1/2 окна, на 6, и тогда это 6 копирований в регистры и 6 в память, но это будет уже не так часто.
Эта оптимизация не поможет при вызовах функций, но при вычислении выражений в стековой архитектуре будет эффективна.
Кажется, нагрузка на цикл декодирования будет выше, профита от такой оптимизации.
Для современных арихитектур, в том числе ARM, доступ в память на порядки дороже любых операций с регистрами.
Доступ к кешу имеет latency 4 цикла. С другой стороны, там взбухнет таблица переходов: больше нагрузка на icache и усложниться работа предсказателя ветвлений. Для меня неочевидно, что будет быстрее.@qw1 ответил Вам здесь
Возможно стоит посмотреть на компромисс: хранить в регистрах только два верхних элемента стека. Условно:
loop {
if !has_x2 {
x2 = pop();
has_x2 = true;
}
match opcodes[ip] {
Add => {
x1 = x1 + x2;
has_x2 = false;
}
Dup => {
push(x2);
x2 = x1;
}
// ...
}
}Такой подход, кажется более щадящим.
Также, если мне не изменяет память, то 3-4 регистра - оптимально для большинства кода на стэковой машине. Наращивать больше не очень эффективно. Но это, в основном учитывает арифметику; возможно специфика форта сдвинет данный оптимум.
больше нагрузка на icache
Да, но код интерпретатора - это всё, что нужно положить в icache. В процессорах кеши растут, чем-то надо заполнять. Есть шанс, что даже в варианте расхода x12 поместится кусок с "горячим" набором опкодов.
и усложниться работа предсказателя ветвлений
А это наоборот хорошо. Когда в коде единая точка прыжка на следующую инструкцию, в начале цикла интерпретатора, предсказатель вообще сбит с толку, куда будет следующей прыжок.
Ситуация становится лучше, если дублировать переход на следующую инструкцию после каждой команды. У предсказателя появляются паттерны, например, в этой программе после ADD чаще всего CMP.
А если на каждую глубину стека своя ветка кода, предсказателю ещё больше информации - если на стеке 2 элемента - в этой программе после ADD будет PUSH, а если 3 элемента - будет CMP.
Тут только кода интерпретатора кратно больше (кеш инструкций быстрее закончится), всё остальное быстрее будет работать.
Для простоты предположим, что в архитектуре всего 2 инструкции:
PUSH <const>
ADD
Делаем для этих инструкций N разных обработчиков, считая что i-тый обработчик работает со случаем, когда первые i ячеек стека лежат в регистрах x1, x2, ... xi
Помещаем эти обработчики в таблицы JmpTbl0, JmpTbl1, ... JmpTblN
И тогда обработчик PUSH для ветки 0
MOV x1, <const>
jmp JmpTbl1[nextopcode] ; переходим к ветке N=1
Обработчик PUSH для ветки 1
MOV x2, <const>
jmp JmpTbl2[nextopcode] ; переходим к ветке N=2
Обработчик ADD ветки 2 - оба аргумента в регистрах, результат оставляем тоже в регистре
ADD x1, x2, x1
jmp JmpTbl1[nextopcode] ; переходим к ветке N=1
Обработчик ADD ветки 1 - один аргумент в регистре, второй вытеснен в память
ADD x1, [sp], x1
INC sp
jmp JmpTbl1[nextopcode] ; остаёмся на ветке N=1
Безотносительно содержимого статьи - а что это за такой интересный инструмент, выдающий разбивку времени выполнения по каждой ассемблерной операции? (1я картинка)
Я так и не понял, как называется эта реализация Форта?
Статья интересная, спасибо за перевод. Особо ценна первая ссылка на статью The Structure and Performance of Efficient Interpreters посвященную исследованию поведения предсказателей в различных вриантах имплементации VM, всё остальное это её производные.
Прочитав оригинальную статью я даже немного побаловался с direct threaded кодом на Си: https://github.com/pointcheck/code_snippets/blob/master/Labels_as_Values_Direct_Threaded/direct-threaded.c
Ассемблерная реализация примерно на 30% быстрее исходной!
Восклицательный знак здесь совершенно неуместен - 30% это совершенно незначительный результат по соотношению ускорение/затраченное время. Я не берусь за асм, если не уверен в хотя бы 200% процентах (то есть 2-кратного ускорения), а в целом достигал 40-кратного ускорения.
Быстрее на 100 % - это двукратное ускорение.
Быстрее на 200 % - это уже трехкратное ускорение.
(да, я очень популярен на вечеринках)
Ну он не говорил "на".
Не суть. Я потому и предпочитаю говорить "в", а не "на", потому что это более интуитивно понятный критерий. Оптимизация на ассемблере в наше время это прежде всего что? Это прежде всего SSE, ускорение в 2 раза, AVX, ускорение в 4 раза, и FPU, ускорение за счёт хранения промежуточных результатов в стеке сопроцессорра, а не в памяти.
Зависит от задачи. 30% ускорение на сжатие архива, 3D-рендер или кодирование видео - это 46 минут ожидания вместо часа.
Ну опять же - такие задачи обычно в фоновом режиме выполняются. Никто в здравом уме не втыкает в монитор в течение часа, наблюдая за шкалой прогресса. Критично - это когда архив нужно делать каждый час, а время на создание этот самый час превышает. Или когда данные сжимаются перед отправкой по сети - суммарное время должно быть меньше, чем при передаче просто несжатых данных.
А 30% прироста можно получить просто используя компилятор от Intel (я пробовал). Который может делать несколько вариантов оптимизации кода в зависимости от платформы, на которой этот код запускается. И прославившийся тем, что АМД в эти варианты не входила)
Есть нюанс. Разница в 30% это разница между топовой и средней видеокартой. Либо между топовым и средним процессором. Да и задачи бывают разные. Многократное минутное повторение одного и того же процесса в течении восьми рабочих часов, к примеру.
Если разница между топовой и средней железкой заключается только в 30% производительности, то это чистый развод на бабки, и приобретать такую топовую железку имеет смысл только в целях демонстративного потребления.
На практике обычно топовое железо имеет те или иные качественные преимущества (например, высокую надёжность, хорошие условия гарантии и т.д.)
Компиляторы — это результат буквально человеко-веков разработки, и они понимают процессор гораздо лучше, чем вы.
В гораздо большей степени правильно следующее: современные процессоры глубоко оптимизированы исполнять код, который генерируют компиляторы, и не оптимизированы исполнять код, который удобно писать человеку.
Компиляторы — это результат буквально человеко-веков разработки, и они понимают процессор гораздо лучше, чем вы.
Какое-то время назад я вдруг столкнулся с тем, что все вокруг начали бездумно повторять это утверждение. Вроде бы это было связано с какой-то презентацией нового gcc, или типа того. Но это же вовсе не так для любых случаев. Если у вас есть компилятор C образца 1989 года и ассемблер - вы совершенно точно понимаете процессор гораздо лучше, чем этот компилятор и напишете в разы более оптимальный код. Да и в специфических случаях даже с современными компиляторами всё не так однозначно, так как компилятор не понимает алгоритм и не видит, где можно срезать углы или пренебречь точностью.
К тому же далеко не все эти человеко-века были потрачены на увеличение эффективности компилятора. Вангую, что основная часть времени уходит на отладку и поддержку совместимости с тоннами накопленного легаси кода.
Так и есть. Компиляторы в большинстве случаев дают сравнимый код. При этом снижается порог вхождения в специальность и решается одна из важнейших задач программирования - преемственность. Представьте себе промсистему на QNX, программу для которой писал дед, а правит внук
Скажи мне мой юный друг, как ветвление в асме будет не предсказуемым, по-моему вам надо начинать с асма для Z80!!!!😂😂😂
Побеждаем компилятор в скорости при помощи ассемблера