About the computational complexity of HTML and CSS algorithms
The HTML document uploaded to the browser has a DOM tree of elements and a set of CSS rules. Each CSS rule is a pair — a selector and a list of properties.
We do not think much about what, and what is actually worth drawing an HTML document from a computational point of view? Knowledge about the fact that the thinker thinks, and neon shine brightly through opacity: 0.5, the elements are clearly not enough.
Actually about this is the data of the article - about the computational complexity (computational complexity) of displaying HTML and CSS. I want to note that I use my own experience in implementing HTML / CSS rendering engines (HTMLayout and Sciter), but the computational problems in this area are universal - determined by the very nature of HTML and CSS specifications.
Imagine an HTML document that after the parser turned into a DOM tree consisting of N elements. The style system of this document consists of S CSS rules. Then the computational complexity of the procedure for assigning styles to all elements of the DOM is expressed as:
')
Where D is the “depth” metric of the tree and selectors used.
As an example, consider this “remarkable” rule:
'*' - to each element inside the <body> assign the red color of the substrate. Of course, the practical benefits of such a rule are slightly but to illustrate what is needed: take the nth element of the DOM and iterate over all its parents (in depth) on the subject of the body tag. And so for each item. If there are only S of such rules, then we have the formula given above.
In principle, N * S * D is not so terrible in the static case - it was calculated once and forgotten. But in case of frequent dynamic changes problems are possible. Say, if you change the class of a container element, then for its entire subtree, you need to recalculate styles. And this is again the
Of course, CSS implementations try to optimize the style recalculation process, but this is not always possible. The main method of dealing with O (N ...) problems is to use results caching. Say, when defining the style of an element, you can check the previous element and if it is “similar” to the desired one, then take its style (if it is defined). But this trick stumbles, for example, on rules like
WebKit, for example, does not support dynamic attribute selectors at all. For example, if you want to turn on the document display mode by changing the value of a certain DOM attribute “mode” and a pair of rules like
Recommendations for optimal use of styles:
... and this is the topic of the next article if this topic is interesting to someone.
We do not think much about what, and what is actually worth drawing an HTML document from a computational point of view? Knowledge about the fact that the thinker thinks, and neon shine brightly through opacity: 0.5, the elements are clearly not enough.
Actually about this is the data of the article - about the computational complexity (computational complexity) of displaying HTML and CSS. I want to note that I use my own experience in implementing HTML / CSS rendering engines (HTMLayout and Sciter), but the computational problems in this area are universal - determined by the very nature of HTML and CSS specifications.
Word about CSS selectors
Imagine an HTML document that after the parser turned into a DOM tree consisting of N elements. The style system of this document consists of S CSS rules. Then the computational complexity of the procedure for assigning styles to all elements of the DOM is expressed as:
')
O ( N * S * D )Where D is the “depth” metric of the tree and selectors used.
As an example, consider this “remarkable” rule:
body * { background:red; }'*' - to each element inside the <body> assign the red color of the substrate. Of course, the practical benefits of such a rule are slightly but to illustrate what is needed: take the nth element of the DOM and iterate over all its parents (in depth) on the subject of the body tag. And so for each item. If there are only S of such rules, then we have the formula given above.
In principle, N * S * D is not so terrible in the static case - it was calculated once and forgotten. But in case of frequent dynamic changes problems are possible. Say, if you change the class of a container element, then for its entire subtree, you need to recalculate styles. And this is again the
O ( N * S * D ) problem in the general case.Of course, CSS implementations try to optimize the style recalculation process, but this is not always possible. The main method of dealing with O (N ...) problems is to use results caching. Say, when defining the style of an element, you can check the previous element and if it is “similar” to the desired one, then take its style (if it is defined). But this trick stumbles, for example, on rules like
li:nth-child(even) . The reason I think is obvious.WebKit, for example, does not support dynamic attribute selectors at all. For example, if you want to turn on the document display mode by changing the value of a certain DOM attribute “mode” and a pair of rules like
body[mode=first] .widget {color:red} and body[mode=second] .widget {color:green} you will fail (in WebKit). Such is the optimization in this engine.Recommendations for optimal use of styles:
- We follow the total number of rules. If a rule is not used in this document (there are no elements satisfying its selector), it still loads the CPU. Such rules need to be removed.
- In the compound selector, the rightmost selector should be as specific as possible (specific?).
Example: theul.cls2 liselector is worse than theul li.cls1selector in the sense that in the first case, all li elements and their parents are viewed for ul.cls2, and in the second, li set for which depth search is performed - only for those li which have class = cls1. - The selector
.cls2 .cls1“worse” than the selector.cls2 > .cls1. In the second case, the compliance check will always be limited to the element itself and its parent. In the first case, the viewing depth is potentially up to the root <html> inclusive.
Word about layout algorithms
... and this is the topic of the next article if this topic is interesting to someone.
Source: https://habr.com/ru/post/140399/
All Articles