Мы, в компании Linkurious, занимаемся работой над Linkurious Enterprise. Это — веб-платформа, которая, используя возможности графов и средства их визуализации, призвана помогать компаниям и органам власти, расположенным по всему миру, бороться с финансовыми преступлениями.
Одна из главных возможностей Linkurious Enterprise — это простой в освоении и использовании интерфейс визуализации графов, рассчитанный на неспециалистов.
В 2015 году, разочарованные возможностями существующих JavaScript-библиотек для визуализации графов, мы приступили к разработке собственной библиотеки — Ogma.
Ogma — это JS-библиотека, отличающаяся высоким уровнем производительности в плане рендеринга и выполнения вычислений, которая нацелена на визуализацию сетевых структур. Возможно, вы видели, как сетевые структуры визуализируются с помощью других JavaScript-инструментов, вроде D3.js или Sigma.js. Нам возможностей этих инструментов не хватало. Нам было важно, чтобы используемое нами решение обладало бы некоторыми специфическими возможностями, чтобы оно соответствовало бы определённым требованиям к производительности. Ни того, ни другого в сторонних библиотеках мы не нашли. Поэтому мы и решили разработать собственную библиотеку с нуля.
Визуализация сетевой структуры
Библиотека Ogma проектировалась в расчёте на использование самых современных алгоритмов. Все её составные части, от передового движка рендеринга, основанного на WebGL, до используемых в её недрах веб-воркеров, были нацелены на то, чтобы обеспечить наилучшую среди существующих решений производительность в деле визуализации сетевых структур. Мы стремились сделать так, чтобы библиотека отличалась бы хорошей интерактивностью при выполнении длительных задач, и чтобы реализованные в ней ведущие алгоритмы визуализации графов работали бы быстро и стабильно.
Технология WebAssembly (Wasm), с момента первого сообщения о ней, обещала веб-разработчикам уровень производительности, выгодно отличающийся от того, который был им доступен ранее. При этом самим разработчикам не нужно было прилагать чрезмерные усилия для использования новой технологии. Им достаточно было просто писать код на некоем известном им высокопроизводительном языке, который, после компиляции, можно было бы запускать в браузере.
После того, как технология Wasm немного развилась, мы, прежде чем внедрять её, решили её испытать, и провести некоторые тесты производительности. В общем, прежде чем без оглядки прыгать в быстрый поезд Wasm, мы решили подстраховаться.
Нас в Wasm привлекало то, что эта технология вполне могла решить стоящие перед нами задачи, используя ресурсы памяти и процессора эффективнее, чем JavaScript.
Наше исследование началось с поиска алгоритма, направленного на работу с графами, который легко было бы портировать на разные языки с использованием похожих структур данных.
Мы выбрали алгоритм n-body. Он часто используется в качестве базы для сравнения силовых алгоритмов визуализации графов. Выполняемые в соответствии с этим алгоритмом расчёты являются самой ресурсоёмкой частью систем визуализации. Если эту часть работы подобных систем удалось бы выполнить эффективнее, чем прежде, это весьма позитивно сказалось бы на всех силовых алгоритмах визуализации графов, реализованных в Ogma.
Есть ложь, грубая ложь и бенчмарки.
Макс Де Марзи
Разработка «честного» бенчмарка — это, часто, задача, которую решить невозможно. Дело в том, что в искусственно созданной среде сложно воспроизвести сценарии, характерные для реального мира. Создание адекватного окружения для обеспечения работы сложных систем — это всегда крайне сложно. Ведь в лабораторной среде легко контролировать внешние факторы, а в реальности на то, какой выглядит «производительность» решения, влияет много неожиданного.
В нашем случае бенчмарк был нацелен на решение единственной, чётко определённой задачи, на исследование производительности реализации алгоритма n-body.
Это — чёткий и хорошо описанный алгоритм, используемый уважаемыми организациями для измерения производительности языков программирования.
Как и при проведении любых честных испытаний, мы заранее определили некоторые правила, касающиеся различных исследуемых нами языков:
После того, как мы определились с правилами, мы уже могли перейти к реализации алгоритма. Но, прежде чем этим заняться, нам надо было ещё выбрать языки, производительность которых мы будем исследовать.
Wasm — это бинарный формат инструкций, запускаемых в браузере. В этот формат компилируется код, написанный на различных языках программирования. О Wasm-коде говорят, как о коде, понятном человеку, но писать программы сразу на Wasm — это не то решение, которое может принять человек, находящийся в здравом уме. В результате мы устроили опрос, касающийся бенчмарка, и выбрали следующих кандидатов:
Алгоритм n-body был реализован на этих трёх языках. Производительность различных реализаций сравнивалась с производительностью базовой реализации на JavaScript.
В каждой из реализаций алгоритма мы использовали 1000 точек и запускали алгоритм с различным количеством итераций. Мы измеряли время, необходимое на выполнение каждого сеанса работы программ.
Испытания выполнялись с использованием следующих программных и аппаратных средств:
Как видите, для тестов мы выбрали не самый быстрый компьютер, но тестируем мы Wasm, то есть — код, который будет выполняться в контексте браузера. А браузер, всё равно, обычно не имеет доступа ко всем имеющимся в системе процессорным ядрам и ко всей оперативной памяти.
Чтобы было интереснее, мы создали несколько версий каждой реализации алгоритма. В одной точки в системе n-body имели 64-битное числовое представление координат, в другой — 32-битное.
Ещё стоит отметить то, что мы использовали «двойную» реализацию алгоритма на Rust. Сначала, без использования каких-либо Wasm-инструментов, была написана «исходная», «небезопасная» Rust-реализация. Позже, с использованием wasm-pack, была создана дополнительная, «безопасная» Rust-реализация. Ожидалось, что эту реализацию алгоритма будет легче интегрировать с JS, и то, что она сможет лучше управлять памятью в Wasm.
Мы проводили эксперименты в двух основных средах. Это — Node.js и браузер (Chrome).
В обоих случаях бенчмарки выполнялись с использованием «тёплого» сценария. А именно, перед запуском испытаний сборка мусора не запускалась. Когда мы выполняли сборку мусора после запуска каждого теста, оказалось, что это не оказывает особого влияния на результаты.
На основе исходного кода, написанного на AssemblyScript, было создано следующее:
Интересно отметить тот факт, что asm.js-модуль был не полностью совместим с asm.js. Мы попытались добавить в верхнюю часть модуля директиву «use asm», но браузер не принял эту оптимизацию. Позже мы обнаружили, что использованный нами компилятор binaryen, на самом деле, и не стремился сделать код полностью совместимым с asm.js. Он, вместо этого, был ориентирован на формирование некоей эффективной JS-версии Wasm.
Сначала мы провели испытания в Node.js.
Запуск кода в среде Node.js
Потом измерили производительность того же кода в браузере.
Запуск кода в браузере
Мы сразу обратили внимание на то, что asm.js-вариант кода работает медленнее других вариантов. Но эти графики не позволяют достаточно чётко сравнить результаты различных вариантов кода с базовой JS-реализацией алгоритма. Поэтому мы, чтобы лучше во всём разобраться, построили ещё несколько диаграмм.
Отличия других реализаций алгоритма от JS-реализации (вариант бенчмарка с 64-битными координатами точек)
Отличия других реализаций алгоритма от JS-реализации (вариант бенчмарка с 32-битными координатами точек)
Варианты бенчмарка с 64-битными и 32-битными координатами точек заметно различаются. Это может привести нас к мысли о том, что в JS числа могут быть и такими, и такими. Дело в том, что числа в JS, в реализации алгоритма, принятой за базу сравнения, всегда являются 64-битными, а вот компиляторы, преобразующие код с других языков в Wasm, работают с такими числами по-разному.
В частности, огромнейшее влияние это оказывает на asm.js-вариант теста. Его вариант с 32-битными координатами точек очень сильно уступает в производительности как базовой JS-реализации, так и asm.js-варианту, в котором используются 64-битные числа.
На предыдущих диаграммах сложно понять то, как производительность других вариантов кода соотносится с JS-вариантом. Всё дело в том, что показатели AssemblyScript слишком сильно отличаются от остальных. Для того чтобы в этом разобраться, мы построили другие диаграмму, убрав результаты asm.js.
Отличия других реализаций алгоритма от JS-реализации (вариант бенчмарка с 64-битными координатами точек, без asm.js)
Отличия других реализаций алгоритма от JS-реализации (вариант бенчмарка с 32-битными координатами точек, без asm.js)
Разные представления чисел, похоже, повлияли и на другие варианты теста. Но повлияли по-разному. Так, C-вариант, в котором использовались 32-битные числа (float), стал медленнее, чем C-вариант, в котором применялись 64-битные числа (double). А оба Rust-варианта теста с 32-битными числами (f32) стали быстрее их разновидности с 64-битными числами (f64).
Анализ вышеприведённых данных может навести на следующую мысль. Так как все протестированные Wasm-сборки весьма близки по производительности к JavaScript-реализации, возможно ли, что Wasm-реализации лишь отражают особенности производительности нативных реализаций алгоритма?
Сравнение нативных реализаций алгоритма с JavaScript-реализацией
Нативные версии реализаций алгоритма всегда быстрее JavaScript-реализации.
Мы, кроме того, заметили, что Wasm-сборки работают медленнее, чем нативные варианты кода, используемого для создания таких сборок. Разница в производительности составляет 20-50%. Мы выяснили это на сокращённом варианте бенчмарка с 1000 итераций.
C-реализация и соответствующая Wasm-сборка
Rust-реализация и соответствующая Wasm-сборка
Rust-реализация, при создании которой использовался wasm-pack, и соответствующая Wasm-сборка
При измерении времени выполнения нативного кода в расчёт бралось и время, необходимое на загрузку программы, а в случае с Wasm-вариантами это время не учитывалось.
В среднем, прирост производительности двух Rust-реализаций алгоритма, в сравнении с его базовой JS-реализацией, составил 20%. Это, вероятно, хорошо для имиджа Rust, но это — слишком маленький прирост производительности в сравнении с затраченными на его получение усилиями.
Какие выводы мы можем сделать из этих испытаний? А вот какие: вдумчивое написание JS-кода позволяет получать достаточно высокую производительность и не требует перехода на другие языки программирования.
Изучение новых языков программирования — это всегда хорошо. Но на то, чтобы учить новые языки, должны быть веские причины. Производительность — это, часто, «неправильная» причина, так как на производительность сильнее влияет высокоуровневая архитектура проекта, а не компиляторы или микрооптимизации.
В порядке эксперимента, для написания реализации силового алгоритма визуализации графа, мы поменяли JavaScript на TypeScript. В результате мы улучшили качество кодовой базы, но не производительность. Мы специально замеряли производительность, и оказалась, что она, после перехода, незначительно, на 5%, выросла. Вероятно, причина тут в рефакторинге кода.
Если вам близки вопросы JavaScript-разработки и производительности, то вам, возможно, будет интересно посмотреть это выступление, в котором озвучены результаты, сходные с теми, которые получили мы.
Как вы подходите к разработке «тяжёлых» частей веб-проектов?
Одна из главных возможностей Linkurious Enterprise — это простой в освоении и использовании интерфейс визуализации графов, рассчитанный на неспециалистов.
В 2015 году, разочарованные возможностями существующих JavaScript-библиотек для визуализации графов, мы приступили к разработке собственной библиотеки — Ogma.
Ogma — это JS-библиотека, отличающаяся высоким уровнем производительности в плане рендеринга и выполнения вычислений, которая нацелена на визуализацию сетевых структур. Возможно, вы видели, как сетевые структуры визуализируются с помощью других JavaScript-инструментов, вроде D3.js или Sigma.js. Нам возможностей этих инструментов не хватало. Нам было важно, чтобы используемое нами решение обладало бы некоторыми специфическими возможностями, чтобы оно соответствовало бы определённым требованиям к производительности. Ни того, ни другого в сторонних библиотеках мы не нашли. Поэтому мы и решили разработать собственную библиотеку с нуля.
Задача
Визуализация сетевой структуры
Библиотека Ogma проектировалась в расчёте на использование самых современных алгоритмов. Все её составные части, от передового движка рендеринга, основанного на WebGL, до используемых в её недрах веб-воркеров, были нацелены на то, чтобы обеспечить наилучшую среди существующих решений производительность в деле визуализации сетевых структур. Мы стремились сделать так, чтобы библиотека отличалась бы хорошей интерактивностью при выполнении длительных задач, и чтобы реализованные в ней ведущие алгоритмы визуализации графов работали бы быстро и стабильно.
Технология WebAssembly (Wasm), с момента первого сообщения о ней, обещала веб-разработчикам уровень производительности, выгодно отличающийся от того, который был им доступен ранее. При этом самим разработчикам не нужно было прилагать чрезмерные усилия для использования новой технологии. Им достаточно было просто писать код на некоем известном им высокопроизводительном языке, который, после компиляции, можно было бы запускать в браузере.
После того, как технология Wasm немного развилась, мы, прежде чем внедрять её, решили её испытать, и провести некоторые тесты производительности. В общем, прежде чем без оглядки прыгать в быстрый поезд Wasm, мы решили подстраховаться.
Нас в Wasm привлекало то, что эта технология вполне могла решить стоящие перед нами задачи, используя ресурсы памяти и процессора эффективнее, чем JavaScript.
Наше исследование
Наше исследование началось с поиска алгоритма, направленного на работу с графами, который легко было бы портировать на разные языки с использованием похожих структур данных.
Мы выбрали алгоритм n-body. Он часто используется в качестве базы для сравнения силовых алгоритмов визуализации графов. Выполняемые в соответствии с этим алгоритмом расчёты являются самой ресурсоёмкой частью систем визуализации. Если эту часть работы подобных систем удалось бы выполнить эффективнее, чем прежде, это весьма позитивно сказалось бы на всех силовых алгоритмах визуализации графов, реализованных в Ogma.
Бенчмарк
Есть ложь, грубая ложь и бенчмарки.
Макс Де Марзи
Разработка «честного» бенчмарка — это, часто, задача, которую решить невозможно. Дело в том, что в искусственно созданной среде сложно воспроизвести сценарии, характерные для реального мира. Создание адекватного окружения для обеспечения работы сложных систем — это всегда крайне сложно. Ведь в лабораторной среде легко контролировать внешние факторы, а в реальности на то, какой выглядит «производительность» решения, влияет много неожиданного.
В нашем случае бенчмарк был нацелен на решение единственной, чётко определённой задачи, на исследование производительности реализации алгоритма n-body.
Это — чёткий и хорошо описанный алгоритм, используемый уважаемыми организациями для измерения производительности языков программирования.
Как и при проведении любых честных испытаний, мы заранее определили некоторые правила, касающиеся различных исследуемых нами языков:
- В различных реализациях алгоритма должны использоваться схожие структуры кода.
- Запрещено использование нескольких процессов или нескольких потоков.
- Запрещено использование SIMD.
- Испытанию подвергаются только стабильные версии компиляторов. Запрещено использование релизов наподобие nightly, beta, alpha, pre-alpha.
- Для каждого языка используются только самые свежие версии компиляторов.
После того, как мы определились с правилами, мы уже могли перейти к реализации алгоритма. Но, прежде чем этим заняться, нам надо было ещё выбрать языки, производительность которых мы будем исследовать.
Конкуренты JS
Wasm — это бинарный формат инструкций, запускаемых в браузере. В этот формат компилируется код, написанный на различных языках программирования. О Wasm-коде говорят, как о коде, понятном человеку, но писать программы сразу на Wasm — это не то решение, которое может принять человек, находящийся в здравом уме. В результате мы устроили опрос, касающийся бенчмарка, и выбрали следующих кандидатов:
- C
- Rust
- AssemblyScript
Алгоритм n-body был реализован на этих трёх языках. Производительность различных реализаций сравнивалась с производительностью базовой реализации на JavaScript.
В каждой из реализаций алгоритма мы использовали 1000 точек и запускали алгоритм с различным количеством итераций. Мы измеряли время, необходимое на выполнение каждого сеанса работы программ.
Испытания выполнялись с использованием следующих программных и аппаратных средств:
- NodeJS 12.9.1
- Chrome 79.0.3945.130 (Официальная сборка) (64-bit)
- clang 10.0.0 — для версии алгоритма, реализованного на языке C
- emcc 1.39.6 — фронтенд для вызова компилятора Emscripten из командной строки, альтернатива gcc/clang, а так же — линковщик
- cargo 1.40.0
- wasm-pack 0.8.1
- AssemblyScript 0.9.0
- MacOS 10.15.2
- Macbook Pro 2017 Retina
- Intel Dual Core i5 2,3 GHz, 8GB DDR3, 256GB SSD
Как видите, для тестов мы выбрали не самый быстрый компьютер, но тестируем мы Wasm, то есть — код, который будет выполняться в контексте браузера. А браузер, всё равно, обычно не имеет доступа ко всем имеющимся в системе процессорным ядрам и ко всей оперативной памяти.
Чтобы было интереснее, мы создали несколько версий каждой реализации алгоритма. В одной точки в системе n-body имели 64-битное числовое представление координат, в другой — 32-битное.
Ещё стоит отметить то, что мы использовали «двойную» реализацию алгоритма на Rust. Сначала, без использования каких-либо Wasm-инструментов, была написана «исходная», «небезопасная» Rust-реализация. Позже, с использованием wasm-pack, была создана дополнительная, «безопасная» Rust-реализация. Ожидалось, что эту реализацию алгоритма будет легче интегрировать с JS, и то, что она сможет лучше управлять памятью в Wasm.
Тестирование
Мы проводили эксперименты в двух основных средах. Это — Node.js и браузер (Chrome).
В обоих случаях бенчмарки выполнялись с использованием «тёплого» сценария. А именно, перед запуском испытаний сборка мусора не запускалась. Когда мы выполняли сборку мусора после запуска каждого теста, оказалось, что это не оказывает особого влияния на результаты.
На основе исходного кода, написанного на AssemblyScript, было создано следующее:
- Базовая JS-реализация алгоритма.
- Wasm-модуль.
- Asm.js-модуль.
Интересно отметить тот факт, что asm.js-модуль был не полностью совместим с asm.js. Мы попытались добавить в верхнюю часть модуля директиву «use asm», но браузер не принял эту оптимизацию. Позже мы обнаружили, что использованный нами компилятор binaryen, на самом деле, и не стремился сделать код полностью совместимым с asm.js. Он, вместо этого, был ориентирован на формирование некоей эффективной JS-версии Wasm.
Сначала мы провели испытания в Node.js.
Запуск кода в среде Node.js
Потом измерили производительность того же кода в браузере.
Запуск кода в браузере
Мы сразу обратили внимание на то, что asm.js-вариант кода работает медленнее других вариантов. Но эти графики не позволяют достаточно чётко сравнить результаты различных вариантов кода с базовой JS-реализацией алгоритма. Поэтому мы, чтобы лучше во всём разобраться, построили ещё несколько диаграмм.
Отличия других реализаций алгоритма от JS-реализации (вариант бенчмарка с 64-битными координатами точек)
Отличия других реализаций алгоритма от JS-реализации (вариант бенчмарка с 32-битными координатами точек)
Варианты бенчмарка с 64-битными и 32-битными координатами точек заметно различаются. Это может привести нас к мысли о том, что в JS числа могут быть и такими, и такими. Дело в том, что числа в JS, в реализации алгоритма, принятой за базу сравнения, всегда являются 64-битными, а вот компиляторы, преобразующие код с других языков в Wasm, работают с такими числами по-разному.
В частности, огромнейшее влияние это оказывает на asm.js-вариант теста. Его вариант с 32-битными координатами точек очень сильно уступает в производительности как базовой JS-реализации, так и asm.js-варианту, в котором используются 64-битные числа.
На предыдущих диаграммах сложно понять то, как производительность других вариантов кода соотносится с JS-вариантом. Всё дело в том, что показатели AssemblyScript слишком сильно отличаются от остальных. Для того чтобы в этом разобраться, мы построили другие диаграмму, убрав результаты asm.js.
Отличия других реализаций алгоритма от JS-реализации (вариант бенчмарка с 64-битными координатами точек, без asm.js)
Отличия других реализаций алгоритма от JS-реализации (вариант бенчмарка с 32-битными координатами точек, без asm.js)
Разные представления чисел, похоже, повлияли и на другие варианты теста. Но повлияли по-разному. Так, C-вариант, в котором использовались 32-битные числа (float), стал медленнее, чем C-вариант, в котором применялись 64-битные числа (double). А оба Rust-варианта теста с 32-битными числами (f32) стали быстрее их разновидности с 64-битными числами (f64).
Некачественные реализации алгоритма?
Анализ вышеприведённых данных может навести на следующую мысль. Так как все протестированные Wasm-сборки весьма близки по производительности к JavaScript-реализации, возможно ли, что Wasm-реализации лишь отражают особенности производительности нативных реализаций алгоритма?
Сравнение нативных реализаций алгоритма с JavaScript-реализацией
Нативные версии реализаций алгоритма всегда быстрее JavaScript-реализации.
Мы, кроме того, заметили, что Wasm-сборки работают медленнее, чем нативные варианты кода, используемого для создания таких сборок. Разница в производительности составляет 20-50%. Мы выяснили это на сокращённом варианте бенчмарка с 1000 итераций.
C-реализация и соответствующая Wasm-сборка
Rust-реализация и соответствующая Wasm-сборка
Rust-реализация, при создании которой использовался wasm-pack, и соответствующая Wasm-сборка
При измерении времени выполнения нативного кода в расчёт бралось и время, необходимое на загрузку программы, а в случае с Wasm-вариантами это время не учитывалось.
Итоги
В среднем, прирост производительности двух Rust-реализаций алгоритма, в сравнении с его базовой JS-реализацией, составил 20%. Это, вероятно, хорошо для имиджа Rust, но это — слишком маленький прирост производительности в сравнении с затраченными на его получение усилиями.
Какие выводы мы можем сделать из этих испытаний? А вот какие: вдумчивое написание JS-кода позволяет получать достаточно высокую производительность и не требует перехода на другие языки программирования.
Изучение новых языков программирования — это всегда хорошо. Но на то, чтобы учить новые языки, должны быть веские причины. Производительность — это, часто, «неправильная» причина, так как на производительность сильнее влияет высокоуровневая архитектура проекта, а не компиляторы или микрооптимизации.
В порядке эксперимента, для написания реализации силового алгоритма визуализации графа, мы поменяли JavaScript на TypeScript. В результате мы улучшили качество кодовой базы, но не производительность. Мы специально замеряли производительность, и оказалась, что она, после перехода, незначительно, на 5%, выросла. Вероятно, причина тут в рефакторинге кода.
Если вам близки вопросы JavaScript-разработки и производительности, то вам, возможно, будет интересно посмотреть это выступление, в котором озвучены результаты, сходные с теми, которые получили мы.
Как вы подходите к разработке «тяжёлых» частей веб-проектов?
