NOT FOR LANDING: Autofill regexp benchmark

NOT FOR LANDING: Autofill regexp benchmark

This CL contains a patch with a benchmark for a discussion about changing the regexp library in autofill for performance reasons.

COMMIT=False

CC=isherman@chromium.org
BUG=None

[vabr (Chromium), 2015-03-23 12:51:06]

vabr@chromium.org changed reviewers:
+ isherman@chromium.org

[vabr (Chromium), 2015-03-23 12:51:06]

NOTE: This is not a review request, I do not intend to land this.

Hi Ilya,

Following up on your recent comment [1] I put together a benchmark to compare
ICU and RE2. The benchmark is just benchmark.cc here, the rest is so that you
can easily run it yourself on top of a Chromium checkout.

The results are pretty much in favour of RE2, which seems to beat ICU both in
the matching times (with compiled matchers), and compilation times. Sample logs
from my machine say that matching of 7 different snippets against 3 different
patterns, repeated 10000 times took 660452 microseconds with ICU, while only
21180 microseconds with RE2 (yes, that is 30 times less). Compilation of 3
different patterns, repeated 10000 times took 1312459 microseconds with ICU and
only 877126 microseconds with RE2.

Without precompiling, RE2 are still slow, of course (10x slower than the
precompiled ICU).

I have not studied yet how RE2 handles Unicode, but I suspect it takes in UTF8
(as opposed to UTF16 of ICU).

For the benchmark I randomly selected 3 patterns from the autofill code, and
provided 7 short snippets. I did not check the actual correctness of the
results. :) If you think the benchmark is flawed, please suggest improvements.

Otherwise, what do you think? Seems like switching to RE2 could be beneficial?
If so, I'm happy to have a look.

Cheers,
Vaclav

[1]
https://codereview.chromium.org/1014683006/diff/140001/components/autofill/co...

[vabr (Chromium), 2015-03-23 13:18:53]

> The results are pretty much in favour of RE2, which seems to beat ICU both in
> the matching times (with compiled matchers), and compilation times. Sample
logs
> from my machine say that matching of 7 different snippets against 3 different
> patterns, repeated 10000 times took 660452 microseconds with ICU, while only
> 21180 microseconds with RE2 (yes, that is 30 times less). Compilation of 3
> different patterns, repeated 10000 times took 1312459 microseconds with ICU
and
> only 877126 microseconds with RE2.

I forgot to say that this was tested in Release build, on my Z620.

[Ilya Sherman, 2015-03-24 00:36:58]

Thanks for running this benchmark!  I think that back when we looked into this
before, there wasn't a way to precompile RE2 patterns, which was almost
certainly the cause of the slowdown.  Seems like it would be a win to switch to
RE2, keeping the same precompilation that we do for ICU.

IIRC, the other place that we use ICU is in libphonenumber.  It would be
interesting to re-run the benchmark with the patterns used there, and phone
number-like strings as inputs.  libphonenumber uses some really absurdly large
regexes, which I think RE2 used to have trouble with.  But, if RE2 is a win
there too, then maybe we can move all of the autofill code over to using RE2.  I
think we could even remove the ICU dependency from libphonenumber, which the
maintainers of that library would probably appreciate =)