Главная

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

2012-03-24 в 5:59, admin, рубрики: css, html, веб дизайн и сайтостроение, метки: веб дизайн и сайтостроение

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). Такая вот оптимизация в этом движке.

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

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