15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright 2006-2008 The RE2 Authors.  All Rights Reserved.
25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style
35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// license that can be found in the LICENSE file.
45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmarks for regular expression implementations.
65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/test.h"
85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "re2/prog.h"
95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "re2/re2.h"
105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "re2/regexp.h"
115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/pcre.h"
125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "util/benchmark.h"
135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace re2 {
155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Test();
165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MemoryUsage();
175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace re2
185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef testing::MallocCounter MallocCounter;
205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace re2 {
225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Test() {
245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Regexp* re = Regexp::Parse("(\\d+)-(\\d+)-(\\d+)", Regexp::LikePerl, NULL);
255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(re);
265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Prog* prog = re->CompileToProg(0);
275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(prog);
285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(prog->IsOnePass());
295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const char* text = "650-253-0001";
305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StringPiece sp[4];
315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(prog->SearchOnePass(text, text, Prog::kAnchored, Prog::kFullMatch, sp, 4));
325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_EQ(sp[0], "650-253-0001");
335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_EQ(sp[1], "650");
345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_EQ(sp[2], "253");
355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_EQ(sp[3], "0001");
365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  delete prog;
375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  re->Decref();
385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  LOG(INFO) << "test passed\n";
395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MemoryUsage() {
425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const char* regexp = "(\\d+)-(\\d+)-(\\d+)";
435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const char* text = "650-253-0001";
445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    MallocCounter mc(MallocCounter::THIS_THREAD_ONLY);
465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // Can't pass mc.HeapGrowth() and mc.PeakHeapGrowth() to LOG(INFO) directly,
495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    // because LOG(INFO) might do a big allocation before they get evaluated.
505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "Regexp: %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    mc.Reset();
525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Prog* prog = re->CompileToProg(0);
545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog);
555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog->IsOnePass());
565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "Prog:   %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    mc.Reset();
585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    StringPiece sp[4];
605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog->SearchOnePass(text, text, Prog::kAnchored, Prog::kFullMatch, sp, 4));
615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "Search: %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete prog;
635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    MallocCounter mc(MallocCounter::THIS_THREAD_ONLY);
685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    PCRE re(regexp, PCRE::UTF8);
705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "RE:     %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    PCRE::FullMatch(text, re);
725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "RE:     %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    MallocCounter mc(MallocCounter::THIS_THREAD_ONLY);
775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    PCRE* re = new PCRE(regexp, PCRE::UTF8);
795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "PCRE*:  %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    PCRE::FullMatch(text, *re);
815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "PCRE*:  %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete re;
835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  {
865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    MallocCounter mc(MallocCounter::THIS_THREAD_ONLY);
875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    RE2 re(regexp);
895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "RE2:    %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    RE2::FullMatch(text, re);
915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    fprintf(stderr, "RE2:    %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  fprintf(stderr, "sizeof: PCRE=%d RE2=%d Prog=%d Inst=%d\n",
955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          static_cast<int>(sizeof(PCRE)),
965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          static_cast<int>(sizeof(RE2)),
975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          static_cast<int>(sizeof(Prog)),
985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          static_cast<int>(sizeof(Prog::Inst)));
995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Regular expression implementation wrappers.
1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Defined at bottom of file, but they are repetitive
1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and not interesting.
1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef void SearchImpl(int iters, const char* regexp, const StringPiece& text,
1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             Prog::Anchor anchor, bool expect_match);
1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)SearchImpl SearchDFA, SearchNFA, SearchOnePass, SearchBitState,
1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)           SearchPCRE, SearchRE2,
1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)           SearchCachedDFA, SearchCachedNFA, SearchCachedOnePass, SearchCachedBitState,
1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)           SearchCachedPCRE, SearchCachedRE2;
1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)typedef void ParseImpl(int iters, const char* regexp, const StringPiece& text);
1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ParseImpl Parse1NFA, Parse1OnePass, Parse1BitState,
1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse1PCRE, Parse1RE2,
1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse1Backtrack,
1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse1CachedNFA, Parse1CachedOnePass, Parse1CachedBitState,
1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse1CachedPCRE, Parse1CachedRE2,
1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse1CachedBacktrack;
1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ParseImpl Parse3NFA, Parse3OnePass, Parse3BitState,
1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse3PCRE, Parse3RE2,
1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse3Backtrack,
1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse3CachedNFA, Parse3CachedOnePass, Parse3CachedBitState,
1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse3CachedPCRE, Parse3CachedRE2,
1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)          Parse3CachedBacktrack;
1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ParseImpl SearchParse2CachedPCRE, SearchParse2CachedRE2;
1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)ParseImpl SearchParse1CachedPCRE, SearchParse1CachedRE2;
1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: failed search for regexp in random text.
1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Generate random text that won't contain the search string,
1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// to test worst-case search behavior.
1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void MakeText(string* text, int nbytes) {
1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  text->resize(nbytes);
1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  srand(0);
1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < nbytes; i++) {
1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (!rand()%30)
1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      (*text)[i] = '\n';
1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    else
1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      (*text)[i] = rand()%(0x7E + 1 - 0x20)+0x20;
1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Makes text of size nbytes, then calls run to search
1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the text for regexp iters times.
1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search(int iters, int nbytes, const char* regexp, SearchImpl* search) {
1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StopBenchmarkTiming();
1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s;
1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MakeText(&s, nbytes);
1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StartBenchmarkTiming();
1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  search(iters, regexp, s, Prog::kUnanchored, false);
1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// These two are easy because they start with an A,
1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// giving the search loop something to memchr for.
1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define EASY0      "ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define EASY1      "A[AB]B[BC]C[CD]D[DE]E[EF]F[FG]G[GH]H[HI]I[IJ]J$"
1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is a little harder, since it starts with a character class
1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// and thus can't be memchr'ed.  Could look for ABC and work backward,
1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// but no one does that.
1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MEDIUM     "[XYZ]ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This is a fair amount harder, because of the leading [ -~]*.
1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// A bad backtracking implementation will take O(text^2) time to
1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// figure out there's no match.
1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define HARD       "[ -~]*ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This stresses engines that are trying to track parentheses.
1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define PARENS     "([ -~])*(A)(B)(C)(D)(E)(F)(G)(H)(I)(J)(K)(L)(M)" \
1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                   "(N)(O)(P)(Q)(R)(S)(T)(U)(V)(W)(X)(Y)(Z)$"
1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Easy0_CachedDFA(int i, int n)     { Search(i, n, EASY0, SearchCachedDFA); }
1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Easy0_CachedNFA(int i, int n)     { Search(i, n, EASY0, SearchCachedNFA); }
1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Easy0_CachedPCRE(int i, int n)    { Search(i, n, EASY0, SearchCachedPCRE); }
1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Easy0_CachedRE2(int i, int n)     { Search(i, n, EASY0, SearchCachedRE2); }
1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Easy0_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Easy0_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Easy0_CachedPCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Easy0_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Easy1_CachedDFA(int i, int n)     { Search(i, n, EASY1, SearchCachedDFA); }
1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Easy1_CachedNFA(int i, int n)     { Search(i, n, EASY1, SearchCachedNFA); }
1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Easy1_CachedPCRE(int i, int n)    { Search(i, n, EASY1, SearchCachedPCRE); }
1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Easy1_CachedRE2(int i, int n)     { Search(i, n, EASY1, SearchCachedRE2); }
1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Easy1_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Easy1_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Easy1_CachedPCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Easy1_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Medium_CachedDFA(int i, int n)     { Search(i, n, MEDIUM, SearchCachedDFA); }
2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Medium_CachedNFA(int i, int n)     { Search(i, n, MEDIUM, SearchCachedNFA); }
2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Medium_CachedPCRE(int i, int n)    { Search(i, n, MEDIUM, SearchCachedPCRE); }
2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Medium_CachedRE2(int i, int n)     { Search(i, n, MEDIUM, SearchCachedRE2); }
2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Medium_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Medium_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Medium_CachedPCRE,    8, 256<<10)->ThreadRange(1, NumCPUs());
2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Medium_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Hard_CachedDFA(int i, int n)     { Search(i, n, HARD, SearchCachedDFA); }
2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Hard_CachedNFA(int i, int n)     { Search(i, n, HARD, SearchCachedNFA); }
2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Hard_CachedPCRE(int i, int n)    { Search(i, n, HARD, SearchCachedPCRE); }
2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Hard_CachedRE2(int i, int n)     { Search(i, n, HARD, SearchCachedRE2); }
2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Hard_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Hard_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Hard_CachedPCRE,    8, 4<<10)->ThreadRange(1, NumCPUs());
2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Hard_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Parens_CachedDFA(int i, int n)     { Search(i, n, PARENS, SearchCachedDFA); }
2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Parens_CachedNFA(int i, int n)     { Search(i, n, PARENS, SearchCachedNFA); }
2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Parens_CachedPCRE(int i, int n)    { Search(i, n, PARENS, SearchCachedPCRE); }
2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Parens_CachedRE2(int i, int n)     { Search(i, n, PARENS, SearchCachedRE2); }
2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Parens_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Parens_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Parens_CachedPCRE,    8, 8)->ThreadRange(1, NumCPUs());
2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Parens_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchBigFixed(int iters, int nbytes, SearchImpl* search) {
2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StopBenchmarkTiming();
2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s;
2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s.append(nbytes/2, 'x');
2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string regexp = "^" + s + ".*$";
2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string t;
2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MakeText(&t, nbytes/2);
2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s += t;
2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StartBenchmarkTiming();
2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  search(iters, regexp.c_str(), s, Prog::kUnanchored, true);
2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_BigFixed_CachedDFA(int i, int n)     { SearchBigFixed(i, n, SearchCachedDFA); }
2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_BigFixed_CachedNFA(int i, int n)     { SearchBigFixed(i, n, SearchCachedNFA); }
2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_BigFixed_CachedPCRE(int i, int n)    { SearchBigFixed(i, n, SearchCachedPCRE); }
2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_BigFixed_CachedRE2(int i, int n)     { SearchBigFixed(i, n, SearchCachedRE2); }
2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_BigFixed_CachedDFA,     8, 1<<20)->ThreadRange(1, NumCPUs());
2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_BigFixed_CachedNFA,     8, 32<<10)->ThreadRange(1, NumCPUs());
2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_BigFixed_CachedPCRE,    8, 32<<10)->ThreadRange(1, NumCPUs());
2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_BigFixed_CachedRE2,     8, 1<<20)->ThreadRange(1, NumCPUs());
2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: FindAndConsume
2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void FindAndConsume(int iters, int nbytes) {
2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StopBenchmarkTiming();
2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s;
2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MakeText(&s, nbytes);
2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s.append("Hello World");
2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StartBenchmarkTiming();
2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  RE2 re("((Hello World))");
2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    StringPiece t = s;
2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    StringPiece u;
2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(RE2::FindAndConsume(&t, re, &u));
2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(u, "Hello World");
2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(FindAndConsume, 8, 16<<20)->ThreadRange(1, NumCPUs());
2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: successful anchored search.
2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchSuccess(int iters, int nbytes, const char* regexp, SearchImpl* search) {
2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s;
2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MakeText(&s, nbytes);
2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  search(iters, regexp, s, Prog::kAnchored, true);
2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Unambiguous search (RE2 can use OnePass).
2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success_DFA(int i, int n)     { SearchSuccess(i, n, ".*$", SearchDFA); }
2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success_OnePass(int i, int n) { SearchSuccess(i, n, ".*$", SearchOnePass); }
2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success_PCRE(int i, int n)    { SearchSuccess(i, n, ".*$", SearchPCRE); }
2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success_RE2(int i, int n)     { SearchSuccess(i, n, ".*$", SearchRE2); }
3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success_DFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success_PCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success_RE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success_OnePass, 8, 2<<20)->ThreadRange(1, NumCPUs());
3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success_CachedDFA(int i, int n)     { SearchSuccess(i, n, ".*$", SearchCachedDFA); }
3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success_CachedOnePass(int i, int n) { SearchSuccess(i, n, ".*$", SearchCachedOnePass); }
3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success_CachedPCRE(int i, int n)    { SearchSuccess(i, n, ".*$", SearchCachedPCRE); }
3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success_CachedRE2(int i, int n)     { SearchSuccess(i, n, ".*$", SearchCachedRE2); }
3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success_CachedPCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success_CachedOnePass, 8, 2<<20)->ThreadRange(1, NumCPUs());
3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Ambiguous search (RE2 cannot use OnePass).
3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success1_DFA(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchDFA); }
3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success1_PCRE(int i, int n)    { SearchSuccess(i, n, ".*.$", SearchPCRE); }
3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success1_RE2(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchRE2); }
3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success1_BitState(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchBitState); }
3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success1_DFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success1_PCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success1_RE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success1_BitState, 8, 2<<20)->ThreadRange(1, NumCPUs());
3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success1_Cached_DFA(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchCachedDFA); }
3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success1_Cached_PCRE(int i, int n)    { SearchSuccess(i, n, ".*.$", SearchCachedPCRE); }
3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Success1_Cached_RE2(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchCachedRE2); }
3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success1_Cached_DFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success1_Cached_PCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(Search_Success1_Cached_RE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: use regexp to find phone number.
3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchDigits(int iters, SearchImpl* search) {
3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  const char *text = "650-253-0001";
3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int len = strlen(text);
3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  search(iters, "([0-9]+)-([0-9]+)-([0-9]+)",
3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)         StringPiece(text, len), Prog::kAnchored, true);
3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkItemsProcessed(iters);
3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Digits_DFA(int i)         { SearchDigits(i, SearchDFA); }
3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Digits_NFA(int i)         { SearchDigits(i, SearchNFA); }
3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Digits_OnePass(int i)     { SearchDigits(i, SearchOnePass); }
3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Digits_PCRE(int i)        { SearchDigits(i, SearchPCRE); }
3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Digits_RE2(int i)         { SearchDigits(i, SearchRE2); }
3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Search_Digits_BitState(int i)         { SearchDigits(i, SearchBitState); }
3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Search_Digits_DFA)->ThreadRange(1, NumCPUs());
3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Search_Digits_NFA)->ThreadRange(1, NumCPUs());
3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Search_Digits_OnePass)->ThreadRange(1, NumCPUs());
3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Search_Digits_PCRE)->ThreadRange(1, NumCPUs());
3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Search_Digits_RE2)->ThreadRange(1, NumCPUs());
3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Search_Digits_BitState)->ThreadRange(1, NumCPUs());
3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: use regexp to parse digit fields in phone number.
3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse3Digits(int iters,
3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)               void (*parse3)(int, const char*, const StringPiece&)) {
3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  parse3(iters, "([0-9]+)-([0-9]+)-([0-9]+)", "650-253-0001");
3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkItemsProcessed(iters);
3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Digits_NFA(int i)         { Parse3Digits(i, Parse3NFA); }
3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Digits_OnePass(int i)     { Parse3Digits(i, Parse3OnePass); }
3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Digits_PCRE(int i)        { Parse3Digits(i, Parse3PCRE); }
3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Digits_RE2(int i)         { Parse3Digits(i, Parse3RE2); }
3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Digits_Backtrack(int i)   { Parse3Digits(i, Parse3Backtrack); }
3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Digits_BitState(int i)   { Parse3Digits(i, Parse3BitState); }
3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Digits_NFA)->ThreadRange(1, NumCPUs());
3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Digits_OnePass)->ThreadRange(1, NumCPUs());
3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Digits_PCRE)->ThreadRange(1, NumCPUs());
3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Digits_RE2)->ThreadRange(1, NumCPUs());
3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Digits_Backtrack)->ThreadRange(1, NumCPUs());
3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Digits_BitState)->ThreadRange(1, NumCPUs());
3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigits_NFA(int i)         { Parse3Digits(i, Parse3CachedNFA); }
3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigits_OnePass(int i)     { Parse3Digits(i, Parse3CachedOnePass); }
3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigits_PCRE(int i)        { Parse3Digits(i, Parse3CachedPCRE); }
3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigits_RE2(int i)         { Parse3Digits(i, Parse3CachedRE2); }
4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigits_Backtrack(int i)   { Parse3Digits(i, Parse3CachedBacktrack); }
4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigits_BitState(int i)   { Parse3Digits(i, Parse3CachedBitState); }
4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigits_NFA)->ThreadRange(1, NumCPUs());
4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigits_OnePass)->ThreadRange(1, NumCPUs());
4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigits_PCRE)->ThreadRange(1, NumCPUs());
4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigits_Backtrack)->ThreadRange(1, NumCPUs());
4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigits_RE2)->ThreadRange(1, NumCPUs());
4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigits_BitState)->ThreadRange(1, NumCPUs());
4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse3DigitDs(int iters,
4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)               void (*parse3)(int, const char*, const StringPiece&)) {
4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  parse3(iters, "(\\d+)-(\\d+)-(\\d+)", "650-253-0001");
4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkItemsProcessed(iters);
4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_DigitDs_NFA(int i)         { Parse3DigitDs(i, Parse3NFA); }
4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_DigitDs_OnePass(int i)     { Parse3DigitDs(i, Parse3OnePass); }
4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_DigitDs_PCRE(int i)        { Parse3DigitDs(i, Parse3PCRE); }
4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_DigitDs_RE2(int i)         { Parse3DigitDs(i, Parse3RE2); }
4235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_DigitDs_Backtrack(int i)   { Parse3DigitDs(i, Parse3CachedBacktrack); }
4245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_DigitDs_BitState(int i)   { Parse3DigitDs(i, Parse3CachedBitState); }
4255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_DigitDs_NFA)->ThreadRange(1, NumCPUs());
4275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_DigitDs_OnePass)->ThreadRange(1, NumCPUs());
4285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
4295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_DigitDs_PCRE)->ThreadRange(1, NumCPUs());
4305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
4315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_DigitDs_RE2)->ThreadRange(1, NumCPUs());
4325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_DigitDs_Backtrack)->ThreadRange(1, NumCPUs());
4335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_DigitDs_BitState)->ThreadRange(1, NumCPUs());
4345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigitDs_NFA(int i)         { Parse3DigitDs(i, Parse3CachedNFA); }
4365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigitDs_OnePass(int i)     { Parse3DigitDs(i, Parse3CachedOnePass); }
4375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigitDs_PCRE(int i)        { Parse3DigitDs(i, Parse3CachedPCRE); }
4385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigitDs_RE2(int i)         { Parse3DigitDs(i, Parse3CachedRE2); }
4395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigitDs_Backtrack(int i)   { Parse3DigitDs(i, Parse3CachedBacktrack); }
4405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedDigitDs_BitState(int i)   { Parse3DigitDs(i, Parse3CachedBitState); }
4415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigitDs_NFA)->ThreadRange(1, NumCPUs());
4435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigitDs_OnePass)->ThreadRange(1, NumCPUs());
4445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
4455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigitDs_PCRE)->ThreadRange(1, NumCPUs());
4465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
4475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigitDs_Backtrack)->ThreadRange(1, NumCPUs());
4485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigitDs_RE2)->ThreadRange(1, NumCPUs());
4495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedDigitDs_BitState)->ThreadRange(1, NumCPUs());
4505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: splitting off leading number field.
4525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse1Split(int iters,
4545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)              void (*parse1)(int, const char*, const StringPiece&)) {
4555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
4565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  parse1(iters, "[0-9]+-(.*)", "650-253-0001");
4575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkItemsProcessed(iters);
4585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
4595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Split_NFA(int i)         { Parse1Split(i, Parse1NFA); }
4615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Split_OnePass(int i)     { Parse1Split(i, Parse1OnePass); }
4625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Split_PCRE(int i)        { Parse1Split(i, Parse1PCRE); }
4635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Split_RE2(int i)         { Parse1Split(i, Parse1RE2); }
4645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_Split_BitState(int i)         { Parse1Split(i, Parse1BitState); }
4655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Split_NFA)->ThreadRange(1, NumCPUs());
4675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Split_OnePass)->ThreadRange(1, NumCPUs());
4685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
4695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Split_PCRE)->ThreadRange(1, NumCPUs());
4705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
4715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Split_RE2)->ThreadRange(1, NumCPUs());
4725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_Split_BitState)->ThreadRange(1, NumCPUs());
4735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplit_NFA(int i)         { Parse1Split(i, Parse1CachedNFA); }
4755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplit_OnePass(int i)     { Parse1Split(i, Parse1CachedOnePass); }
4765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplit_PCRE(int i)        { Parse1Split(i, Parse1CachedPCRE); }
4775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplit_RE2(int i)         { Parse1Split(i, Parse1CachedRE2); }
4785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplit_BitState(int i)         { Parse1Split(i, Parse1CachedBitState); }
4795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplit_NFA)->ThreadRange(1, NumCPUs());
4815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplit_OnePass)->ThreadRange(1, NumCPUs());
4825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
4835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplit_PCRE)->ThreadRange(1, NumCPUs());
4845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
4855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplit_RE2)->ThreadRange(1, NumCPUs());
4865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplit_BitState)->ThreadRange(1, NumCPUs());
4875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: splitting off leading number field but harder (ambiguous regexp).
4895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse1SplitHard(int iters,
4915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                  void (*run)(int, const char*, const StringPiece&)) {
4925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
4935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  run(iters, "[0-9]+.(.*)", "650-253-0001");
4945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkItemsProcessed(iters);
4955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
4965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
4975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_SplitHard_NFA(int i)         { Parse1SplitHard(i, Parse1NFA); }
4985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_SplitHard_PCRE(int i)        { Parse1SplitHard(i, Parse1PCRE); }
4995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_SplitHard_RE2(int i)         { Parse1SplitHard(i, Parse1RE2); }
5005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_SplitHard_BitState(int i)         { Parse1SplitHard(i, Parse1BitState); }
5015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
5035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_SplitHard_PCRE)->ThreadRange(1, NumCPUs());
5045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
5055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_SplitHard_RE2)->ThreadRange(1, NumCPUs());
5065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_SplitHard_BitState)->ThreadRange(1, NumCPUs());
5075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_SplitHard_NFA)->ThreadRange(1, NumCPUs());
5085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitHard_NFA(int i)       { Parse1SplitHard(i, Parse1CachedNFA); }
5105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitHard_PCRE(int i)      { Parse1SplitHard(i, Parse1CachedPCRE); }
5115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitHard_RE2(int i)       { Parse1SplitHard(i, Parse1CachedRE2); }
5125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitHard_BitState(int i)       { Parse1SplitHard(i, Parse1CachedBitState); }
5135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitHard_Backtrack(int i)       { Parse1SplitHard(i, Parse1CachedBacktrack); }
5145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
5165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitHard_PCRE)->ThreadRange(1, NumCPUs());
5175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
5185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitHard_RE2)->ThreadRange(1, NumCPUs());
5195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitHard_BitState)->ThreadRange(1, NumCPUs());
5205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitHard_NFA)->ThreadRange(1, NumCPUs());
5215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitHard_Backtrack)->ThreadRange(1, NumCPUs());
5225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: Parse1SplitHard, big text, small match.
5245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse1SplitBig1(int iters,
5265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                  void (*run)(int, const char*, const StringPiece&)) {
5275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s;
5285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s.append(100000, 'x');
5295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s.append("650-253-0001");
5305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
5315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  run(iters, "[0-9]+.(.*)", s);
5325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkItemsProcessed(iters);
5335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitBig1_PCRE(int i)      { Parse1SplitBig1(i, SearchParse1CachedPCRE); }
5365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitBig1_RE2(int i)       { Parse1SplitBig1(i, SearchParse1CachedRE2); }
5375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
5395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitBig1_PCRE)->ThreadRange(1, NumCPUs());
5405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
5415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitBig1_RE2)->ThreadRange(1, NumCPUs());
5425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: Parse1SplitHard, big text, big match.
5445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse1SplitBig2(int iters,
5465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                  void (*run)(int, const char*, const StringPiece&)) {
5475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s;
5485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s.append("650-253-");
5495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s.append(100000, '0');
5505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
5515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  run(iters, "[0-9]+.(.*)", s);
5525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkItemsProcessed(iters);
5535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitBig2_PCRE(int i)      { Parse1SplitBig2(i, SearchParse1CachedPCRE); }
5565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void Parse_CachedSplitBig2_RE2(int i)       { Parse1SplitBig2(i, SearchParse1CachedRE2); }
5575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
5595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitBig2_PCRE)->ThreadRange(1, NumCPUs());
5605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
5615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(Parse_CachedSplitBig2_RE2)->ThreadRange(1, NumCPUs());
5625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Benchmark: measure time required to parse (but not execute)
5645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a simple regular expression.
5655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ParseRegexp(int iters, const string& regexp) {
5675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
5685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
5695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
5705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
5715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SimplifyRegexp(int iters, const string& regexp) {
5755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
5765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
5775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
5785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* sre = re->Simplify();
5795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(sre);
5805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    sre->Decref();
5815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
5825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void NullWalkRegexp(int iters, const string& regexp) {
5865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
5875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(re);
5885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
5895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->NullWalk();
5905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
5915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  re->Decref();
5925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
5935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
5945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SimplifyCompileRegexp(int iters, const string& regexp) {
5955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
5965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
5975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
5985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* sre = re->Simplify();
5995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(sre);
6005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Prog* prog = sre->CompileToProg(0);
6015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog);
6025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete prog;
6035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    sre->Decref();
6045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
6055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CompileRegexp(int iters, const string& regexp) {
6095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
6105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
6115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
6125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Prog* prog = re->CompileToProg(0);
6135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog);
6145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete prog;
6155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
6165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CompileToProg(int iters, const string& regexp) {
6205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
6215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(re);
6225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
6235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Prog* prog = re->CompileToProg(0);
6245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog);
6255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete prog;
6265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  re->Decref();
6285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CompileByteMap(int iters, const string& regexp) {
6315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
6325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(re);
6335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Prog* prog = re->CompileToProg(0);
6345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(prog);
6355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
6365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    prog->ComputeByteMap();
6375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  delete prog;
6395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  re->Decref();
6405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CompilePCRE(int iters, const string& regexp) {
6435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
6445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    PCRE re(regexp, PCRE::UTF8);
6455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(re.error(), "");
6465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CompileRE2(int iters, const string& regexp) {
6505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
6515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    RE2 re(regexp);
6525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(re.error(), "");
6535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
6545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void RunBuild(int iters, const string& regexp, void (*run)(int, const string&)) {
6575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  run(iters, regexp);
6585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkItemsProcessed(iters);
6595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
6605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}  // namespace re2
6625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DEFINE_string(compile_regexp, "(.*)-(\\d+)-of-(\\d+)", "regexp for compile benchmarks");
6645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace re2 {
6665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_PCRE_Compile(int i)      { RunBuild(i, FLAGS_compile_regexp, CompilePCRE); }
6685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_Regexp_Parse(int i)      { RunBuild(i, FLAGS_compile_regexp, ParseRegexp); }
6695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_Regexp_Simplify(int i)   { RunBuild(i, FLAGS_compile_regexp, SimplifyRegexp); }
6705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_CompileToProg(int i)     { RunBuild(i, FLAGS_compile_regexp, CompileToProg); }
6715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_CompileByteMap(int i)     { RunBuild(i, FLAGS_compile_regexp, CompileByteMap); }
6725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_Regexp_Compile(int i)    { RunBuild(i, FLAGS_compile_regexp, CompileRegexp); }
6735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_Regexp_SimplifyCompile(int i)   { RunBuild(i, FLAGS_compile_regexp, SimplifyCompileRegexp); }
6745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_Regexp_NullWalk(int i)   { RunBuild(i, FLAGS_compile_regexp, NullWalkRegexp); }
6755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void BM_RE2_Compile(int i)       { RunBuild(i, FLAGS_compile_regexp, CompileRE2); }
6765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
6785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_PCRE_Compile)->ThreadRange(1, NumCPUs());
6795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
6805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_Regexp_Parse)->ThreadRange(1, NumCPUs());
6815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_Regexp_Simplify)->ThreadRange(1, NumCPUs());
6825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_CompileToProg)->ThreadRange(1, NumCPUs());
6835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_CompileByteMap)->ThreadRange(1, NumCPUs());
6845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_Regexp_Compile)->ThreadRange(1, NumCPUs());
6855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_Regexp_SimplifyCompile)->ThreadRange(1, NumCPUs());
6865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_Regexp_NullWalk)->ThreadRange(1, NumCPUs());
6875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK(BM_RE2_Compile)->ThreadRange(1, NumCPUs());
6885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
6905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Makes text of size nbytes, then calls run to search
6915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// the text for regexp iters times.
6925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchPhone(int iters, int nbytes, ParseImpl* search) {
6935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StopBenchmarkTiming();
6945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s;
6955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  MakeText(&s, nbytes);
6965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  s.append("(650) 253-0001");
6975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  BenchmarkMemoryUsage();
6985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  StartBenchmarkTiming();
6995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  search(iters, "(\\d{3}-|\\(\\d{3}\\)\\s+)(\\d{3}-\\d{4})", s);
7005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
7015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchPhone_CachedPCRE(int i, int n) {
7045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SearchPhone(i, n, SearchParse2CachedPCRE);
7055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchPhone_CachedRE2(int i, int n) {
7075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SearchPhone(i, n, SearchParse2CachedRE2);
7085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#ifdef USEPCRE
7115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(SearchPhone_CachedPCRE, 8, 16<<20)->ThreadRange(1, NumCPUs());
7125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif
7135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)BENCHMARK_RANGE(SearchPhone_CachedRE2, 8, 16<<20)->ThreadRange(1, NumCPUs());
7145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/*
7165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TODO(rsc): Make this work again.
7175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Generates and returns a string over binary alphabet {0,1} that contains
7195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// all possible binary sequences of length n as subsequences.  The obvious
7205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// brute force method would generate a string of length n * 2^n, but this
7215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// generates a string of length n + 2^n - 1 called a De Bruijn cycle.
7225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// See Knuth, The Art of Computer Programming, Vol 2, Exercise 3.2.2 #17.
7235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static string DeBruijnString(int n) {
7245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_LT(n, 8*sizeof(int));
7255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK_GT(n, 0);
7265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  vector<bool> did(1<<n);
7285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < 1<<n; i++)
7295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    did[i] = false;
7305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s;
7325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < n-1; i++)
7335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    s.append("0");
7345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int bits = 0;
7355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  int mask = (1<<n) - 1;
7365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < (1<<n); i++) {
7375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    bits <<= 1;
7385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    bits &= mask;
7395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (!did[bits|1]) {
7405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      bits |= 1;
7415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      s.append("1");
7425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    } else {
7435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      s.append("0");
7445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    }
7455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(!did[bits]);
7465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    did[bits] = true;
7475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  return s;
7495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CacheFill(int iters, int n, SearchImpl *srch) {
7525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string s = DeBruijnString(n+1);
7535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  string t;
7545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = n+1; i < 20; i++) {
7555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    t = s + s;
7565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    swap(s, t);
7575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
7585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  srch(iters, StringPrintf("0[01]{%d}$", n).c_str(), s,
7595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)       Prog::kUnanchored, true);
7605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*s.size());
7615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
7625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CacheFillPCRE(int i, int n) { CacheFill(i, n, SearchCachedPCRE); }
7645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CacheFillRE2(int i, int n)  { CacheFill(i, n, SearchCachedRE2); }
7655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CacheFillNFA(int i, int n)  { CacheFill(i, n, SearchCachedNFA); }
7665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void CacheFillDFA(int i, int n)  { CacheFill(i, n, SearchCachedDFA); }
7675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// BENCHMARK_WITH_ARG uses __LINE__ to generate distinct identifiers
7695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// for the static BenchmarkRegisterer, which makes it unusable inside
7705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// a macro like DO24 below.  MY_BENCHMARK_WITH_ARG uses the argument a
7715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// to make the identifiers distinct (only possible when 'a' is a simple
7725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// expression like 2, not like 1+1).
7735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define MY_BENCHMARK_WITH_ARG(n, a) \
7745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  bool __benchmark_ ## n ## a =     \
7755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    (new ::testing::Benchmark(#n, NewPermanentCallback(&n)))->ThreadRange(1, NumCPUs());
7765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define DO24(A, B) \
7785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  A(B, 1);    A(B, 2);    A(B, 3);    A(B, 4);    A(B, 5);    A(B, 6);  \
7795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  A(B, 7);    A(B, 8);    A(B, 9);    A(B, 10);   A(B, 11);   A(B, 12); \
7805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  A(B, 13);   A(B, 14);   A(B, 15);   A(B, 16);   A(B, 17);   A(B, 18); \
7815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  A(B, 19);   A(B, 20);   A(B, 21);   A(B, 22);   A(B, 23);   A(B, 24);
7825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DO24(MY_BENCHMARK_WITH_ARG, CacheFillPCRE)
7845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DO24(MY_BENCHMARK_WITH_ARG, CacheFillNFA)
7855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DO24(MY_BENCHMARK_WITH_ARG, CacheFillRE2)
7865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)DO24(MY_BENCHMARK_WITH_ARG, CacheFillDFA)
7875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef DO24
7895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#undef MY_BENCHMARK_WITH_ARG
7905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/
7915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)////////////////////////////////////////////////////////////////////////
7935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)//
7945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Implementation routines.  Sad that there are so many,
7955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// but all the interfaces are slightly different.
7965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
7975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Runs implementation to search for regexp in text, iters times.
7985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Expect_match says whether the regexp should be found.
7995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Anchored says whether to run an anchored search.
8005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchDFA(int iters, const char* regexp, const StringPiece& text,
8025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            Prog::Anchor anchor, bool expect_match) {
8035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
8045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
8065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Prog* prog = re->CompileToProg(0);
8075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog);
8085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    bool failed = false;
8095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(prog->SearchDFA(text, NULL, anchor, Prog::kFirstMatch,
8105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                             NULL, &failed, NULL),
8115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             expect_match);
8125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(!failed);
8135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete prog;
8145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
8155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchNFA(int iters, const char* regexp, const StringPiece& text,
8195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            Prog::Anchor anchor, bool expect_match) {
8205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
8215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
8235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Prog* prog = re->CompileToProg(0);
8245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog);
8255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(prog->SearchNFA(text, NULL, anchor, Prog::kFirstMatch, NULL, 0),
8265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             expect_match);
8275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete prog;
8285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
8295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchOnePass(int iters, const char* regexp, const StringPiece& text,
8335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            Prog::Anchor anchor, bool expect_match) {
8345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
8355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
8375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Prog* prog = re->CompileToProg(0);
8385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog);
8395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog->IsOnePass());
8405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(prog->SearchOnePass(text, text, anchor, Prog::kFirstMatch, NULL, 0),
8415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             expect_match);
8425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete prog;
8435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
8445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchBitState(int iters, const char* regexp, const StringPiece& text,
8485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)            Prog::Anchor anchor, bool expect_match) {
8495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
8505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(re);
8525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    Prog* prog = re->CompileToProg(0);
8535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(prog);
8545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(prog->SearchBitState(text, text, anchor, Prog::kFirstMatch, NULL, 0),
8555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             expect_match);
8565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    delete prog;
8575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    re->Decref();
8585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchPCRE(int iters, const char* regexp, const StringPiece& text,
8625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                Prog::Anchor anchor, bool expect_match) {
8635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
8645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    PCRE re(regexp, PCRE::UTF8);
8655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(re.error(), "");
8665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (anchor == Prog::kAnchored)
8675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_EQ(PCRE::FullMatch(text, re), expect_match);
8685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    else
8695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_EQ(PCRE::PartialMatch(text, re), expect_match);
8705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchRE2(int iters, const char* regexp, const StringPiece& text,
8745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)               Prog::Anchor anchor, bool expect_match) {
8755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
8765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    RE2 re(regexp);
8775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(re.error(), "");
8785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    if (anchor == Prog::kAnchored)
8795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_EQ(RE2::FullMatch(text, re), expect_match);
8805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    else
8815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)      CHECK_EQ(RE2::PartialMatch(text, re), expect_match);
8825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
8835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
8845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// SearchCachedXXX is like SearchXXX but only does the
8865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// regexp parsing and compiling once.  This lets us measure
8875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// search time without the per-regexp overhead.
8885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
8895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchCachedDFA(int iters, const char* regexp, const StringPiece& text,
8905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                     Prog::Anchor anchor, bool expect_match) {
8915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(re);
8935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Prog* prog = re->CompileToProg(1LL<<31);
8945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(prog);
8955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
8965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    bool failed = false;
8975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(prog->SearchDFA(text, NULL, anchor,
8985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                             Prog::kFirstMatch, NULL, &failed, NULL),
8995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             expect_match);
9005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK(!failed);
9015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
9025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  delete prog;
9035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  re->Decref();
9045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchCachedNFA(int iters, const char* regexp, const StringPiece& text,
9075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                     Prog::Anchor anchor, bool expect_match) {
9085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
9095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(re);
9105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Prog* prog = re->CompileToProg(0);
9115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(prog);
9125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++) {
9135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(prog->SearchNFA(text, NULL, anchor, Prog::kFirstMatch, NULL, 0),
9145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             expect_match);
9155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  }
9165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  delete prog;
9175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  re->Decref();
9185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchCachedOnePass(int iters, const char* regexp, const StringPiece& text,
9215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                     Prog::Anchor anchor, bool expect_match) {
9225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
9235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(re);
9245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Prog* prog = re->CompileToProg(0);
9255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(prog);
9265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(prog->IsOnePass());
9275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  for (int i = 0; i < iters; i++)
9285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)    CHECK_EQ(prog->SearchOnePass(text, text, anchor, Prog::kFirstMatch, NULL, 0),
9295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)             expect_match);
9305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  delete prog;
9315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  re->Decref();
9325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}
9335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)
9345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SearchCachedBitState(int iters, const char* regexp, const StringPiece& text,
9355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)                     Prog::Anchor anchor, bool expect_match) {
9365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
9375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  CHECK(re);
9385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)  Pro