- PVSM.RU - https://www.pvsm.ru -
Привет!
Продолжаем битву за производительность Javascript на примере построения сводных таблиц. В прошлый раз [1] мы реализовали несколько оптимизаций, и оставалась последняя реальная возможность ускорить расчет — перейти на многопоточные вычисления. В Javascript уже давно существуют воркеры [2], реализация которых не лишена недостатков, но заявлено, что они используют реальные потоки операционной системы — так почему бы не попробовать? Неожиданно оказалось, что для распараллеливания простого, в сущности, алгоритма пришлось переписать синтакис агрегатных формул, так как старые не обладали свойстом аддитивности (подробнее под катом), но, в конечном итоге, все получилось.
Тестировалась обработка 1 миллиона фактов на двух устройствах:
Из графиков следует несколько выводов.
Поиграться с тестами можно самостоятельно — приложение тут [3], генератор тестовых данных в комплекте, время расчета выводится.
Напомню, что представляет собой наш алгоритм. В качестве исходных данных используется неструктурированное хранилище фактов, схема данных не создается. На вход подается JSON, содержащий вперемешку операции и справочники. Мы определяем вычисления на 2-х уровнях — формула на уровне отдельного факта (по сути вычисляемый атрибут), и агрегатная формула на уровне строки сводной таблицы. Затем накладываем фильтр, и строим сводную таблицу одним проходом по массиву фактов. В этом единственном цикле осуществляется группировка, рассчитываются агрегаты, извлекаются данные справочников, и определяется ширина колонок.
Данные хранятся в IndexedDB блоками, каждому воркеру выделяется свой диапазон блоков, главный поток запускает воркеры, периодически принимает от них статус (количество обработанных записей), и, дождавшись останова всех — сводит результат. На контрольном примере время сведения результата пренебрежимо мало, но на других данных, конечно, могут быть варианты. Чтобы результат сводился правильно — все агрегатные формулы должны обладать аддитивностью, то есть их можно было бы применить как к одиночным фактам, так и к уже посчитанным блокам.
Я раньше не понимал, почему Excel, взрослые OLAP системы и РСУБД не позволяют написать собственную агрегатную функцию на скриптовом языке, а содержат лишь набор заранее предопределенных типа sum(), avg() и проч. Например, достаточно долгое время в Excel не было даже функции count_distinct, да и сейчас не во всех СУБД она есть. Оказывается, если дать возможность пользователю определять свои агрегатные функции — не все из них будут аддитивными, а значит, расчет не может быть распараллелен, что убийственно для промышленной системы. Покажем это на примере 3-х функций агрегирования массива:
console.log([1, 2, 3, 4].reduce(
(accumulator, currentValue) => accumulator + currentValue
));
console.log([1, 2, 3, 4].reduce(
(accumulator, currentValue) => (accumulator + currentValue) ** 2
));
console.log([1, 2, 3, 4].reduce(
(accumulator, currentValue) => accumulator + currentValue ** 2
));
Первая функция аддитивна, так как может быть применена сама к себе, то есть:
accumulator + (accumulator + currentValue).
Вторая функция вообще не может быть распараллелена, с третьей нужно поработать, ибо применение ее в лоб к блоку:
accumulator + (accumulator + currentValue ** 2) ** 2 — даст некорректный результат, но если распарсить выражение, и понять, что это всего-лишь сумма квадратов — аддитивность достигается. В нашем же алгоритме accumulator — не просто скаляр, а массив, представляющий текущую строку сводной таблицы, а currentValue — соответственно массив значений атрибутов текущего факта (в том числе и вычисляемых), в результате чего риск поломки аддитивности возрастает.
Напомню, что в первом варианте [4] приложения в агрегатных формулах использовались функции fact(colname) и row(colname) (первая возвращает атрибут текущего факта, вторая — промежуточное рассчитанное значение колонки сводной таблицы), и уже из них составлялись выражения суммирования, подсчета количества, и т.д. Однако для пользователя велик сооблазн в одной агрегатной формуле использовать, например, несколько атрибутов факта, что недопустимо, если мы хотим многопоточности. Заниматься парсингом формул мне было лень — мало ли чего пользователь может придумать — и я принял самое простое решение — запретить в агрегатной формуле использовать атрибуты факта напрямую, а только оборачивая их в предопределенные агрегатные примитивы, таким образом наша сводная таблица будет описываться такими формулами:
"quantity-sum": "sum('quantity')",
"amount-sum": "round(sum('amount'), 2)",
"price-max": "max('price')",
"price-min": "min('price')",
"price-last": "last('price')",
"price-avg": "round(sum('price') / count(), 2)",
"price-weight": "round(sum('amount') / sum('quantity'), 2)",
"EAN-code": "selectlast('EAN-code', "fact('product') == row('product')")"
Повторных вычислений не происходит — результаты вычисления агрегатных примитивов кэшируются. Доступны примитивы sum(), count(), mul(), min(), max(), last(), first(). Последняя функция selectlast() подтягивает реквизит справочника из другого факта, то есть, по сути, реализует join хранилища самого к себе, но вычисляется в общем цикле, то есть без потери производительности. Что касается функций mode() [5], median() [6], count_distinct() — они не аддитивны, не масштабируются линейно, до окончания расчета потребуют хранить все значения в отдельной структуре (расход памяти), и поэтому будут реализованы позднее.
Наверное, на этом можно закончить попытки разгона Javascript, мы все-таки не вполне догнали Excel, хотя и вплотную приблизились.Теоретически, можно еще посмотреть в сторону gpu.js [7], для чего придется переписать алгоритм на чистые функции, но, в принципе, и так получилось неплохо. Желаю приятного программирования и свежих идей!
Автор: epishman
Источник [8]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/javascript/304643
Ссылки в тексте:
[1] прошлый раз: https://habr.com/post/434438/
[2] воркеры: https://developer.mozilla.org/ru/docs/DOM/Using_web_workers
[3] приложение тут: https://pocketolap.com/3
[4] первом варианте: https://habr.com/post/433080/
[5] mode(): https://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D0%B4%D0%B0_(%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B0)
[6] median(): https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D0%B4%D0%B8%D0%B0%D0%BD%D0%B0_(%D1%81%D1%82%D0%B0%D1%82%D0%B8%D1%81%D1%82%D0%B8%D0%BA%D0%B0)
[7] gpu.js: https://github.com/gpujs/gpu.js
[8] Источник: https://habr.com/post/435276/?utm_source=habrahabr&utm_medium=rss&utm_campaign=435276
Нажмите здесь для печати.