Большое обновление ObjectScript 0.99-vm3. Часть 1: Регистровая виртуальная машина

ObjectScript — новый встраиваемый и очень легкий объектно-ориентированный язык программирования с открытым исходным кодом. ObjectScript расширяет возможности таких языков, как JavaScript, Lua, Ruby и PHP. Вы можете ознакомится с первоначальным синтаксисом языка в этой статье.

ObjectScript 0.99-vm3 — новая быстрая виртуальная машина и новые возможности.

Убраны некоторые операторы, например, clone, numberof и др. заменены функциями. Последнее значение в функции возвращается автоматически. Добавлена короткая запись для доступа к членам объекта — @varname, новый короткий синтаксис для объявления функций и мн. др.

Часть 1. Регистровая виртуальная машина ObjectScript

Традиционно языки программирования используют стековую виртуальную машину (Java, .Net, ActionScript и некоторые др.). Такие VM используют команды push, pop, чтобы добавлять значения в стек и убирать его при необходимости. При вычислении математических операций, в качестве аргументов, используются два значение на вершине стека, а результат операции замещает аргументы. Например, следующий код:

	i = j + k 

на стековой VM будет скомпилирован в команды:

	push_local  j    - в стеке одно значение 	push_local  k    - в стеке два значения 	operator    +    - в стеке одно значение 	set_local   i    - значение из стека сохранено в переменную 	pop              - в стеке нет значений 

Раньше ObjectScript тоже использовал стековую VM, но не сейчас. Виртуальная машина была полностью переписана. Теперь ObjectScript использует Регистровую виртуальную машину (Register-based Virtual Machine), а выше приведенный пример будет скомпилирован в одну команду:

	add i, j, k 

ObjectScript в отладочной информации показывает данную команду следующим образом:

	var i = var j [operator +] var k 

Сразу бросается в глаза разница в количестве команд для выполнения действия (5 для стековой VM и 1 для регистровой). Действительно, код стековых VM имеет намного больше команд, чем у регистровых, также сильно разнится количество команд VM. Например, предыдущая стековая версия ObjectScript VM2 имела 111 команд против текущей VM3 с 36 командами. Чем меньше команд, тем проще VM, тем ее легче поддерживать и оптимизировать, тем проще реализовать на разных языках программирования при необходимости, в том числе проще сделать JIT (компиляция в машинный код).

Пример со сменой значений в переменных:

	i, j = j, i 

ObjectScript компилирует этот код в три команды:

	move: # = var j 	move: var j = var i 	move: var i = # 

где # означает использование регистра под временную переменную. Если посмотреть на команды, то можно заметить, что смена значений переменных происходит оптимальным образом и полностью эквивалентна следующему коду:

	temp = j 	j = i 	i = temp 

Что такое Регистровая виртуальная машина

Регистровая виртуальная машина работает не со стеком значений, а со значениями в регистрах. Регистр — это временная локальная переменная, которая существует все время, когда к ней возможен доступ.

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

Вторая изюминка — нету команд push и pop. Такие команды довольно накладны для VM, т.к. нужно изменять стек и контролировать его вершину, нужно постоянно проверять стек на переполнение и необходимость реаллоцирования. Когда мы избавляемся от команд работы со стеком, появляется возможность сохранять результаты операций сразу в итоговые переменные, минуя временное пристанище в стеке.

Третья изюминка — намного меньшее количество команд, более простая VM для реализации, в том числе для JIT.

Как было видно из вышеприведенного примера, команда для стековой VM представляет из себе атомарное действие, она более простая, чем команда для регистровой VM и занимает меньше места. Например, команда push может быть закодирована 1 байтом и следующим байтом может кодироваться уже следующая команда. В этом таится и плюс и жирный минус.

Плюс стековой VM в том, что команды кодируются меньшим количеством байт и результирующий код занимает меньше места.

Минус в том, что часть команд все же невозможно закодировать одним байтом, например, push_double, jump и др. Такие команда требуют дополнительный аргумент, для push_double — это число с двойной точностью double (8 байт), для jump — смещение (например, 4 байтовое — int32) для перехода. Т.к. команды в стековой VM следуют друг за другом, они никак не выравнены, поэтому число double или смещение int32 могут оказаться в памяти по любому адресу, в том числе по не четному и вообще какому угодно. Те, кто знаком с архитектурой процессоров, сразу обратят на это внимание, т.к. такие аргументы нельзя читать одной командой процессора. Если попытаться это сделать, например, прочитать dword по нечетному адресу в памяти, то на архитектуре ARM произойдет исключение и программа закроется с ошибкой. На разных архитекторах могут быть либо ошибки либо катастрофическое падение в производительности. Поэтому читать такие многобайтовые аргументы из потока байт нужно только побайтно и с помощью побитовых операций смещений формировать итоговый аргумент. Это несколько уменьшает скорость работы VM.

В регистровой VM многие команды имеют три аргумента и занимают (вместе с аргументами) 4 байта. Для того, чтобы исключить выше описанные проблемы, все команды в ObjectScript выравнены и всегда занимают 4 байта, даже в том случае, если часть битов реально не используется. Например, команда move в ObjectScript имеет два аргумента. Но даже в этом случае ObjectScript выходит из положения следующим образом. Очень часто команды move следуют друг за другом и заполняют два последовательных регистра. В этом случае ObjectScript (на этапе оптимизации) генерирует одну команду move2 вместо двух move:

	move2 R, A, B 

которая исполняется как две команды move:

	move    R,      A 	move    R+1,    B 

при этом move2 имеет три аргумента и полностью использует 4 байта. Выравнивание команд дает возможность читать их одной командой процессора, что увеличивает скорость работы VM.

В совокупности с др. плюсами, ObjectScript с новой регистровой VM3 стал быстрее на треть по сравнению с предыдущей стековой VM2.

Как работает регистровая VM и от куда берутся регистры

Компилятор ObjectScript собирает информацию не только о локальных переменных, которые программист использует в функциях, но и обо всех временных переменных (заведенных компилятором). Таким образом, регистр — это временная локальная переменная в функции. VM обращается к локальным переменным и к регистрам полностью эквивалентно, по индексу. Поэтому одна и та же команда VM может работать и с локальными переменными и с регистрами, а результат операции может быть сохранен сразу в локальную переменную, минуя временную.

Например, следующий код:

	k = i - j*k / (x + y - z*i / j) + i 

ObjectScript компилирует в:

	# (59) = var j (5) [operator *] var k (6) 	# (60) = var x (7) [operator +] var y (8) 	# (61) = var z (9) [operator *] var i (4) 	# (61) = # (61) [operator /] var j (5) 	# (60) = # (60) [operator -] # (61) 	# (59) = # (59) [operator /] # (60) 	# (58) = var i (4) [operator -] # (59) 	var k (10) = # (58) [operator +] var i (4) 

В скобках указаны индексы, где находятся локальные переменные или регистры (индексы рассчитываются во время компиляции). Собранная компилятором информация обо всех локальных переменных (в том числе временных — регистрах), позволяет вычислить максимальный размер стека, необходимый для выполнения данной функции. Когда функция запускается, она сохраняет вершину стека и резервирует размер стека, определенный компилятором. Индексы к регистрам (локальным переменным) используются как относительные смещения от сохраненной вершины стека, что позволяет делать рекурсивные вызовы функций без каких либо затруднений.

Вызов функции в регистровой VM

Для того, чтобы вызвать функцию, ObjectScript резервирует непрерывную последовательность регистров, в которые помещает аргументы функции. Затем происходит сам вызов функции с информацией о том, где начинается первый аргумент (начало последовательности) и количество значений в последовательности. Первый аргумент становится вершиной стека для новой функции, а аргументы уже находятся по нужным смещениях в стеке и становятся ее локальными переменными. Пример, как это выглядит при вызове функции с тремя параметрами:

	func(i, k - x*y * (z + i), j*k) 

ObjectScript компилирует в:

	begin call 	  move: # (59) = var func (11) 	  move: # (60) = const null (-1) 	  move: # (61) = var i (4) 	  # (63) = var x (7) [operator *] var y (8) 	  # (64) = var z (9) [operator +] var i (4) 	  # (63) = # (63) [operator *] # (64) 	  # (62) = var k (10) [operator -] # (63) 	  # (63) = var j (5) [operator *] var k (10) 	end call: start 59, params 5 

Функция запускается с последовательностью из пяти значений, начиная с индекса 59. Первые два значения — это служебные параметры, а именно 59 — сама функция, 60 — this для функции (в данном случае null):

  move: # (59) = var func (11)   move: # (60) = const null (-1) 

Далее передаются сами параметры, они располагаются в регистрах с 61 по 63. Первый параметр — это просто переменная i, она копируется в регистр 61:

  move: # (61) = var i (4) 

Второй параметр — это результат математических операций k - x*y * (z + i), он сохраняется в регистре 62:

  # (63) = var x (7) [operator *] var y (8)   # (64) = var z (9) [operator +] var i (4)   # (63) = # (63) [operator *] # (64)   # (62) = var k (10) [operator -] # (63) 

Третий параметр (j*k) сохраняется в регистре 63:

  # (63) = var j (5) [operator *] var k (10) 

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

Где еще используется регистровая виртуальная машина

Регистровая VM также используется в Lua 5.0 и выше, в quakec (был такой скриптовой язык программирования для quake 1 и многочисленных портов), есть регистровые VM для Java (например, Dalvik VM). Формально, любая программа на C++/C и др. языках, которая компилируется в машинный код, использует регистровую модель для внутренних операций и стек для вызова функций.

Итого

Новая Регистровая виртуальная машина ObjectScript (VM3) стала быстрее на треть предыдущей стековой VM2 и имеет меньше команд, всего 36 против 111 в VM2. Меньшее количество команд сильно упрощает VM и увеличивает шансы реализовать JIT при необходимости.

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

Также стек используется в ObjectScript API для упрощения интеграции с пользовательским кодом. ObjectScript API остался без изменений и полностью совместим с предыдущей версией.

Продолжение

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

print "factorial(10) = " .. {|a| a <= 1 ? 1 : a * _F(a-1)}(10) 

выведет:

factorial(10) = 3628800 

и мн. др.

Другие релевантные статьи об ObjectScript:

• ObjectScript API, интеграция с C++. Часть 4: подключение пользовательских классов и функций на C++
• ObjectScript API, интеграция с C++. Часть 3: подключение модуля с функциями на C++
• ObjectScript API, интеграция с C++. Часть 2: выполнение скрипта на OS из C++
• ObjectScript API, интеграция с C++. Часть 1: работа со стеком, вызов функций OS из C++
• ObjectScript — новый язык программирования, быстрее чем PHP и JS
• ObjectScript — новый язык программирования