I've just made a fairly significant optimisation to libcss's selection engine performance. It's now using more memory, but hopefully that's worth the extra speed. Please let me know how you get on with it.
In brief, compare: Before: http://www.netsurf-browser.org/temp/sel-opt/before-bloom-main.png After: http://www.netsurf-browser.org/temp/sel-opt/bloom-04-main.png More info below. Skip to the "Selection optimisation" section if you already know why we were so slow before. How selection works ------------------- Take the following CSS rule from NetSurf's own web site: .navigation ul.languages li a:hover, .navigation ul.sitelinks li a:hover { display: block; color: #00f; padding: 0 0 0 0.2em; margin: 0; background: transparent; text-decoration: none; } It's a single rule with two selector chains. To determine whether to apply that rule the element node we're selecting for, at least one of the selector chains must match. Considering only the first selector chain, it's saying, "Match an 'a' element in the hover state who has an ancestor node which is an 'li' element who has an ancestor node which is a 'ul' element with the 'languages' class who has an ancestor node with the 'navigation' class." Libcss is able to ask the client (NetSurf) about element nodes via a series of callbacks. So to match a selector chain, libcss asks if the node being selected is an 'a' element. It then needs to ask wether the element has a ancestor of type 'li'. And so on. On the NetSurf side the callbacks are implemented with a bunch of calls to libdom to walk up the DOM tree to look for whatever libcss is enquiring after. Selection performance problem ----------------------------- CSS selection has been dominating NetSurf profiles for ages. For a site like http://www.bbc.co.uk/news/ at the current time there are 4366 selector chains to match for each of 1156 element nodes. We already had an optimisation whereby selector chains were hashed by the right most selector details. There are four hash tables for element name, class name, id name and finally for selector chains whose right most selector has no element name, class name or id name. However even with that selection is expensive. When launching framebuffer NetSurf with the BBC news homepage, and quitting as soon as the page finishes loading, over 45% of NetSurf's CPU usage is spent in the selection engine: http://www.netsurf-browser.org/temp/sel-opt/before-bloom-main.png Selection optimisation ---------------------- I've made two optimisations. The first is quite minor, though worthwhile. We skip selector chains which don't meet the following criteria: + The rule must have some bytecode, i.e. if the rule matches, there must be some style data to apply. + If the selector chain's right most selector specifies the element name, then the name of the element we're selecting for must be a match. + The rule must be applicable for the media type we're selecting for. I moved the testing for those so they happen a bit earlier. It's now done before we compare the rules that emerge from each of the selector chain hash itterators for specificity and rule index (to ensure they're applied in the correct order). The second optimisation is to generate bloom filters loosely describing node ancestry and selector chain ancestry requirements. In NetSurf, we now store a node bloom filter as user data on the libdom element nodes. This bloom filter is filled with all the node's ancestor element names, class names and id names. In libcss, for each selector chain, we store a bloom filter containing all the element/class/id names that follow an ancestor or parent, combinator (' ' or '+'). So for the first selector chain in the example rule above, we'd add the following strings to the bloom filter. "li" "languages" "ul" "navigation" To determine wether a selector chain can be ruled out without manually matching it, we simply have to see whether the selector chain bloom is a subset of the node bloom. This is a much faster operation. All the strings involved were already interned with libwapcaplet, so string hash values were already calculated and available. The size of the bloom filter can be set (at compile time) to either 4, 8, or 16 * uint32_t. I've commited it with CSS_BLOOM_SIZE of 4. That means 4 * 4 bytes per DOM node, and per selector chain. For the example of http://www.bbc.co.uk/news/ that's: DOM nodes: 16 * 1156 = 18,496 Bytes Selector chains: 16 * 4366 = 69,856 Bytes ------------ 88,352 Bytes The selector chain cost is shared between pages that share the same external stylesheets. However, there are over 20,000 element nodes alone for a page like: http://git.netsurf-browser.org/netsurf.git/tree/render/layout.c I have run tests with the larger bloom filters and it does reduce false positive rates, however I judge the overall improvement/cost ratio to be best with a CSS_BLOOM_SIZE of 4 at the moment. Test | Total Instruction Fetch Cost | In selection --------------+------------------------------+------------- Before bloom | 785,536,304 | 45.30% Bloom size 4 | 500,727,778 | 13.95% Bloom size 8 | 484,935,082 | 11.94% Bloom size 16 | 480,928,151 | 11.06% What's interesting is that from bloom size 4 to 16 there isn't a huge drop in total computation required, but the number of calls to match_details (used in matching selector chains manually) drops sharply: Test | match_details calls --------------+-------------------- Before bloom | 1,428,184 Bloom size 4 | 171,451 Bloom size 8 | 101,397 Bloom size 16 | 54,112 That shows that with a bloom size of 4, there are plenty of false positives, but the cost of testing bloom filters for being a subset is getting quite heavy with the longer filters. See the other profile results using the 8 and 16 settings: http://www.netsurf-browser.org/temp/sel-opt/ What next? ---------- I pushed my changes at this stage since they were showing a decent improvement, but there are some more things I plan to experiment with. I tried generating the selector chain bloom filters on the fly, which was quite costly, so they're currently stored with the selector chains. It may be faster to avoid generating selector chain bloom filters at all and walk the selector chain using css_bloom_has_hash on each relevant string. We could dismiss the selector chain as soon as css_bloom_has_hash returns false. -- Michael Drake (tlsa) http://www.netsurf-browser.org/
