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.

I removed the restrictions on the repo, you may comment there if you prefer.

The steps I used to embed the benchmark loop in ABP itself are in this Gist (which I linked to earlier in an answer to you on reddit):
https://gist.github.com/gorhill/67d7b4e75e268fb36658823968427fb5

The main difference I would say is the use of two new URL() in order to comply with ABP's entry point matchRequest() -- which computes 3rd-partyness etc. They do use such code in their onBeforeRequest, so I consider it's representative. Maybe these URL constructors called for every single request is what is causing the difference.

On uBO's side, I used filteringContext in order to extract hostname, domain, etc. which is also what is used by uBO in its onBeforeRequest handler (the goal of filteringContext was to allow reusing as much as possible already computed values from one request to another).

I have to agree with @gorhill that the benchmark should include the extraction of the hostname. In Adblock Plus this is done using the URL object (but see #7296).

It should also include the determination of whether the request is third-party. In the benchmark you do this simply by comparing the request URL's hostname with the hostname of the source document, but in reality it is a bit more complicated.

Thanks for your input on this. I agree that it would be nice to also include request preparation in the benchmark, I can add this in the next iteration for all blockers. Regarding the check of third-party, as far as I can see the only difference in behavior is that we might consider third-party a request for which no frameUrl is available. I will probably re-use the exact same code used by each project to make this decision currently so that results are more representative.

I spotted and fixed a (minor) mistake in the benchmark loop I added in uBO. This was causing uBO to wrongly reuse an already computed hostname/domain for each request.url. The fix does not seem to have much of an influence on benchmark timings (hence why I use "minor").

@mjethani

see #7296

I am sure you will have realized it soon enough, you forgot anchoring your regex to start of tested string.

@gorhill thanks, updated.

@gorhill I have been updating the benchmark to include the URL processing as part of the measurements and I could now reproduce the results you obtained on your side. This probably means that there are optimizations opportunities in this part of Adblock Plus (FYI @mjethani I'm sure you're already aware of this with #7296). I'm going to clean this up and post more details on the final results a bit later.

Hi, it's me again. I have been updating the benchmarks in the following way:

1. Pin versions of different libraries used:
   • adblockerpluscore commit 34c49bbf029e586226220c067c50cec6e8bf8842
   • Brave's ad-block version 4.1.3
   • uBlock Origin commit 47ceaea3b916681e90604002224d87e76f21222f
   • Duckduckgo's abp-filter-parser version 0.2.0
2. The benchmark now also measures parsing the requests before matching, trying to reproduce what happens in the respective extensions.
3. uBlock Origin's code is now mostly identical to what happens in the extension, using the vm module from Node.js to simular an webExtension environment. It has also been updated to a more recent version and the WebAssembly code is used.

After re-running the benchmarks, I think we obtain results which are closer to what you measured on your side @gorhill. Parsing URLs is indeed a costly step and taking it into account changes makes sense. Thanks a lot for your input on this.

Here are the new results:

	99% OF REQUESTS	MEDIAN
Ghostery	0.058ms	0.010ms
uBlock Origin	0.117ms (2.0x slower)	0.018ms (1.8x slower)
Adblock Plus	0.174ms (3.0x slower)	0.033ms (3.2x slower)
Brave	1.160ms (19.9x slower)	0.043ms (4.3x slower)
DuckDuckGo	12.232ms (209.7x slower)	8.077ms (799.6x slower)

@remusao thanks for doing this.

When we have made further improvements to Adblock Plus, I shall update this space.

By the way, while I appreciate the performance study, Ghostery is woefully inefficient as a browser extension. One need only look at the amount of time spent in the onBeforeRequest handler.

Here are some numbers from a single run with the top 25 sites from Alexa:

• Ghostery 8.3.1: 1,223.7 ms
• uBlock Origin development build 1.18.5.3: 385.8 ms
• Adblock Plus development build 3.4.3.2258 (with a few local not-too-significant changes): 435.2 ms

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

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.