Re: Bugs, their care and stomping
by Vincent Sanders
On Wed, Dec 18, 2013 at 02:29:06AM +0000, Harriet Bazley wrote:
> On 17 Dec 2013 as I do recall,
> Vincent Sanders wrote:
>
> [snip]
>
>
> > We have created users within the new system for everyone who has
> > reported a bug. For most imported users the email address used was
> > their sourceforge contact address [3]
> >
> >
> Oh -- oops, there's two of me now, then...
Only one now, I moved all 59 of your old reports to your new user
> --
> Harriet Bazley == Loyaulte me lie ==
>
> It is better to wear out than to rust.
>
>
--
Regards Vincent
http://www.kyllikki.org/
9 years, 9 months
NetSurf 3.1 alert
by Michael Drake
The core developers are gathering for a development weekend on 4/5th Jan.
We plan to get things sorted out so that a release of NetSurf 3.1 can be
made shortly after.
So the message to front end maintainers is to try to get anything
outstanding tidied up and ready for release by then.
Cheers,
--
Michael Drake (tlsa) http://www.netsurf-browser.org/
9 years, 9 months
iOS adaptation
by Pedro Remedios
Hi,
Has anyone successfully used this library in an iOS application? If so how did you go about implementing this?
Pedro
9 years, 9 months
Selection optimisation
by Michael Drake
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/
9 years, 10 months
