Виртуализация для ускорения отображения UI

Формулировка проблемы: все жутко тупит. У нас есть необходимость показать список/таблицу с большим количеством элементов. Но увы, при попытке это сделать наивным путем все тормозит. Пагинация по ряду причин невозможна.

Если начнем детально исследовать то увидим, что происходит примерно следующее:

1. UI-поток пытается отрисовать кучу элементов, чем остается занят на пару секунд. В это время UI-поток не может реагировать на пользовательские события совсем.
2. При попытке скроллинга или изменения UI-поток пытается пересчитать все что видит и поэтому притормаживает.
3. Если у вас рендеринг происходит через какую-нибудь прослойку (вроде React, ng2 или еще какой-то ерунды), то во время рендеринга вы не можете выполнять никаких действих параллельно в этом же потоке. Прим.: насколько я знаю, в браузере UI-поток и основной Javascript-поток — это один и тот же поток.
4. Вам или фреймворку приходится отслеживать изменения для всех элементов. Хотя гораздо проще отслеживать изменения только для видимых элементов.

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

Вы наверняка натыкались: на больших дисскусиях на хабре (или другом подобном сайте) браузер адски тормозит. Это все по причине отсутствия виртуализации.

Сама техника состоит в том, что мы перестаем доверять браузеру/фреймворку и начинаем делать работу за него. Поэтому было бы неплохо понять, что браузер делает и почему у него это получается плохо.

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

Типичный scroll в вакууме головы разработчика

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

А на практике браузер должен вести себя корректо по отношению к:

1. элементам с любым позиционированием;
2. элементам с любым размером;
3. элементам, которые вызовут каскадный пересчет всех узлов дальше;

В общем, для браузера задача отсечения невидимых элементов нетривиальна. Поэтому полноценное отсечение происходит гораздо ближе к отрисовке, чем хотелось бы.

А уж не тупить при попытке всунуть пару тысяч элементов в DOM через кривой фреймворк — это задача, решение которой находится в стране единорогов и фей.

В принципе понятно, почему браузер не справляется с задачей. Задача слишком сложна, но мы её можем упростить. Ведь нам действительно не понадобятся в большинстве случаев никакие упоротые элементы. Большинство случаев покрывается элементами фиксированных (а возможно даже и одинаковых) размеров! Без всяких выебонов с кастомным позиционированием.

Прим.: фиксированный размер значит, что размер элемента не зависит от его DOM внутренностей. Если контент будет больше элемента, то контент урежется. Суть в том, что мы должны знать размер элемента до его отрисовки.

В итоге, конечное решение выглядит примерно так:

1. Описываем контейнер элементов. Контейнер внешне должен быть ограниченной высоты и ширины.
2. Подписываемся на события скроллинга внутри контейнера и пересчитываем видимые элементы.
3. Вместо невидимых элементов мы можем отрисовать пустое пространство. К примеру, через свойства margin/padding. Ни в коем случае не делайте через создание блока и изменение его размеров, иначе косяков не оберетесь. См. мою же статью “Scroll Anchoring”.
4. Отрисовываем видимые элементы.

Если у вас элементы одинаковых размеров, то рассчет видимых элементов прост и примитивен. А вот для гридов с элементами разных размеров вам понадобится что-то именуемое Spatial Index.

Если у вас не двумерный грид, а одномерный список, то можно в принципе написать решение на коленке. Суть:

1. Сконвертируем массив элементов в массив размеров (высота/ширина).
2. Превратим массив размеров в массив offsetов. Теперь проведем операцию суммирования на массиве. Последовательно к каждому элементу с самого начала будет прибавлять число от предыдущего элемента. После в начала массива докинем ноль, раз первый элемент находится в нулевой позиции. Ну и выкинем последний результат, потому что он для несуществующего элемента. Из массива размеров [10,20,10,10] должен получиться массив offsetов [0,10,30,40] .
3. Для вычисления индекса первого видимого элемента пройдемся бинарным поиском по массиву.

Но в большинстве случаев такие приколы не нужны. Гораздо проще убедить тестера, что элемент должен обрезаться, нежели реализовать это корректно.

Все бы хорошо, но в лоб написанный виртуализированный контейнер тормозит и не успевает отрисовывать новые элементы.

Для этих целей делаются следующие вещи:

1. Мы обязываемся отрисовывать не N видимых элементов, а как минимум N + lowBuffer видимых элементов. Это дает нам время отрисовать контент до того, как его увидит пользователь;
2. Мы не перерисовываем видимые элементы на каждом событие скролла. Вместо этого мы изначально отрисовываем N + highBuffer видимых элементов.

Чисто теоретически можно сделать так, чтобы отрисованные, но уже бесполезные элементы удалялись в фоне. Т.е. размазывать нагрузку по работе с DOMом на несколько тиков. Но я не уверен, что это вообще имеет какой-то смысл.

Есть один тонкий момент, который нужно учитывать при реализации. Приостановитесь на секунду и подумайте: сколько видимых элементов будет в контейнере (без учета буфферов)?

Во-первых, у вас нет гарантий, что высота контейнера обязана быть кратной высоте элементов.

Во-вторых, может случиться такая ситуация, что верхний и/или нижний элементы будут отрисованы наполовину.

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

Это накладывает забавный отпечаток на реализацию. Индекс верхнего видимого элемента нужно считать так:floor(scrollTop / itemHeight) . А индекс нижнего видимого элемента нужно считать так: ceil((scrollTop + containerHeight) / itemHeight) . Где floor — операция округления до ближайшего целого вниз, а ceil — операция округления до ближайшего целого вверх.

В итоге: в контейнере количество видимых элементов плавает.

Вас наверняка заинтересовал вопрос, а почему бы не взять уже готовую библиотеку? А потому что эти библиотеки либо под jQuery, либо под React, либо под устаревший вариант ng2. А мне нужна реализация под актуальный ng2. Фронтенд слишком коротко живет, чтобы вам не пришлось имплементить эту ерунду заново :-)

P.S: Термин “виртуализация” пошел из WPF. А вот откуда там появился — уже не знаю.