Производительность Excel на чистом Javascript — достижима +23


Привет Хабр!

Продолжаем битву за производительность Javascript на примере построения сводных таблиц. В прошлый раз камнем преткновения стал асинхронный интерфейс IndexedDB, который, используя межпоточный вызов для каждой записи курсора, работает чудовищно медленно. Решив эту проблему путем организации крупноблочного хранения, а также применив все известные оптимизации, мне удалось поднять производительность приложения в 20 раз, и в настоящее время расчет по хранилищу в 1 миллион фактов занимает 21 секунду, что потенциально дает надежду догнать Америку Excel, который обрабатывает тот же миллион строк за 5..7 секунд.

Однопроходный алгоритм, не использующий индексы и вложенные запросы, отлично ложится на блочную схему хранения данных, и, самое обнадеживающее — позволяет распараллелить расчет по разным потокам (воркерам), по сути повторяя алгоритмы «взрослых» СУБД. Таким образом — возможности по оптимизации далеко не исчерпаны. В настоящее время расчет производится лишь одним воркером, WASM не используется, результаты «милионного» теста на различных браузерах следующие:

Браузер Время
Chomium Linux 21 сек
Firefox Linux 51 сек
Chrome Android 29 сек
Firefox Android 62 сек
В приложении доступен генератор тестовых данных, также можно загрузить собственный JSON и проверить цифры. Приложение в глубокой бетте, так что ошибки должным образом не обрабатываются, простите. Под катом — несколько кейсов по ускорению WEB-приложений, которые, конечно, все являются банальностями и очевидностями, просто я, как любитель учиться на собственных ошибках — их проверил, зафиксировал, и теперь стараюсь соблюдать.

IndexedDB


Нормальная СУБД, гарантированно поддерживаемая всеми браузерами, и не имеющая ограничений на размер базы, просто ее нужно уметь готовить. Моя первоначальная схема хранения (1 факт == 1 документ БД) обернулась неприемлемой скоростью чтения, и я был вынужден перейти к хранению данных большими блоками. Размер блока выбирается путем компромисса. Слишком маленький блок — падает общая производительность расчета из-за колбэков, слишком большой блок — падает отзывчивать интерфейса в момент чтения/записи блока (например при расшифровке строки). Опытным путем подобрал размер блока (10000 фактов == 1 документ БД). Код не сильно усложнился — перебираем в цикле блоки, внутри блока цикл по фактам, формируем полный id факта, и т.д. Единственная проблема — внутри вложенных циклов нужно делат асинхронный вызов, так что пришлось отказаться от рекурсии и изучить await :) В спецификации IndexedDB заявлен синхронный интерфейс, возможно он окажется существенно быстрее, хотя, что может быть быстрее итерации массива в памяти?

Межпоточные вызовы Javascript


Межпоточные вызовы postMessage() работают медленно. И дело даже не в том, что передаваемые данные копируются (как раз это происходит довольно быстро), а сам вызов почему-то имеет серьезные накладные расходы, и просто уменьшив частоту обменов между воркером и главным потоком со 100 раз в секунду до 10 — я увеличил производительность приложения почти в 2 раза. Проблему усугубляет медленная инициализация воркера (файл JS читается с диска и компилируется каждый раз заново), и невозможность повторного использования контекста воркера — браузер убивает завершенный воркер, и тяжелые операции (открытие базы, инициализация данных) приходится повторять каждый раз при старте потока. Ну и конечно — передать сложный объект по ссылке в воркер и обратно невозможно (за исключением ArrayBuffer, который нам не подходит). Таким образом — чем реже стартуют воркеры, и чем реже они общаются между собой, и с главным потоком — тем быстрее приложение.

Аллокации памяти


Конечно, банально звучит, но Array.push(), повторенный в цикле миллион раз, просто в разы медленней единовременной инициализации массива let arr = new Array(1000000), и последующей проверки в цикле if (arr[i] !== undefined). Даже если длину массива нельзя вычислить заранее — разумнее создать его “с запасом”, в конце концов у Javascript нет проблем с большими объектами в памяти.

PS
Нарвался на смешную особенность при попытке инициализации массива не-примитивом:

let a = new Array(100).fill({});
a[1] .prop = 1;
a[2] .prop = 2;
console.log(a[1].prop);   // выводит 2

Языку явно не хватает ИИ, чтобы понять мои очевидные намерения :)

Работа с DOM


  1. Если необходима вставка больших объемов данных (например строки таблицы) — лучше это делать группами в 100..1000 строк — так мы меньше нагружаем основной поток, и, соответственно, интерфейс будет более отзывчивым. Браузеры уже научились быстро парсить большие тексты, но легко вешаются частыми обновлениями DOM, поэтому метод insertAdjacentHTML() отрабатывает в среднем быстрее чем серия appendChild().
  2. Если нужно показать большую таблицу — контейнерная верстка тэгами TABLE или DIV не позволяет отобразить более 10 тысяч строк. Конечно, можно подгружать хвост/голову таблицы динамически при прокрутке, но в любом случае — при добавлении/удалении содержимого в блочный элемент — браузеру необходимо пересчитать ширину, то есть, по сути, отрисовать всю таблицу заново. Фиксация ширины колонок не помогает — все равно медленно, и вешает интерфейс. Как ни странно, выход нашелся в использовании контейнера PRE, который позволил вывести в расшифровку более 100 тысяч строк, да еще работать с таблицей (прокрутка, поиск, масштабирование) в процессе подгрузки “хвоста”. Единственное неудобство — при форматировании таблицы моноширинным шрифтом надо заранее знать максимальную ширину каждой колонки (значения дополняем пробелами). Замечена разница в поведении браузеров — медленный и предсказуемый Firefox позволяет работать с таблицей в процессе подгрузки хвоста, а более быстрый Chromium практически подвешивает интерфейс до окончания загрузки — понятно, что это цена оптимизации, а хочется всего и сразу.

Нарушение паттерна MVC


К сожалению, высокая производительнось несовместима с некоторыми паттернами программирования, разделяющими уровень данных, бизнес-логики и представления. Если нужна настоящая скорость — функциии нужно не разделять, а объединять, особенно при отсутствии нормального языка запросов, когда все расчеты осуществляются в циклах и рекурсиях. Например — ширина колонки для вывода на экран и преимущественный тип данных в этой колонке — это точно уровень view, но, во избежание повторного цикла — вычисление этих характеристик совмещено с вычислением агрегатов (уровень бизнес-логики), то есть паттерн явно нарушен. Это не единственный пример — разделение функций на слои предполагает обмен данными между слоями, причем на каждом уровне данные нужно трансформировать/упаковывать/распаковывать, что и составляет львиную долю тормозов при использовании фреймворков. Именно поэтому я не люблю MVC, предпочитая всегда быть ближе к народу изначальному формату данных, а если этот изначальный формат неоптимален — логичнее (для целей производительности) изменить/нормализовать/денормализовать схему хранения, чем пытаться исправлять ситуацию в промежуточных слоях. Конечно, применение паттернов — вопрос религиозный, сильно зависит от проекта, и все вышеизложенное имеет смысл, если вы пишите свою программу, а не чужую.

Перспективы дальнейшей оптимизации


  1. Параллельные вычисления. Однопроходный алгоритм плюс блочное хранение данных — отлично параллелится. Выделяем пул воркеров, каждый воркер работает со своим диапазоном блоков, дожидаемся всех в главном потоке и собираем результат. Эта часть кода пока в работе, но даже ускорение расчета в 5 раз вплотную приближает нас к заветной цели — догнать Excel.
  2. WASM. Конечно, заманчиво переписать алгоритм расчета на wasm, только я не уверен что поможет. Узким местом расчета является скорость работы объектов Map, Set, Array, а с какой стати эти объекты должны работать быстрее в wasm? Традиционно, переход на wasm оправдывают скоростью компиляции, но в данном проекте всего полторы тысячи строк, разве это много ?

Резюме


Я в восторге от возможностей WEB-приложений, от языка Javascript, и думаю, что несмотря на прохладное отношение хабровчан к данному вопросу — PWA вполне могут захватить мир. Если захотят.




К сожалению, не доступен сервер mySQL