Здравствуйте, уважаемые хабровчане!
Чуть меньше года назад я, так же, в песочнице, публиковал статью о начале разработки движка JavaScript на C#. Прошел год после создания проекта и я рад представить вам первую версию сего творения, которую можно скачать на nuget.
Но в этой статье я не буду пиариться, приводить сравнения с конкурентами, измерять производительность и прочее. Здесь я напишу о том, через что мне пришлось пройти, какой кровью всё это далось и с чем пришлось столкнуться.
Конфликт типизаций
Эта проблема встала одной из первых. И следует она из того, что в самом начале была поставлена цель обеспечить лёгкое взаимодействие с классами .NET. Как следствие, все встроенные типи стандартной библиотеки JavaScript реализуются одноимёнными типами на C#.
Всем известно, что в JavaScript можно вызвать любую функцию в контексте любого объекта. Некоторые из таких случаев даже описаны в спецификации. К примеру, что будет если объект arguments, хранящий аргументы вызова функции и их количество, отправить в какую нибудь функцию от Array.prototype? Правильно, она отработает как с обычным массивом и вернёт корректный результат. А как это реализовать на C#?! Оказалось, есть такой способ:
Теперь мы можем вызывать этот делегат, передав первым аргументом объект любого ссылочного типа.
Как видно, здесь нет никакой магии, используются стандартные документированные функции. Но к тому, что наступает после этого, создатели платформы, явно, не готовились — Visual Studio не может определиться с типом и при отладке даже не пытается вызвать ToString, а оператор is выдает true при проверке на тип, объявивший метод, даже если с проверяемым объектом их роднит только наследование от object. Спасает GetType, который не обманывает и возвращает реальный тип.
Понимая всю опасность такой операции я добавил атрибут AllowUnsafeCall, конструктор которого требует яно указать альтернативный тип, который готовы получить внутри помеченного им метода (так же будут приходить и наследники указанного типа).
Sparse Array (Разреженный массив)
Массивы JavaScript обладают чудным свойством — хранить элементы с индексами 0, 1, 2 и 10005000, не занимать при этом несколько гигабайт памяти, да ещё и при переборе выдавать существующие индексы в порядке возрастания, что не свойственно хеш-таблицам, про которые можно подумать. В поисках подходящей структуры данных, имеющей такие свойства, да ещё и быстрой, было перелопачено куча книг и сайтов. В какой-то момент вся эта мешанина из информации выродилась в «префиксное бинарное дерево поиска с оптимизацией под кеш процессора». Звучит громко и длинно, но на деле реализация этой структуры занимает чуть больше 100 строк кода.
Для хранения объектов создаётся три поля: один массив под «узел дерева», второй массив под сами значения и целочисленное количество выделенных элементов.
В каждом узле 4 поля:
По-умолчанию мы считаем, что объект с индексом 0 уже добавлен в массив.
Добавление:
Получение:
Здесь уже без формализации, так как оно такое же, как и добавление, за той лишь разницей, что нет шага 3, на втором шаге мы возвращаем значение, а не записываем, а в случае отсутствия нужного потомка у элемента обрабатываем отсутствие запрашиваемого значения, а не добавляем новый.
В ходе экспериментов выяснилось, что эта структура (а это чистой воды бинарное дерево), работает не намного медленнее хеш-таблицы. При этом, есть одна особенность: если перед формальным выполнением алгоритма добавления или получения «наступить» в случайный элемент, то есть вероятность, что он нас приведёт к нужному элементу за меньшее число шагов (вот тут уже пригодится значение индекса бита, который обрабатывался во время добавления этого элемента, хранящееся в поле 4). Ещё одним приятным свойством оказалось то, что при последовательном добавлении элементов они хранятся по индексам, в точности соответствующим своим ключам, что сводит время поиска к O(1).
Вот такая структурка получилась. Когда я её реализовал, время прохождения SunSpider 0.9.1 уменьшилось на 10%. По моему, это неплохо.
Rope String (Верёвочная строка)
На хабре уже писали об этом, поэтому здесь напишу только идею. Когда происходит конкатенация строк в .NET, создаётся новая строка, значение в которую сначала копируется из первой строки, потом из второй. На лицо O(n+m). Rope String это объект, который хранит ссылки на исходные объекты, а не копирует их значение. По сути, он является обещанием того, что эти две строки, если потребуется, будут одной строкой. Получается O(1). Разумеется, если мы для каждого такого объекта будем звать ToString, который, в данном случае, займёт O(n+m), выигрыша мы не получим, но когда они создают Rope от Rope и Rope от Rope… соединить их можно будет за линейное время, используя StringBuilder. Когда я добавил это решение, время на всё том же SunSpider'e уменьшилось в 5 раз.
Type prediction (Предсказание типа)
Эта оптимизация специфична для динамической природы JavaScript. Снова пример:
Какую из многочисленных реализаций "+" следует позвать в третей строке? Ну конечно же сложение чисел, здесь и думать не стоит. Но то, что очевидно для человека, не всегда понятно машине. И поэтому когда выполнение дойдёт до третей строки, виртуальная машина должна подумать и «походить» по огромной таблице сопоставления. Type prediction это попытка научить компьютер анализировать операции чуточку ближе к тому, как это делает человек. Поэтому в третей строке будет вызван таки оператор сложения чисел, который лишь будет следить, а не ошиблись ли мы при предсказании и вызовет стандартную реализацию, если это, всё таки, произошло. Сейчас эта оптимизация ещё в процессе интеграции, но уже при замене операторов "+", "<", ">", "<=", ">=" эффект хорошо заметен.
Отдельно упомяну ещё раз про конкатенацию. Сейчас этот эффект перекрывается Rope String, но когда-то, заменив
На оператор множественного слияния строк (с одним проходом по всем элементам), я получил двукратное ускорение.
В завершении немного о проекте. Движок остался интерпретирующим. Были попытки добавить JIT с помощью System.Linq.Expressions, но по какой-то причине это решение привело только к замедлению, посему это направление заброшено.
Чуть меньше года назад я, так же, в песочнице, публиковал статью о начале разработки движка JavaScript на C#. Прошел год после создания проекта и я рад представить вам первую версию сего творения, которую можно скачать на nuget.
Но в этой статье я не буду пиариться, приводить сравнения с конкурентами, измерять производительность и прочее. Здесь я напишу о том, через что мне пришлось пройти, какой кровью всё это далось и с чем пришлось столкнуться.
Конфликт типизаций
Эта проблема встала одной из первых. И следует она из того, что в самом начале была поставлена цель обеспечить лёгкое взаимодействие с классами .NET. Как следствие, все встроенные типи стандартной библиотеки JavaScript реализуются одноимёнными типами на C#.
Всем известно, что в JavaScript можно вызвать любую функцию в контексте любого объекта. Некоторые из таких случаев даже описаны в спецификации. К примеру, что будет если объект arguments, хранящий аргументы вызова функции и их количество, отправить в какую нибудь функцию от Array.prototype? Правильно, она отработает как с обычным массивом и вернёт корректный результат. А как это реализовать на C#?! Оказалось, есть такой способ:
- Через Reflection получить MethodInfo того метода, который нужно вызвать.
- Получить MethodHandle.GetFunctionPointer()
- Через Activator создать делегат с аргументами тех типов, которые использованы в оригинальной функции, но при этом добавить первый аргумент типа object.
Теперь мы можем вызывать этот делегат, передав первым аргументом объект любого ссылочного типа.
Как видно, здесь нет никакой магии, используются стандартные документированные функции. Но к тому, что наступает после этого, создатели платформы, явно, не готовились — Visual Studio не может определиться с типом и при отладке даже не пытается вызвать ToString, а оператор is выдает true при проверке на тип, объявивший метод, даже если с проверяемым объектом их роднит только наследование от object. Спасает GetType, который не обманывает и возвращает реальный тип.
Понимая всю опасность такой операции я добавил атрибут AllowUnsafeCall, конструктор которого требует яно указать альтернативный тип, который готовы получить внутри помеченного им метода (так же будут приходить и наследники указанного типа).
Sparse Array (Разреженный массив)
Массивы JavaScript обладают чудным свойством — хранить элементы с индексами 0, 1, 2 и 10005000, не занимать при этом несколько гигабайт памяти, да ещё и при переборе выдавать существующие индексы в порядке возрастания, что не свойственно хеш-таблицам, про которые можно подумать. В поисках подходящей структуры данных, имеющей такие свойства, да ещё и быстрой, было перелопачено куча книг и сайтов. В какой-то момент вся эта мешанина из информации выродилась в «префиксное бинарное дерево поиска с оптимизацией под кеш процессора». Звучит громко и длинно, но на деле реализация этой структуры занимает чуть больше 100 строк кода.
Для хранения объектов создаётся три поля: один массив под «узел дерева», второй массив под сами значения и целочисленное количество выделенных элементов.
В каждом узле 4 поля:
- Ключ, по которому осуществляется доступ. Целое беззнаковое 32 бита
- Индекс первого потомка (или нулевой, что уместнее в данном случае)
- Индекс второго потомка
- Индекс бита. Создан для оптимизации
По-умолчанию мы считаем, что объект с индексом 0 уже добавлен в массив.
Добавление:
- Пусть i = 31;
- Если ключ равен ключу текущего элемента, записать в массив значений по индексу текущего элемента добавляемое значение и выйти.
- Если ключ текущего элемента больше добавляемого ключа, записать в текущий элемент добавляемый ключ, в массив значений добавляемое значение, после чего вызвать добавление рекурсивно с предыдущим ключом и значением, после чего выйти.
- Взять i-тый бит ключа. Если он равен 0, сделать текущим элементом первого потомка, иначе второго потомка, уменьшить i на 1. Если потомком считается элемент с индексом 0, добавить новый элемент, назначить его потомком предыдущего, потомками нового элемента элемент с индексом 0, ключ сделать равным добавляемому ключу, индекс бита равным i и записать значение. Иначе перейти к шагу 2.
Получение:
Здесь уже без формализации, так как оно такое же, как и добавление, за той лишь разницей, что нет шага 3, на втором шаге мы возвращаем значение, а не записываем, а в случае отсутствия нужного потомка у элемента обрабатываем отсутствие запрашиваемого значения, а не добавляем новый.
В ходе экспериментов выяснилось, что эта структура (а это чистой воды бинарное дерево), работает не намного медленнее хеш-таблицы. При этом, есть одна особенность: если перед формальным выполнением алгоритма добавления или получения «наступить» в случайный элемент, то есть вероятность, что он нас приведёт к нужному элементу за меньшее число шагов (вот тут уже пригодится значение индекса бита, который обрабатывался во время добавления этого элемента, хранящееся в поле 4). Ещё одним приятным свойством оказалось то, что при последовательном добавлении элементов они хранятся по индексам, в точности соответствующим своим ключам, что сводит время поиска к O(1).
Вот такая структурка получилась. Когда я её реализовал, время прохождения SunSpider 0.9.1 уменьшилось на 10%. По моему, это неплохо.
Rope String (Верёвочная строка)
На хабре уже писали об этом, поэтому здесь напишу только идею. Когда происходит конкатенация строк в .NET, создаётся новая строка, значение в которую сначала копируется из первой строки, потом из второй. На лицо O(n+m). Rope String это объект, который хранит ссылки на исходные объекты, а не копирует их значение. По сути, он является обещанием того, что эти две строки, если потребуется, будут одной строкой. Получается O(1). Разумеется, если мы для каждого такого объекта будем звать ToString, который, в данном случае, займёт O(n+m), выигрыша мы не получим, но когда они создают Rope от Rope и Rope от Rope… соединить их можно будет за линейное время, используя StringBuilder. Когда я добавил это решение, время на всё том же SunSpider'e уменьшилось в 5 раз.
Type prediction (Предсказание типа)
Эта оптимизация специфична для динамической природы JavaScript. Снова пример:
var a = 1;
var b = 2;
var c = a + b;
Какую из многочисленных реализаций "+" следует позвать в третей строке? Ну конечно же сложение чисел, здесь и думать не стоит. Но то, что очевидно для человека, не всегда понятно машине. И поэтому когда выполнение дойдёт до третей строки, виртуальная машина должна подумать и «походить» по огромной таблице сопоставления. Type prediction это попытка научить компьютер анализировать операции чуточку ближе к тому, как это делает человек. Поэтому в третей строке будет вызван таки оператор сложения чисел, который лишь будет следить, а не ошиблись ли мы при предсказании и вызовет стандартную реализацию, если это, всё таки, произошло. Сейчас эта оптимизация ещё в процессе интеграции, но уже при замене операторов "+", "<", ">", "<=", ">=" эффект хорошо заметен.
Отдельно упомяну ещё раз про конкатенацию. Сейчас этот эффект перекрывается Rope String, но когда-то, заменив
"abc" + 1234 + 567На оператор множественного слияния строк (с одним проходом по всем элементам), я получил двукратное ускорение.
В завершении немного о проекте. Движок остался интерпретирующим. Были попытки добавить JIT с помощью System.Linq.Expressions, но по какой-то причине это решение привело только к замедлению, посему это направление заброшено.
