[Done] Faster filter matching algorithm
Re: [Roadmap] Faster filter matching algorithm
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?
Re: [Roadmap] Faster filter matching algorithm
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).
Re: [Roadmap] Faster filter matching algorithm
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.
Re: [Roadmap] Faster filter matching algorithm
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.
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.
Re: [Roadmap] Faster filter matching algorithm
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.
- Adblock Plus Fan
- Posts: 1255
- Joined: Sat Feb 24, 2007 11:08 am
Re: [Roadmap] Faster filter matching algorithm
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?
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?
ABP video download trick / Want to help? Test new builds/report bugs you find.
Re: [Roadmap] Faster filter matching algorithm
Yes. "900 keywords each holding 1 filter" is the optimum.