Часть 2. Иллюзорный автомобиль

[thedeemon]

Чуть менее, чем все виртуальные машины, которые я встречал и делал, были стековыми или регистровыми. В первом случае у нас есть некий стек значений, в него можно складывать всякие константы, а разные операции берут из него значения, проводят над ними какие-то действия, и результат кладут вместо взятых. При этом большинство команд в байткоде не имеют аргументов, т.к. их аргументы уже лежат на стеке, будучи положены туда другими командами. Соответственно, даже простые действия представляются целой серией операций (положить в стек один аргумент, положить другой, совершить действие...), и все время туда-сюда изменяется stack pointer, в простейшем случае - индекс в массиве. В случае регистровых ВМ у нас есть массив регистров, а у команд есть аргументы, указывающие из каких регистров брать исходные значения и куда сохранять результат операции. Количество операций, необходимых для совершения тех же действий, у регистровой ВМ меньше, но если мы хотим иметь вызовы функций, особенно рекурсивных, то возникают отдельные сложности - нужно или сохранять нужные регистры на стеке, или иметь целый стек регистровых массивов.

Виртуальная машина, которая использовалась у меня до этого момента, и в код которой компилился тот DSEL на Руби, была регистровой, причем вообще без стека. Все функции там инлайнились, а рекурсивные функции не поддерживались. Выделением памяти она тоже не занималась - все необходимые буферы должны были быть выделены вызывающей программой и переданы через регистры. Такие ограничения создавали ряд неудобств, поэтому было решено, что в LeoVM нужен какой-то стек и какое-то управление памятью. В стеке будут аргументы функций. Если из функции А вызывается Б, то локальные переменные А должны пережить этот вызов, значит их тоже стоит хранить в стеке. Что осталось? Временные значения при вычислении сложных выражений. Стек у нас резиновый, почему бы не поместить их туда же. В итоге отдельный набор регистров уже не нужен. Но хочется сохранить хорошую скорость регистровой ВМ, поэтому будем к значениям на стеке относиться как к регистрам: пусть команды берут исходные значения не с верхушки стека, а с произвольных позиций во фрейме, и результат пусть пишут в произвольное место. Каждое значение на стеке будет адресоваться смещением относительно frame pointer'a - специального регистра, хранящего абсолютный адрес некоторого места в стеке. Количество локальных переменных в каждой функции компилятору известно. При компиляции сложных выражений смещения для временных значений тоже можно вычислить заранее. Т.е. тот процесс распределения адресов, который в стековой ВМ происходит динамически путем изменения SP, можно один раз проделать статически при компиляции. При вызове функций мы сохраняем стековую семантику: аргументы кладутся на верхушку стека, а после отработки вызванной функции вместо них на стеке должен быть результат. В LeoVM никакого Stack Pointer'a нет, и "верхушка стека" определяется статически как минимальное смещение от FP, которое больше всех смещений переменных и временных значений. Количество аргументов и возвращаемых значений тоже компилятору известно, поэтому он просто вычисляет "верхушку стека", кладет аргументы туда, и при вызове функции увеличивает Frame Pointer на величину ("верхушка стека" + место для аргументов и результата). Соответственно, команда Call имеет два аргумента - адрес кода функции и величину, на которую нужно увеличить FP (команд прямого изменения FP нету, он меняется только командами Call и Ret). Вызванная функция знает, что аргументы надо искать слева от FP, туда же нужно положить результат, а справа от FP - свободное место для локальных переменных и пр.



Команд в LeoVM изначально было всего 15: арифметика, копирование интов и байтов, вызов/возврат, выделение памяти, условные и безусловный переходы. Арифметические команды трехадресные - имеют три аргумента: два источника и результат. У других команд может быть меньше источников, или нет результата, зато есть адрес кода для перехода или вызова. Каждый источник и результат задается числом, а у команд есть модификаторы, которые говорят как это число понимать - как регистр с заданным смещением от FP, как значение, на которое такой регистр указывает, или как просто число. Команды условного перехода имеют два аргумента-источника и адрес. Они сравнивают аргументы, и если условие выполнено, то управление переходит по указанному адресу.

Про память.
В программах, которые будут писаться для LeoVM, динамическое выделение памяти нужно довольно редко и в основном для выделения временных краткоживущих буферов для расшифрованных строк и посчитанных матриц. Делать ручное освобождение или сложный механизм отслеживания мусора не хотелось, поэтому была реализована очень простая схема. В набор команд вошла команда New с аргументом-назначением, получающим адрес выделенной памяти, и аргументом-источником, задающим требуемый размер. У ВМ есть большой заранее выделенный кусок памяти, от которого просто отщипывается очередная часть, и указатель на свободную зону (HP - Heap Pointer) смещается. Когда командой Call вызывается какая-нибудь функция, этот указатель, вместе с Frame Pointer и Instruction Pointer сохраняется в отдельном стеке контекстов (в стек данных они не пишутся, чтобы нельзя было испортить), а при возврате по команде Ret они все восстанавливаются, таким образом, вся выделенная внутри функции динамическая память автоматически освобождается одним махом. При этом компилятор гарантирует, что указатели на нее не будут переданы из функции наверх. Спросите, как же работал map из первого примера? Об этом позже, но краткий ответ: без Call'ов.

Оптимизация.
Когда работающий вариант ВМ был получен и проверен, я стал снизу-вверх строить компилятор, постепенно повышая уровень конструкций, о чем будет рассказано в других частях. Когда компилятор был готов, пришло время заняться оптимизацией. Для этого команды ВМ были разделены на комбинации более мелких команд, реализующих элементарные действия. Например, команда ADD Dest Src1 Src2 была представлена последовательностью из четырех команды: LOAD Src2, LOAD Dest, LOAD Src1, ADD. Получилась новая МикроВМ с той же семантикой, но другим набором инструкций, более атомарным. Компилятор был модифицирован на выдачу кода этой МикроВМ. После этого в МикроВМ была добавлена запись трасс: во время исполнения программы каждая исполняемая команда записывалась в трассу в виде одного символа. На более-менее типичной программе была получена трасса - файл размером около 100 мегабайт. После этого был написан специальный компрессор: он считал число вхождений каждой пары подряд идущих символов, брал самую часто встречающуюся пару и заменял ее на новый символ. Т.е. определялось, какие действия чаще всего идут подряд, чтобы можно было их объединить в одну команду. После каждой такой итерации размер трассы сокращался, и после примерно 20 итераций он сократился в 10 раз. Дальше полученные супер-команды были проанализированы, и стало ясно, какие комбинации стоит сделать отдельными командами ВМ. Например, оказалось, что в командах условного перехода чаще всего сравниваются регистры. А из арифметики чаще всего используется сложение, причем либо с только регистровыми операндами, либо с регистрами и константой. И еще, что тоже логично, часто встречается увеличение регистра на 1 или 4 (размер инта). В итоге к первоначальному набору из 15 команд были добавлены еще 7, являющиеся частными случаями предыдущих команд, когда жестко заданы модификаторы и/или значения. Так, например, появились команды INC и INC4. Частота появления этих новоиспеченных инструкций весьма велика, а поскольку при их исполнении не нужно разбирать модификаторы аргументов и ветвиться по ним, то скорость исполнения заметно возрастает. Такая оптимизация (плюс перенос разбора модификаторов из главного цикла внутрь веток отдельных команд) увеличила скорость работы в 2 раза по сравнению с оригинальной LeoVM.

Дальше уже в новую ВМ была добавлена запись трассы и был проведен аналогичный анализ. Он показал, что очень часто за безусловным переходом сразу идет сравнение и условный переход. Это было вызвано устройством циклов, которые компилировались так:

while (condition) { body }

превращался в

Label:
if (condition) {
 body;
 goto Label;
}

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

goto Cond_Label;
Body_Label:
body;
Cond_Label:
if (condition) goto Body_Label;

Так у нас цикл на одну инструкцию короче - нет безусловного перехода. Эта оптимизация дала около 5%, т.к. безусловный переход был довольно простой командой, и много времени на него не уходило.

Сама ВМ сделана как простой цикл

while(ip < codelen) { switch(code[ip] & CMD_MASK) { ...

т.е. без всякого шитого кода и computed gotos. Что занятно, интеловский компилятор 7.1 ее компилирует в менее эффективный код, чем MSVC6.

Дальше: Часть 3. Первые шаги

Comments

[mr-aleph.livejournal.com]

а, region based memory management... просто и со вкусом.

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

[thedeemon.livejournal.com]

В Leo функции не первоклассные и возвращать их нельзя. Но передавать и конструлить на лету можно, в определенных пределах.

[nponeccop.livejournal.com]

> сделать в одной функции массив и сделать лямбду, которая ссылается
> на этот массив, а потом вернуть эту лямбду из функции нельзя?

Лучше короче спросить: "upwards funarg problem не решена?"

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

iinc 3 -10    ; subtract 10 from local variable 3

, стековая часть PABC-машины, используемой в Клине, также содержит инструкции чтения и записи стеков на произвольной глубине (Плазмеер-Экелен, разделы 10.2.5, 10.2.6).

[mr-aleph.livejournal.com]

>> Вот хотя бы JVM

вы чего-то попутали.
в JVM локальные переменные и стэк операндов --- это разные вещи.

[nponeccop.livejournal.com]

Это не имеет значения. Я возражал против этого неверного пассажа (скажем, большинство команд в байткодах JVM, PABC и х87 FPU имеют аргументы, простые действия не представляются серией операций).
---
При этом большинство команд в байткоде не имеют аргументов, т.к. их аргументы уже лежат на стеке, будучи положены туда другими командами. Соответственно, даже простые действия представляются целой серией операций (положить в стек один аргумент, положить другой, совершить действие...)
---
Ниже thedeemon исправился и уточнил, в чём он видит новизну своего решения.

[mr-aleph.livejournal.com]

Я возражал против использования JVM, как иллюстрации для предложения

В частности, стековые машины как правило, допускают произвольную адресацию вглубь

JVM не допускает никакой "произвольной адресации вглубь"

[nponeccop.livejournal.com]

JVM допускает произвольную адресацию вглубь в пределах массива локальных переменных. Этого достаточно для решения проблемы производительности, описанной thedeemon. А логическое вынесение фреймов локальных переменных из стека нужно для работы bytecode verifier, т.е. иррелевантно обсуждаемым вопросам.

[mr-aleph.livejournal.com]

мы говорим не о проблеме производительности.

причем тут вообще верификатор? откуда взялось это "нужно"?

факт №1: стэк и локальные переменные в JVM разделены.
факт №2: адресация по стеку в JVM не поддерживается.

dixi.

[nponeccop.livejournal.com]

Мы говорим как раз о том, что thedeemon реализовал аналог локальных переменных Java для достижения производительности, и ничего нового этим не придумал.

С фактами 1-2 я как бы не спорю. См. также мой комментарий ниже о том, что возможность более глубокой адресации, чем текущие локальные переменные, вряд ли будет востребована кодогенератором.

[mr-aleph.livejournal.com]

Это никаким образом не "аналог локальных переменных Java".

У Java совершенно другая архитектура комманд - практически постоянно используется стэк и ничего серьезного не сделать без этого. Даже из функции значения не вернуть без стэка.

[thedeemon.livejournal.com]

Базовый x87:
The x87 family does not use a directly addressable register set such as the main registers of the x86 processors; instead the x87 registers form a 8-level deep stack structure ranging from ST(0) to ST(7). The x87 instructions typically operate by pushing, calculating, and popping values on this stack with monadic operations (FSQRT, FPTAN etc) implicitly addressing the topmost ST(0) and dyadic operations (FADD, FMUL, FCOM, etc) implicitly addressing ST(0) and ST(1).


JVM:
The computational model of Java bytecode is that of a stack-oriented programming language. For example, assembly code for an x86 processor might look like this:

add eax, edx
mov ecx, eax

This code would add two values and move the result to a different location. Similar disassembled bytecode might look like this:

0 iload_1
1 iload_2
2 iadd
3 istore_3


CLR:
The Common Intermediate Language is object-oriented and stack-based. That means that data is pushed on a stack instead of pulled from registers like in most CPU architectures.

In x86 it might look like this:

add eax, edx
mov ecx, eax

The corresponding code in IL can be rendered as this:

ldloc.0
ldloc.1
add
stloc.0 // a = a + b or a += b


Squeak (Smalltalk):
20 <70> self
21 <10> pushTemp: 0
22 <77> pushConstant: 2
23 send: -
24 send: fib:
25 send: +
26 <7C> returnTop


Python bytecode:
21 LOAD_GLOBAL 1 (fib)
24 LOAD_FAST 0 (n)
27 LOAD_CONST 2 (1)
30 BINARY_SUBTRACT
31 CALL_FUNCTION 1


Elisp:
12 constant fib
13 varref n
14 constant 2
15 diff
16 call 1
17 plus
18 return


Yarv (Ruby 1.9), SECD, Forth - аргументы и результат на стеке.
Так что неверный пассаж вполне верный.

[nponeccop.livejournal.com]

Да, приличная выборка, отличающаяся от моей.

> аргументы и результат на стеке

Это само по себе не является признаком отсутствия произвольной адресации. В PABC например "аргументы и результат на стеке", но есть произвольное чтение-запись вглубь.

[thedeemon.livejournal.com]

Произвольное чтение и запись практически всегда в таких ВМ есть. Речь о параметрах арифметических и логических операций - могут ли они обращаться напрямую или нужно сначала класть в стек.

[thedeemon.livejournal.com]

Да, обычно можно обращаться вглубь стека, но адресуют обычно от SP, который все равно динамически плавает, и результат кладется на верхушку, а потом записывается вглубь отдельной командой. Тут же SP вообще нет.

[nponeccop.livejournal.com]

Всё равно непонятно.

SP нет, но есть FP. В чем отличия? Чем подход отличается от JVM Local Variables Array? В JVM внутри функции SP не плавает - и обращения к переменным выполняются по их индексу.

[mr-aleph.livejournal.com]

В JVM внутри функции SP не плавает - и обращения к переменным выполняются по их индексу.

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

[nponeccop.livejournal.com]

Приведенная мной команда проигнорирована?

вы троллите что ли?

[mr-aleph.livejournal.com]

приведённая вами комманда примитивна по сути --- позволяет инкрементировать локальную переменную на _константу_. уже инкремент на значение из другой локальной переменной требует перекладывать оба значения в стек и снимать результат со стека в локал.

Re: вы троллите что ли?

[nponeccop.livejournal.com]

Спасибо, теперь понятно.

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

[mr-aleph.livejournal.com]

Пожалуйста.

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

Да это не суть и важно, наверное... Главное, что человек поделился своим весьма интересным опытом.

[thedeemon.livejournal.com]

Во что превращается a = b+c ?
Я так понимаю, они сначала a и b положатся на стек операндов (меняя SP), потом безаргументный add их там сложит (меняя SP) потом верхушку стека запишут в а.
У меня же это одна команда, типа ADD|RRR, 0, 1, 2.

[thedeemon.livejournal.com]

* b и c положатся на стек.

[nponeccop.livejournal.com]

Вы команду iinc, которую я упомянул, смотрели? Есть возможность двухадресной работы с локальными переменными. Т.е. в JVM стековые операции присутствуют ДОПОЛНИТЕЛЬНО к регистровым, т.е. наиболее критичные операции там ускорены, и стековые вычисления служат для хранения темпорари при вычислении длинных выражений (чтобы не захламлять фрейм), которые редки. Вам же на каждую темпорари придется резервировать слот.

[zeux.livejournal.com]

Количество используемой памяти при данном подходе разумеется не больше, чем при javовском - слоты, зарезервированные под temporary, очень быстро отмирают. Т.е. это фактически тот же стек, только все положения в нем явно записаны в байткоде (положение относительно текущего фрейма - compile-time константа в обоих подходах, просто в случае со стеком - неявная)

[nponeccop.livejournal.com]

> Что занятно, интеловский компилятор 7.1 ее компилирует
> в менее эффективный код, чем MSVC6.

Насколько менее эффективный?

[thedeemon.livejournal.com]

VC6 - 1.71 s
Intel - 2.26 s

[zeux.livejournal.com]

С локальными переменными в общем достаточно типичный подход, в lua если я правильно понимаю такая же схема, ну и у меня такая же.

Про оптимизации - неужели недостаточно было трассировать исходную VM, зачем вводить еще один слой?

[mr-aleph.livejournal.com]

в lua адресация в пределах одного фрейма и нету push/pop-операций

а тут я так понял можно пушать/попать и лазить по всему стэку (может быть неправильно понял).

[zeux.livejournal.com]

насколько я понимаю, и тут нет push/pop и адресация в пределах фрейма (ну, если расширить фрейм на параметры функции)

[thedeemon.livejournal.com]

Команд push/pop в LeoVM нет, писать и читать можно в произвольное место относительно FP, в том числе, при желании, сильно левее FP, например, обращаться к переменным вызывающей функции.

[nponeccop.livejournal.com]

Но, как я понимаю, реальное применение этой возможности ограничено возможностями компилятора, и лазить выше текущего фрейма имеет смысл только при наличии в языке локальных процедур а ля Паскаль. Т.е. фактически эта возможность ПРОИЗВОЛЬНО ГЛУБОКОЙ адресации не будет никогда использована, и реально имеем ту же Джавскую модель локальных переменных, только БЕЗ стека для хранения темпорари.

И новизна заключается, таким образом, в отказе от отдельного механизма для темпорари и использовании для этого статически выделенных слотов в local variables array.

[thedeemon.livejournal.com]

Да, все верно.

Я на новизну вообще не претендую, кстати.

[thedeemon.livejournal.com]

Да, весьма похоже на Lua, только без таких жестких ограничений на размер фрейма.

Про еще один слой - была шальная мысль, что получится увидеть более интересные сочетания микрокоманд и так родить новые интересные команды. В принципе, трассу МикроВМ можно рассматривать как просто чуть более детальную трассу оригинальной ВМ.

[aka-rider.livejournal.com]

Спасибо, очень интересно.
Т.е. из конца цикла делался прыжок на условие, вот и получалась такая частая комбинация. Но ее можно сократить, если компилировать циклы иначе:
Там либо фрагменты кода надо местами поменять, либо я ничего не понимаю.

У меня в VM идеи похожи, только формат команд поддерживает константы.

+--------+--------+--------+--------+
|        |        | addr1  | addr2  |
| opcode |dst addr+--------+--------+
|        |        |  const operand  |
+-----------------+-----------------+

[ijne* ][jmp_addr][ v1_addr][ v2_addr]
[imovc** ][dst_addr][ 0x000000FA ]
* (integer) jump if not equal
** (integer) move constant

[thedeemon.livejournal.com]

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

У меня формат команд тоже поддерживает константы. У инструкций есть модификаторы, говорящие как трактовать аргументы - как константы или как смещения переменных.

[aka-rider.livejournal.com]

Не, местами менять не надо
А, понял наконец-то, спасибо.