24 марта 2012 в 09:59

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

HTML*, CSS*
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 алгоритмы


… а это уже тема следующей статьи если кому-то эта тема интересна.
+61
1094
172
csmile 19,6

Комментарии (60)

–30
p777, #
Я извиняюсь, но что такое O( )?
+7
ishaba, #
Оценка сложности алгоритма ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое
+6
ishaba, #
Простите, вот правильная ссылка «O»_большое_и_«o»_малое
+22
AgentSmith, #
А что здесь делают выпускники Щукинского театрального?
+4
HomoErectus, #
А ведь я повелся, полез смотреть профиль.
0
AgentSmith, #
И что ты там увидел? Правда, интересно.
0
PlanetsDrawing, #
> Увлекаюсь web-безопасностью и андроидами.
дальше читать не смог.
–1
AgentSmith, #
Ну, во-первых, вопрос был не к тебе. А во-вторых, у меня в профиле такой надписи нет.
+1
PlanetsDrawing, #
А кто про твой профиль говорит? Вообще, keep it easy :)
0
Error_403_Forbidden, #
А остальное всё понятно?
+9
AntonShevchuk, #
Стоит слегка прояснить ситуацию для тех кто не в теме:

CSS правила читаются справа налево — и чем меньше элементов попадает под самый правый селектор, тем лучше, плюс еще надо учитывать скорость работы самого селектора, где #id < .class < tag (не берем старый IE в расчет)

Термин «специфичность селектора» вроде как уже закреплен за вычислением приоритета селектора вида (X,Y,Z)
0
csmile, #
Что такое «скорость работы самого селектора» и это вот "#id < .class < tag"?
+1
1099511627776, #
Наверное это скорость нахождения элемента по определенному селекотру а "#id < .class < tag"? наверное значит: что по ИД будет искаться наиболее быстро, потом по классу, а потом по имени тэга
0
csmile, #
td { color:red } и #id { color:red } имеют в принципе одну и ту же сложность. Если представить что DOM элемент внутри выглядит как-то так:
struct  Element {
  symbol_t tag;
  symbol_t id;
  ...
}

(symbol_t это int) то сравнение с id и сравнение с tag идентично.

Честно говоря не знаю откуда эта «мулечка» про "#id < .class < tag" появилась.
0
VolCh, #
То что id нужен один только, а теги все нужно перебирать на скорость разве не влияет?
0
csmile, #
Ну во первых никто не гарантирует что элемент с данным id он один. Уникальность id это рекомендация. Не более.

С точки зрения CSS id это такой же атрибут как и любой другой. Просто #id селектор имеет больший вес. Все CSS имплементации раcсчитанны на «неуникальность» ID.

Про скорость. Представь себе документ в начальном состоянии. Расчет стилей в этом случае это все те же O(N*S*D). id никак не помогают.

+1
salas, #
Не гарантирована уникальность id, да. Но неужели настолько много страниц, где половина элементов с одним id, что никто не делает по нему индекс?
0
TheShock, #
Ну мне кажется, что всё-равно придётся перебирать все элементы
0
csmile, #
Индекс по ID нужен для эффективного исполнения функции getElementByID().

Если же у тебя есть, скажем, такие CSS правила

body.mode1 #one { color:red }
body.mode2 #one { color:green }
body.mode1 a { color:blue }
body.mode2 a { color:orange }


и ты меняешь класс у body c mode1 на mode2 то ты просто обязан пересчитать все стили внутри body. При этом есть у элемента ID или нет — не важно абсолютно.
0
salas, #
Интересный-то случай — это когда там не только #one, но и т.д. до #forty-two, правильно? А составление индекса и S обращений к нему (с перебором предков или без такового) — совсем не то же, что S полных переборов (которые подразумевает Ваша формула для общего случая с N*S).
0
csmile, #
Давай представим такой документ
<div #n0>0</div>
<div #n1>1</div>
<div #n2>2</div>
<div #n3>3</div>
...
<div #n9>9</div>

И набор правил
div { background:gold; }
#n1 { color:red; }

Для определения полной картины нужно пройтись по всем N=10 элементам и последовательно проверить оба селектора  (S=2).
Итого строго по формуле O(N*S*D) -> 10*2*1 = 20 операций проверки селекторов.

Никакие индексы тут не помогут.
0
salas, #
Э… O(2)? Вы серьёзно?
0
csmile, #
Что такое «O(2)»?
+12
grep0, #
Взорвать-то получилось? Покажите пример css с экспоненциальной сложностью
+10
resetnow, #
twitter.com — тормозит даже с выключенным js.
0
Anonym, #
Рекомендации отличные. Google Page Speed говорит то же самое.
+3
8bitjoey, #
Хочу большего раскрытия темы. Не могли бы вы показать, например, алгоритм назначения стилей? В псевдокоде хотя бы. Плюс хочется узнать про другие оптимизации. Сейчас, как я понимаю, для каждого элемента DOM просматривается список стилей. Не думаю, что это делается полным его перебором. В одной из реализаций HTML-движка (Cobra), при парсинге CSS правила сразу разделяются на правила для элемента, для класса и для id (правая часть селектора) и перебор делается уже в одной из этих трех категорий.

Дальше интересует порядок назначения стилей. Что id-стиль имеет больший приоритет, чем class, а псевдокласс — еще больше (?). Напоследок хочу заметить, что по-идее, каждый элемент имеет стили по-умолчанию от браузера (имеющие наименьший приоритет).
+1
ishaba, #
Рекомендую прочитать статью и комментарии к ней web-standards.ru/articles/parent-selector/
0
8bitjoey, #
Статью прочитал, но не увидел ответов на свои вопросы. Заметка интересна, скорее верстальщикам крупных порталов (см. последние два коммента там). Я же интересуюсь общими особенностями работы со стилями.
Конкретно мне надо сделать применение MapCSS. Специфика там другая, но знать как это делается для «обычного» CSS было бы весьма полезно.
0
csmile, #
Алгоритм прост и изложен здесь www.w3.org/TR/CSS2/cascade.html#cascade

Есть набор из S правил (selector/properties). Этот набор сортируется по selector specificity.
И для каждого DOM элемента n просматриваются все S правил в указаном порядке.

Для составных селекторов сначала проверяется самый правый селектор и далее справа налево по цепочке parents.

С точки зрения CPU эти вот два селектора:

td { color:red }
#id { color:red }


имеют одинаковую сложность (у меня это сравнение двух int).

А селектор:
.cls1 { color:red }
несколько более сложен для определения(у меня это — поиск int в массиве int)

0
rmaksim, #
имеют одинаковую сложность (у меня это сравнение двух int).

у вас СВОЙ движок???
0
csmile, #
Ну да. Sciter и HTMLayout используют мой h-smile core.
+4
Serator, #
Ответ на вопрос о приоритетах селекторов: www.w3.org/TR/selectors/#specificity
+ картинка в тему: image (частично отвечает на вопрос).
+4
DmitryKoterov, #
Точно ли производится сравнение каждого dom-элемента с каждым селектором? Может быть, в каких-то случаях наоборот все же?

Просто логика подсказывает, что процентное соотношение элементов, совпавших хоть с каким-то селектором, длвольно мало. Соответственно, может иметь смысл отталкиваться именно от селектора, а не от dom. И кажется, что задача найти все подходящие селектору элементы в большинстве случаев хорошо укладывается в индексы.
+1
yurtaev, #
а как на счет дефолтных значений для всех элементов? которые не во всех браузерах одинаковы
0
csmile, #
«Может быть, в каких-то случаях наоборот все же?»

А наоборот это как? Что имеется ввиду?
0
Operatino, #
А разве в статье сказанно что декорирование ДОМ элемента идёт от самого дом элемента а не от css?
+2
iStyx, #
WebKit например вообще не поддерживает динамические атрибут-селекторы.

А вы ничего не путаете? Я этим успешно пользуюсь в OS X приложении с встроенным WebView, все работает.
0
csmile, #
Вот баг про это: bugs.webkit.org/show_bug.cgi?id=60752
Хотя он и закрыт прошлым годом но до Андроидов и iOS эти изменения не дошли и по всйе видимости не дойдут.

Вот можно проверить: terrainformatica.com/w3/webkit-attr-sel.htm
0
iStyx, #
При первом заходе — PASSED, при обновлениях страницы — FAILED. Safari 5.1.4
Что-то тут не то.
0
csmile, #
Ну тест там простой и безхитростный.
Если FAILED то это значит что Safari пытается использовать некую оптимизацию которая ломает селекторы.
+1
Dmitry_f, #
Большое спасибо за разъяснения. Недавно столкнулся с этим наглядно. В последнем проекте на перетаскивании шла проверка пересечений. Элементу, если он доступен для drop, присваивался класс highlighted. Body также был доступен для drop, и ему периодически присваивался/отнимался класс highlighted, что вызывало заметный лаг. Когда body перестали присваивать класс, все пошло заметно шустрее, но главное не была понятна причина — казалось бы, лишь класс. Теперь все ясно.
0
kashey, #
Вот примерно это и лечит БЭМ
0
Dmitry_f, #
БЭМ лечит только неконкретность, сводя глубину к единице. Число селекторов, однако, разрастается до числа элементов (не из БЭМ, а N из статьи). Это действительно может до нескольких раз облегчить выборку по селектору. Но в динамике, как и замечено в статье, ситуация не поменяется, а именно она часто наиболее наглядна.
Плюс некоторые классы все равно хочется сделать общими.
+1
Operatino, #
В БЭМ так же придусматривается присоединение к страннице только нужных стилей, что намного ускоряет CSS парсинг.

Помимо БЭМ еще есть другие подход — OOCSS и SMACSS, смысл у них примерно одинаковый и решают те же проблемы, включая проблемы производительности.
0
Dmitry_f, #
Спасибо. Довольно занятно, хотя и ничего нового.
+1
CKOPOBAPKuH, #
Представим себе HTML документ который после парсера превратился в DOM дерево состоящее из N элементов. Система стилей данного документя состоит из S CSS правил. Тогда вычислительная сложность процедуры назначения стилей всем элементам DOM выражается так:

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


Нет, она не обязательно выражается именно так. Вы привели оценку сверху, она оценивает производительность тупого лобового решения полным перебором без каких-либо индексов и оптимизаций. Однако можно придумать и реализовать много разных эвристик, ну и естественно могут быть более эффективные алгоритмы.

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

Посмотрите, например:
webo.in/articles/habrahabr/38-css-efficiency-tests-3/
www.stevesouders.com/blog/2009/03/10/performance-impact-of-css-selectors/
developer.mozilla.org/en/Writing_Efficient_CSS
www.shauninman.com/archive/2008/05/05/css_qualified_selectors — комментарии dave hyatt

0
csmile, #
Нет, она не обязательно выражается именно так.

Именно так selector complexity и выражается если следовать спецификации.

По поводу оптимизаций… да они могут уменьшить нагрузку в некоторых случаях.
Скажем есть эвристика которая неким магическим образом исключает из просмотра половину style rules т.е.
можно записать O( N * (S*0.5) * D ) что c точки зрения теории равно всё тем же
O( N * S * D ). Если есть сомнения то вот en.wikipedia.org/wiki/Big_O_notation

Собственно это проблема и есть основная причина по которой в CSS никогда не будет селекторов типа:

body:has(a.cool) { color:red }

Ибо в таком случае (has-something-inside selectors) сложность скачком возрастает до квадратичной — O(N2). Это вообще убьет Web.
0
salas, #
Чем в смысле сложности body:has(a.cool) отличается от body a.cool?
0
csmile, #
Для того чтобы проверить элемент body на предмет соответствия body:has(a.cool) селектору нужно просмотреть все N-1 его детей. Т.е. не просто сам элемент и его D parents, а еще и детей.
Т.е. в общем случае сложность выражается как O(N*S*D*N) -> O(N2).
0
salas, #
N² — очень грубая оценка на суммарное количество детей всех элементов. Тут, по сути, тот же самый перебор пар элементов, являющихся потомками друг друга, только стиль устанавливается не внутреннему элементу пары, а внешнему. Количество таких пар вы в другом случае почему-то оцениваете менее грубо — N*D.
0
csmile, #
N2 с точки зрения computational complexity theory есть точная оценка сложности :has(...) селектора.

Представим себе такой документ:

<div>
  <div>
    <div>
      <a>...</a>
    </div> 
  </div> 
</div>

и правило  
div:has(a) { color:red }

Количество элементов внутри root элемента здесь N=3
Назначаем стили:
Для первого DIV (root) элемента требуется просмотр n=3 детей (пока найдем <a>).
Для второго DIV элемента  n=2
Для третьего n=1
Итого 6 просмотров, что для данного случая  N * (N + 1) / 2  
Что и есть O(N2) сложность с точки зрения теории.

0
salas, #
Теоретически — да, может быть D=N. Но для чего в таком случае у Вас вообще обозначение D?
0
csmile, #
D есть метрика глубины самого DOM и используемых descendant selectors.
Если система стилей не использует descendant selectors, а имеет только два правила (S=2):
#id {color:red}
.cls {color:blue}

то D в этом случае равно 1. Системе не требутеся просматривать parent chain на предмет ответа уволетворяет ли селектор или нет.

Если же мы имеем набор правил вида
.super #id {color:red}
.super .cls {color:blue}

то для проверки таких селекторов нам нужно просмотреть весь parent chain каждого элемента. В худшем случае на полную глубину вплоть до root (html) элемента включительно. В этом случае метрика D есть средняя глубина элементов в DOM.
Т.е. метрика D не точная — зависит от конфигурации дерева.

0
CKOPOBAPKuH, #
> Именно так selector complexity и выражается если следовать спецификации.

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

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

body div.x a.y {..}
a.z { ...}
body.p div > a {… }
body.v * {..}

то можно транфсормировать их в:
body{CLASSES} {ELEMENTS} div{CLASSES}.x{CLASSES} {ELEMENTS} a{CLASSES}.y{CLASSES}
a{CLASSES}.z{CLASSES
body{CLASSES}.p{CLASSES} {ELEMENTS} div{CLASSES} a{CLASSES}
body{CLASSES}.v{CLASSES} ([^ ]+)
где
{CLASSES} означает ([^. ]+)*
{ELEMENTS} означает ([^ ]+ )*([^ ]+)

далее склеиваем их в (rule_1 | rule_2… | rule_N)$

итого, мы получаем 1 регулярное выражение (за время, я полагаю, O(S*ln(S)) ?)

теперь при обходе дерева элементов записываем, где мы находимся.
например, html body p div.a.x b (не найдено)
html body a.z.x (найдено)
html body p div.x a.y (найдено)
на поиск по регекспу тратится O(длина строки) = O(D), верно?
итого O(S*ln(S) + D*N)

естественно, это сложность только поиска (плюс я упускаю пока момент с определением, какие именно правила подошли. но он тоже решается, навскидку будет +D*N*ln(S)).
но ещё эти правила нужно применять, и тут ваша оценка скорее всего верна.
+2
getElementById, #
В этом тексте четыре запятые
0
csmile, #
Извиняюсь. Отвык от писания по русски.
0
kuchumovn, #
Например если вы захотите преключать режим отображения документа c помощью изменения значения некоего DOM атрибута «mode» и пары правил вида body[mode=first] .widget {color:red} и body[mode=second] .widget {color:green} то у вас ничего не получится (в WebKit).

Неправда.
У меня в хроме работает.
(Пишу сайт с режимами)
0
kuchumovn, #
Правда у меня не пара, а просто обычный режим и режим правки типа body[mode=«правка»] a { cursor: default }, и всё работает при переключениях туда-обратно.
0
csmile, #
См. сообщение выше «Вот баг про это: bugs.webkit.org/show_bug.cgi?id=60752 ....»

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