10d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Copyright 2006-2008 The RE2 Authors.  All Rights Reserved.
20d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Use of this source code is governed by a BSD-style
30d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// license that can be found in the LICENSE file.
40d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
50d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmarks for regular expression implementations.
60d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
70d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "util/test.h"
80d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "re2/prog.h"
90d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "re2/re2.h"
100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "re2/regexp.h"
110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "util/pcre.h"
120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#include "util/benchmark.h"
130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinnamespace re2 {
150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Test();
160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid MemoryUsage();
170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}  // namespace re2
180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkintypedef testing::MallocCounter MallocCounter;
200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinnamespace re2 {
220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Test() {
240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Regexp* re = Regexp::Parse("(\\d+)-(\\d+)-(\\d+)", Regexp::LikePerl, NULL);
250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(re);
260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Prog* prog = re->CompileToProg(0);
270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(prog);
280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(prog->IsOnePass());
290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  const char* text = "650-253-0001";
300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StringPiece sp[4];
310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(prog->SearchOnePass(text, text, Prog::kAnchored, Prog::kFullMatch, sp, 4));
320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK_EQ(sp[0], "650-253-0001");
330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK_EQ(sp[1], "650");
340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK_EQ(sp[2], "253");
350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK_EQ(sp[3], "0001");
360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  delete prog;
370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  re->Decref();
380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  LOG(INFO) << "test passed\n";
390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid MemoryUsage() {
420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  const char* regexp = "(\\d+)-(\\d+)-(\\d+)";
430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  const char* text = "650-253-0001";
440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  {
450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    MallocCounter mc(MallocCounter::THIS_THREAD_ONLY);
460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    // Can't pass mc.HeapGrowth() and mc.PeakHeapGrowth() to LOG(INFO) directly,
490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    // because LOG(INFO) might do a big allocation before they get evaluated.
500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "Regexp: %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    mc.Reset();
520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Prog* prog = re->CompileToProg(0);
540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog);
550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog->IsOnePass());
560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "Prog:   %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    mc.Reset();
580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    StringPiece sp[4];
600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog->SearchOnePass(text, text, Prog::kAnchored, Prog::kFullMatch, sp, 4));
610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "Search: %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete prog;
630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  {
670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    MallocCounter mc(MallocCounter::THIS_THREAD_ONLY);
680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    PCRE re(regexp, PCRE::UTF8);
700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "RE:     %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    PCRE::FullMatch(text, re);
720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "RE:     %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  {
760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    MallocCounter mc(MallocCounter::THIS_THREAD_ONLY);
770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    PCRE* re = new PCRE(regexp, PCRE::UTF8);
790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "PCRE*:  %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    PCRE::FullMatch(text, *re);
810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "PCRE*:  %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete re;
830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  {
860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    MallocCounter mc(MallocCounter::THIS_THREAD_ONLY);
870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    RE2 re(regexp);
890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "RE2:    %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    RE2::FullMatch(text, re);
910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    fprintf(stderr, "RE2:    %7lld bytes (peak=%lld)\n", mc.HeapGrowth(), mc.PeakHeapGrowth());
920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  fprintf(stderr, "sizeof: PCRE=%d RE2=%d Prog=%d Inst=%d\n",
950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          static_cast<int>(sizeof(PCRE)),
960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          static_cast<int>(sizeof(RE2)),
970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          static_cast<int>(sizeof(Prog)),
980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          static_cast<int>(sizeof(Prog::Inst)));
990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
1000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Regular expression implementation wrappers.
1020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Defined at bottom of file, but they are repetitive
1030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// and not interesting.
1040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkintypedef void SearchImpl(int iters, const char* regexp, const StringPiece& text,
1060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin             Prog::Anchor anchor, bool expect_match);
1070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinSearchImpl SearchDFA, SearchNFA, SearchOnePass, SearchBitState,
1090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin           SearchPCRE, SearchRE2,
1100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin           SearchCachedDFA, SearchCachedNFA, SearchCachedOnePass, SearchCachedBitState,
1110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin           SearchCachedPCRE, SearchCachedRE2;
1120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkintypedef void ParseImpl(int iters, const char* regexp, const StringPiece& text);
1140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinParseImpl Parse1NFA, Parse1OnePass, Parse1BitState,
1160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse1PCRE, Parse1RE2,
1170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse1Backtrack,
1180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse1CachedNFA, Parse1CachedOnePass, Parse1CachedBitState,
1190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse1CachedPCRE, Parse1CachedRE2,
1200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse1CachedBacktrack;
1210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinParseImpl Parse3NFA, Parse3OnePass, Parse3BitState,
1230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse3PCRE, Parse3RE2,
1240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse3Backtrack,
1250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse3CachedNFA, Parse3CachedOnePass, Parse3CachedBitState,
1260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse3CachedPCRE, Parse3CachedRE2,
1270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin          Parse3CachedBacktrack;
1280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinParseImpl SearchParse2CachedPCRE, SearchParse2CachedRE2;
1300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinParseImpl SearchParse1CachedPCRE, SearchParse1CachedRE2;
1320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: failed search for regexp in random text.
1340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Generate random text that won't contain the search string,
1360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// to test worst-case search behavior.
1370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid MakeText(string* text, int nbytes) {
1380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  text->resize(nbytes);
1390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  srand(0);
1400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < nbytes; i++) {
1410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    if (!rand()%30)
1420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      (*text)[i] = '\n';
1430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    else
1440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      (*text)[i] = rand()%(0x7E + 1 - 0x20)+0x20;
1450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
1460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
1470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Makes text of size nbytes, then calls run to search
1490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// the text for regexp iters times.
1500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search(int iters, int nbytes, const char* regexp, SearchImpl* search) {
1510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StopBenchmarkTiming();
1520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s;
1530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  MakeText(&s, nbytes);
1540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
1550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StartBenchmarkTiming();
1560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  search(iters, regexp, s, Prog::kUnanchored, false);
1570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
1580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
1590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// These two are easy because they start with an A,
1610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// giving the search loop something to memchr for.
1620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#define EASY0      "ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
1630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#define EASY1      "A[AB]B[BC]C[CD]D[DE]E[EF]F[FG]G[GH]H[HI]I[IJ]J$"
1640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// This is a little harder, since it starts with a character class
1660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// and thus can't be memchr'ed.  Could look for ABC and work backward,
1670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// but no one does that.
1680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#define MEDIUM     "[XYZ]ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
1690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// This is a fair amount harder, because of the leading [ -~]*.
1710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// A bad backtracking implementation will take O(text^2) time to
1720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// figure out there's no match.
1730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#define HARD       "[ -~]*ABCDEFGHIJKLMNOPQRSTUVWXYZ$"
1740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// This stresses engines that are trying to track parentheses.
1760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#define PARENS     "([ -~])*(A)(B)(C)(D)(E)(F)(G)(H)(I)(J)(K)(L)(M)" \
1770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                   "(N)(O)(P)(Q)(R)(S)(T)(U)(V)(W)(X)(Y)(Z)$"
1780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Easy0_CachedDFA(int i, int n)     { Search(i, n, EASY0, SearchCachedDFA); }
1800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Easy0_CachedNFA(int i, int n)     { Search(i, n, EASY0, SearchCachedNFA); }
1810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Easy0_CachedPCRE(int i, int n)    { Search(i, n, EASY0, SearchCachedPCRE); }
1820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Easy0_CachedRE2(int i, int n)     { Search(i, n, EASY0, SearchCachedRE2); }
1830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Easy0_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
1850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Easy0_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
1860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
1870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Easy0_CachedPCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
1880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
1890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Easy0_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
1900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Easy1_CachedDFA(int i, int n)     { Search(i, n, EASY1, SearchCachedDFA); }
1920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Easy1_CachedNFA(int i, int n)     { Search(i, n, EASY1, SearchCachedNFA); }
1930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Easy1_CachedPCRE(int i, int n)    { Search(i, n, EASY1, SearchCachedPCRE); }
1940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Easy1_CachedRE2(int i, int n)     { Search(i, n, EASY1, SearchCachedRE2); }
1950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
1960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Easy1_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
1970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Easy1_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
1980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
1990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Easy1_CachedPCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
2000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
2010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Easy1_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
2020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Medium_CachedDFA(int i, int n)     { Search(i, n, MEDIUM, SearchCachedDFA); }
2040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Medium_CachedNFA(int i, int n)     { Search(i, n, MEDIUM, SearchCachedNFA); }
2050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Medium_CachedPCRE(int i, int n)    { Search(i, n, MEDIUM, SearchCachedPCRE); }
2060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Medium_CachedRE2(int i, int n)     { Search(i, n, MEDIUM, SearchCachedRE2); }
2070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Medium_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
2090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Medium_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
2100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
2110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Medium_CachedPCRE,    8, 256<<10)->ThreadRange(1, NumCPUs());
2120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
2130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Medium_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
2140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Hard_CachedDFA(int i, int n)     { Search(i, n, HARD, SearchCachedDFA); }
2160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Hard_CachedNFA(int i, int n)     { Search(i, n, HARD, SearchCachedNFA); }
2170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Hard_CachedPCRE(int i, int n)    { Search(i, n, HARD, SearchCachedPCRE); }
2180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Hard_CachedRE2(int i, int n)     { Search(i, n, HARD, SearchCachedRE2); }
2190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Hard_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
2210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Hard_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
2220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
2230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Hard_CachedPCRE,    8, 4<<10)->ThreadRange(1, NumCPUs());
2240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
2250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Hard_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
2260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Parens_CachedDFA(int i, int n)     { Search(i, n, PARENS, SearchCachedDFA); }
2280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Parens_CachedNFA(int i, int n)     { Search(i, n, PARENS, SearchCachedNFA); }
2290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Parens_CachedPCRE(int i, int n)    { Search(i, n, PARENS, SearchCachedPCRE); }
2300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Parens_CachedRE2(int i, int n)     { Search(i, n, PARENS, SearchCachedRE2); }
2310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Parens_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
2330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Parens_CachedNFA,     8, 256<<10)->ThreadRange(1, NumCPUs());
2340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
2350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Parens_CachedPCRE,    8, 8)->ThreadRange(1, NumCPUs());
2360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
2370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Parens_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
2380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchBigFixed(int iters, int nbytes, SearchImpl* search) {
2400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StopBenchmarkTiming();
2410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s;
2420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  s.append(nbytes/2, 'x');
2430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string regexp = "^" + s + ".*$";
2440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string t;
2450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  MakeText(&t, nbytes/2);
2460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  s += t;
2470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
2480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StartBenchmarkTiming();
2490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  search(iters, regexp.c_str(), s, Prog::kUnanchored, true);
2500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
2510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
2520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_BigFixed_CachedDFA(int i, int n)     { SearchBigFixed(i, n, SearchCachedDFA); }
2540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_BigFixed_CachedNFA(int i, int n)     { SearchBigFixed(i, n, SearchCachedNFA); }
2550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_BigFixed_CachedPCRE(int i, int n)    { SearchBigFixed(i, n, SearchCachedPCRE); }
2560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_BigFixed_CachedRE2(int i, int n)     { SearchBigFixed(i, n, SearchCachedRE2); }
2570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_BigFixed_CachedDFA,     8, 1<<20)->ThreadRange(1, NumCPUs());
2590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_BigFixed_CachedNFA,     8, 32<<10)->ThreadRange(1, NumCPUs());
2600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
2610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_BigFixed_CachedPCRE,    8, 32<<10)->ThreadRange(1, NumCPUs());
2620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
2630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_BigFixed_CachedRE2,     8, 1<<20)->ThreadRange(1, NumCPUs());
2640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: FindAndConsume
2660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid FindAndConsume(int iters, int nbytes) {
2670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StopBenchmarkTiming();
2680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s;
2690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  MakeText(&s, nbytes);
2700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  s.append("Hello World");
2710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StartBenchmarkTiming();
2720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  RE2 re("((Hello World))");
2730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
2740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    StringPiece t = s;
2750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    StringPiece u;
2760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(RE2::FindAndConsume(&t, re, &u));
2770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(u, "Hello World");
2780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
2790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
2800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
2810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(FindAndConsume, 8, 16<<20)->ThreadRange(1, NumCPUs());
2830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: successful anchored search.
2850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchSuccess(int iters, int nbytes, const char* regexp, SearchImpl* search) {
2870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s;
2880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  MakeText(&s, nbytes);
2890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
2900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  search(iters, regexp, s, Prog::kAnchored, true);
2910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
2920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
2930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Unambiguous search (RE2 can use OnePass).
2950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
2960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success_DFA(int i, int n)     { SearchSuccess(i, n, ".*$", SearchDFA); }
2970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success_OnePass(int i, int n) { SearchSuccess(i, n, ".*$", SearchOnePass); }
2980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success_PCRE(int i, int n)    { SearchSuccess(i, n, ".*$", SearchPCRE); }
2990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success_RE2(int i, int n)     { SearchSuccess(i, n, ".*$", SearchRE2); }
3000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success_DFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
3020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
3030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success_PCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
3040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
3050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success_RE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
3060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success_OnePass, 8, 2<<20)->ThreadRange(1, NumCPUs());
3070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success_CachedDFA(int i, int n)     { SearchSuccess(i, n, ".*$", SearchCachedDFA); }
3090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success_CachedOnePass(int i, int n) { SearchSuccess(i, n, ".*$", SearchCachedOnePass); }
3100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success_CachedPCRE(int i, int n)    { SearchSuccess(i, n, ".*$", SearchCachedPCRE); }
3110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success_CachedRE2(int i, int n)     { SearchSuccess(i, n, ".*$", SearchCachedRE2); }
3120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success_CachedDFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
3140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
3150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success_CachedPCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
3160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
3170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success_CachedRE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
3180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success_CachedOnePass, 8, 2<<20)->ThreadRange(1, NumCPUs());
3190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Ambiguous search (RE2 cannot use OnePass).
3210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success1_DFA(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchDFA); }
3230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success1_PCRE(int i, int n)    { SearchSuccess(i, n, ".*.$", SearchPCRE); }
3240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success1_RE2(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchRE2); }
3250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success1_BitState(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchBitState); }
3260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success1_DFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
3280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
3290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success1_PCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
3300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
3310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success1_RE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
3320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success1_BitState, 8, 2<<20)->ThreadRange(1, NumCPUs());
3330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success1_Cached_DFA(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchCachedDFA); }
3350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success1_Cached_PCRE(int i, int n)    { SearchSuccess(i, n, ".*.$", SearchCachedPCRE); }
3360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Success1_Cached_RE2(int i, int n)     { SearchSuccess(i, n, ".*.$", SearchCachedRE2); }
3370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success1_Cached_DFA,     8, 16<<20)->ThreadRange(1, NumCPUs());
3390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
3400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success1_Cached_PCRE,    8, 16<<20)->ThreadRange(1, NumCPUs());
3410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
3420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(Search_Success1_Cached_RE2,     8, 16<<20)->ThreadRange(1, NumCPUs());
3430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: use regexp to find phone number.
3450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchDigits(int iters, SearchImpl* search) {
3470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  const char *text = "650-253-0001";
3480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  int len = strlen(text);
3490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
3500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  search(iters, "([0-9]+)-([0-9]+)-([0-9]+)",
3510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin         StringPiece(text, len), Prog::kAnchored, true);
3520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkItemsProcessed(iters);
3530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
3540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Digits_DFA(int i)         { SearchDigits(i, SearchDFA); }
3560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Digits_NFA(int i)         { SearchDigits(i, SearchNFA); }
3570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Digits_OnePass(int i)     { SearchDigits(i, SearchOnePass); }
3580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Digits_PCRE(int i)        { SearchDigits(i, SearchPCRE); }
3590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Digits_RE2(int i)         { SearchDigits(i, SearchRE2); }
3600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Search_Digits_BitState(int i)         { SearchDigits(i, SearchBitState); }
3610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Search_Digits_DFA)->ThreadRange(1, NumCPUs());
3630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Search_Digits_NFA)->ThreadRange(1, NumCPUs());
3640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Search_Digits_OnePass)->ThreadRange(1, NumCPUs());
3650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
3660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Search_Digits_PCRE)->ThreadRange(1, NumCPUs());
3670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
3680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Search_Digits_RE2)->ThreadRange(1, NumCPUs());
3690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Search_Digits_BitState)->ThreadRange(1, NumCPUs());
3700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: use regexp to parse digit fields in phone number.
3720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse3Digits(int iters,
3740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin               void (*parse3)(int, const char*, const StringPiece&)) {
3750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
3760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  parse3(iters, "([0-9]+)-([0-9]+)-([0-9]+)", "650-253-0001");
3770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkItemsProcessed(iters);
3780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
3790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Digits_NFA(int i)         { Parse3Digits(i, Parse3NFA); }
3810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Digits_OnePass(int i)     { Parse3Digits(i, Parse3OnePass); }
3820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Digits_PCRE(int i)        { Parse3Digits(i, Parse3PCRE); }
3830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Digits_RE2(int i)         { Parse3Digits(i, Parse3RE2); }
3840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Digits_Backtrack(int i)   { Parse3Digits(i, Parse3Backtrack); }
3850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Digits_BitState(int i)   { Parse3Digits(i, Parse3BitState); }
3860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Digits_NFA)->ThreadRange(1, NumCPUs());
3880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Digits_OnePass)->ThreadRange(1, NumCPUs());
3890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
3900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Digits_PCRE)->ThreadRange(1, NumCPUs());
3910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
3920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Digits_RE2)->ThreadRange(1, NumCPUs());
3930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Digits_Backtrack)->ThreadRange(1, NumCPUs());
3940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Digits_BitState)->ThreadRange(1, NumCPUs());
3950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
3960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigits_NFA(int i)         { Parse3Digits(i, Parse3CachedNFA); }
3970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigits_OnePass(int i)     { Parse3Digits(i, Parse3CachedOnePass); }
3980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigits_PCRE(int i)        { Parse3Digits(i, Parse3CachedPCRE); }
3990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigits_RE2(int i)         { Parse3Digits(i, Parse3CachedRE2); }
4000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigits_Backtrack(int i)   { Parse3Digits(i, Parse3CachedBacktrack); }
4010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigits_BitState(int i)   { Parse3Digits(i, Parse3CachedBitState); }
4020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigits_NFA)->ThreadRange(1, NumCPUs());
4040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigits_OnePass)->ThreadRange(1, NumCPUs());
4050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
4060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigits_PCRE)->ThreadRange(1, NumCPUs());
4070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
4080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigits_Backtrack)->ThreadRange(1, NumCPUs());
4090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigits_RE2)->ThreadRange(1, NumCPUs());
4100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigits_BitState)->ThreadRange(1, NumCPUs());
4110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse3DigitDs(int iters,
4130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin               void (*parse3)(int, const char*, const StringPiece&)) {
4140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
4150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  parse3(iters, "(\\d+)-(\\d+)-(\\d+)", "650-253-0001");
4160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkItemsProcessed(iters);
4170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
4180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_DigitDs_NFA(int i)         { Parse3DigitDs(i, Parse3NFA); }
4200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_DigitDs_OnePass(int i)     { Parse3DigitDs(i, Parse3OnePass); }
4210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_DigitDs_PCRE(int i)        { Parse3DigitDs(i, Parse3PCRE); }
4220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_DigitDs_RE2(int i)         { Parse3DigitDs(i, Parse3RE2); }
4230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_DigitDs_Backtrack(int i)   { Parse3DigitDs(i, Parse3CachedBacktrack); }
4240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_DigitDs_BitState(int i)   { Parse3DigitDs(i, Parse3CachedBitState); }
4250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_DigitDs_NFA)->ThreadRange(1, NumCPUs());
4270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_DigitDs_OnePass)->ThreadRange(1, NumCPUs());
4280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
4290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_DigitDs_PCRE)->ThreadRange(1, NumCPUs());
4300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
4310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_DigitDs_RE2)->ThreadRange(1, NumCPUs());
4320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_DigitDs_Backtrack)->ThreadRange(1, NumCPUs());
4330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_DigitDs_BitState)->ThreadRange(1, NumCPUs());
4340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigitDs_NFA(int i)         { Parse3DigitDs(i, Parse3CachedNFA); }
4360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigitDs_OnePass(int i)     { Parse3DigitDs(i, Parse3CachedOnePass); }
4370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigitDs_PCRE(int i)        { Parse3DigitDs(i, Parse3CachedPCRE); }
4380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigitDs_RE2(int i)         { Parse3DigitDs(i, Parse3CachedRE2); }
4390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigitDs_Backtrack(int i)   { Parse3DigitDs(i, Parse3CachedBacktrack); }
4400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedDigitDs_BitState(int i)   { Parse3DigitDs(i, Parse3CachedBitState); }
4410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigitDs_NFA)->ThreadRange(1, NumCPUs());
4430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigitDs_OnePass)->ThreadRange(1, NumCPUs());
4440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
4450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigitDs_PCRE)->ThreadRange(1, NumCPUs());
4460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
4470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigitDs_Backtrack)->ThreadRange(1, NumCPUs());
4480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigitDs_RE2)->ThreadRange(1, NumCPUs());
4490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedDigitDs_BitState)->ThreadRange(1, NumCPUs());
4500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: splitting off leading number field.
4520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse1Split(int iters,
4540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin              void (*parse1)(int, const char*, const StringPiece&)) {
4550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
4560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  parse1(iters, "[0-9]+-(.*)", "650-253-0001");
4570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkItemsProcessed(iters);
4580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
4590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Split_NFA(int i)         { Parse1Split(i, Parse1NFA); }
4610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Split_OnePass(int i)     { Parse1Split(i, Parse1OnePass); }
4620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Split_PCRE(int i)        { Parse1Split(i, Parse1PCRE); }
4630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Split_RE2(int i)         { Parse1Split(i, Parse1RE2); }
4640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_Split_BitState(int i)         { Parse1Split(i, Parse1BitState); }
4650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Split_NFA)->ThreadRange(1, NumCPUs());
4670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Split_OnePass)->ThreadRange(1, NumCPUs());
4680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
4690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Split_PCRE)->ThreadRange(1, NumCPUs());
4700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
4710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Split_RE2)->ThreadRange(1, NumCPUs());
4720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_Split_BitState)->ThreadRange(1, NumCPUs());
4730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplit_NFA(int i)         { Parse1Split(i, Parse1CachedNFA); }
4750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplit_OnePass(int i)     { Parse1Split(i, Parse1CachedOnePass); }
4760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplit_PCRE(int i)        { Parse1Split(i, Parse1CachedPCRE); }
4770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplit_RE2(int i)         { Parse1Split(i, Parse1CachedRE2); }
4780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplit_BitState(int i)         { Parse1Split(i, Parse1CachedBitState); }
4790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplit_NFA)->ThreadRange(1, NumCPUs());
4810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplit_OnePass)->ThreadRange(1, NumCPUs());
4820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
4830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplit_PCRE)->ThreadRange(1, NumCPUs());
4840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
4850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplit_RE2)->ThreadRange(1, NumCPUs());
4860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplit_BitState)->ThreadRange(1, NumCPUs());
4870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: splitting off leading number field but harder (ambiguous regexp).
4890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse1SplitHard(int iters,
4910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                  void (*run)(int, const char*, const StringPiece&)) {
4920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
4930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  run(iters, "[0-9]+.(.*)", "650-253-0001");
4940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkItemsProcessed(iters);
4950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
4960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
4970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_SplitHard_NFA(int i)         { Parse1SplitHard(i, Parse1NFA); }
4980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_SplitHard_PCRE(int i)        { Parse1SplitHard(i, Parse1PCRE); }
4990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_SplitHard_RE2(int i)         { Parse1SplitHard(i, Parse1RE2); }
5000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_SplitHard_BitState(int i)         { Parse1SplitHard(i, Parse1BitState); }
5010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
5030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_SplitHard_PCRE)->ThreadRange(1, NumCPUs());
5040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
5050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_SplitHard_RE2)->ThreadRange(1, NumCPUs());
5060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_SplitHard_BitState)->ThreadRange(1, NumCPUs());
5070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_SplitHard_NFA)->ThreadRange(1, NumCPUs());
5080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitHard_NFA(int i)       { Parse1SplitHard(i, Parse1CachedNFA); }
5100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitHard_PCRE(int i)      { Parse1SplitHard(i, Parse1CachedPCRE); }
5110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitHard_RE2(int i)       { Parse1SplitHard(i, Parse1CachedRE2); }
5120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitHard_BitState(int i)       { Parse1SplitHard(i, Parse1CachedBitState); }
5130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitHard_Backtrack(int i)       { Parse1SplitHard(i, Parse1CachedBacktrack); }
5140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
5160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitHard_PCRE)->ThreadRange(1, NumCPUs());
5170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
5180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitHard_RE2)->ThreadRange(1, NumCPUs());
5190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitHard_BitState)->ThreadRange(1, NumCPUs());
5200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitHard_NFA)->ThreadRange(1, NumCPUs());
5210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitHard_Backtrack)->ThreadRange(1, NumCPUs());
5220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: Parse1SplitHard, big text, small match.
5240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse1SplitBig1(int iters,
5260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                  void (*run)(int, const char*, const StringPiece&)) {
5270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s;
5280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  s.append(100000, 'x');
5290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  s.append("650-253-0001");
5300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
5310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  run(iters, "[0-9]+.(.*)", s);
5320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkItemsProcessed(iters);
5330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
5340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitBig1_PCRE(int i)      { Parse1SplitBig1(i, SearchParse1CachedPCRE); }
5360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitBig1_RE2(int i)       { Parse1SplitBig1(i, SearchParse1CachedRE2); }
5370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
5390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitBig1_PCRE)->ThreadRange(1, NumCPUs());
5400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
5410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitBig1_RE2)->ThreadRange(1, NumCPUs());
5420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: Parse1SplitHard, big text, big match.
5440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse1SplitBig2(int iters,
5460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                  void (*run)(int, const char*, const StringPiece&)) {
5470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s;
5480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  s.append("650-253-");
5490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  s.append(100000, '0');
5500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
5510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  run(iters, "[0-9]+.(.*)", s);
5520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkItemsProcessed(iters);
5530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
5540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitBig2_PCRE(int i)      { Parse1SplitBig2(i, SearchParse1CachedPCRE); }
5560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid Parse_CachedSplitBig2_RE2(int i)       { Parse1SplitBig2(i, SearchParse1CachedRE2); }
5570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
5590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitBig2_PCRE)->ThreadRange(1, NumCPUs());
5600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
5610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(Parse_CachedSplitBig2_RE2)->ThreadRange(1, NumCPUs());
5620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Benchmark: measure time required to parse (but not execute)
5640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// a simple regular expression.
5650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid ParseRegexp(int iters, const string& regexp) {
5670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
5680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
5690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
5700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
5710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
5720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
5730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SimplifyRegexp(int iters, const string& regexp) {
5750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
5760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
5770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
5780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* sre = re->Simplify();
5790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(sre);
5800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    sre->Decref();
5810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
5820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
5830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
5840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid NullWalkRegexp(int iters, const string& regexp) {
5860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
5870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(re);
5880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
5890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->NullWalk();
5900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
5910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  re->Decref();
5920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
5930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
5940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SimplifyCompileRegexp(int iters, const string& regexp) {
5950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
5960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
5970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
5980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* sre = re->Simplify();
5990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(sre);
6000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Prog* prog = sre->CompileToProg(0);
6010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog);
6020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete prog;
6030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    sre->Decref();
6040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
6050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
6060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
6070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CompileRegexp(int iters, const string& regexp) {
6090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
6100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
6110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
6120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Prog* prog = re->CompileToProg(0);
6130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog);
6140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete prog;
6150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
6160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
6170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
6180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CompileToProg(int iters, const string& regexp) {
6200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
6210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(re);
6220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
6230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Prog* prog = re->CompileToProg(0);
6240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog);
6250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete prog;
6260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
6270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  re->Decref();
6280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
6290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CompileByteMap(int iters, const string& regexp) {
6310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
6320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(re);
6330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Prog* prog = re->CompileToProg(0);
6340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(prog);
6350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
6360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    prog->ComputeByteMap();
6370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
6380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  delete prog;
6390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  re->Decref();
6400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
6410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CompilePCRE(int iters, const string& regexp) {
6430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
6440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    PCRE re(regexp, PCRE::UTF8);
6450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(re.error(), "");
6460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
6470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
6480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CompileRE2(int iters, const string& regexp) {
6500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
6510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    RE2 re(regexp);
6520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(re.error(), "");
6530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
6540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
6550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid RunBuild(int iters, const string& regexp, void (*run)(int, const string&)) {
6570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  run(iters, regexp);
6580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkItemsProcessed(iters);
6590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
6600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}  // namespace re2
6620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinDEFINE_string(compile_regexp, "(.*)-(\\d+)-of-(\\d+)", "regexp for compile benchmarks");
6640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinnamespace re2 {
6660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_PCRE_Compile(int i)      { RunBuild(i, FLAGS_compile_regexp, CompilePCRE); }
6680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_Regexp_Parse(int i)      { RunBuild(i, FLAGS_compile_regexp, ParseRegexp); }
6690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_Regexp_Simplify(int i)   { RunBuild(i, FLAGS_compile_regexp, SimplifyRegexp); }
6700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_CompileToProg(int i)     { RunBuild(i, FLAGS_compile_regexp, CompileToProg); }
6710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_CompileByteMap(int i)     { RunBuild(i, FLAGS_compile_regexp, CompileByteMap); }
6720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_Regexp_Compile(int i)    { RunBuild(i, FLAGS_compile_regexp, CompileRegexp); }
6730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_Regexp_SimplifyCompile(int i)   { RunBuild(i, FLAGS_compile_regexp, SimplifyCompileRegexp); }
6740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_Regexp_NullWalk(int i)   { RunBuild(i, FLAGS_compile_regexp, NullWalkRegexp); }
6750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid BM_RE2_Compile(int i)       { RunBuild(i, FLAGS_compile_regexp, CompileRE2); }
6760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
6780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_PCRE_Compile)->ThreadRange(1, NumCPUs());
6790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
6800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_Regexp_Parse)->ThreadRange(1, NumCPUs());
6810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_Regexp_Simplify)->ThreadRange(1, NumCPUs());
6820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_CompileToProg)->ThreadRange(1, NumCPUs());
6830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_CompileByteMap)->ThreadRange(1, NumCPUs());
6840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_Regexp_Compile)->ThreadRange(1, NumCPUs());
6850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_Regexp_SimplifyCompile)->ThreadRange(1, NumCPUs());
6860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_Regexp_NullWalk)->ThreadRange(1, NumCPUs());
6870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK(BM_RE2_Compile)->ThreadRange(1, NumCPUs());
6880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
6900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Makes text of size nbytes, then calls run to search
6910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// the text for regexp iters times.
6920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchPhone(int iters, int nbytes, ParseImpl* search) {
6930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StopBenchmarkTiming();
6940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s;
6950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  MakeText(&s, nbytes);
6960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  s.append("(650) 253-0001");
6970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  BenchmarkMemoryUsage();
6980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  StartBenchmarkTiming();
6990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  search(iters, "(\\d{3}-|\\(\\d{3}\\)\\s+)(\\d{3}-\\d{4})", s);
7000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*nbytes);
7010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
7020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchPhone_CachedPCRE(int i, int n) {
7040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SearchPhone(i, n, SearchParse2CachedPCRE);
7050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
7060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchPhone_CachedRE2(int i, int n) {
7070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SearchPhone(i, n, SearchParse2CachedRE2);
7080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
7090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#ifdef USEPCRE
7110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(SearchPhone_CachedPCRE, 8, 16<<20)->ThreadRange(1, NumCPUs());
7120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#endif
7130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinBENCHMARK_RANGE(SearchPhone_CachedRE2, 8, 16<<20)->ThreadRange(1, NumCPUs());
7140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin/*
7160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinTODO(rsc): Make this work again.
7170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Generates and returns a string over binary alphabet {0,1} that contains
7190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// all possible binary sequences of length n as subsequences.  The obvious
7200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// brute force method would generate a string of length n * 2^n, but this
7210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// generates a string of length n + 2^n - 1 called a De Bruijn cycle.
7220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// See Knuth, The Art of Computer Programming, Vol 2, Exercise 3.2.2 #17.
7230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinstatic string DeBruijnString(int n) {
7240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK_LT(n, 8*sizeof(int));
7250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK_GT(n, 0);
7260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  vector<bool> did(1<<n);
7280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < 1<<n; i++)
7290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    did[i] = false;
7300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s;
7320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < n-1; i++)
7330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    s.append("0");
7340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  int bits = 0;
7350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  int mask = (1<<n) - 1;
7360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < (1<<n); i++) {
7370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    bits <<= 1;
7380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    bits &= mask;
7390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    if (!did[bits|1]) {
7400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      bits |= 1;
7410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      s.append("1");
7420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    } else {
7430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      s.append("0");
7440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    }
7450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(!did[bits]);
7460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    did[bits] = true;
7470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
7480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  return s;
7490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
7500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CacheFill(int iters, int n, SearchImpl *srch) {
7520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string s = DeBruijnString(n+1);
7530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  string t;
7540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = n+1; i < 20; i++) {
7550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    t = s + s;
7560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    swap(s, t);
7570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
7580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  srch(iters, StringPrintf("0[01]{%d}$", n).c_str(), s,
7590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin       Prog::kUnanchored, true);
7600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  SetBenchmarkBytesProcessed(static_cast<int64>(iters)*s.size());
7610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
7620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CacheFillPCRE(int i, int n) { CacheFill(i, n, SearchCachedPCRE); }
7640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CacheFillRE2(int i, int n)  { CacheFill(i, n, SearchCachedRE2); }
7650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CacheFillNFA(int i, int n)  { CacheFill(i, n, SearchCachedNFA); }
7660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid CacheFillDFA(int i, int n)  { CacheFill(i, n, SearchCachedDFA); }
7670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// BENCHMARK_WITH_ARG uses __LINE__ to generate distinct identifiers
7690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// for the static BenchmarkRegisterer, which makes it unusable inside
7700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// a macro like DO24 below.  MY_BENCHMARK_WITH_ARG uses the argument a
7710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// to make the identifiers distinct (only possible when 'a' is a simple
7720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// expression like 2, not like 1+1).
7730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#define MY_BENCHMARK_WITH_ARG(n, a) \
7740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  bool __benchmark_ ## n ## a =     \
7750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    (new ::testing::Benchmark(#n, NewPermanentCallback(&n)))->ThreadRange(1, NumCPUs());
7760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#define DO24(A, B) \
7780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  A(B, 1);    A(B, 2);    A(B, 3);    A(B, 4);    A(B, 5);    A(B, 6);  \
7790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  A(B, 7);    A(B, 8);    A(B, 9);    A(B, 10);   A(B, 11);   A(B, 12); \
7800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  A(B, 13);   A(B, 14);   A(B, 15);   A(B, 16);   A(B, 17);   A(B, 18); \
7810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  A(B, 19);   A(B, 20);   A(B, 21);   A(B, 22);   A(B, 23);   A(B, 24);
7820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinDO24(MY_BENCHMARK_WITH_ARG, CacheFillPCRE)
7840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinDO24(MY_BENCHMARK_WITH_ARG, CacheFillNFA)
7850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinDO24(MY_BENCHMARK_WITH_ARG, CacheFillRE2)
7860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander GutkinDO24(MY_BENCHMARK_WITH_ARG, CacheFillDFA)
7870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#undef DO24
7890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin#undef MY_BENCHMARK_WITH_ARG
7900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin*/
7910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin////////////////////////////////////////////////////////////////////////
7930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin//
7940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Implementation routines.  Sad that there are so many,
7950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// but all the interfaces are slightly different.
7960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
7970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Runs implementation to search for regexp in text, iters times.
7980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Expect_match says whether the regexp should be found.
7990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// Anchored says whether to run an anchored search.
8000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
8010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchDFA(int iters, const char* regexp, const StringPiece& text,
8020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin            Prog::Anchor anchor, bool expect_match) {
8030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
8040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
8060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Prog* prog = re->CompileToProg(0);
8070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog);
8080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    bool failed = false;
8090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(prog->SearchDFA(text, NULL, anchor, Prog::kFirstMatch,
8100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                             NULL, &failed, NULL),
8110d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin             expect_match);
8120d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(!failed);
8130d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete prog;
8140d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
8150d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
8160d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
8170d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
8180d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchNFA(int iters, const char* regexp, const StringPiece& text,
8190d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin            Prog::Anchor anchor, bool expect_match) {
8200d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
8210d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8220d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
8230d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Prog* prog = re->CompileToProg(0);
8240d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog);
8250d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(prog->SearchNFA(text, NULL, anchor, Prog::kFirstMatch, NULL, 0),
8260d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin             expect_match);
8270d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete prog;
8280d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
8290d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
8300d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
8310d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
8320d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchOnePass(int iters, const char* regexp, const StringPiece& text,
8330d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin            Prog::Anchor anchor, bool expect_match) {
8340d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
8350d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8360d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
8370d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Prog* prog = re->CompileToProg(0);
8380d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog);
8390d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog->IsOnePass());
8400d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(prog->SearchOnePass(text, text, anchor, Prog::kFirstMatch, NULL, 0),
8410d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin             expect_match);
8420d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete prog;
8430d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
8440d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
8450d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
8460d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
8470d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchBitState(int iters, const char* regexp, const StringPiece& text,
8480d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin            Prog::Anchor anchor, bool expect_match) {
8490d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
8500d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8510d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(re);
8520d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    Prog* prog = re->CompileToProg(0);
8530d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(prog);
8540d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(prog->SearchBitState(text, text, anchor, Prog::kFirstMatch, NULL, 0),
8550d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin             expect_match);
8560d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    delete prog;
8570d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    re->Decref();
8580d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
8590d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
8600d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
8610d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchPCRE(int iters, const char* regexp, const StringPiece& text,
8620d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                Prog::Anchor anchor, bool expect_match) {
8630d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
8640d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    PCRE re(regexp, PCRE::UTF8);
8650d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(re.error(), "");
8660d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    if (anchor == Prog::kAnchored)
8670d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      CHECK_EQ(PCRE::FullMatch(text, re), expect_match);
8680d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    else
8690d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      CHECK_EQ(PCRE::PartialMatch(text, re), expect_match);
8700d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
8710d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
8720d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
8730d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchRE2(int iters, const char* regexp, const StringPiece& text,
8740d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin               Prog::Anchor anchor, bool expect_match) {
8750d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
8760d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    RE2 re(regexp);
8770d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(re.error(), "");
8780d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    if (anchor == Prog::kAnchored)
8790d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      CHECK_EQ(RE2::FullMatch(text, re), expect_match);
8800d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    else
8810d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin      CHECK_EQ(RE2::PartialMatch(text, re), expect_match);
8820d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
8830d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
8840d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
8850d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// SearchCachedXXX is like SearchXXX but only does the
8860d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// regexp parsing and compiling once.  This lets us measure
8870d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin// search time without the per-regexp overhead.
8880d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
8890d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchCachedDFA(int iters, const char* regexp, const StringPiece& text,
8900d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                     Prog::Anchor anchor, bool expect_match) {
8910d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
8920d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(re);
8930d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Prog* prog = re->CompileToProg(1LL<<31);
8940d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(prog);
8950d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  for (int i = 0; i < iters; i++) {
8960d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    bool failed = false;
8970d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK_EQ(prog->SearchDFA(text, NULL, anchor,
8980d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                             Prog::kFirstMatch, NULL, &failed, NULL),
8990d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin             expect_match);
9000d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin    CHECK(!failed);
9010d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  }
9020d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  delete prog;
9030d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  re->Decref();
9040d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin}
9050d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin
9060d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkinvoid SearchCachedNFA(int iters, const char* regexp, const StringPiece& text,
9070d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin                     Prog::Anchor anchor, bool expect_match) {
9080d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Regexp* re = Regexp::Parse(regexp, Regexp::LikePerl, NULL);
9090d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  CHECK(re);
9100d4c52358a1af421705c54bd8a9fdd8a30558a2eAlexander Gutkin  Prog* prog = re->CompileToProg(0);
911