New issue
Advanced search Search tips
Note: Color blocks (like █ or █) mean that a user may not be available. Tooltip shows the reason.

Issue 705499 link

Starred by 2 users
Status: WontFix
Owner:
█ pkalinnikov@chromium.org
Last visit > 30 days ago
Closed: Apr 2017
Cc:
engedy@chromium.org
csharrison@chromium.org
EstimatedDays: ----
NextAction: ----
OS: ----
Pri: 2
Type: Feature

Blocking:
issue 609747



Sign in to add a comment

[Subresource Filter] Use Rabin-Karp instead of Knuth-Morris-Pratt.

Project Member Reported by pkalinnikov@chromium.org, Mar 27 2017 
Using Rabin-Karp instead of KMP allows to reduce Subresource Filter's memory consumption by almost 0.5 Mb (as of today), because it does not require to store any precomputed state to the ruleset.

Evaluate performance of Rabin-Karp with different rolling hashes, evaluate feasibility of this change.

Comment 1 by pkalinnikov@chromium.org, Apr 5 2017

Status: WontFix (was: Started)
I have run a quick analysis of the following string matching alternatives: KMP, Rabin-Karp, and naive base::StringPiece::find/std::search. Turns out that for subresource_filter's patterns the naive search does at most 4-5 comparisons per character (in the worst case of URL, which is normally not the case), and even in this case it works as fast as Rabin-Karp. Additionally, the IndexedRuleset stress-test shows that the naive algorithm is the fastest for real world URLs.

Closing this bug because there is no need to use Rabin-Karp.

Comment 2 by pkalinnikov@chromium.org, Apr 5 2017 

This bug has beed transformed into crbug/708458.
►

Sign in to add a comment