Ublock: Consider converting has/if filters to xpath queries instead of manually evaluating them.

[kasper93]

Hi,

I would like to open discussion about this. Because I found that :xpath queries are a lot faster than uBO's code that evaluates has/if filters. So it might be better to convert those to xpath queries instead.

Now that has/if filters are used more and more in filters list I think it is important to take care about performance of those filters.

I found www.wp.pl good benchmark page, because it has a lot of elements and they are dynamically loaded as you scroll the page, so a lot DOM mutations.

I loaded page and scrolled to the bottom of main section letting new ones load and started scrolling back up. As you can see :xpath filter scales quite well with increasing number of div elements while :has version quickly starts to struggle to keep up to the point that filter is disabled. And those results translates to other pages so it might be worth investigating if handcrafted :has code is still better approach than implementing :xpath filter builder or using one of existing implementation that would achieve the same.

Let's consider those two filters as our test objects:

www.wp.pl##:xpath(//div[@class][div[1][contains(text(), 'REKLAMA')]])

Navigated to https://www.wp.pl/
procedural selectors/dom layout changed: 1.03ms
procedural selectors/dom layout changed: 0.99ms
procedural selectors/filterset changed: 0.52ms
procedural selectors/dom layout changed: 0.4ms
procedural selectors/dom layout changed: 0.7ms
procedural selectors/dom layout changed: 0.67ms
procedural selectors/dom layout changed: 0.5ms
procedural selectors/dom layout changed: 0.45ms
procedural selectors/dom layout changed: 0.51ms
procedural selectors/dom layout changed: 0.79ms
procedural selectors/dom layout changed: 0.72ms
procedural selectors/dom layout changed: 0.75ms
procedural selectors/dom layout changed: 0.8ms
procedural selectors/dom layout changed: 0.89ms
procedural selectors/dom layout changed: 0.89ms
procedural selectors/dom layout changed: 0.9ms
procedural selectors/dom layout changed: 0.91ms
procedural selectors/dom layout changed: 1.14ms
procedural selectors/dom layout changed: 0.95ms
procedural selectors/dom layout changed: 0.92ms
procedural selectors/dom layout changed: 0.95ms
procedural selectors/dom layout changed: 0.88ms
procedural selectors/dom layout changed: 1.05ms
procedural selectors/dom layout changed: 1.06ms
procedural selectors/dom layout changed: 1.16ms
procedural selectors/dom layout changed: 1.19ms
procedural selectors/dom layout changed: 1.16ms
procedural selectors/dom layout changed: 1.2ms
procedural selectors/dom layout changed: 1.14ms
procedural selectors/dom layout changed: 1.87ms
procedural selectors/dom layout changed: 1.26ms
procedural selectors/dom layout changed: 1.31ms
procedural selectors/dom layout changed: 1.32ms
procedural selectors/dom layout changed: 1.25ms
procedural selectors/dom layout changed: 1.17ms
procedural selectors/dom layout changed: 1.44ms
procedural selectors/dom layout changed: 1.36ms
procedural selectors/dom layout changed: 1.57ms
procedural selectors/dom layout changed: 1.8ms
procedural selectors/dom layout changed: 1.64ms
procedural selectors/dom layout changed: 1.71ms
procedural selectors/dom layout changed: 1.76ms
procedural selectors/dom layout changed: 1.69ms
procedural selectors/dom layout changed: 2.02ms
procedural selectors/dom layout changed: 1.77ms
procedural selectors/dom layout changed: 1.81ms
procedural selectors/dom layout changed: 1.83ms
procedural selectors/dom layout changed: 1.94ms
procedural selectors/dom layout changed: 1.85ms
procedural selectors/dom layout changed: 1.88ms
procedural selectors/dom layout changed: 1.66ms
procedural selectors/dom layout changed: 2.09ms
procedural selectors/dom layout changed: 2.01ms
procedural selectors/dom layout changed: 2.13ms
procedural selectors/dom layout changed: 1.99ms
procedural selectors/dom layout changed: 2.08ms
procedural selectors/dom layout changed: 1.95ms
procedural selectors/dom layout changed: 1.99ms
procedural selectors/dom layout changed: 2.31ms
procedural selectors/dom layout changed: 2.41ms
procedural selectors/dom layout changed: 2.37ms
procedural selectors/dom layout changed: 2.06ms
procedural selectors/dom layout changed: 1.94ms
procedural selectors/dom layout changed: 2.03ms
procedural selectors/dom layout changed: 1.99ms
procedural selectors/dom layout changed: 2.26ms
procedural selectors/dom layout changed: 1.81ms
procedural selectors/dom layout changed: 1.7ms
procedural selectors/dom layout changed: 1.81ms
procedural selectors/dom layout changed: 1.85ms
procedural selectors/dom layout changed: 1.68ms
procedural selectors/dom layout changed: 1.57ms
procedural selectors/dom layout changed: 1.59ms
procedural selectors/dom layout changed: 1.56ms
procedural selectors/dom layout changed: 1.61ms
procedural selectors/dom layout changed: 1.57ms
procedural selectors/dom layout changed: 1.65ms
procedural selectors/dom layout changed: 1.71ms
procedural selectors/dom layout changed: 1.68ms
procedural selectors/dom layout changed: 1.71ms
procedural selectors/dom layout changed: 1.64ms
procedural selectors/dom layout changed: 1.6ms
procedural selectors/dom layout changed: 1.62ms
procedural selectors/dom layout changed: 1.67ms
procedural selectors/dom layout changed: 1.7ms
procedural selectors/dom layout changed: 1.69ms
procedural selectors/dom layout changed: 1.6ms
procedural selectors/dom layout changed: 1.64ms
procedural selectors/dom layout changed: 1.98ms
procedural selectors/dom layout changed: 1.72ms
procedural selectors/dom layout changed: 1.67ms
procedural selectors/dom layout changed: 1.68ms
procedural selectors/dom layout changed: 1.66ms
procedural selectors/dom layout changed: 1.99ms
procedural selectors/dom layout changed: 1.52ms
procedural selectors/dom layout changed: 1.9ms

www.wp.pl##div[class]:if(>div[class]:first-child:has-text(REKLAMA))

Navigated to https://www.wp.pl/
procedural selectors/dom layout changed: 4.65ms
procedural selectors/filterset changed: 1.8ms
contentscript.js:832:17
procedural selectors/dom layout changed: 1ms
procedural selectors/dom layout changed: 1.5ms
procedural selectors/dom layout changed: 3.15ms
procedural selectors/dom layout changed: 1.64ms
procedural selectors/dom layout changed: 1.28ms
procedural selectors/dom layout changed: 1.83ms
procedural selectors/dom layout changed: 3.86ms
procedural selectors/dom layout changed: 3.57ms
procedural selectors/dom layout changed: 2.39ms
procedural selectors/dom layout changed: 2.7ms
procedural selectors/dom layout changed: 2.74ms
procedural selectors/dom layout changed: 4.28ms
procedural selectors/dom layout changed: 4.14ms
procedural selectors/dom layout changed: 4.05ms
procedural selectors/dom layout changed: 4.2ms
procedural selectors/dom layout changed: 4.95ms
procedural selectors/dom layout changed: 4.4ms
procedural selectors/dom layout changed: 4.48ms
procedural selectors/dom layout changed: 4.4ms
procedural selectors/dom layout changed: 6.19ms
procedural selectors/dom layout changed: 9.1ms
procedural selectors/dom layout changed: 6.02ms
procedural selectors/dom layout changed: 5.93ms
procedural selectors/dom layout changed: 6.02ms
procedural selectors/dom layout changed: 6.31ms
procedural selectors/dom layout changed: 6.2ms
procedural selectors/dom layout changed: 7.19ms
procedural selectors/dom layout changed: 9.03ms
procedural selectors/dom layout changed: 8.19ms
procedural selectors/dom layout changed: 8.56ms
procedural selectors/dom layout changed: 8.57ms
procedural selectors/dom layout changed: 8.41ms
procedural selectors/dom layout changed: 10.77ms
procedural selectors/dom layout changed: 9.99ms
procedural selectors/dom layout changed: 9.91ms
procedural selectors/dom layout changed: 10.03ms
procedural selectors/dom layout changed: 9.66ms
procedural selectors/dom layout changed: 11.32ms
procedural selectors/dom layout changed: 10.69ms
procedural selectors/dom layout changed: 12.68ms
procedural selectors/dom layout changed: 12.55ms
procedural selectors/dom layout changed: 12.59ms
procedural selectors/dom layout changed: 12.53ms
procedural selectors/dom layout changed: 10.84ms
procedural selectors/dom layout changed: 10.27ms
procedural selectors/dom layout changed: 10.52ms
procedural selectors/dom layout changed: 12.36ms
procedural selectors/dom layout changed: 10.11ms
procedural selectors/dom layout changed: 10.48ms
procedural selectors/dom layout changed: 10.28ms
procedural selectors/dom layout changed: 10.23ms
procedural selectors/dom layout changed: 12.89ms
procedural selectors/dom layout changed: 10.23ms
procedural selectors/dom layout changed: 9.97ms
disabling div[class]:if(:scope >div[class]:first-child:has-text(REKLAMA))
procedural selectors/dom layout changed: 10.64ms
procedural selectors/dom layout changed: 0.74ms
procedural selectors/dom layout changed: 0.3ms
procedural selectors/dom layout changed: 0.37ms

Regards,
Kacper

[adisib]

You should also mention which browser you are testing on, and possibly do the same test on others, as browsers can have very different xpath implementations.

[kasper93]

I tested both Firefox and Chrome. Numbers in first post are form Firefox Nightly (20171104100412). I explicitly haven't provide other browsers results, because it is exactly the same story. Chrome 62.0.3202.75 is little bit faster when it comes to :xpath it goes up to 1.5ms, while Firefox is at around ~2ms when everything is loaded. Chrome is also faster (looking how time progresses) when it comes to has case, but it also ends up with disabling the filter after enough elements on page are loaded.

I don't want to make it browser contest I wanted only to show that uBO has/if is slower than :xpath equivalent.

[kasper93]

For the record, today's Firefox Nightly enabled Stylo for QuerySelectorAll https://hg.mozilla.org/integration/autoland/pushloghtml?fromchange=be1d69e97c5a7d389348ae92ab7361109f23cd8c&tochange=ab10dee6754602dc43038618032c2a6b06396661

It is slower than Gecko for most selectors in my test, except some corner cases that Gecko struggled with (or possibly some more complex ones). See https://bugzilla.mozilla.org/show_bug.cgi?id=1414789 for reference. They seem to push Stylo forward hard regardless.

Anyhow I just wanted to say that numbers in the first post are from older build (with Gecko) so it is not perf regression. And like I said Chrome behave similarly.

[gorhill]

@kasper93

Would you be interested in working on this one?

[kasper93]

@gorhill: Sure, I will implement it soon.

[gorhill]

Closing this as stale, this is a significant undertaking with no guarantee of actual gains. Procedural filters can be crafted in various ways and one procedural filter under-performing can often be replaced with a much better targeted procedural filters. Additionally, Firefox's CSS selector engine has improved since then, especially when using attributes in selectors.