JavaScript в C ++ для более быстрого JavaScript
Сегодня я собираюсь провести смелый эксперимент.
Придумываем оптимизирующий компилятор JavaScript для JavaScript.
Оптимизировать по какой метрике? Производительность выполнения кода (например, сколько времени нужно, чтобы вычислить n-е простое число).
Я начал с того, что прочитал статью Сурма, защитника разработчиков Google, Является ли WebAssembly волшебной производительностью, пикси-пылью?. Пойдите, посмотрите, это сбалансированная, продуманная и хорошо написанная статья. Для этого требуются 3 программы JavaScript и следует процесс создания более быстрой версии WebAssembly (проходящей через AssemblyScript).
Я попробую что-то подобное, но нацелив его непосредственно на JavaScript, а не на WebAssembly.
Правила игры:
- Я взял несколько произвольных тестов JavaScript
- Мне нужно придумать эквивалентную версию только для JavaScript, которая будет более производительной.
- Я должен делать это в основном автоматически
- Добавление аннотации типа - единственная разрешенная модификация исходного кода.
TL; DR: В основном мне удалось добиться успеха! Перейдите на страницу https://carlopi.github.io/js-opt-benchmark/, чтобы запустить тесты на вашем собственном устройстве / браузере.
Определение объема
Как продолжать решать такую задачу? Возможно ли это вообще?
Механизмы JavaScript (V8 / SpiderMonkey / JavaScriptCore) выполняют множество умных и мощных оптимизаций, но должны соблюдать баланс, поскольку более сложные оптимизации повлекут за собой неприемлемую задержку компиляции (компиляция и выполнение происходят в вашем браузере).
Нам просто нужно заранее найти способ выполнить эти более сложные оптимизации.
Вот план: преобразовать код JavaScript в LLVM Промежуточное представление, позволить LLVM оптимизировать IR и сгенерировать код JavaScript.
Одна из основных проблем заключается в том, что LLVM IR и JavaScript имеют совершенно разные модели памяти: «сырая» линейная память в одном случае по сравнению с независимыми объектами (и указателями, в которых нельзя выполнять арифметические действия).
Это влияет на все 3 этапа: JavaScript - ›IR, IR -› Оптимизированный IR, оптимизированный IR - ›Оптимизированный JavaScript по-разному.
Презентаций
Сначала сделаем шаг назад, кто я? Я Карло, инженер-компилятор компании Leaning Technologies.
В последние месяцы мне поставили задачу улучшить возможности взаимодействия Cheerp.
Cheerp - это компилятор, чем-то похожий на Emscripten, поскольку он основан на LLVM, принимает C ++ в качестве входных данных и генерирует WebAssembly. Вдобавок ко всему Cheerp уникален тем, что позволяет компилировать код C ++ в родной JavaScript (= объекты C ++ преобразуются в объекты JavaScript с компоновкой, дружественной к движкам JavaScript: детали).
Я нахожусь в привилегированном положении: у меня есть практические знания об инструменте, который сделает шаги по оптимизации и генерации кода выполнимыми.
Вернемся к основной проблеме: теперь у нас есть код JavaScript, и мы хотим передать его в Cheerp. Оттуда компилятор позаботится о применении всех проходов оптимизации LLVM (и обеспечении того, чтобы дополнительные инварианты не были нарушены) и генерации JavaScript для нас.
Теперь, чтобы начать этот процесс, нам нужно обработать код JavaScript и вывести либо Cheerp-совместимый LLVM IR, либо непосредственно код C ++ (соответствующий модели Cheerp).
Я выбрал путь прототипа, который казался более быстрым: компиляцию JS в C ++.
JavaScript → C ++
Теперь проблема, с которой я остался, выглядела так: как сгенерировать код C ++, который имеет ту же семантику, что и данная программа JavaScript?
Я немного исследовал, какие инструменты были доступны для синтаксического анализа JavaScript в абстрактное синтаксическое дерево, и обнаружил, что в TypeScript есть легко взломанная демонстрация того, как построить линтер на их AST. Это была идеальная отправная точка.
TypeScript - это надмножество JavaScript, которое позволяет добавлять информацию о типе к параметрам / возвратам / переменным, и он должен быть скомпилирован в JavaScript, чтобы его запускали движки.
(Обратите внимание, что одна из явных нецелевых TypeScript - это оптимизация результирующего кода, поэтому компилятор TypeScript в основном занят проверкой того, что запрещенные операции не выполняются, используя информацию о типе всякий раз, когда она предоставляется)
TypeScript AST
TypeScript AST в настоящее время имеет более 300 видов узлов. Например, PlusToken, AsteriskEqualsToken, Identifier, IfStatement и многие другие. Вот полный список: typescript.d.ts.
Учитывая, что у меня был доступ к уже проанализированному AST, я начал реализовывать рекурсивное посещение каждого узла абстрактного синтаксического дерева, реализуя один за другим каждый узел, с которым я столкнулся.
Я продолжал добавлять реализации этому посетителю, пока требовалось выполнить несколько тестов.
Я действительно столкнулся с некоторыми проблемами, не все конструкции JavaScript так же естественно, как «IfStatement», отображаются в программе на C ++, поэтому я отказался от тестов, которые требовали функциональности, которая казалась слишком длинной для реализации, или немного изменил исходный код, чтобы использовать другой (но эквивалентный) шаблон.
Затем я повторил несколько итераций, в настоящее время я реализовал около 100 видов узлов, и инструмент JavaScript для C ++ не сможет документировать, какие узлы еще не были реализованы, чтобы иметь возможность анализировать данную программу.
Я также использовал еще один ярлык, мне потребуются параметры и возвращаемые значения, чтобы тип был назначен явно. Это значительно упрощает проект, позволяя сделать больше оптимизаций.
Как выглядит этот промежуточный код C ++?
В основном это все, благодаря двум функциям Cheerp:
- Возможность клиента пространства имен отображать внешние классы и функции JavaScript, просто объявляя их вперед (уже предоставлено предоставленными Cheerp файлами заголовков: ссылка)
- Тег JSExport для экспорта данных классов или функций.
C ++ → JavaScript
Теперь нам просто нужно запустить Cheerp на нем.
/opt/cheerp/bin/clang++ intermediate.cpp -o optmized.js -O3 -target cheerp
Cheerp основан на clang / LLVM, поэтому он в основном анализирует код C ++ в промежуточное представление; запускать различные проходы оптимизации (в основном преобразования IR - ›IR) как на уровне единицы перевода, так и во время компоновки; и сгенерируйте файл JavaScript, который будет иметь семантику, эквивалентную исходному исходному коду.
Следует отметить, что нечитаемая версия оказывается примерно такой же большой, как исходный (свернутый) код. Это происходит из-за двух факторов:
- мы не поставляем нашу собственную стандартную библиотеку, но мы полагаемся на функциональные возможности языка
- Cheerp генерирует довольно компактный код
Микро эталонное время
Трудно получить правильные тесты, а тесты для микропрограмм имеют свой собственный дополнительный набор ограничений. Прочтите, например, отказ от ответственности в центральной части статьи Сурмы или Зачем измерять игрушечные тестовые программы? ».
Я запускаю свой игрушечный компилятор в следующих программах:
- алгоритмическое размытие изображения
- реализация структуры данных BinaryHeap (= проталкивать объекты, извлекать всегда самый ценный элемент из кучи)
- пузырьковая сортировка
- вычисление n-го простого числа
- вычисление n-го числа Фибоначчи
- Оценка Пи методом Монте-Карло
- Моделирование N-тела
Первые 3 теста были предметом статьи Сурмы. Четвертый вариант предложила Франциска Хинкельманн в своем докладе Скорость, скорость, скорость: JavaScript vs C ++ vs WebAssembly (репо). NBody является частью Тестовой игры компьютерного языка, а числа Фибоначчи и Пи - это стандарт сортировки математических вычислений (с целыми числами или с плавающей запятой).
Я хотел бы еще раз подчеркнуть, что эти программы не относятся к общим программам JavaScript и не представляют их. Но это нормально, так как меня интересует показать, что есть место для JavaScript - ›оптимизирующего компилятора JavaScript, и приложите несколько цифр к заявлению.
Полученные результаты
Я разместил простую веб-страницу, где вы можете протестировать эти 7 тестов на своем собственном устройстве + браузере (и, следовательно, движке JavaScript) по выбору: https://carlopi.github.io/js-opt-benchmark/.
Несмотря на то, что существует огромная вариативность (некоторые тесты выполняются быстрее только на определенных движках и более или менее эквивалентны в других), некоторые тесты показывают значительное повышение производительности (например, увеличение скорости в 1,8 раза для многих комбинаций устройств / движков). В частности, isPrime и BinaryHeap демонстрируют последовательные улучшения, которые, как я полагаю, связаны с фактической оптимизацией.
Здесь нужно сделать несколько замечаний:
- Эти цифры являются лишь нижней границей того, что можно сделать с таким инструментом. Есть много оптимизаций (например, целые числа везде!), Которые вышли за рамки.
- Смысл выбора этих тестов заключается в том, чтобы использовать уже написанный JavaScript, чтобы минимизировать время выполнения, поэтому любая производительность, извлеченная поверх этого, гораздо более значима.
- Код JavaScript, который был не таким оптимальным, как этот, возможно, выиграл бы гораздо больше от этапа компиляции.
Конец?
Мы сделали это.
Мы начали с программ на JavaScript. Мы добавили информацию о типе. Мы скомпилировали их на C ++, используя возможности Cheerp. Затем мы скомпилировали это для более быстрого JavaScript.
Идеальный рабочий процесс для такого оптимизатора был бы в основном автоматическим, с единственным шагом, требующим знания предметной области, - это добавление информации о типе.
Фактический процесс, который я повторил, чтобы добавить новый бенчмарк / тест, выглядел так:
- запустите инструмент TypeScript JavaScript to C ++
- если есть ошибки типа (например: «original.ts (12,34): Отсутствует тип в ParameterDeclaration»), добавьте соответствующие типы, вернитесь к 2
- если есть недостающие ноды AST, которые нужно реализовать, реализуйте их, вернитесь к 2
- запустите Cheerp на сгенерированном файле C ++
- если есть ошибки компиляции, найдите ошибку в посетителе AST и исправьте
- тесты + бенчмарк
Он далек от идеала и хрупкого, но работал достаточно, чтобы запустить этот эксперимент с помощью нескольких сотен строк кода.
Сравнения
Вот некоторые связанные проекты:
V8 / SpiderMonkey / JavaScriptCode
Это движки, которые фактически запускают JavaScript, в основном компилируя JavaScript в машинный код. Под капотом творится много волшебства. Стоит упомянуть, что большая часть магии зависит от знания среды выполнения о том, что на самом деле выполняется (даже не только о типах).
Компилятор закрытия Google
Closure Compiler - это компилятор JavaScript - ›JavaScript, который выполняет оптимизацию в основном с целью уменьшения размера файла JavaScript. Идея состоит в том, что загрузка файла JavaScript блокирует интерактивность, поэтому меньший размер кода является основным показателем (в моем понимании). Оптимизация компилятора Closure (например, устранение мертвого кода) в основном поможет в этом направлении. Обязательно прочтите отказ от ответственности.
Компилятор TypeScript
TypeScript дополняет язык JavaScript с целью предоставления компилятору дополнительной информации, которая помогает выявлять ошибки во время разработки. Другая цель - помочь в преобразовании современного синтаксиса JavaScript в (более) широко поддерживаемый синтаксис JavaScript.
Улучшения производительности явно не входят в компетенцию компилятора TypeScript.
AssemblyScript
AssemblyScript - это диалект TypeScript, который компилируется в Bynarien IR, а оттуда в WebAssembly. Я начал после прочтения статьи Сурмы о том, как оптимизировать производительность JavaScript (через AssemblyScript, а затем через WebAssembly).
Я очень мало разбираюсь в AssemblyScript, но уже проделано много классной работы, проверьте это.
Cheerp
Cheerp - это компилятор C ++ в JavaScript / WebAssembly. Он выполняет тяжелую работу в этом исследовании, обеспечивая генерацию кода и доступ к оптимизации LLVM. Cheerp также является основным строительным блоком для CheerpJ (от Java до HTML5) и CheerpX (от x86 / Flash до HTML5).
WebAssembly
Этот пост достаточно длинный, и, вероятно, я мог бы заполнить еще много абзацев, рассказывающих о том, что такое WebAssembly, а что нет.
Короткий ответ заключается в том, что это еще не идеальная цель для компиляции чистого JavaScript. Я мог бы поручить Cheerp скомпилировать смешанный JavaScript и Webassembly, но это означало бы дополнительную сложность (как при генерации кода C ++ , так и в объяснении), что, я не думаю, принесло бы большую пользу.
Конец!
Вот и все, я показал, как может работать оптимизирующий компилятор JavaScript - ›JavaScript, и путь для его создания. Я думаю, что это в некотором роде уникальный результат, и я очень горжусь тем, что мне это удалось.
Спасибо, что подписались до этого момента, мне было бы очень любопытно услышать какие-либо отзывы.
Я доступен в Твиттере по адресу @ carlop54002226.