Не так давно я столкнулся с довольно простой и одновременно интересной задачей: реализация read-only терминала в веб приложении. Интереса задаче придавали три важных аспекта:

• поддержка основных ANSI Escape sequences
• поддержка минимум 50 000 строк данных
• отображение данных по мере их поступления.

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

Disclaimer: я не являюсь опытным web разработчиком, поэтому некоторые вещи могут показаться вам очевидными, а выводы или решения ошибочными. За исправления и пояснения я буду благодарен.

Для чего это затевалось

Задача целиком выглядит следующим образом: на сервере работает скрипт (bash, python, и т.п.) и что-то пишет в stdout. И этот вывод нужно отображать на веб странице по мере его поступления. При этом он должен выглядеть как на терминале (с форматированием, переносами курсора и т.п.)
Сам скрипт и его выходные данные я никак не контролирую и отображаю в чистом виде.

Разумеется между веб интерфейсом и скриптом должен быть посредник — веб сервер. И если не лукавить — веб приложение и сервер у меня уже есть и худо-бедно работают. Схема выглядит примерно следующим образом:

Но раньше ответственным за обработку и форматирование был сервер. И хотелось это улучшить по большому ряду причин:

• двойная обработка данных — сперва разбор на сервере, потом трансформация в html компоненты на клиенте
• неоптимальность алгоритма из-за подготовки данных для клиента
• большая нагрузка на сервер — обработка вывода от одного скрипта могла полностью загрузить единственный поток на сервере
• неполная поддержка ANSI Escape sequences
• трудноуловимые баги
• клиент очень плохо справлялся с отображением даже 10к форматированных строк

Поэтому было решено всю логику парсинга перенести в веб приложение, а серверу оставить только потоковую отдачу необработанных данных

Постановка задачи

На клиент приходят части текста. Клиент должен их разобрать на составляющие: обычный текст, перенос строки, возвращение каретки и специальные ANSI команды. Гарантий в целостности частей нет — одна команда или слово может прийти в разных пакетах.

ANSI команды могут влиять на формат текста (цвет, фон, стиль), положение курсора (откуда должен выводиться последующий текст) или делать очистку части экрана.
Пример того, как это выглядит:

Кроме того, среди текста могут быть URL, которые также необходимо распознавать и подсвечивать.

Берём готовую библиотеку и ...

Я понимал, что правильная и быстрая обработка всех команд — это дело непростое. Поэтому решил поискать уже готовую библиотеку. И, о чудо, буквально сразу наткнулся на xterm.js. Готовый компонент терминала, который уже много где используется и, вдобавок, "is really fast, it even includes a GPU-accelerated renderer". Последнее было для меня самым важным, т.к. хотелось наконец получить очень быстрый клиент.

Несмотря на то, что я люблю писать собственные велосипеды, я был крайне рад, что могу не только сэкономить время, но и бесплатно получить кучу полезного функционала.

На попытки подключить терминал у меня ушло 2 вечера и я с этим не справился. Совсем.
Разная высота строк, кривое выделение, адаптивный размер терминала, очень странное API, отстутсвие вменяемой документации…

Но у меня ещё оставалось немного воодушевления и я верил, что смогу разобраться с этими проблемами.
Пока я не скормил в терминал свои тестовые 10к строк… Он умер. И похоронил с собой остатки моих надежд.

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

Первым делом, я скопипастил текущий алгоритм, реализованный на python, и адаптировал его под javascript (всего-то удаление фигурных скобок и другой синтакс у for).

Я знал все основные плюсы и минусы старого алгоритма, поэтому мне требовалось только улучшить неэффектиные места в нём.

После обдумывания, проб и ошибок, я остановился на следующем варианте: делим алгоритм на 2 составляющие:

• модель, для разбора текста и хранения текущего состояния "терминала"
• отображение, которое переводит модель в HTML

Модель (структура и алгоритм)

• Все строки хранятся в массиве (номер строки = индекс в массиве)
• Стили текста хранятся в отдельном массиве
• Текущее положение курсора хранится и может изменяться командами
• Сам алгоритм посимвольно проверяет входящие данные:
  
  • Если это просто текст, добавляем в текущую строку
  • Если перенос строки, то увеличиваем текущий индекс строки
  • Если этот один из символов команды, то кладём его в буфер команды и ждём следующий символ
  • Если буфер команды правильный, то запускаем эту команду, иначе пишем этот буфер как текст
• Модель оповещает слушателей о том, какие строки изменились после обработки входящего текста

В моей реализации сложность алгоритма получается O(n log n), где log n это подготовка измененных строк для оповещения (уникальность и сортировка). Во время написания этой статьи, я понял, что для частного случая можно избавиться от log n, поскольку строки чаще всего добавляются в конец.

Отображение

• Отображает текст в виде HTML элементов
• Если строка изменилась, полностью заменяет все элементы строки
• Разбивает каждую строку исходя из стилей: каждый стилизованный отрезок имеет свой элемент

При такой структуре тестирование это довольно простая задача — передаём текст в модель (единым пакетом или по частям) и просто проверяем текущее состояние всех строк и стилей в ней. А для отображения достаточно всего нескольких тестов, т.к. оно всегда перерисовывает изменившиеся строки.

Важным преимуществом также является некая ленивость отображения. Если в одном куске текста мы перезаписываем одну и ту же строку (например, прогресс бар), то после работы модели, для отображения это будет выглядеть как одна изменившаяся строка.

DOM vs Canvas

Хотелось бы немного остановиться на том, почему я выбрал DOM, хотя целью была производительность. Ответ прост — лень. Для меня отрисовка всего в Canvas самостоятельно выглядит довольно сложной задачей. При сохранении usability: выделение, копирование, изменение размера экрана, опрятного вида и т.п. Пример xterm.js мне наглядно показал, что это совсем непросто. Их отрисовка в canvas'е была далеко не идеальной.

Кроме того, отлаживаение DOM дерева в браузере и возможность покрытия юнит тестами — это немаловажное преимущество.

В конце концов, моей целью было 50к строк, и я знал, что DOM с этим должен был справиться, на основании работы старого алгоритма.

Оптимизации

Алгоритм был готов, отлажен и медленно, но верно работал. Пора было открывать профилировщик и оптимизировать. Забегая вперёд, скажу что большая часть оптимизаций была для меня сюрпризом (как это обычно и бывает).

Профилирование проводилось на 10к строк, каждая из которых содержала стилизованные элементы. Общее число DOM элементов около 100к.

Никаких специальных подходов и инструментов не использовалось. Только Chrome Dev Tools и пара запусков на каждый замер. На практике, в запусках отличались только абсолютные значения замеров (сколько секунд на выполнение), но не процентное соотношение между методами. Поэтому, считаю такую методику условно-достаточной.

Ниже хотелось бы подробнее остановиться на самых интересных улучшениях. И для начала график того, что было:

Все графики профилирования были построены уже после реализации, путём деоптимизации кода по-памяти.

string.trim

Первым делом я наткнулся на непонятный string.trim, который съедал очень заметное количество CPU (мне кажется это было в районе 10-20%)

trim() — это базовая функция языка. Почему для неё используется какая-то библиотека? И даже если это какой-то polyfill, то почему он включился на последней версии хрома?

Немного гугления и ответ найден: https://babeljs.io/docs/en/babel-preset-env. По-умолчанию он включает polyfill для довольно большого количества браузеров, и делает это на этапе компиляции. Решением для меня было указать 'targets': '> 0.25%, not dead'
Но в конечном этоге я удалил вызов trim совсем, за ненадобностью.

Vue.js

В прошлом году я перевел компонент терминала на Vue.js. Теперь пришлось перевести его обратно на ваниллу, причина на скриншоте ниже (смотреть количество строк с участием Vue.js):

Я оставил во Vue компоненте только обертку, стили и обработку мыши. Всё что относится к созданию DOM элементов ушло в чистый JS, который подключается во Vue компонент как обычное поле (которое не отслеживается фреймворком).

created() {
    this.terminalModel = new TerminalModel();
    this.terminal = new Terminal(this.terminalModel);
},

Я не считаю это минусом или недоработкой Vue.js. Просто фреймворки и перфоманс сами по себе плохо сочетаются. Ну а когда вы в реактивный фреймворк закидываете десятки и сотни тысяч объектов, очень трудно от него ожидать обработки в течении пары миллисекунд. И, честно говоря, я даже удивлен, что Vue.js довольно хорошо справился.

Добавление новых элементов

Тут всё просто — если у вас несколько тысяч новых элементов и вы хотите их добавить в родительский компонент, делать appendChild не самая удачная идея. Браузеру приходится чуть чаще делать обработку и больше времени тратить на отрисовку. Одним из побочных эффектов в моём случае было замедление автоскролла, т.к. он принудительно вызывает пересчет всех добавленных компонентов.

Чтобы решить проблему, существует DocumentFragment. Сперва добавляем все элементы в него, а потом его самого в родительский компонент. Браузер позаботится об инлайне входящих компонентов.

Данный подход снижает количество времени, которое браузер тратит на отрисовку и расположение элементов.
Я также пробовал и другие способы ускорения добавления элементов. Ни один из них не мог ничего добавить поверх DocumentFragment.

span vs div

На самом деле это можно было назвать display:inline (span) vs display:block (div).

Изначально у меня каждая строка была в span и оканчивалась символом переноса строки. Однако с точки зрения производительности это не очень эффективно: браузеру приходится рассчитывать где элемент начинается и заканчивается. С display:block такие подсчёты гораздо проще.

Замена на div ускорила отрисовку почти в 2 раза.

К сожалению, в случае display:block выделение нескольких строк текста выглядит хуже:

Я долго не мог решить, что лучше — лишние 2 секунды отрисовки или человеческое выделение. В итоге практичность победила красоту.

Мастер CSS 10-го уровня

Ещё ~10% времени отрисовки удалось срезать "оптимизацией" CSS, который у меня используется для форматирования текста.

Против меня сыграла неопытность в веб разработке и понимания основ. Я думал, что чем точнее селекторы, тем лучше, однако конкретно в моем случае это было не так.

Для форматирования текста в терминале я использовал такие селекторы:

#script-panel-container .log-content > div > span.text_color_green,

Но (в хроме), следующий вариант немного шустрее:

span.text_color_green

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

string.split

Если у вас возникло дежавю из-за одного из предыдущих пунктов, то оно ложное. На этот раз речь не о polyfill, а о стандартной реализации в хроме:

(я обернул string.split в defSplit, чтобы функция показывалась в профилировщике)

1% это мелочи. Но велосипедист-идеалист во мне не давал покоя. В моём случае split всегда делается по одному символу и без каких-либо регулярок. Поэтому я реализовал простой вариант. Вот результат:

function fastSplit(str, separatorChar) {
    if (str === '') {
        return [''];
    }

    let result = [];

    let lastIndex = 0;
    for (let i = 0; i < str.length; i++) {
        const char = str[i];
        if (char === separatorChar) {
            const chunk = str.substr(lastIndex, i - lastIndex);
            lastIndex = i + 1;
            result.push(chunk);
        }
    }

    if (lastIndex < str.length) {
        const lastChunk = str.substr(lastIndex, str.length - lastIndex);
        result.push(lastChunk);
    }

    return result;
}

Я считаю, что после такого, меня обязаны брать в команду Google Chrome без собеседования.

Оптимизация, послесловие

Оптимизация это процесс без конца и можно что-то улучшать до бесконечности. Особенно учитывая, что разные use case требуют различных (и противоречивых) оптимизаций.

Для моего случая, я выбрал основной use case и оптимизировал его время работы с 15 сек до 5 сек. На этом я решил остановиться.

Осталась ещё пара мест, которые я планирую улучшить, но это уже благодаря полученному опыту.

Бонус. Мутационное тестирование.

Так получилось, что за последние несколько месяцев я часто сталкивался с термином "мутационное тестирование". И решил, что данная задача это отличный способ попробовать этого зверя. Особенно после того, как у меня не завелся code coverage в Webstorm, для тестов на карме.

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

Но как ни крути, пришлось немало повозиться, чтобы добиться интеграции с кармой и вебпаком.

В конце концов всё завелось и спустя полчаса я увидел печальные результаты: около половины мутантов выжило. Часть я убил сразу, часть оставил на будущее (когда реализовывал недостающие ANSI команды).

После этого лень победила, и на текущий момент результаты выглядят следующим образом (для 128 тестов):

Ran 79.04 tests per mutant on average.
------------------|---------|----------|-----------|------------|---------|
File              | % score | # killed | # timeout | # survived | # error |
------------------|---------|----------|-----------|------------|---------|
terminal_model.js |   73.10 |      312 |        25 |        124 |       1 |
------------------|---------|----------|-----------|------------|---------|
23:01:08 (18212) INFO Stryker Done in 26 minutes 32 seconds.

В целом данный подход мне показался очень полезным (явно лучше, чем code coverage) и забавным. Единственный минус это жутко долгое время работы — 30 минут на один класс это перебор.

И самое главное — этот подход заставил меня ещё раз задуматься о 100% покрытии и стоит ли абсолютно всё покрывать тестами: теперь моё мнение ещё ближе к "да", при ответе на этот вопрос.

Заключение

Оптимизация производительности, на мой взгляд, это хороший способ узнать что-то глубже. А также это неплохая разминка для мозга. И очень жаль, что это редко когда действительно нужно (по крайней мере в моих проектах).

И как всегда подход "сперва профилирование, потом оптимизация" работает гораздо лучше, чем интуиция.

Ссылки

Старая реализация:

• terminal_formatter.py
• log_panel.vue

Новая реализация:

• terminal_model.js
• terminal_view.js

К сожалению демо веб-компонента нет, поэтому просто так его потыкать у вас не получится. Так что заранее извиняюсь

Спасибо за уделённое время, буду рад замечаниям, предложениям и разумной критике!