Здравствуйте, дорогие хабровчане! Чуть меньше года назад я тоже в песочнице опубликовал статью о начале разработки Движок JavaScript на C# .
Прошел год с момента создания проекта и я рад представить вам первую версию этого творения, которую можно скачать с сайта Нугет .
Но в этой статье я не буду пиарить себя, проводить сравнения с конкурентами, измерять производительность и т. д. Здесь я напишу о том, через что мне пришлось пройти, какой кровью все это стоило и с чем мне пришлось столкнуться.
Конфликт ввода Эта проблема возникла одной из первых.
И это следует из того, что в самом начале целью было обеспечить простое взаимодействие с .
NET-классами.
В результате все встроенные типы стандартной библиотеки JavaScript реализованы одноименными типами в C#.
Всем известно, что в JavaScript можно вызвать любую функцию в контексте любого объекта.
Некоторые из этих случаев даже описаны в спецификации.
Например, что произойдет, если объект аргументы , сохраняя аргументы вызова функции и их количество, отправить в некоторую функцию из Массив.
прототип ? Все верно, он будет работать как с обычным массивом и возвращать правильный результат. Как это реализовать на С#?! Оказалось, есть такой способ:
- Получите это через отражение Информация о методе метод, который нужно вызвать.
- Получать MethodHandle.GetFunctionPointer()
- Через Активатор создайте делегат с аргументами тех же типов, что и в исходной функции, но добавьте аргумент первого типа объект .
Как видите, никакой магии здесь нет, используются стандартные документированные функции.
Но к тому, что будет после этого, создатели платформы явно не подготовились — Visual Studio не может определиться с типом и при отладке даже не пытается вызвать Нанизывать и оператор является проблемы истинный при проверке типа, объявившего метод, даже если они связаны только с проверяемым объектом путем наследования от объект .
Сохранения GetType , который не обманывает и возвращает реальный тип.
Понимая опасность такой операции, я добавил атрибут Алловунсафекалл , конструктор которого требует явно указать альтернативный тип, готовый к приему внутри помеченного им метода (придут и наследники указанного типа).
Разреженный массив Массивы JavaScript обладают замечательным свойством хранить элементы с индексами 0, 1, 2 и 10005000, не занимая при этом несколько гигабайт памяти, и даже при переборе по ним возвращают существующие индексы в порядке возрастания, что не характерно для хеш-таблиц.
вы можете подумать.
В поисках подходящей структуры данных, обладающей такими свойствами и при этом быстрой, было просмотрено множество книг и веб-сайтов.
В какой-то момент вся эта каша информации выродилась в «префиксное двоичное дерево поиска, оптимизированное под кэш процессора».
Звучит громко и долго, но на самом деле реализация этой структуры занимает чуть больше 100 строк кода.
Для хранения объектов создаются три поля: один массив для «узла дерева», второй массив для самих значений и целое число выбранных элементов.
Каждый узел имеет 4 поля:
- Ключ, по которому осуществляется доступ.
Беззнаковое целое число 32 бита
- Индекс первого дочернего элемента (или нулевой, что более уместно в данном случае)
- Индекс второго ребенка
- Битовый индекс.
Создан для оптимизации
Добавление:
- Позволять я = 31;
- Если ключ равен ключу текущего элемента, записываем добавленное значение в массив значений по индексу текущего элемента и выходим.
- Если ключ текущего элемента больше, чем добавляемый ключ, запишите добавленный ключ в текущий элемент, добавленное значение в массив значений, затем рекурсивно вызовите сложение с предыдущим ключом и значением, а затем выйдите.
- Брать i-й ключевой бит. Если он равен 0, сделайте первый дочерний элемент текущим, в противном случае второй дочерний элемент уменьшите.
я на 1. Если элемент с индексом 0 считается потомком, добавьте новый элемент, назначьте его потомком предыдущего, потомками нового элемента является элемент с индексом 0, сделайте ключ равным добавленному ключу , битовый индекс равен я и запишите значение.
В противном случае перейдите к шагу 2.
В ходе экспериментов выяснилось, что эта структура (а это чистое бинарное дерево) работает не намного медленнее хеш-таблицы.
При этом есть одна особенность: если перед формальным выполнением алгоритма добавления или получения мы «наступим» на случайный элемент, то есть вероятность, что он приведет нас к искомому элементу за меньшее количество шагов (здесь значение индекса бита, который был обработан при добавлении этого элемента, хранится в поле 4).
Еще одной приятной особенностью было то, что при последовательном добавлении элементов они сохраняются в индексах, точно соответствующих их ключам, что сокращает время поиска до O(1).
Вот такая конструкция получилась.
Когда я это реализовал, время завершения SunSpider 0.9.1 уменьшилось на 10%.
На мой взгляд, это неплохо.
Веревочная струна Уже в хабе написал об этом , поэтому напишу здесь только идею.
Когда в .
NET происходит конкатенация строк, создается новая строка, значение которой сначала копируется из первой строки, затем из второй.
На грани O(n+m).
Rope String — это объект, который хранит ссылки на исходные объекты, а не копирует их значения.
По сути, это обещание, что эти две строки, при необходимости, будут одной строкой.
Получается О(1).
Конечно, если мы вызовем ToString для каждого такого объекта, что в данном случае будет принимать O(n+m), мы не получим никакого выигрыша, но когда они создают Rope from Rope и Rope from Rope. они могут подключаться в линейное время с помощью StringBuilder. Когда я добавил это решение, время на том же SunSpider уменьшилось в 5 раз.
Тип прогнозирования Эта оптимизация специфична для динамической природы JavaScript. Другой пример:
Какая из множества реализаций «+» должна вызываться в третьей строке? Ну и о сложении цифр здесь, конечно, думать не стоит. Но то, что очевидно для человека, не всегда понятно машинам.var a = 1; var b = 2; var c = a + b;
И поэтому, когда выполнение доходит до третьей строки, виртуальная машина должна подумать и «пройтись» по огромной таблице сопоставлений.
Тип предсказания это попытка научить компьютер анализировать операции немного ближе к тому, как это делает человек.
Поэтому в третьей строке будет вызван оператор сложения чисел, который будет лишь следить за тем, ошиблись ли мы в предсказании, и вызывать стандартную реализацию, если это все-таки произошло.
Сейчас эта оптимизация еще в процессе интеграции, но уже при замене операторов «+», «<”, “> ”, “<=", “> =" эффект хорошо заметен.
Отдельно еще раз упомяну о конкатенации.
Сейчас этот эффект перекрывается Rope String, но когда-то, заменяя "abc" + 1234 + 567
Для оператора слияния нескольких строк (с одним проходом по всем элементам) я получил двукратное ускорение.
В заключение немного о проекте.
Двигатель остается интерпретативным.
Были попытки добавить JIT с помощью System.Linq.Expressions, но это решение почему-то приводило только к замедлению, поэтому от этого направления отказались.
Теги: #nil #JavaScript #C++ #.
NET #JavaScript #.
NET #Алгоритмы
-
Логика
19 Oct, 24 -
23 Мая, 18:30 – Прямой Эфир Qiwi Кухни
19 Oct, 24 -
Доменно-Ориентированный Дизайн На Php
19 Oct, 24
