ublock_perf_thread_answer.md

Answer to comments on uBlock Origin thread: https://github.com/gorhill/uBlock/commit/5733439f629da948cfc3cae74afa519f6cff7b7f as it seems I do not have permission to comment.

Hi,

First of all I'd like to personnaly thank you for all the work you do on uBlock Origin and other extensions, the source code of which have been an inspiration to me personally many times in the past.

I am also really excited that there are multiple people pushing for more accurate measurements of the efficiency of content-blockers and I think sharing methodologies, data and results is a great start!

It is interesting that the results you obtained diverge from the study published yesterday. If I understand correctly you got similar timings for uBlock Origin itself, but the numbers for Adblock Plus do not seem to match (45µs instead of ~19µs). I'd really like to understand where this difference could come from.

The setup we used for the (synthetic) benchmark was the following:

1. The version of uBlock Origin we used was commit 29b10d215184aef1a9a12b715b47de9656ecdc3c
2. The version of Adblock Plus we used was commit 34c49bbf029e586226220c067c50cec6e8bf8842 of the adblockpluscore repository
3. The code used to run the benchmark for Adblock Plus is the following: https://github.com/cliqz-oss/adblocker/blob/master/bench/comparison/adblockplus.js

We initialized an instance of the CombinedMatcher class using all the network filters (as it seems to be the case in the extension), then used the matchesAny method of the matcher as an entry-point. Moreover, the parsing of the URLs were performed using tldts and not included in the measurement. It could be that the parsing and preparation of requests in Adblock Plus is less efficient than in uBlock Origin (which I know is extremely efficient).

The focus of the study was specifically on the network matching engine of the content-blockers and it seems likely that other parts of the extensions are introducing overhead. That's why I really like the in-browser measurement you have setup in uBlock Origin. In the end I guess all of these can be valuable in some way.

Thanks for taking the time to also check the extension. Firstly, some of the optimizations are still being released so it is going to get faster in next update. Secondly, I would not call it inefficient because comparing Ghostery as a whole with uBlock Origin or Adblock Plus does not really make sense: they are not doing the same thing. There is indeed a content-blocker in Ghostery (using the code benchmarked in the study) but that is really not the only thing happening; in particular our anti-tracking tech allows to make sure that any request not blocked by the adblocker is safe and does not contain unique identifiers which could be used to track users. This fine filtering takes more work than simply blocking requests but the benefit is huge in terms of privacy protection and reduced potential breakage. We are working in parallel to make this part of the extension more efficient and it is continuously improving.

@remusao thanks, this explanation makes sense.

The number is the total amount of time spent in the onBeforeRequest handler.

By the way, in the case of uBlock Origin and Adblock Plus, I disabled all filter lists except EasyList. I also turned off automatic updates of filter lists (for Adblock Plus I had to patch the code to do this). For Ghostery, I unchecked all boxes except "Advertising" (I am assuming this is the equivalent of EasyList-only blocking), while leaving all other settings at their defaults.

With commit 83f4c12, Adblock Plus should be looking significantly better now.

Before, with commit 34c49bb:

Total requests: 221451
Total match: 42771
Total no match: 178680

Number of samples: 42771
Min match: 0.006804
Max match: 9.142732
Avg match: 0.05548187989525618

Number of samples: 178680
Min no match: 0.005694
Max no match: 28.906369
Avg no match: 0.05254267835795824

Number of samples: 221451
Min (total): 0.005694
Max (total): 28.906369
Avg (total): 0.05311035513048049

In order to see the difference, switch adblockpluscore to commit 83f4c12 and apply the following patch to the benchmarking code:

diff --git a/bench/comparison/blockers/adblockplus.js b/bench/comparison/blockers/adblockplus.js
index 55219a7..2125c2f 100644
--- a/bench/comparison/blockers/adblockplus.js
+++ b/bench/comparison/blockers/adblockplus.js
@@ -6,7 +6,7 @@ const { URL } = require('url');

 const { CombinedMatcher } = require('./adblockpluscore/lib/matcher.js');
 const { Filter, RegExpFilter } = require('./adblockpluscore/lib/filterClasses.js');
-const { isThirdParty } = require('./adblockpluscore/lib/domain.js');
+const { parseURL, isThirdParty } = require('./adblockpluscore/lib/url.js');

 // Chrome can't distinguish between OBJECT_SUBREQUEST and OBJECT requests.
 RegExpFilter.typeMap.OBJECT_SUBREQUEST = RegExpFilter.typeMap.OBJECT;
@@ -73,8 +73,8 @@ module.exports = class AdBlockPlus {
   }

   match(request) {
-    const url = new URL(request.url);
-    const sourceURL = new URL(request.frameUrl);
+    const url = parseURL(request.url);
+    const sourceURL = parseURL(request.frameUrl);
     const thirdParty = isThirdParty(url, sourceURL.hostname);
     const filter = this.matcher.matchesAny(
       url.href,

Total requests: 221451
Total match: 42771
Total no match: 178680

Number of samples: 42771
Min match: 0.001194
Max match: 6.876924
Avg match: 0.025724892099787205

Number of samples: 178680
Min no match: 0.001045
Max no match: 11.41862
Avg no match: 0.02922782791023087

Number of samples: 221451
Min (total): 0.001045
Max (total): 11.41862
Avg (total): 0.028551271617649362

uBlock Origin, for comparison:

Total requests: 221451
Total match: 45163
Total no match: 176288

Number of samples: 45163
Min match: 0.00401
Max match: 7.435235
Avg match: 0.03555580120895435

Number of samples: 176288
Min no match: 0.003716
Max no match: 11.738337
Avg no match: 0.030611913924941503

Number of samples: 221451
Min (total): 0.003716
Max (total): 11.738337
Avg (total): 0.03162017661694901

I've been updating the comparison with some fixes as well as updated adblockpluscore. I also ran the benchmarks again on the exact same hardware (X1 Carbon 2016, i7 U6600 + 16GB of RAM) in a cold environment to prevent too much CPU throttling. I used the latest Node.js 11.11.0. Here are the results I got:

All Requests

	99% OF REQUESTS	MEDIAN
Ghostery	0.057ms	0.009ms
uBlock Origin	0.121ms (2.1x slower)	0.017ms (1.9x slower)
Adblock Plus	0.104ms (1.8x slower)	0.020ms (2.3x slower)
Brave	1.144ms (20.2x slower)	0.043ms (4.7x slower)
DuckDuckGo	12.594ms (222.5x slower)	8.044ms (895.9x slower)

Requests Not Blocked

	99% OF REQUESTS	MEDIAN
Ghostery	0.056ms	0.009ms
uBlock Origin	0.107ms (1.9x slower)	0.018ms (2.0x slower)
Adblock Plus	0.106ms (1.9x slower)	0.021ms (2.4x slower)
Brave	1.134ms (20.3x slower)	0.038ms (4.4x slower)
DuckDuckGo	11.961ms (213.6x slower)	2.164ms (248.5x slower)

Requests Blocked

	99% OF REQUESTS	MEDIAN
Ghostery	0.058ms	0.010ms
uBlock Origin	0.166ms (2.9x slower)	0.017ms (1.6x slower)
Adblock Plus	0.101ms (1.7x slower)	0.016ms (1.5x slower)
Brave	1.308ms (22.6x slower)	0.076ms (7.4x slower)
DuckDuckGo	13.132ms (226.5x slower)	8.311ms (809.4x slower)

Thanks, this is great!

@remusao, I consider there is a flaw in the benchmark code to measure matching algorithm.

I can't speak for other filtering engines, but in uBO there is initialization work which is done in a lazy manner, at match() time if required. This initialization works occur only once and thus my opinion is that the only-once initialization work done at match() time should not influence measurement of the match() algorithm.

I believe the new engine created here should be first warmed up by making it go through all the data first, then measurement can proceed.

Edit 1: Quick local changes to add code to warm up the engine before measurements, it does seem warming up yield better results for cliqz and ublock (I didn't check the others).

Edit 2: Never mind. Thinking more of it, I suppose it makes sense to measure these lazily initializations, given that the benchmark contains over 220K URL to match, this would be the equivalent of valid browsing session in the real world.

@gorhill, that is an interesting point. I was a bit reluctant to warm-up the different blockers too much since some of them implement internal caching in one form or another (AdblockPlus will cache results of matching for the last N requests for example). If warming up is applied, should we clear caches before running the benchmark? Should caching be left as is and considered representative enough of a normal workload? Should warming up before benchmarking considered representative?

With regard to uBO, would there be a way to trigger the initialization work artificially before benchmarking without having to run through the dataset once?

Thanks for taking the time to look in the the benchmark into more details, your opinions and feedback are very appreciated!

Edit 1: By the way, congratz for the recent optimizations added to uBO.

@remusao I edited my comment above, thinking more about it, I now think it's fine to measure the lazy initialization because of the sheer amount of URLs being matched in the benchmark. If ever the lazy initialization becomes such an issue that it does affect the benchmark timings a lot, then it's the responsibility of the developers to improve that part.