Hacker News Reader

Comment by Arnt | Hacker News Reader

I see that differently… my wife uses firefox and that API. She eventually replaced her laptop. The only problem was that the old one wasn't fast enough to process about 90,000 regexps each time she clicked a link.

Chrome replaced it with a less flexible API that has bounded runtime, preventing the browser from the kind of slowness that caused a certain dissatisfaction, even disharmony here.

You could say that people shouldn't configure so much adblocking that the browser has to evaluate 90,000 regexps for a simple click. Or you could say that the browser shouldn't prevent that case by design. It's not simple. IMO a worst case like this is one of the causes of "invisible pressure".

View on HN

No well-known content blocker "process about 90,000 regexps" to find out whether a resource needs to be blocked or not, that's just not how it works internally.

Last time I ran benchmarks of all well-known content blockers using Ghostery's benchmark tool[1], all of them could process a network request under 20µs on average.

Some do have performance concerns, but it has nothing to do with network filtering, it has to do with other stuff they do beyond network filtering (for example see [2]) and declarativeNetRequest does not help there, so they will still suffer these performance issues under MV3.

---

[1] https://github.com/ghostery/adblocker/tree/master/packages/a...

[2] https://www.extremetech.com/computing/182428-ironic-iframes-...

I doubt that 90,000 rules were an issue. On 12 year old laptop (thinkpad x230) with 260,000 ublock rules (+240,000 cosmetic) the slowdown is imperceptible. Contrary, ad-ridden websites load much faster.

Disabling the blockers (plural because three) fixed it, so it was either that or that the extra processing pushed firefox over a RAM cliff and into swap, which sounds unlikely. Anyway, we didn't try any more debugging, she just got a new laptop.

You invented a problem and "didn't try any more debugging". Its like complaining about using three condoms, then changing partner to fix it.

Probably one of the extensions was the culprit. But clearly it's not about the number of rules and crippling that functionality would not bring performance benefit. Ublock origin is pretty lightweight even with 500,000 rules applied.

Most of those regexes fail after processing the first few characters.

I wonder if an optimizing regex-compiler could transform the set of regexes into a single finite state machine that’s more efficient than running individual regex recognizers in parallel. The optimal solution feels NP-hard, but I wonder if one could get sufficient improvements with some heuristic optimizations, like extracting common clauses, etc.

Maybe @burntsushi has some insights about this?

Taking a set of regexes and compiling them all into one automaton is exactly what RegexSet is: https://docs.rs/regex/latest/regex/struct.RegexSet.html

However, when you're talking about thousands of regexes, that's going to be a very large automaton. Probably impractically large. It's not NP-hard. It's "just" impractical.

Using heuristics to whittle down the set of possible regexes to match---likely using literals extracted from each regex---is exactly what you want to do for a problem like this. If all you have are literals, an Aho-Corasick automaton is feasible to build for 90,000 entries. Aho-Corasick, in my experience, doesn't really start to break down until you eclipse 1,000,000 entries.

Emacs used such a thing ~30 years ago. Common wisdom was that it was great when it worked, but a few carelessly written regexes would shoot the performance. If course there'll be some carelessly written ones in any set of >1k regexes.

Reply on news.ycombinator.com