A Shocking Truth About CSS
blog.twoalex.com
blog.twoalex.com
Billions, not millions.
What you want is a CPU with a short pipeline, a fast clock rate and if possible instruction reordering and multiple dispatch.
Large caches and good branch prediction help a lot too.
Most instructions have not taken over 2 cycles on x86 since P4. This is a mesofact, update your worldview. :)
11:44:33 AM Alex K: that makes it sound like it may not be worth huge optimization?
11:44:46 AM Alex M: no, not really
“For most web sites, the possible performance gains from optimizing CSS selectors will be small, and are not worth the costs. ”
http://www.stevesouders.com/blog/2009/03/10/performance-impa...
Thanks for all the comments, everyone! Very cool to have that post picked up by Hacker News.
#alert > p { background: yellow }
Suppose you have a DOM tree like this:
div #alert - p, p, p
- div #alert - p [lots of children]
- p - div #alert [lots of children]
In order to find all Ps with an #alert parent, you first get a set of all paragraph elements. Most likely a list of all paragraphs is kept in memory, so it can be enumerated quickly. Since DOM trees are generally well balanced the number of parents of any one paragraph is going to be roughly O( 2log(|DOMSIZE|) ) and it can be enumerated in C, so this is basically nothing (compared to how grossly inefficient javascript is). Total complexity: O( |P NODES| * 2log( |DOMSIZE| ) ). Memory complexity: 1 linked list of size of result set.
[left to right]
If we were to look at it from left to right, it gets trickier. You have to find all #alert nodes (easy & fast), but then you have to take all children of all #alert nodes. Every sub-tree of the DOM can be a significant fraction of the entire DOM tree, or perhaps the _entire_ dom tree. Not only that, but you CANNOT filter for all "p" children, because then you'd need to have lookup tables for every level in the tree (hugely inefficient). So you're left with one solution, that is to enumerate all children (and a DOM node can have a few thousand child nodes easily). But, wait, one #alert contains another #alert. We're already looking at O( |DOMSIZE| * |DOMSIZE| ), and now we have to consider uniqueness as well. We cannot alloc a hash map to keep track of uniqueness, because that would completely fragement your memory space; you'd end up allocating&deallocating hashmaps for every selector call. So you end up having to traverse the result set linked list for every node you add, to see if it isn't already in there. This, needless to say, is another O(N^2) detour. Total worst case complexity for M selectors:
O( M * |DOMSIZE|^2 + M * |RESULTSET|^2 ).
Difference becomes more profound as complexity increases:
#uniq p p span b
(L2R) find all #uniq nodes, enumerate all "p" children. Make sure all "p" children are unique. Take all children of these "p" nodes, filter for "p" children, make sure result set is unique. Take all children of these "p" nodes, filter for "span", make sure.... and so it goes.
So that's why.
OT, this was one of the problems XHTML was supposed to solve, since it was originally assumed by many that pages that weren't well-formed XML would not be rendered at all, forcing the developers to fix the code. This didn't happen, and developers are still at the mercy of how individual browsers implementat quirks mode.
Isn't it just easier to teach web developers to write their DOM selectors in a specific way? The R2L approach is (a) easy to understand (b) has predictable (and stable) performance (c) doesn't malloc (d) is easy to implement. I see this as a simple case of "good enough".
And it is also fine in standards mode - double win.
The Two Alexs
Alexes? Alex's? Alexi? Alexim?
In hackanonical form, Alexen. As in oxen, vaxen, boxen.
From what I can tell, it looks like OE nouns could have either "strong" or "weak" declensions, and this is different from the dual form. Someone on another forum claims that "brethren" is another example.
Thanks for the words!
Alex K
PS I appreciate how strong codex/codices example is, but, well, Alices, not so much.
Hackanonical, however, is without flaw. It should be in the name of this site!
Why do I really doubt Alex's yoga site needs to worry about this.
This is where Speed Tracer comes in handy ( http://code.google.com/webtoolkit/speedtracer/ )
https://chrome.google.com/extensions/detail/ognampngfcbddbfe...
It's Chrome-only but you can sometimes get cross-browser insights. It's also a lot easier to conduct a cursory investigation using this tool than it is to start changing your selectors.
Plus, it's always fun to try out new formats, even -- or maybe especially -- if they don't stick.
https://developer.mozilla.org/en/Writing_Efficient_CSS
That's from April 21st, 2000 - almost a decade ago.
Last two lines scares the hell out of me.
It's new to me, and I bet it's new to most news.yc-ers.
your premise is rediculous.
(And I have proof that I do actually do this; I had a misbehaving joystick, and the linux fork in my github contains the fix.)
Anyway, in conclusion, if you want to know what algorithm Firefox uses to process CSS selectors, just read the Firefox source code. If you don't give a damn, then don't do that instead. But if you care and you do nothing, that's just silly.
yummy trollspam.