The Adblock Project

[mcm_ham]

Ok, I know that you can speed up the filter list by grouping words that start the same like so:

.ad.
.adserver.
.adimg.

/\Wad(server|img)?\W/

But I also know that grouping together words that end the same does not:

.blogad.
.getad.
.onlinead.

/\W(blog|get|online)ad\W/

This is because it starts the pattern matching from the beginning of the url. And since it has to initially test the three or cases this is really just the same as having three different filters. However, in trying to understand the regexp documentation it seems possible to start pattern matching from the end. In which case the above filter will bring about a speed increase. I gather this is done like this:

/\W(blog|get|online)ad\W/g

Where 'g' at the end represents the last index flag. However, AdBlock I've been told automatically handles case sensitive issues by making filters case insensitive and the '/' character appearing in the middle of a filter by escaping like this "\/". Of course if it was intelligent it would only escape the '/' characters that appear between the outer two. If it does escape the last one because there is a character after it then the flag wouldn't work.

So my question is, have I understood the situation correctly and is there a way to start pattern matching from the end for speed improvements?
Thanks for any help.

[Ken Cooper]

[mcm_ham]

[wonkothesane]

You're free to look at the actual code Adblock uses for details, but this is roughly how things work:

If a filter starts with '/' and ends with '/' (e.g. matches /^\/.*\/$/) then the beginning and ending slashes are stripped off (filter.slice(1,-1) and the resulting filter is passed to the RegExp constructor to create the RegExp object to use to .test() against each URL on the page as passed to shouldLoad. The RegExp constructor automatically escapes slashes for us, which is why you can write filters like /http://example\.com/ and have it work.

However, when you add that 'g' to the end, it makes Adblock think you haven't entered a regexp, but a plain string to be matched against instead (think: /ads/*). Oh, and Ken: no, Adblock does not make RegExps global; not much point, when all we're interested in is a boolean yes-or-no decision on whether a URL matched the pattern.

Non-regexp patterns have "special" characters escaped, leading and trailing asterisks removed, and "internal" asterisks converted to ".*?"; the resulting pattern is passed to the RegExp constructor.

Before making any assumptions about speed, it would behoove you to construct simple iterative tests in the JavaScript Console to get a better handle of how much time it actually takes to call .test(). As it turns out, callling .test() on a RegExp object is just as fast as a string-based indexOf(), which certainly surprised rue and myself. In 0.5, there was a distinction between "simple" filters and regexps, because rue assumed that .indexOf() was faster than .test(); later testing shattered that assumption.

**edit**
In some cases, .test can be much (4x) faster than .indexOf. It's most noticable for short strings; when the test-string gets to ~200 characters, the methods are about equal in speed. Try copy & pasting the following two code snippets in to the JS Console. I get ~760 for .indexOf and ~188 for .test

[Ken Cooper]

[rue]

Ken:
Wonko was referring to the url's length, not the filter's. He also didn't offer a complete view of the performance-difference:

[Ken Cooper]

Okay Rue, a few questions:

If you know most URL's will be <176 characters use a RegEx, otherwise use Simple?

In regards to the forward-slash, are you advocating that all forward-slashes now be escaped to comply with the literal syntax? Will 0.6 require these to be escaped, or can we keep cheating?
_________________
My Firefox Page
NOTE: Firefox is spelled “F-i-r-e-f-o-x”; only the first letter capitalized. The preferred abbreviation is “Fx” or “fx”.

[wonkothesane]

Ken: Being 'global' means a regexp will continue to search a string after it's found a match. For example, /\d/.test('1 plus 2 is 3.'); would (should) stop after the first character has satisfied the RE, but if that re were global (/\d/g) the whole string would be searched, which is unnecessary.

As I noted before: we're talking about a hundredth of a millisecond execution time for re.test(string). It's much faster for Adblock to test one long regexp than three short ones.

Technically, it's not cheating to not escape forward-slashes. Filter strings are not constructed with the literal syntax, which does require escaped forward slashes; instead, the string (minus leading and trailing slashes) is passed to the RegExp constructor. The above method ("details", as rue calls it) is highly unlikely to change.

In future-versions, simple filters will most-likely be transformed into RegExp -- meaning the trend rue posted will remain specific to v.5. Additional Note: it's quite rare to see URLs over 200 characters or so.

[Ken Cooper]

[Paulfox]

Well, this is perhaps the best thread EVER - both KenCooper and mcm_ham have taught me LOADS of stuff, and I learned more today here, because the three of us are "tightening the screws" of knowledge with this script.

Just fantastic. The not having to escape forward slashes is the reason my yahoo filter works (and well!); I may post here later with a couple of specifics myself but want to make it as specific, short and sweet as possible.

Many thanks to all here . . . AdBlock is just AMAZING and anyone connected with it should be knighted!

[mcm_ham]

Thanks for all the information, indexOf being slower then RegExp suprises me too. I think you are right wonkothesane writing some simple tests in java instead of making assumptions is the way to go, either that or try and work out the Big Oh notation to see how it scales.

[MW]

[Guest]

[someone]

Maybe it could be an option on 0.6
Another suggestion is to have a little stop watch type of thing to show users how much time it is taking to block the ads.

[wonkothesane]

MW: It's still true for v.5 -- that's all I'm allowed to say.

Guest: That's odd. I wonder if the relative speed difference is actually processor-based or dependent on another factor, like RAM (I've got a healthy 1 GB). Still, though: 4000 .test() calls take just over a second to complete, which means each call is using a fourth of a millisecond of processor time. Since each page is unlikely to have more than 80 calls to .test(), I think 20 ms of processor time per page on a 400 MHz Pentium II devoted to .test() isn't too exorbiant. That's rather more than most pages will generate (where calls = filters * elements).

someone: no, being able to treat all filters as regexp objects far outweighs the minor speed delta between .test and .indexOf.