Многопоточные вычисления на Javascript, или как телефон выиграл гонку у ноутбука

    Привет, Хабр!

    Продолжаем битву за производительность Javascript на примере построения сводных таблиц. В прошлый раз мы реализовали несколько оптимизаций, и оставалась последняя реальная возможность ускорить расчет — перейти на многопоточные вычисления. В Javascript уже давно существуют воркеры, реализация которых не лишена недостатков, но заявлено, что они используют реальные потоки операционной системы — так почему бы не попробовать? Неожиданно оказалось, что для распараллеливания простого, в сущности, алгоритма пришлось переписать синтакис агрегатных формул, так как старые не обладали свойстом аддитивности (подробнее под катом), но, в конечном итоге, все получилось.

    Тестировалась обработка 1 миллиона фактов на двух устройствах:

    • Нетбук Linux 4.15, 2 x Intel Celeron CPU N2830 @ 2.16 GHz
    • Телефон Android 7.0, 4 x ARM Cortex-A53 @ 1.44 GHz


    Из графиков следует несколько выводов.

    1. Выигрыш от многопоточности получился весьма скромным, намного меньше ожидаемого, ибо чудес не бывает — программная многопоточность требует аппаратной многопроцессорности, а в наших устройствах мало ядер.
    2. Оптимальный размер пула воркеров совпадает с количеством ядер. Именно поэтому телефон, стабильно проигрывавший все однопоточные тесты, внезапно вырвался вперед, показав лучший результат — миллион фактов за 9 секунд.
    3. Однопроходный алгоритм масштабируется линейно — при увеличении объема исходных данных на порядок — на этот же порядок увеличивается время расчета. Проверил на телефоне — 10 миллионов фактов рассчитались за 80 секунд, 100 миллионов фактов — за 1000 секунд. Ничего не повисло и не упало. Лет 15 назад для таблиц такого размера обычно покупали Oracle.
    4. Поскольку бизнес-приложения активно переходят в WEB и мобильники — многоядерность персональных устройств абсолютно оправдана, а многопоточное программирование — это просто must have, даже для фронтенда.

    Поиграться с тестами можно самостоятельно — приложение тут, генератор тестовых данных в комплекте, время расчета выводится.

    Особенности алгоритма


    Напомню, что представляет собой наш алгоритм. В качестве исходных данных используется неструктурированное хранилище фактов, схема данных не создается. На вход подается 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 — соответственно массив значений атрибутов текущего факта (в том числе и вычисляемых), в результате чего риск поломки аддитивности возрастает.

    Напомню, что в первом варианте приложения в агрегатных формулах использовались функции 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(), median(), count_distinct() — они не аддитивны, не масштабируются линейно, до окончания расчета потребуют хранить все значения в отдельной структуре (расход памяти), и поэтому будут реализованы позднее.

    Резюме


    Наверное, на этом можно закончить попытки разгона Javascript, мы все-таки не вполне догнали Excel, хотя и вплотную приблизились. Теоретически, можно еще посмотреть в сторону GPU-вычислений, для чего придется полностью переписать алгоритм (прецедент имеется), но, в принципе, и так получилось неплохо. Желаю приятного программирования и свежих идей!
    Поделиться публикацией

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

      +4
      Как это вообще можно сравнивать, поставьте на этот нетбук нативный андроид, он будет лагать в интерфейсе. Атомы днище.
        –1
        Приложение писалось с прицелом на дальнейшее использование в мобильниках, а так, согласен конечно.
        +2
        Любопытно, что пересечение графиков (синий-красный, зелёный-жёлтый) проходит где-то в районе числа e.
          0
          Почему выигрыш получился весьма скромным?
          По-моему, вполне ожидаемо: было 28 секунд, стало 9 — в 3.1 раза быстрее. Параллелизм ограничен доступными ядрами, эффективностью декомпозиции и межпоточным взаимодействием. Плюс не стоит забывать, что внутри VM JS может тоже отъедать кусок на доступе к разделяемым данным.
            +1
            Слава богу, тут нет разделяемых данных, каждый поток полностью автономен вплоть до вычитки из БД. Сейчас пытаюсь курить шейдеры, теоретически задействовать GPU возможно, но сколько работы придется сделать — ужас. Начиная с того, что в GPU нет строк и нормальных вещественных чисел — все придется эмулировать на хешах и байтах.
              0
              Какое-то странное заявление, ведь GPU как раз с вещественными числами и работает…
                0

                Не уверен что float texture доступны на недорогих мобильниках, а без них имеем отдельные байты rgba, которые надо конвертить с учётом платформы.

                  0
                  Да и вообще, насколько я успел вникнуть в тему, шейдер может читать по сути любой элемент матрицы, а писать может только в текущий, и непонятно, как на этом сделать группировку. А если группировка на CPU, а суммирование на GPU — то и смысла нет, ведь главная задача — избавиться от цикла — распилить исходную таблицу на фрагменты, и отдать видеокарте, чтобы она сделала все сама. Изучаю дальше…
                    0
                    Насколько я помню, пиксельный шейдер выполняется для каждого пикселя изображения с той степенью параллелизма, которая поддерживается железом, и этим можно воспользоваться:

                    1. Создаете окно 1 на N пикселей,
                    2. Рисуете в нём линию через все пиксели, и тем самым запускаете пиксельный шейдер N раз,
                    3. В шейдере в цикле агрегируете 1/N часть элементов исходного массива.

                    Потом нужно уже на CPU получить N значений и агрегировать их.
                      0
                      Спасибо, я так и представлял. Просто хотелось кроме суммирования делать еще и группировку по нескольким колонкам (допустим там хеши лежат). Шейдер обработал текущий факт (ячейку матрицы), понял что сумму нужно отнести к группировке XX.YY.ZZ, но куда он данные положит? Ведь на входе мы получаем матрицу фактов, и заранее не знаем — во сколько итоговых строк ее удасться сгруппировать.
                      Логика шредера — отталкиваться от выходной матрицы, натягивая на нее входную (текстура), а у меня задача обратная — плясать от входных данных и формировать выход.
              +2
              Ничего удивительного нет. N2830 — дохлый процессор 14 года, у многих смартфоны гораздо быстрее.

              Как-то проводил тест на octane benchmark:
              • средний смартфон 2012 года: 2 400
              • cortex a53 (на rasp pi 3b+): 2 500
              • ipad pro 11 2018: 30 000
              • i7-8700 5ггц: 47 000


              Еще пару лет и в многопотоке apple догонит топовые i7.
                0
                У меня телефон s7 делает в многопотоке i5 750.

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

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