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

    Привет Хабр!

    Продолжаем битву за производительность 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 вполне могут захватить мир. Если захотят.

    PS
    Продолжение: Ускорились за счет многопоточный вычислений.
    Поделиться публикацией

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

      0
      .fill({});
      если бы посмотрели спеку то стало бы понятно что fill заполняет массив одним экземпляром, т.е. каждый элемент массива — это ссылка на один и тот же объект
        0
        Я это понял уже потом :)
          +2
          Вот так сработает, если вам это еще интересно:

          let a = Array.from({length: 10}, () => ({}));
          a[1].prop = 1;
          a[2].prop = 2;
          console.log(a[1].prop);   // выводит 1
          
            0
            Спасибо!
        0
        pocketolap.com/2 — че-то все повисло на 'joining dirs...' при 1 000 000 тестовых данных
          0
          Что за браузер и платформа?
          Там в единственном месте используется await (все остальное на рекурсиях), посмотрю, отпишу…
            0
            macos sierra, последний firefox
              0
              Починил опечатку, вот что значит на автотестах экономить…
              +1
              macos mohave, chrome 71
              Uncaught (in promise) TypeError: Cannot read property 'product' of undefined
              at fact (po-common.js:70)
              at eval (eval at selectlast (po-common.js:120), :1:1)
              at selectlast (po-common.js:120)
              at eval (eval at jsontojs (po-common.js:323), :3:8)
              at row (po-common.js:99)
              at calcfinal (po-calcworker.js:130)
                0
                Спасибо, завтра починю!
                  0
                  Починил опечатку, вот что значит на автотестах экономить
              0
              WASM. Конечно, заманчиво переписать алгоритм расчета на wasm

              А как в WASM с JS объектами? Пару дней назад хотел переписать небольшую часть вычислений с обычного JS на ASM.js и наткнулся на то, что он оказывается пока для чисел. А у меня там плотная работа со вложенными объектами.

                0
                А не знаю, по идее если писать на том же Rust, который компилится в wasm — там есть все эти объекты-коллекции. Для меня даже Javascript новый язык, вот в промисах ошибку нашли уже, буду разбираться как в Rust передать Javascript Map.
                  0

                  На самом деле интересует именно поддержка родных JS-объектов. Иначе на сериализацию и десериализацию в ряде задач уйдёт шибко много времени.

                    0
                    У меня получается, что затраты на JSON.stringify() / JSON.parse() занимают не более 10% всего времени, то есть не так страшна сериализация, она в JS хорошо проработана, и смысл попробовать видимо есть.
                  +2
                  Так asm.js это же фактически тот же js только работа с числами там по возомжности приводится к целочисленным и виртуальная память/файловая система в array buffer. Если транспайлить из других языков и писать абстракции отличные от JS объектов, то можно получить некоторый профит. В Rust знаю точно есть web-sys и js-sys которые соотвественно позволяют прямо из ржавого кода работать с api браузера и js соотвестенно. Если это все не слишком интерактивно и нет необходиомости постоянно преобразовывать js в чанки памяти для wasm и наоборот, то вероятно оно может вам помочь.
                  0
                  А для интереса вы не сверяли производительность с Google Sheets и MS Office Online?
                    +1

                    Я не очень понял, чем вас не устроил виртуальный скроллинг. Он вполне себе летает. Ещё пример с электронной таблицей.

                      0
                      Хотелось иметь поиск стандартно по Ctrl-F, ну и вообще понять пределы HTML. Понял что не тянет, и надо использовать динамический, как у Вас в примере.
                      PS
                      Я другим был поражен — на мобильнике те же 100 тыс строк выводятся в расшифровку, и с ними можно работать. Да и вообще производительность почти не отличается от десктопа. PWA на мобильнике всегда критиковали за тормоза, но я их не обнаружил.
                        0

                        Может у вас просто мобильник из high-end сегмента? ) Для excell-е подобных UI виртуальный-скроллинг это даже не то, что доктор прописал, это must have.

                      +1

                      Возможно будет интересно: https://github.com/tonsky/datascript
                      Там есть js api.

                        0

                        У меня в екселе файл весит около 800 килобайт. Сводные таблицы летают на windows на версиях ms office 2013 и младше и на os x 2011 и младше. Эксперементальным путем выяснил, виновник тормозов-power query. Штука хорошая. Но дико тормозная. Приходится паралельно использовать старую и новую версию офиса без этой функции. С ней даже простой ввод данных в ячейку занимает полторы-две секунды

                          +2
                          К сожалению, высокая производительнось несовместима с некоторыми паттернами программирования, разделяющими уровень данных, бизнес-логики и представления. Если нужна настоящая скорость — функциии нужно не разделять, а объединять, особенно при отсутствии нормального языка запросов, когда все расчеты осуществляются в циклах и рекурсиях.


                          Золотые слова! К сожалению часто встречаю обратное утверждение, о том, что только следование паттернам может обеспечить наилучшее быстродействие и использование памяти.
                            0
                            Здравстуйте,
                            Я вот сам пробовал сделать типа RowBuffer, чтоб подчищал хвосты. И в какой-то момент подумал, что эта же фича может затормозить скроллинг, ведь ему, как вы и сказали — «необходимо пересчитать ширину, то есть, по сути, отрисовать всю таблицу заново» и это затратно.
                            Заметили вы прирост в скорости за счет этой фичи с тегом PRE?
                            Спасибо
                              +1
                              PRE дал офигенный прирост, в 10 раз где-то, хотя полностью проблема подвисания не решена — хром (и только хром) с его пере-оптимизацией слегка подтормаживает при подгрузке данных. Но с таблицами и дивами даже и сравнивать нечего.
                              0
                              А планируется выложить в свободный доступ исходники? Или это коммерческий проект?
                                0
                                Это экспериментальный проект, исходники можно брать и пользовать. В каталогах /1 /2 /3 соответственно — все .js лежат в исходном виде (каталог /3 — многопоточность, после НГ будет статья). Чтобы выложить их на гитхаб, мне нужно потратить время на минимальное комментирование и документирование кода, а это во-первых, еще рано, т.к. алгоритм еще плавает, во-вторых непонятно, нужно ли. Если Вам это нужно — могу напрячься и выложить, или с Вашей помощью довести до товарного вида.
                                PS
                                Коммерческим этот проект может стать позже, как часть более крупной задумки, о которой напишу в свое время, но данный маленький кусочек точно продаваться не будет :)

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

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