[subresource_filter] Replace KMP by std::search.

[subresource_filter] Replace KMP by std::search.

This CL replaces Knuth-Morris-Pratt algorithm in IndexedRuleset with a naive
string searching algorithm, i.e. base::StringPiece::find/std::search.

This reduces the size of the IndexedRuleset by 500+ kB, because currently that
much space is needed to store failure functions for all the (sub-)patterns.

This also improves performance of IndexedRuleset by 40%, as measured by
stress-testing. This is explained as follows:
  * The subresource_filter's patterns are inherently simple. In the worst
    case of a URL the matching will make 4-5 comparisons per character.
  * The real world URLs are usually not worst-case, and the real average number
    drops down to 1-2 comparisons per character.

BUG=708458
Review-Url: https://codereview.chromium.org/2793993002
Cr-Commit-Position: refs/heads/master@{#462131}
Committed: https://chromium.googlesource.com/chromium/src/+/35d1881dac3470d2ed891feae0c1cfcf30025a0b

[pkalinnikov, 2017-04-03 15:05:14]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-03 15:05:32]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-03 15:44:19]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-03 15:44:20]

Dry run: Try jobs failed on following builders:
  win_chromium_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)
  win_chromium_x64_rel_ng on master.tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_x64_...)

[pkalinnikov, 2017-04-04 09:28:28]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-04 09:28:45]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2017-04-04 09:50:42]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-04 09:50:57]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-04 09:54:36]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-04 09:54:37]

Dry run: Try jobs failed on following builders:
  cast_shell_linux on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/cast_shell_linu...)
  linux_chromium_chromeos_ozone_rel_ng on master.tryserver.chromium.linux
(JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)
  linux_chromium_compile_dbg_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[pkalinnikov, 2017-04-04 09:58:42]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-04 09:58:51]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2017-04-04 10:00:15]

Patchset #3 (id:40001) has been deleted

[pkalinnikov, 2017-04-04 10:06:48]

pkalinnikov@chromium.org changed reviewers:
+ csharrison@chromium.org, engedy@chromium.org

[pkalinnikov, 2017-04-04 10:06:48]

PTAL.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/url_pattern_unittest.cc (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern_unittest.cc:7: #include
<vector>
nit: Not used.

[commit-bot: I haz the power, 2017-04-04 11:13:03]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-04 11:13:04]

Dry run: This issue passed the CQ dry run.

[engedy, 2017-04-04 12:29:32]

Charlie, do you want to take a first look?

[Charlie Harrison, 2017-04-04 12:59:17]

On 2017/04/04 12:29:32, engedy wrote:
> Charlie, do you want to take a first look?

Sure, taking a look right now.

[Charlie Harrison, 2017-04-04 13:58:26]

It looks pretty good to me, just nits and a few requests for comments.

Overall I am very pleased with this cleanup :)

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/fuzzy_pattern_matching.h (left):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/fuzzy_pattern_matching.h:22: #include
<type_traits>
I think you can remove all of these includes except string_piece.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_utils.h (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_utils.h:18:
proto::UrlRule CreateUrlRule(base::StringPiece pattern,
This might need some documentation that it doesn't support anchors without
subsequent calls to set_anchor*

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:85: class Subpattern {
It looks like this class is only used for generating temporaries. Can we replace
it with flat functions?

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:124: };
does it need to be copyable?

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:176: base::StringPiece
subpattern = *subpattern_it++;
nit: Can you break this into two lines for clarity?

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:176: base::StringPiece
subpattern = *subpattern_it++;
Can you include comments above these code paragraphs to explain the algorithm?

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.h (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:66: private:
Not needed

[pkalinnikov, 2017-04-04 16:40:55]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-04 16:41:41]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2017-04-04 16:42:59]

Thank you Charlie! Addressed all your comments. Feel free to make another round,
or to pass the token to Balazs.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/fuzzy_pattern_matching.h (left):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/fuzzy_pattern_matching.h:22: #include
<type_traits>
On 2017/04/04 13:58:26, Charlie Harrison wrote:
> I think you can remove all of these includes except string_piece.

Done.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_utils.h (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_utils.h:18:
proto::UrlRule CreateUrlRule(base::StringPiece pattern,
On 2017/04/04 13:58:26, Charlie Harrison wrote:
> This might need some documentation that it doesn't support anchors without
> subsequent calls to set_anchor*

Done.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:85: class Subpattern {
On 2017/04/04 13:58:26, Charlie Harrison wrote:
> It looks like this class is only used for generating temporaries. Can we
replace
> it with flat functions?

Done.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:124: };
On 2017/04/04 13:58:26, Charlie Harrison wrote:
> does it need to be copyable?

Not relevant anymore.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:176: base::StringPiece
subpattern = *subpattern_it++;
On 2017/04/04 13:58:26, Charlie Harrison wrote:
> nit: Can you break this into two lines for clarity?

How about this?

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:176: base::StringPiece
subpattern = *subpattern_it++;
On 2017/04/04 13:58:26, Charlie Harrison wrote:
> Can you include comments above these code paragraphs to explain the algorithm?

Done.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.h (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:66: private:
On 2017/04/04 13:58:26, Charlie Harrison wrote:
> Not needed

Done.

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/url_pattern_unittest.cc (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern_unittest.cc:7: #include
<vector>
On 2017/04/04 10:06:48, pkalinnikov wrote:
> nit: Not used.

Done.

[Charlie Harrison, 2017-04-04 16:49:40]

LGTM % nit assuming engedy is happy

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/60001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:176: base::StringPiece
subpattern = *subpattern_it++;
On 2017/04/04 16:42:59, pkalinnikov wrote:
> On 2017/04/04 13:58:26, Charlie Harrison wrote:
> > nit: Can you break this into two lines for clarity?
> 
> How about this?

looks good.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:97: subpattern.end(),
[](char text_char, char subpattern_char) {
nit: Could you hoist the lambda to a member var? It is more readable to me as:

auto searcher = [](char text_char, char subpattern_char) {
  return text_char == subpattern_char || 
    (subpattern_char == kSeparatorPlaceholder && 
      IsSeparator(text_char));
};
auto* found = std::search(text.begin() + from, text.end(),
                          subpattern.begin(), subpattern.end(), searcher);

[commit-bot: I haz the power, 2017-04-04 17:46:40]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-04 17:46:41]

Dry run: This issue passed the CQ dry run.

[pkalinnikov, 2017-04-05 09:31:30]

Description was changed from

==========
[subresource_filter] Replace KMP by std::search.

BUG=705499
==========

to

==========
[subresource_filter] Replace KMP by std::search.

This CL replaces Knuth-Morris-Pratt algorithm in IndexedRuleset with a naive
string searching algorithm, i.e. base::StringPiece::find/std::search.

This reduces the size of the IndexedRuleset by 500+ Mb, because currently that
much space is needed to store failure functions for all the (sub-)patterns.

This also improves performance of IndexedRuleset by 40%, as measured by
stress-testing. This is explained as follows:
  * The subresource_filter's patterns are inherently simple. In the worst
    case of a URL the matching will make 4-5 comparisons per character.
  * The real world URLs are usually not worst-case, and the real average number
    drops down to 1-2 comparisons per character.

BUG=708458
==========

[engedy, 2017-04-05 10:55:11]

LGTM % comments, thanks!

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_creator.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_creator.cc:124:
CreateRulesetWithRules({suffix_rule}, test_unindexed_ruleset);
nit: Enclose this in ASSERT_NO_FATAL_FAILURE too, so in case the innermost
function ASSERTs, a complete chain of nested function calls gets logged in the
test output.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_creator.h (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_creator.h:88: void
CreateRulesetWithRules(const std::vector<proto::UrlRule>& rules,
nit: CreateUnindexedRulesetWithRulest for consistency, and to avoid overloading.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_utils.h (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_utils.h:18: // Creates a
simple blacklist URL rule from a |pattern| of a certain |type|. The
This is used only by a single call site to create a REGEX rule, for which
anchors do not have a meaning. What do you think about just inlining the bare
minimum rule to that test, and removing this function?

  proto::UrlRule rule;
  rule.set_semantics(proto::RULE_SEMANTICS_BLACKLIST);
  rule.set_url_pattern_type(proto::URL_PATTERN_TYPE_REGEX);

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_utils.h:24: // Creates a
blacklist URL rule which targets subresources of any type such that
nit: ... such that the resource URL ends with |suffix|.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:86: // |text|, starting
|from| a certain position. If |is_fuzzy| then
nit: s/a certain/the specified/g

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:96:
std::search(text.begin() + from, text.end(), subpattern.begin(),
nit: Have you considered moving this to fuzzy_pattern_matching.h?

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:117: // starts in the
beginning of a (sub-)domain within the url's |host| component.
nit: ... at the beginning ...

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:121: const bool
is_fuzzy =
Do we need to check subpattern for being empty here? Looks like in that case, we
might increment the iterator in line 96 beyond text.end(), which might not be
allowed for some kind of things backing the StringPiece. Alternatively, we could
do some bounds checking in FindSubpatternImpl or somehow enforce that this never
happens.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:165:
DCHECK(url.is_valid());
Could you please add a comment here that empty URLs are also invalid?

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:182: base::StringPiece
subpattern = *subpattern_it;
nit: Could you please add a comment to explain why we expect this way is faster?
(Does the compiler not optimize this anyway?)

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.h (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:22: // The structure
used to mirror a URL pattern regardless of the representation
nit: Should update this comment now that there is behavior to this class.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:52: //
TODO(pkalinnikov): Outline algorithms implemented in this method.
nit: Can we resolve this in this CL?

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:57: // convertions in
IndexedRuleset.
typo: conversions

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:69: // Stream operator
so UrlPattern can be used in testing assertions.
nit: It can be used in GTest assertions without this as well, right? It is just
that it will be printed as a binary blob. How about:

// Allow pretty-printing URLPatterns when they are used in GTest assertions.

[engedy, 2017-04-05 10:57:13]

Also, I find it hard to believe the 500+ Mb savings in the CL description. :P
(Note that it correct capitalization is kB.)

[engedy, 2017-04-05 11:40:30]

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern_unittest.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern_unittest.cc:28: {{"",
kBoundary, kAnchorNone}, "http://ex.com/", true},
nit: Could you please also add a test with {"", kAnchorNone, kAnchorNone}?

[pkalinnikov, 2017-04-05 13:25:46]

Description was changed from

==========
[subresource_filter] Replace KMP by std::search.

This CL replaces Knuth-Morris-Pratt algorithm in IndexedRuleset with a naive
string searching algorithm, i.e. base::StringPiece::find/std::search.

This reduces the size of the IndexedRuleset by 500+ Mb, because currently that
much space is needed to store failure functions for all the (sub-)patterns.

This also improves performance of IndexedRuleset by 40%, as measured by
stress-testing. This is explained as follows:
  * The subresource_filter's patterns are inherently simple. In the worst
    case of a URL the matching will make 4-5 comparisons per character.
  * The real world URLs are usually not worst-case, and the real average number
    drops down to 1-2 comparisons per character.

BUG=708458
==========

to

==========
[subresource_filter] Replace KMP by std::search.

This CL replaces Knuth-Morris-Pratt algorithm in IndexedRuleset with a naive
string searching algorithm, i.e. base::StringPiece::find/std::search.

This reduces the size of the IndexedRuleset by 500+ kB, because currently that
much space is needed to store failure functions for all the (sub-)patterns.

This also improves performance of IndexedRuleset by 40%, as measured by
stress-testing. This is explained as follows:
  * The subresource_filter's patterns are inherently simple. In the worst
    case of a URL the matching will make 4-5 comparisons per character.
  * The real world URLs are usually not worst-case, and the real average number
    drops down to 1-2 comparisons per character.

BUG=708458
==========

[pkalinnikov, 2017-04-05 13:25:59]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-05 13:26:18]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2017-04-05 13:28:19]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-05 13:28:40]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2017-04-05 13:29:22]

Addressed all comments, thanks!

Balazs, can you make a final round?

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_creator.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_creator.cc:124:
CreateRulesetWithRules({suffix_rule}, test_unindexed_ruleset);
On 2017/04/05 10:55:10, engedy wrote:
> nit: Enclose this in ASSERT_NO_FATAL_FAILURE too, so in case the innermost
> function ASSERTs, a complete chain of nested function calls gets logged in the
> test output.

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_creator.h (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_creator.h:88: void
CreateRulesetWithRules(const std::vector<proto::UrlRule>& rules,
On 2017/04/05 10:55:10, engedy wrote:
> nit: CreateUnindexedRulesetWithRulest for consistency, and to avoid
overloading.

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_utils.h (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_utils.h:18: // Creates a
simple blacklist URL rule from a |pattern| of a certain |type|. The
On 2017/04/05 10:55:11, engedy wrote:
> This is used only by a single call site to create a REGEX rule, for which
> anchors do not have a meaning. What do you think about just inlining the bare
> minimum rule to that test, and removing this function?
> 
>   proto::UrlRule rule;
>   rule.set_semantics(proto::RULE_SEMANTICS_BLACKLIST);
>   rule.set_url_pattern_type(proto::URL_PATTERN_TYPE_REGEX);

SGTM. However, such a rule would be considered unsupported for another reason
(source_type is UNSPECIFIED). I made it simpler: just use the
default-constructed proto::UrlRule. WDYT?

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_utils.h:24: // Creates a
blacklist URL rule which targets subresources of any type such that
On 2017/04/05 10:55:10, engedy wrote:
> nit: ... such that the resource URL ends with |suffix|.

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:86: // |text|, starting
|from| a certain position. If |is_fuzzy| then
On 2017/04/05 10:55:11, engedy wrote:
> nit: s/a certain/the specified/g

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:96:
std::search(text.begin() + from, text.end(), subpattern.begin(),
On 2017/04/05 10:55:11, engedy wrote:
> nit: Have you considered moving this to fuzzy_pattern_matching.h?

Done. Also, reused the old AllOccurrences test.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:97: subpattern.end(),
[](char text_char, char subpattern_char) {
On 2017/04/04 16:49:39, Charlie Harrison wrote:
> nit: Could you hoist the lambda to a member var? It is more readable to me as:
> 
> auto searcher = [](char text_char, char subpattern_char) {
>   return text_char == subpattern_char || 
>     (subpattern_char == kSeparatorPlaceholder && 
>       IsSeparator(text_char));
> };
> auto* found = std::search(text.begin() + from, text.end(),
>                           subpattern.begin(), subpattern.end(), searcher);

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:117: // starts in the
beginning of a (sub-)domain within the url's |host| component.
On 2017/04/05 10:55:11, engedy wrote:
> nit: ... at the beginning ...

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:121: const bool
is_fuzzy =
On 2017/04/05 10:55:11, engedy wrote:
> Do we need to check subpattern for being empty here? Looks like in that case,
we
> might increment the iterator in line 96 beyond text.end(), which might not be
> allowed for some kind of things backing the StringPiece. Alternatively, we
could
> do some bounds checking in FindSubpatternImpl or somehow enforce that this
never
> happens.

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:165:
DCHECK(url.is_valid());
On 2017/04/05 10:55:11, engedy wrote:
> Could you please add a comment here that empty URLs are also invalid?

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:182: base::StringPiece
subpattern = *subpattern_it;
On 2017/04/05 10:55:11, engedy wrote:
> nit: Could you please add a comment to explain why we expect this way is
faster?
> (Does the compiler not optimize this anyway?)

I splitted *subpattern_it++ in two lines, because csharrison@ had a readability
concern.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.h (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:22: // The structure
used to mirror a URL pattern regardless of the representation
On 2017/04/05 10:55:11, engedy wrote:
> nit: Should update this comment now that there is behavior to this class.

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:52: //
TODO(pkalinnikov): Outline algorithms implemented in this method.
On 2017/04/05 10:55:11, engedy wrote:
> nit: Can we resolve this in this CL?

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:57: // convertions in
IndexedRuleset.
On 2017/04/05 10:55:11, engedy wrote:
> typo: conversions

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.h:69: // Stream operator
so UrlPattern can be used in testing assertions.
On 2017/04/05 10:55:11, engedy wrote:
> nit: It can be used in GTest assertions without this as well, right? It is
just
> that it will be printed as a binary blob. How about:
> 
> // Allow pretty-printing URLPatterns when they are used in GTest assertions.

Done.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern_unittest.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern_unittest.cc:28: {{"",
kBoundary, kAnchorNone}, "http://ex.com/", true},
On 2017/04/05 11:40:30, engedy wrote:
> nit: Could you please also add a test with {"", kAnchorNone, kAnchorNone}?

The lines 26-27 cover this case already.

[pkalinnikov, 2017-04-05 13:30:57]

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
File
components/subresource_filter/core/common/fuzzy_pattern_matching_unittest.cc
(right):

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/fuzzy_pattern_matching_unittest.cc:60:
TEST(FuzzyPatternMatchingTest, AllOccurrences) {
nit: Add "SubresourceFilter" prefix.

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/fuzzy_pattern_matching_unittest.cc:97:

nit: Remove the blank line.

[engedy, 2017-04-05 13:41:34]

LGTM % one comment and one nit.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/test_ruleset_utils.h (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/test_ruleset_utils.h:18: // Creates a
simple blacklist URL rule from a |pattern| of a certain |type|. The
On 2017/04/05 13:29:21, pkalinnikov wrote:
> On 2017/04/05 10:55:11, engedy wrote:
> > This is used only by a single call site to create a REGEX rule, for which
> > anchors do not have a meaning. What do you think about just inlining the
bare
> > minimum rule to that test, and removing this function?
> > 
> >   proto::UrlRule rule;
> >   rule.set_semantics(proto::RULE_SEMANTICS_BLACKLIST);
> >   rule.set_url_pattern_type(proto::URL_PATTERN_TYPE_REGEX);
> 
> SGTM. However, such a rule would be considered unsupported for another reason
> (source_type is UNSPECIFIED). I made it simpler: just use the
> default-constructed proto::UrlRule. WDYT?

Sounds good.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern.cc:182: base::StringPiece
subpattern = *subpattern_it;
On 2017/04/05 13:29:21, pkalinnikov wrote:
> On 2017/04/05 10:55:11, engedy wrote:
> > nit: Could you please add a comment to explain why we expect this way is
> faster?
> > (Does the compiler not optimize this anyway?)
> 
> I splitted *subpattern_it++ in two lines, because csharrison@ had a
readability
> concern.

Acknowledged.

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
File components/subresource_filter/core/common/url_pattern_unittest.cc (right):

https://codereview.chromium.org/2793993002/diff/80001/components/subresource_...
components/subresource_filter/core/common/url_pattern_unittest.cc:28: {{"",
kBoundary, kAnchorNone}, "http://ex.com/", true},
On 2017/04/05 13:29:22, pkalinnikov wrote:
> On 2017/04/05 11:40:30, engedy wrote:
> > nit: Could you please also add a test with {"", kAnchorNone, kAnchorNone}?
> 
> The lines 26-27 cover this case already.

Ah. Got it.

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
File components/subresource_filter/core/common/fuzzy_pattern_matching.h (right):

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/fuzzy_pattern_matching.h:61: // the
|text|, starting |from| the specified position.
nit: but starting no earlier than |from| ...

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/url_pattern.cc:107: if (position ==
base::StringPiece::npos ||
Shouldn't we return npos in case the first term is true?

[pkalinnikov, 2017-04-05 13:48:20]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-05 13:48:42]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2017-04-05 13:48:47]

Addressed, thanks!

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
File components/subresource_filter/core/common/fuzzy_pattern_matching.h (right):

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/fuzzy_pattern_matching.h:61: // the
|text|, starting |from| the specified position.
On 2017/04/05 13:41:33, engedy wrote:
> nit: but starting no earlier than |from| ...

Done.

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
File
components/subresource_filter/core/common/fuzzy_pattern_matching_unittest.cc
(right):

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/fuzzy_pattern_matching_unittest.cc:60:
TEST(FuzzyPatternMatchingTest, AllOccurrences) {
On 2017/04/05 13:30:57, pkalinnikov wrote:
> nit: Add "SubresourceFilter" prefix.

Done.

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/fuzzy_pattern_matching_unittest.cc:97:

On 2017/04/05 13:30:57, pkalinnikov wrote:
> nit: Remove the blank line.

Done.

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/url_pattern.cc:107: if (position ==
base::StringPiece::npos ||
On 2017/04/05 13:41:33, engedy wrote:
> Shouldn't we return npos in case the first term is true?

If the first term is true, then "return position" returns npos.

[engedy, 2017-04-05 13:55:40]

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
File components/subresource_filter/core/common/url_pattern.cc (right):

https://codereview.chromium.org/2793993002/diff/120001/components/subresource...
components/subresource_filter/core/common/url_pattern.cc:107: if (position ==
base::StringPiece::npos ||
On 2017/04/05 13:48:47, pkalinnikov wrote:
> On 2017/04/05 13:41:33, engedy wrote:
> > Shouldn't we return npos in case the first term is true?
> 
> If the first term is true, then "return position" returns npos.

Oh, of course. :)

[commit-bot: I haz the power, 2017-04-05 14:54:13]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-05 14:54:14]

Dry run: This issue passed the CQ dry run.

[pkalinnikov, 2017-04-05 15:52:18]

The CQ bit was checked by pkalinnikov@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2017-04-05 15:52:50]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[pkalinnikov, 2017-04-05 15:53:08]

Fixed DCHECK condition.

Balazs, can I submit?

[engedy, 2017-04-05 16:20:28]

Yeah, go ahead.

[commit-bot: I haz the power, 2017-04-05 16:50:34]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2017-04-05 16:50:36]

Dry run: This issue passed the CQ dry run.

[pkalinnikov, 2017-04-05 17:18:25]

The CQ bit was checked by pkalinnikov@chromium.org

[pkalinnikov, 2017-04-05 17:18:25]

The patchset sent to the CQ was uploaded after l-g-t-m from
csharrison@chromium.org, engedy@chromium.org
Link to the patchset: https://codereview.chromium.org/2793993002/#ps160001
(title: "Fix DCHECK.")

[commit-bot: I haz the power, 2017-04-05 17:19:03]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2017-04-05 17:28:22]

CQ is committing da patch.

Bot data: {"patchset_id": 160001, "attempt_start_ts": 1491412705222330,
"parent_rev": "385c750bda55aeca96a2b55c30d1f56b6a816f57", "commit_rev":
"35d1881dac3470d2ed891feae0c1cfcf30025a0b"}

[commit-bot: I haz the power, 2017-04-05 17:29:13]

Description was changed from

==========
[subresource_filter] Replace KMP by std::search.

This CL replaces Knuth-Morris-Pratt algorithm in IndexedRuleset with a naive
string searching algorithm, i.e. base::StringPiece::find/std::search.

This reduces the size of the IndexedRuleset by 500+ kB, because currently that
much space is needed to store failure functions for all the (sub-)patterns.

This also improves performance of IndexedRuleset by 40%, as measured by
stress-testing. This is explained as follows:
  * The subresource_filter's patterns are inherently simple. In the worst
    case of a URL the matching will make 4-5 comparisons per character.
  * The real world URLs are usually not worst-case, and the real average number
    drops down to 1-2 comparisons per character.

BUG=708458
==========

to

==========
[subresource_filter] Replace KMP by std::search.

This CL replaces Knuth-Morris-Pratt algorithm in IndexedRuleset with a naive
string searching algorithm, i.e. base::StringPiece::find/std::search.

This reduces the size of the IndexedRuleset by 500+ kB, because currently that
much space is needed to store failure functions for all the (sub-)patterns.

This also improves performance of IndexedRuleset by 40%, as measured by
stress-testing. This is explained as follows:
  * The subresource_filter's patterns are inherently simple. In the worst
    case of a URL the matching will make 4-5 comparisons per character.
  * The real world URLs are usually not worst-case, and the real average number
    drops down to 1-2 comparisons per character.

BUG=708458

Review-Url: https://codereview.chromium.org/2793993002
Cr-Commit-Position: refs/heads/master@{#462131}
Committed:
https://chromium.googlesource.com/chromium/src/+/35d1881dac3470d2ed891feae0c1...
==========

[commit-bot: I haz the power, 2017-04-05 17:29:14]

Committed patchset #8 (id:160001) as
https://chromium.googlesource.com/chromium/src/+/35d1881dac3470d2ed891feae0c1...