[Done] Faster filter matching algorithm

Various discussions related to Adblock Plus development
Michael
Posts: 1361
Joined: Sat Dec 19, 2009 12:29 pm

Re: [Roadmap] Faster filter matching algorithm

Post by Michael »

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?
Wladimir Palant

Re: [Roadmap] Faster filter matching algorithm

Post by Wladimir Palant »

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).
Michael
Posts: 1361
Joined: Sat Dec 19, 2009 12:29 pm

Re: [Roadmap] Faster filter matching algorithm

Post by Michael »

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.
Wladimir Palant

Re: [Roadmap] Faster filter matching algorithm

Post by Wladimir Palant »

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.
Michael
Posts: 1361
Joined: Sat Dec 19, 2009 12:29 pm

Re: [Roadmap] Faster filter matching algorithm

Post by Michael »

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.
User avatar
Adblock Plus Fan
Posts: 1255
Joined: Sat Feb 24, 2007 11:08 am

Re: [Roadmap] Faster filter matching algorithm

Post by Adblock Plus Fan »

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?
Wladimir Palant

Re: [Roadmap] Faster filter matching algorithm

Post by Wladimir Palant »

Yes. "900 keywords each holding 1 filter" is the optimum.
Locked