[Done] Faster filter matching algorithm

Various discussions related to Adblock Plus development

Re: [Roadmap] Faster filter matching algorithm

Postby Michael » Fri Feb 25, 2011 7:25 pm

Would it please be possible to avoid selecting protocols, such as "http", as keywords unless there is no other alternative to ensure that a filter is not checked against practically every loaded item?
Michael
 
Posts: 1361
Joined: Sat Dec 19, 2009 1:29 pm

Re: [Roadmap] Faster filter matching algorithm

Postby Wladimir Palant » Fri Feb 25, 2011 8:21 pm

Isn't that already what happens most of the time? The algorithm tries to balance the lists, this automatically keeps the "http" list short (though "com" list is more problematic).
Wladimir Palant
ABP Developer
 
Posts: 8398
Joined: Fri Jun 09, 2006 6:59 pm
Location: Cologne, Germany

Re: [Roadmap] Faster filter matching algorithm

Postby Michael » Fri Feb 25, 2011 8:37 pm

The suggestion stems from a discussion with Lain_13. Although it would usually be preferable to balance the number of keywords, a keyword of "http" will mean that a filter will be checked practically every item name as it is loaded. It would instead be preferable, I would assume, for an alternative keyword to be selected wherever available, as it would match fewer items and therefore be evaluated less frequently, presumably resulting in an improvement in performance.
Michael
 
Posts: 1361
Joined: Sat Dec 19, 2009 1:29 pm

Re: [Roadmap] Faster filter matching algorithm

Postby Wladimir Palant » Sat Feb 26, 2011 5:10 pm

Michael, I already discussed this with Lain_13 - he tends to micro-optimize things that are not worth optimizing. The matching performance that we have now is very good and the delay isn't really noticeable. Any complication of the current algorithm will most likely cause a larger delay than the eight filters in EasyList currently using "http" keyword.

Btw, not sure whether Lain_13 shared that link with you - http://pastebin.mozilla.org/?dl=1064160 allows visualizing cache.js contents in latest Adblock Plus development builds. Simply put that HTML file into the directory of cache.js and open it in Firefox.
Wladimir Palant
ABP Developer
 
Posts: 8398
Joined: Fri Jun 09, 2006 6:59 pm
Location: Cologne, Germany

Re: [Roadmap] Faster filter matching algorithm

Postby Michael » Sat Feb 26, 2011 6:31 pm

Thanks for the information about keyword choice and the file to visualise cache data; the latter is far more effective and useful than the script that I used to use to determine keyword frequency.
Michael
 
Posts: 1361
Joined: Sat Dec 19, 2009 1:29 pm

Re: [Roadmap] Faster filter matching algorithm

Postby Adblock Plus Fan » Sun Feb 27, 2011 7:46 pm

If I have for example 900 filters.

It could be 30 keywords each holding 30 filters.
Or it could be 900 keywords each holding 1 filter.
Or it could be 100 keywords each holding 9 filters.
etc.

Is there some kind optimum we should aim for that gives the best performance in practice?
User avatar
Adblock Plus Fan
 
Posts: 1255
Joined: Sat Feb 24, 2007 12:08 pm

Re: [Roadmap] Faster filter matching algorithm

Postby Wladimir Palant » Sun Feb 27, 2011 8:06 pm

Yes. "900 keywords each holding 1 filter" is the optimum.
Wladimir Palant
ABP Developer
 
Posts: 8398
Joined: Fri Jun 09, 2006 6:59 pm
Location: Cologne, Germany

Previous

Return to Adblock Plus development

Who is online

Users browsing this forum: No registered users and 2 guests