Как стать автором
Обновить

Про вычислительную сложность алгоритмов HTML и CSS

Время на прочтение3 мин
Количество просмотров5.8K
HTML документ загруженный в browser есть дерево DOM элементов и набор CSS правил. Каждое CSS правило это пара — селектор (selector) и список свойств (list of properties).

Мы мало задумываемся над тем, а собственно чего стоит нарисовать HTML документ c вычислительной точки зрения? Знания про то что думатель — думает, а неонка у нея унутре ярко светит сквозь opacity:0.5 элементы бывает явно не достаточно.

Собственно про это и есть данные статьи — про вычислительную сложность (computational complexity) отображения HTML и CSS. Хочу отметить что я использую свой собственный опыт имплементации HTML/CSS rendering engines (HTMLayout и Sciter), но вычислительные проблемы в данной области универсальны — определяются самой природой HTML и CSS спецификаций.

Слово про CSS селекторы


Представим себе HTML документ который после парсера превратился в DOM дерево состоящее из N элементов. Система стилей данного документя состоит из S CSS правил. Тогда вычислительная сложность процедуры назначения стилей всем элементам DOM выражается так:

O( N * S * D )
Где D это метрика «глубины» (depth) дерева и используемых селекторов.

В качестве примера рассмотрим такое «замечательное» правило:

body * { background:red; }

'*' — каждому элементу внутри <body> присвоить красный цвет подложки. Практической пользы от такого правила конечно чуть но для иллюстрации то что нужно: берем n-ый элемент DOMа и перебираем всех его родителей (в глубину) на предмет body тэга. И так для каждого элемента. Если таких правил всего S то и имеем формулу приведенную выше.

В принципе N*S*D не так уж страшно в статическом случае — вычислили раз и забыли. Но в случае частых динамических измененний возможны проблемы. Скажем если поменять класс элемента-контейнера то для всего его поддерева нужно пересчитывать стили. А это опять в общем случае O( N * S * D ) задача.

Конечно CSS имплементации пытаются оптимизировать процесс перерасчета стилей но это не всегда удается. Основной метод борьбы с O(N...) проблемами это использование кеширования результатов. Скажем при определении стиля элемента можно проверить предыдущий элемент и если он «похож» на искомый то взять его стиль (если он определен). Но этот трюк спотыкается например на правилах типа li:nth-child(even). Причина я думаю очевидна.

WebKit например вообще не поддерживает динамические атрибут-селекторы. Например если вы захотите преключать режим отображения документа c помощью изменения значения некоего DOM атрибута «mode» и пары правил вида body[mode=first] .widget {color:red} и body[mode=second] .widget {color:green} то у вас ничего не получится (в WebKit). Такая вот оптимизация в этом движке.

Рекомендации по оптимальному использованию стилей:

  1. Следим за общим количеством правил. Если какое-то правило и не используется в данном документе (нет элементов удовлетворяющих его selector) оно все равно нагружет CPU. Такие правила нужно убирать.
  2. В составном селекторе самый правый селектор должен быть возможно более опеределен (специфичен?).
    Пример: селектор ul.cls2 li хуже чем селектор ul li.cls1 в том смысле что в первом случае просматриваются все li элементы и их родители на предмет ul.cls2, а во втором набор li для которых выполняется поиск в глубину уже — только для тех li у которых задан class=cls1.
  3. Селектор .cls2 .cls1 «хуже» чем селектор .cls2 > .cls1. Во втором случае проверка на соответствие всегда будет ограничена самим элементом и его родителем. В первом же случае глубина просмотра потенциально до корневого <html> включительно.

Слово про layout алгоритмы


… а это уже тема следующей статьи если кому-то эта тема интересна.
Теги:
Хабы:
Всего голосов 109: ↑85 и ↓24+61
Комментарии60

Публикации

Истории

Ближайшие события

19 августа – 20 октября
RuCode.Финал. Чемпионат по алгоритмическому программированию и ИИ
МоскваНижний НовгородЕкатеринбургСтавропольНовосибрискКалининградПермьВладивостокЧитаКраснорскТомскИжевскПетрозаводскКазаньКурскТюменьВолгоградУфаМурманскБишкекСочиУльяновскСаратовИркутскДолгопрудныйОнлайн
3 – 18 октября
Kokoc Hackathon 2024
Онлайн
24 – 25 октября
One Day Offer для AQA Engineer и Developers
Онлайн
25 октября
Конференция по росту продуктов EGC’24
МоскваОнлайн
7 – 8 ноября
Конференция byteoilgas_conf 2024
МоскваОнлайн
7 – 8 ноября
Конференция «Матемаркетинг»
МоскваОнлайн
15 – 16 ноября
IT-конференция Merge Skolkovo
Москва
25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань