Speed improvements to SubstringSetMatcher

Speed improvements to SubstringSetMatcher

The main one is coputing the Aho-Corasick tree size in advance.

Also contained are code clean-ups and minor optimisations, like removing HasEdge/GetEdge sequences, or adding const to aid compiler optimisations.

This was tested on a benchmark adding 20k+ patterns. It showed a reduction of the running time by 30%.

BUG=236368
Committed: https://src.chromium.org/viewvc/chrome?view=rev&revision=198803

[vabr (Chromium), 2013-05-03 20:37:26]

Hi Dominic,

This is what I have so far.

I had a bit of trouble with my benchmark. Maybe you remember that I repeat the
including of the 20k+ rules 100 times. The issue is that if I don't, I get
different comparison. In particular, when I only did 1 iteration (but still 20k+
rules), reserving the size of |tree_| saved 30% of running time, whereas the
resizing did not help (it was actually slower). For the 100 iterations the
result was opposite, and I'm not sure why.

For the 1-iteration version, the original code executed in about 100ms (+-5ms),
and the patched code in about 70ms (+-5ms).

This CL also involves some other changes, and should contain the equivalent of
your https://codereview.chromium.org/14856016/.

Please feel free to take a look.

I think that I need to design a more reliable benchmark, and test this change
against original before committing.

Thanks,
Vaclav

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
File extensions/common/matcher/substring_set_matcher.cc (right):

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:195: const unsigned& leads_to
= e->second;
I know this is uncommon. However, this method is a hot spot, and in my benchmark
I noticed the speed improved by about 1% when I switched to this (this includes
the similar changes below). My guess, backed by looking at a disassembly of a
toy example, is that the compiler treats leads_to as a synonym for e->second,
having the same effect as me defining:
#define leads_to (e->second)
In particular, I don't think any pointers are created behind the scenes, at
least in release builds.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
File extensions/common/matcher/substring_set_matcher.h (right):

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.h:84: typedef std::map<char,
unsigned> Edges;
The Chromium style guide explicitly says that unsigned numbers should be used
for vector indices.

[battre, 2013-05-03 21:59:12]

For a single iteration, your CPU is probably still in throttled state. Given
that this is triggered at browser start time, I would assume that the CPU is
unthrottled.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
File extensions/common/matcher/substring_set_matcher.cc (right):

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:24: unsigned TreeSize(const
std::vector<const StringPattern*>& patterns) {
This should be size_t; also in all other places.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:38: const std::string& last_s
= (*last)->pattern();
what does "_s" stand for? Can you pick a name without abbreviation?
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Genera...

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:166: while (i != text.end()
&&
text is immutable. Should we have a const std::string::const_iterator text_end?

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:195: const unsigned& leads_to
= e->second;
On 2013/05/03 20:37:27, vabr (Chromium) wrote:
> I know this is uncommon. However, this method is a hot spot, and in my
benchmark
> I noticed the speed improved by about 1% when I switched to this (this
includes
> the similar changes below). My guess, backed by looking at a disassembly of a
> toy example, is that the compiler treats leads_to as a synonym for e->second,
> having the same effect as me defining:
> #define leads_to (e->second)
> In particular, I don't think any pointers are created behind the scenes, at
> least in release builds.

Have you checked what happens if you used "const int leads_to"?

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
File extensions/common/matcher/substring_set_matcher.h (right):

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.h:84: typedef std::map<char,
unsigned> Edges;
On 2013/05/03 20:37:27, vabr (Chromium) wrote:
> The Chromium style guide explicitly says that unsigned numbers should be used
> for vector indices.

I think this should be size_t though.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.h:87: static const unsigned
kInvalidIndex = std::numeric_limits<unsigned>::max();
I think this does not compile on Windows.

How about renaming this to kNoSuchEdge?

[vabr (Chromium), 2013-05-05 23:36:49]

Hi Dominic,

Thanks for your review.

I revised my benchmark, and decided to use just one pass per unit-test, but run
the test repeatedly by using --gtest_repeat=20. That should help with the CPU
throttling, right?

With this benchmark, the optimisations here led to roughly 61% of the original
running time (i.e. 39% decrease).

I have another change in progress, where I try to spare duplicate traversing of
the tree along shared prefixes of two consecutive patterns. I have a bug in that
representation, but I'll let you know once I fix that, and see whether that
saved some more time.

Please take a look at how I addressed your comments in the current state.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
File extensions/common/matcher/substring_set_matcher.cc (right):

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:24: unsigned TreeSize(const
std::vector<const StringPattern*>& patterns) {
On 2013/05/03 21:59:12, battre wrote:
> This should be size_t; also in all other places.

On my machine, size_t is 8 bytes, unsigned is only 4 bytes. This causes a ~1%
slowdown in my benchmark, so I deliberately chose unsigned over size_t.
4 bytes should be enough to capture possible tree sizes, and I don't think
unsigned is ever less than 4 bytes on supported architectures.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:38: const std::string& last_s
= (*last)->pattern();
On 2013/05/03 21:59:12, battre wrote:
> what does "_s" stand for? Can you pick a name without abbreviation?
>
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml?showone=Genera...

Done.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:166: while (i != text.end()
&&
On 2013/05/03 21:59:12, battre wrote:
> text is immutable. Should we have a const std::string::const_iterator
text_end?

It does not seem to make a difference performance-wise, but I changed it as you
suggest.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.cc:195: const unsigned& leads_to
= e->second;
On 2013/05/03 21:59:12, battre wrote:
> On 2013/05/03 20:37:27, vabr (Chromium) wrote:
> > I know this is uncommon. However, this method is a hot spot, and in my
> benchmark
> > I noticed the speed improved by about 1% when I switched to this (this
> includes
> > the similar changes below). My guess, backed by looking at a disassembly of
a
> > toy example, is that the compiler treats leads_to as a synonym for
e->second,
> > having the same effect as me defining:
> > #define leads_to (e->second)
> > In particular, I don't think any pointers are created behind the scenes, at
> > least in release builds.
> 
> Have you checked what happens if you used "const int leads_to"?

Are you asking about removing the reference, or moving from unsigned to int?

As for "const unsigned" instead of "const unsigned&", removing the "&" in the
for-cycle below (lines 205 and 206) caused a 1% slowdown in my benchmark. On
line 195 I don't care, as that cycle does not run as often, but I guess having
no & on line 195 and having & on line 206 could be confusing.

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
File extensions/common/matcher/substring_set_matcher.h (right):

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.h:84: typedef std::map<char,
unsigned> Edges;
On 2013/05/03 21:59:12, battre wrote:
> On 2013/05/03 20:37:27, vabr (Chromium) wrote:
> > The Chromium style guide explicitly says that unsigned numbers should be
used
> > for vector indices.
> 
> I think this should be size_t though.

I went with unsigned for performance reasons (please see my other comment).

https://codereview.chromium.org/14780003/diff/2001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.h:87: static const unsigned
kInvalidIndex = std::numeric_limits<unsigned>::max();
On 2013/05/03 21:59:12, battre wrote:
> I think this does not compile on Windows.
> 
> How about renaming this to kNoSuchEdge?

Done.

https://codereview.chromium.org/14780003/diff/9001/extensions/common/matcher/...
File extensions/common/matcher/substring_set_matcher.h (right):

https://codereview.chromium.org/14780003/diff/9001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.h:118: typedef std::vector<const
StringPattern*> SubstringPatternVector;
While adding the new typedef I also moved this according to
http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml#Declaration_Order

https://codereview.chromium.org/14780003/diff/9001/extensions/common/matcher/...
extensions/common/matcher/substring_set_matcher.h:132: SubstringPatternVector
sorted_patterns_;
I guess once I create the vector, it might be easier to use it also for
iterating over all rules, where I don't need the map. I guess we could also get
rid of the map, re-creating it locally in the register&unregister method, but I
don't think this is performance relevant, rather for memory.

[vabr (Chromium), 2013-05-06 08:44:12]

Hi Dominic,
I added the patch set which spares some traversing of tree_ for shared prefixes
of consecutive patterns.
The speed-up is not serious for the patterns I have (about 1%), but helps a lot
if there are duplicated patterns.

I'm happy to talk about the changes in front of a whiteboard or paper.

Thanks,
Vaclav

[battre, 2013-05-06 14:37:03]

Let's discuss this at the whiteboard. I am concerned that the additional
complexity and memory consumption is not worth 1% of performance improvements.

Can you replace unsigned with uint32_t?

Best regards,
Dominic

[vabr (Chromium), 2013-05-07 08:31:11]

On 2013/05/06 14:37:03, battre wrote:
> Let's discuss this at the whiteboard. I am concerned that the additional
> complexity and memory consumption is not worth 1% of performance improvements.
Sure, once you have time, just let me know.
> 
> Can you replace unsigned with uint32_t?
Done.

Thanks,
Vaclav
> 
> Best regards,
> Dominic

[vabr (Chromium), 2013-05-07 12:49:27]

Hi Dominic,

PTAL.

Vaclav

For the record:
Offline, Dominic and me agreed that the speed-up from patch set 3 is
questionable, and the down-side would be both increased code complexity, and
storage demands (on the order of MBs for my benchmark). So I reverted that
change.

[battre, 2013-05-07 14:30:03]

one last thing

https://codereview.chromium.org/14780003/diff/15002/extensions/common/matcher...
File extensions/common/matcher/substring_set_matcher.cc (right):

https://codereview.chromium.org/14780003/diff/15002/extensions/common/matcher...
extensions/common/matcher/substring_set_matcher.cc:94:
sorted_patterns_.resize(patterns_.size());
I think if you use it this way, sorted_patterns should be a local variable that
is passed to RebuildAhoCorasickTree. Otherwise we keep the memory allocated even
though we don't need it.

[vabr (Chromium), 2013-05-07 14:59:16]

Thanks, Dominic.

PTAL.

Vaclav

https://codereview.chromium.org/14780003/diff/15002/extensions/common/matcher...
File extensions/common/matcher/substring_set_matcher.cc (right):

https://codereview.chromium.org/14780003/diff/15002/extensions/common/matcher...
extensions/common/matcher/substring_set_matcher.cc:94:
sorted_patterns_.resize(patterns_.size());
On 2013/05/07 14:30:03, battre wrote:
> I think if you use it this way, sorted_patterns should be a local variable
that
> is passed to RebuildAhoCorasickTree. Otherwise we keep the memory allocated
even
> though we don't need it.

Done.

Originally I hoped to replace |patterns_| which could save the copying from a
map to vector. That would be possible with efficient binary sorting on the
vector, if that vector would be sorted by id, not by the pattern string. If we
find ourselves in a need to squeeze even more out of the SubstringSetMatcher, we
can revisit this, but currently there are slower parts in AddRules I'm
targeting.

[battre, 2013-05-07 15:14:24]

lgtm

[commit-bot: I haz the power, 2013-05-07 15:23:47]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/vabr@chromium.org/14780003/41003

[commit-bot: I haz the power, 2013-05-07 21:41:36]

Change committed as 198803