Алгоритмы и решения при разработке движка JavaScript на C#

Здравствуйте, уважаемые хабровчане!

Чуть меньше года назад я, так же, в песочнице, публиковал статью о начале разработки движка JavaScript на C#. Прошел год после создания проекта и я рад представить вам первую версию сего творения, которую можно скачать на nuget.
Но в этой статье я не буду пиариться, приводить сравнения с конкурентами, измерять производительность и прочее. Здесь я напишу о том, через что мне пришлось пройти, какой кровью всё это далось и с чем пришлось столкнуться.

Конфликт типизаций

Эта проблема встала одной из первых. И следует она из того, что в самом начале была поставлена цель обеспечить лёгкое взаимодействие с классами .NET. Как следствие, все встроенные типи стандартной библиотеки JavaScript реализуются одноимёнными типами на C#.
Всем известно, что в JavaScript можно вызвать любую функцию в контексте любого объекта. Некоторые из таких случаев даже описаны в спецификации. К примеру, что будет если объект arguments, хранящий аргументы вызова функции и их количество, отправить в какую нибудь функцию от Array.prototype? Правильно, она отработает как с обычным массивом и вернёт корректный результат. А как это реализовать на C#?! Оказалось, есть такой способ:

  1. Через Reflection получить MethodInfo того метода, который нужно вызвать.
  2. Получить MethodHandle.GetFunctionPointer()
  3. Через Activator создать делегат с аргументами тех типов, которые использованы в оригинальной функции, но при этом добавить первый аргумент типа object.

Теперь мы можем вызывать этот делегат, передав первым аргументом объект любого ссылочного типа.

Как видно, здесь нет никакой магии, используются стандартные документированные функции. Но к тому, что наступает после этого, создатели платформы, явно, не готовились — Visual Studio не может определиться с типом и при отладке даже не пытается вызвать ToString, а оператор is выдает true при проверке на тип, объявивший метод, даже если с проверяемым объектом их роднит только наследование от object. Спасает GetType, который не обманывает и возвращает реальный тип.
Понимая всю опасность такой операции я добавил атрибут AllowUnsafeCall, конструктор которого требует яно указать альтернативный тип, который готовы получить внутри помеченного им метода (так же будут приходить и наследники указанного типа).

Sparse Array (Разреженный массив)

Массивы JavaScript обладают чудным свойством — хранить элементы с индексами 0, 1, 2 и 10005000, не занимать при этом несколько гигабайт памяти, да ещё и при переборе выдавать существующие индексы в порядке возрастания, что не свойственно хеш-таблицам, про которые можно подумать. В поисках подходящей структуры данных, имеющей такие свойства, да ещё и быстрой, было перелопачено куча книг и сайтов. В какой-то момент вся эта мешанина из информации выродилась в «префиксное бинарное дерево поиска с оптимизацией под кеш процессора». Звучит громко и длинно, но на деле реализация этой структуры занимает чуть больше 100 строк кода.
Для хранения объектов создаётся три поля: один массив под «узел дерева», второй массив под сами значения и целочисленное количество выделенных элементов.
В каждом узле 4 поля:

  1. Ключ, по которому осуществляется доступ. Целое беззнаковое 32 бита
  2. Индекс первого потомка (или нулевой, что уместнее в данном случае)
  3. Индекс второго потомка
  4. Индекс бита. Создан для оптимизации

По-умолчанию мы считаем, что объект с индексом 0 уже добавлен в массив.
Добавление:

  1. Пусть i = 31;
  2. Если ключ равен ключу текущего элемента, записать в массив значений по индексу текущего элемента добавляемое значение и выйти.
  3. Если ключ текущего элемента больше добавляемого ключа, записать в текущий элемент добавляемый ключ, в массив значений добавляемое значение, после чего вызвать добавление рекурсивно с предыдущим ключом и значением, после чего выйти.
  4. Взять 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, но по какой-то причине это решение привело только к замедлению, посему это направление заброшено.
Поделиться публикацией

Похожие публикации

Комментарии 20

    +1
    А можно всё-таки немного сравнения с конкурентами? =) Что-то же послужило причиной написания своего решения, интересно было бы узнать, чем именно не устроил тот же Jurassic. Когда я где-то год назад присматривался к JS-движкам, остановился именно на нём: он показался самым зрелым и активно развивающимся. (Правда потом пришёл к выводу, что для моих нужд удобнее просто взять и заюзать PhantomJS, но это совсем другая история.)
      +4
      Jurassic использует System.Reflection.Emit, который недоступен на некоторых платформах. В частности WP7. Платформа старенькая, конечно, но всё таки.
      Если смотреть по производительности, то по результатам sunspider jurassic медленнее примерно на 40%: Jurassic, NiL.JS.
      Если смотреть на поддержку стандартов, то Jurassic заваливает 759 тестов (версия 2.1) из 11 121. NiL.JS — 87 из 11 547.
      Если оценивать сложность интеграции (передачу объектов в среду js, получение их обратно) то Jurassic требует навешивать атрибуты на свойства и методы, которые должны быть доступны (у них это в TODO). NiL.JS работает с любым типом (включая generic) из коробки и, при желании, можно дать доступ к целому пространству имён (на GitHub есть пример с System.Windows.Forms).
      Вот в чём я им точно проигрываю, так это в отладке. Они поддерживают отладку в студии, у меня только скромный callback по оператору debugger или на каждую строчку, если это включить.
      0
      Скажите, а события в вашей библиотеке поддерживаются? Эмулировать нажатия клавиш, клики мышкой можно?
        +3
        Да, поддерживаются. При подписывании на событие или передаче функцию js в функцию .net, принимающую делегат, что то же самое, будет создана обёртка, транслирующая вызов в js функцию
          +2
          Очень круто! Спасибо, буду пользоваться!
        0
        А чем плох jint в версии 2.x?
          +4
          На всё том же sunspider первый проход jint закончил за 1 минуту 58 секунд. Понимая, что их осталось ещё 9, я закрыл тест, закрыл студию, удалил jint
            0
            Готов попробовать NiL.JS в нашем проекте, и соответственно писать багрепорты, если найдутся. Есть ли хоть какие-то минимальные примеры использования? Хоть простые вещи:
            1) установка значений глобальных переменных
            2) добавление глобальных внешних функций
            3) вызов js-функции с передачей параметров (простые типы, .net объекты, массивы) и возвратом результата

            Очень полезная штука, если ещё нет — возможность ограничения времени выполнения скрипта.
              0
              В тестовом проекте на GitHub, а конкретно в файле Program.cs есть примеры добавления глобальных переменных и функций. Но нормальных примеров, признаю, нет. Упустил. Сегодня, но чуть позже, напишу мануал по основным возможностям в там вики.
              Ограничить время выполнения нельзя.
                0
                Да, там посмотрел. Но не нашел как вызвать функцию скрипта после его первого выполнения.
                Например:

                var script = new Script(@"
                function test(a,b,c) {
                return a+b+c;
                }
                ");

                script.Invoke();

                а теперь надо вызвать test с передачей туда параметров и получением результата… как?
                в script.Context не нашлось чего-то похожего
                  0
                  Подготовил примеры. Можно посмотреть

                  Конкретно в этом случае:
                   var addFn = script.Context.GetVariable("test").Value as NiL.JS.Core.BaseTypes.Function; 
                   System.Windows.Forms.MessageBox.Show(addFn.Invoke(new NiL.JS.Core.Arguments { 1, 2, 3 }).ToString());
                  
                    0
                    Спасибо. Попробую. Куда лучше писать репорты? Чтобы тут не мусорить
                      0
                      Если, по какой-то причине, недоступен багтрекер на github, то в профиле есть скайп
          +4
          Как автору той статьи про Rope интересно — как вы реализовали этот самый Rope и тестировалась ли скорость получения символа по индексу?
          Дело в том что при простом создании Concatenation Node при склейке строк очень легко придумать сценарий в котором время индексации вырождается до O(n).
          Я провел достаточно много времени в поисках алгоритма конкатенации который минимизирует матожидание времени доступа к символу, но ничего лучше декартова дерева по неявному ключу с рандомными приоритетами так и не откопал. А там конкатенация за логарифм.
            +1
            Нет, таких исследований я не проводил. Хотя, да, стоит. Сейчас там реализация «в лоб». На тот момент задач ещё было гора, вагон и маленькая тележка, поэтому не хотелось надолго задерживаться на чем-то одном
            +1
            Я не спец, но впечатляет. И код аккуратно выглядит, разобраться очень просто. Не хочу показаться глупым, но какое практическое применение? Ну кроме встроенного языка.
              0
              В рабочем проекте я приспособил его для локализации. Вместо стандартного DisplayNameAttribute мы используем его наследника, которому передаем путь к ресурсу с локализованым текстом
              0
              Разреженный массив можно было сделать как LinkedHashMap в java
                0
                А есть возможность подключения html-страницы для дальнейшего обращения к DOM? Скажем, на примере jQuery.
                  0
                  Есть возможность подключить движок html. Если сможете найти или реализовать такой — пожалуйста. Стандарт ECMAScript не предусматривает реализации модели DOM

                Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                Самое читаемое