stdlib/regex/bench/rxbench.cpp · source

2// Original work; see ACKNOWLEDGMENTS.md for the open-source ideas we build upon.

3//

4// rxbench — 4-engine regex benchmark: cheatah::regex vs std::regex vs boost::regex vs Google RE2,

5// on many patterns, input sizes, input shapes, and adversarial (catastrophic-backtracking) inputs.

6//

7// Every case is a BM_<section>_<row>_<engine> group over IDENTICAL inputs. Before anything is

8// timed, every engine's answers are cross-checked on the exact benchmark corpora and the binary

9// abort()s on disagreement — a benchmark that times the wrong answer is worthless. After the runs,

10// main() prints a per-rival win/parity/loss tally (1.15x ratio threshold + 0.25 ns absolute floor,

11// the bench_gate.sh convention) and an honest-losses list. RXBENCH_ASSERT=1 makes the process exit

12// non-zero if cheatah loses any case to RE2.

13//

14// RE2 is timed in its OUT-OF-BOX configuration (UTF-8, leftmost-first) — what real RE2 users get.

15// Offset/count parity is checked against RE2 with longest_match + Latin-1 (cheatah's documented

16// leftmost-longest byte semantics); that configuration is never timed. std::regex and boost::regex

17// are leftmost-first, so they participate in boolean parity only. The 4 MB pattern-table corpus is

18// trimmed of its trailing newline so `$` means the same thing in all four engines (Perl-style `$`

19// would otherwise also match before a final newline in some of them).

20//

21// cmake -S stdlib/regex/bench -B build/regexbench -DCMAKE_BUILD_TYPE=Release

22// cmake --build build/regexbench -j

23// ./build/regexbench/rxbench --benchmark_repetitions=7 --benchmark_report_aggregates_only=true

24

25#include "engines.hpp"

26

27#include <benchmark/benchmark.h>

28

29#include <algorithm>

30#include <cstdio>

31#include <cstdlib>

32#include <ctime>

33#include <map>

34#include <memory>

35#include <string>

36#include <string_view>

37#include <vector>

38

39namespace {

40

41using HayPtr = std::shared_ptr<const std::string>;

42

43std::string make_log(std::size_t bytes) {

44 std::string s;

45 const char* line = "2026-07-02 12:00:01 INFO request id=48213 user=bob@example.com status=200 bytes=1274\n";

46 s.reserve(bytes + 100);

47 while (s.size() < bytes) s += line;

48 return s;

49}

50

51// A mixed "realistic" corpus: JSON-ish records, request lines, key lists, hex tokens,

52// timestamps and UUID-ish ids — the shapes the BM_real_* extraction rows hunt through.

53std::string make_real(std::size_t bytes) {

54 const char* recs[] = {

55 "{\"user_id\": 48213, \"name\": \"bob\", \"ts\": \"12:00:01\", \"tok\": \"0x1f2e3d4c\"}\n",

56 "GET /api/v2/items?id=8ac4-99b2-11ee HTTP/1.1 status=200 t=0.043\n",

57 "field_one=alpha;field_two=beta9;field_three=gamma12; -- padding --------\n",

58 "ERROR at 03:14:15 code=0xdeadbeef uuid=0123-4567-89ab retry=3\n",

59 };

60 std::string s;

61 s.reserve(bytes + 100);

62 for (std::size_t i = 0; s.size() < bytes; ++i) s += recs[i % 4];

63 return s;

64}

65

66// Auto-scale a nanosecond value into a "value unit" cell (ns / us / ms / s).

67std::string fmt_ns(double ns) {

68 char buf[32];

69 if (ns < 1e3) snprintf(buf, sizeof buf, "%9.1f ns", ns);

70 else if (ns < 1e6) snprintf(buf, sizeof buf, "%9.2f us", ns / 1e3);

71 else if (ns < 1e9) snprintf(buf, sizeof buf, "%9.3f ms", ns / 1e6);

72 else snprintf(buf, sizeof buf, "%9.3f s ", ns / 1e9);

73 return buf;

74}

75

76// ---- row tables ----------------------------------------------------------------------

77

78struct Row { const char* tag; const char* pat; };

79

80constexpr Row kTable[] = {

81 {"literal_present", "status=200"},

82 {"literal_absent", "status=500"},

83 {"prefix_class", "id=[0-9]+"},

84 {"digits", "[0-9]+"},

85 {"word", "[a-zA-Z]+"},

86 {"email", "[a-z]+@[a-z.]+"},

87 {"email_absent", "[a-z]+@nowhere"},

88 {"alternation", "INFO|WARN|ERROR"},

89 {"alt_absent", "FATAL|PANIC|SEGV"},

90 {"key_value", "user=[a-z0-9.@]+"},

91 {"ip_absent", "[0-9]+\\.[0-9]+\\.[0-9]+\\.[0-9]+"},

92 {"dotstar", "INFO.*status"},

93 {"anchor_start", "^2026"},

94 {"anchor_end", "1274$"},

95 {"nested_groups", "(id|user)=([a-z0-9]+)"},

96 {"class_quant", "[A-Z][a-z]*"},

97 {"escapes", "\\d+ \\w+"},

98 {"repetition", "([a-z]+=[^ ]+ ?)+"},

99};

100

101constexpr Row kCompile[] = {

102 {"literal", "status=200"},

103 {"class_email", "[a-z]+@[a-z.]+"},

104 {"alternation", "INFO|WARN|ERROR"},

105 {"ip", "[0-9]+\\.[0-9]+\\.[0-9]+\\.[0-9]+"},

106 {"repetition", "([a-z]+=[^ ]+ ?)+"},

107};

108

109constexpr Row kFind[] = {

110 {"digits", "[0-9]+"}, // hit at offset 0

111 {"email", "[a-z]+@[a-z.]+"}, // hit early in the first line

112 {"anchor_end", "1274$"}, // hit only at the very end of the corpus

113 {"ip_absent", "[0-9]+\\.[0-9]+\\.[0-9]+\\.[0-9]+"}, // no hit: full scan

114};

115

116// Rows where leftmost-first and leftmost-longest yield the same matches, so all four engines

117// (and both RE2 configurations) must report the same count.

118constexpr Row kFindall[] = {

119 {"digits", "[0-9]+"},

120 {"word", "[a-zA-Z]+"},

121 {"alternation", "INFO|WARN|ERROR"},

122 {"key_value", "user=[a-z0-9.@]+"},

123};

124

125struct FullRow { const char* tag; const char* pat; const char* text; };

126constexpr FullRow kFull[] = {

127 {"digits_yes", "[0-9]+", "48213"},

128 {"email_yes", "[a-z]+@[a-z.]+", "bob@example.com"},

129 {"email_no", "[a-z]+@[a-z.]+", "bob@Example.com"},

130};

131

132constexpr int kRedosN[] = {16, 20, 24, 28};

133constexpr const char* kRedosNested = "(a+)+$"; // classic nested-quantifier blowup

134constexpr const char* kRedosAltstar = "(a|a)*c"; // alternation-star blowup

135

136// Adversarially LARGE inputs: the same hostile shapes at tens of megabytes, where a linear

137// engine must stay boring and a backtracker melts. Rows with `backtrackers == false` are the

138// exponential ones — std::regex could not finish a single iteration at this size (boost's

139// complexity guard would throw), so only the linear engines run them.

140struct XlRow { const char* tag; const char* pat; const char* corpus; bool backtrackers; };

141constexpr XlRow kXl[] = {

142 {"redos_nested_16M", "(a+)+$", "as_bang", false},

143 {"redos_altstar_16M", "(a|a)*c", "as", false},

144 {"reverse_alive_16M", "c[ab]*$", "as", true}, // reverse DFA alive end-to-end

145 {"email_absent_16M", "[a-z]+@nowhere", "log16", true}, // dense-candidate full scan

146 {"literal_storm_16M", "status=500", "log16", true}, // front-byte storm at scale

147};

148constexpr const char* kXlFindPat = "x[0-9]"; // find over 16M of 'x': the candidate-budget path

149

150enum class Op { Search, SearchBytes, Full, Find, Count };

151

152// The generic extra families: realistic extraction, same-byte-run shapes, tiny-input

153// latency, late finds, and additional adversarial compositions. `backtrackers == false`

154// excludes std/boost where their cost is super-linear at this size; `guarded` wraps the

155// body in try/catch (boost's complexity guard throws at match time).

156struct GRow {

157 const char* section;

158 const char* tag;

159 const char* pat;

160 const char* corpus;

161 Op op;

162 bool backtrackers;

163 bool guarded;

164};

165constexpr GRow kExtra[] = {

166 // realistic extraction over the 4 MB mixed corpus

167 {"real", "quoted", "\"[^\"]*\"", "real4", Op::Search, true, false},

168 {"real", "hex", "0x[0-9a-f]+", "real4", Op::Search, true, false},

169 {"real", "hex_absent", "0X[0-9A-F]+", "real4", Op::Search, true, false},

170 {"real", "timestamp", "[0-9]+:[0-9]+:[0-9]+", "real4", Op::Search, true, false},

171 {"real", "uuid", "[0-9a-f]+-[0-9a-f]+-[0-9a-f]+", "real4", Op::Search, true, false},

172 {"real", "keylist", "([a-z_]+=[a-z0-9]+;)+", "real4", Op::Search, true, false},

173 {"real", "find_hex", "0x[0-9a-f]+", "real4", Op::Find, true, false},

174 {"real", "findall_ts", "[0-9]+:[0-9]+:[0-9]+", "real256k", Op::Count, true, false},

175 // same-byte-run shapes (the self-loop run-skip family)

176 {"run", "class_absent_16M", "[ab]+c", "as", Op::Search, false, true}, // O(n^2) backtrack

177 // A 16 MB MATCH overflows libstdc++ std::regex's recursive matcher (SIGSEGV — a crash,

178 // not a slow answer), so the two long-match rows run linear engines only.

179 {"run", "class_present_16M", "[ab]+c", "as_c", Op::Search, false, true},

180 {"run", "spaces_16M", "\\S+", "spaces", Op::Search, true, false},

181 {"run", "padded_literal_16M", "NEEDLE_[0-9]+", "padded", Op::Search, true, false},

182 {"run", "tailclass_16M", "[^x]*x", "xs_tail", Op::Search, false, true},

183 // tiny-input per-call latency

184 {"tiny", "digit_hit", "[0-9]+", "t_7", Op::Search, true, false},

185 {"tiny", "digit_miss", "[0-9]+", "t_x", Op::Search, true, false},

186 {"tiny", "email_hit", "[a-z]+@[a-z.]+", "t_ab", Op::Search, true, false},

187 {"tiny", "email_miss", "[a-z]+@[a-z.]+", "t_dash", Op::Search, true, false},

188 {"tiny", "full_tok16", "id=[0-9]+ t=[0-9a-f]+", "t_tok", Op::Full, true, false},

189 // find with the only match at the 99% position of 4 MB

190 {"findlate", "xmarker_4M", "XMARKER[0-9]+", "late", Op::Find, true, false},

191 // extra adversarial compositions

192 {"redos2", "alt2_N16", "(a|aa)+$", "a16_bang", Op::Search, true, true},

193 {"redos2", "alt2_N28", "(a|aa)+$", "a28_bang", Op::Search, true, true},

194 {"redos2", "dotstar3_4M", ".*.*.*Q", "log4", Op::Search, false, true}, // O(n^3) backtrack

195};

196

197constexpr std::size_t kSweepSizes[] = {1u << 10, 1u << 14, 1u << 18, 1u << 20, 1u << 24};

198constexpr const char* kSweepTags[] = {"1K", "16K", "256K", "1M", "16M"};

199constexpr const char* kSweepPat = "CRITICAL[0-9]+"; // absent at every size: a full scan

200constexpr const char* kHugePat = "NOSUCHTOKEN_[0-9]+"; // absent in 64 MB

201constexpr const char* kShapePat = "user=[a-z]+";

202

203// ---- corpora -------------------------------------------------------------------------

204

205struct Corpora {

206 HayPtr table; // 4 MB log, trailing '\n' trimmed (uniform `$` semantics)

207 HayPtr slice; // 256 KB of the same log (find-all rows)

208 HayPtr huge; // 64 MB

209 std::vector<std::pair<const char*, HayPtr>> sweep; // tag -> haystack

210 std::vector<std::pair<const char*, HayPtr>> shapes; // tag -> haystack

211 std::vector<std::pair<std::string, HayPtr>> redos; // tag ("nested_N16") -> input, + pattern per family

212 std::vector<std::pair<std::string, std::string>> redos_pat; // tag -> pattern

213 std::map<std::string, HayPtr> xl; // adversarially-large corpora by key

214 std::vector<std::pair<std::string, std::string>> compilescale; // tag -> generated pattern

215};

216

217Corpora build_corpora() {

218 Corpora c;

219 {

220 std::string t = make_log(4'000'000);

221 if (!t.empty() && t.back() == '\n') t.pop_back();

222 c.table = std::make_shared<const std::string>(std::move(t));

223 }

224 c.slice = std::make_shared<const std::string>(c.table->substr(0, 256 * 1024));

225 c.huge = std::make_shared<const std::string>(make_log(64'000'000));

226 for (std::size_t i = 0; i < std::size(kSweepSizes); ++i)

227 c.sweep.emplace_back(kSweepTags[i], std::make_shared<const std::string>(make_log(kSweepSizes[i])));

228 {

229 // The raw log matches "user=[a-z]+" in every line, so a meaningful position sweep needs a

230 // neutral base with every 'u' knocked out; "everywhere" keeps the raw log.

231 std::string neutral = make_log(4'000'000);

232 for (char& ch : neutral) if (ch == 'u') ch = 'x';

233 c.shapes.emplace_back("start", std::make_shared<const std::string>("user=zzz " + neutral));

234 c.shapes.emplace_back("end", std::make_shared<const std::string>(neutral + " user=zzz"));

235 c.shapes.emplace_back("absent", std::make_shared<const std::string>(neutral));

236 c.shapes.emplace_back("everywhere", std::make_shared<const std::string>(make_log(4'000'000)));

237 }

238 for (int n : kRedosN) {

239 c.redos.emplace_back("nested_N" + std::to_string(n),

240 std::make_shared<const std::string>(std::string(std::size_t(n), 'a') + '!'));

241 c.redos_pat.emplace_back("nested_N" + std::to_string(n), kRedosNested);

242 c.redos.emplace_back("altstar_N" + std::to_string(n),

243 std::make_shared<const std::string>(std::string(std::size_t(n), 'a')));

244 c.redos_pat.emplace_back("altstar_N" + std::to_string(n), kRedosAltstar);

245 }

246 constexpr std::size_t kXlBytes = 16u << 20;

247 c.xl.emplace("as", std::make_shared<const std::string>(std::string(kXlBytes, 'a')));

248 c.xl.emplace("as_bang", std::make_shared<const std::string>(std::string(kXlBytes, 'a') + '!'));

249 c.xl.emplace("xs", std::make_shared<const std::string>(std::string(kXlBytes, 'x')));

250 c.xl.emplace("log16", std::make_shared<const std::string>(make_log(kXlBytes)));

251 c.xl.emplace("as_c", std::make_shared<const std::string>(std::string(kXlBytes, 'a') + 'c'));

252 c.xl.emplace("xs_tail", std::make_shared<const std::string>(std::string(kXlBytes, 'a') + 'x'));

253 c.xl.emplace("spaces",

254 std::make_shared<const std::string>(std::string(kXlBytes - 6, ' ') + "token6"));

255 {

256 std::string padded(kXlBytes, '-');

257 padded.replace(15u << 20, 9, "NEEDLE_42");

258 c.xl.emplace("padded", std::make_shared<const std::string>(std::move(padded)));

259 }

260 {

261 std::string real = make_real(4'000'000);

262 c.xl.emplace("real256k", std::make_shared<const std::string>(real.substr(0, 256 * 1024)));

263 c.xl.emplace("real4", std::make_shared<const std::string>(std::move(real)));

264 }

265 {

266 std::string late = make_log(4'000'000);

267 if (!late.empty() && late.back() == '\n') late.pop_back();

268 late.replace(late.size() * 99 / 100, 9, "XMARKER77");

269 c.xl.emplace("late", std::make_shared<const std::string>(std::move(late)));

270 }

271 c.xl.emplace("log4", c.table);

272 c.xl.emplace("t_7", std::make_shared<const std::string>("7"));

273 c.xl.emplace("t_x", std::make_shared<const std::string>("x"));

274 c.xl.emplace("t_ab", std::make_shared<const std::string>("a@b"));

275 c.xl.emplace("t_dash", std::make_shared<const std::string>("a-b"));

276 c.xl.emplace("t_tok", std::make_shared<const std::string>("id=48213 t=9f2e"));

277 c.xl.emplace("a16_bang", std::make_shared<const std::string>(std::string(16, 'a') + '!'));

278 c.xl.emplace("a28_bang", std::make_shared<const std::string>(std::string(28, 'a') + '!'));

279 {

280 std::string alt;

281 for (int i = 0; i < 50; ++i) {

282 if (i) alt += '|';

283 alt += "alpha" + std::to_string(i);

284 }

285 c.compilescale.emplace_back("alt50", alt);

286 std::string lit64;

287 while (lit64.size() < 64) lit64 += "abcdefghijklmnop";

288 c.compilescale.emplace_back("literal64", lit64);

289 c.compilescale.emplace_back("nest100",

290 std::string(100, '(') + "a" + std::string(100, ')'));

291 }

292 return c;

293}

294

295// ---- parity verification (abort on mismatch — never time a wrong answer) -------------

296

297void die(const std::string& msg) {

298 std::fprintf(stderr, "rxbench: PARITY FAILURE: %s\n", msg.c_str());

299 std::abort();

300}

301

302// Cross-check one boolean operation for one pattern over one haystack, across every engine

303// that accepts the pattern. `want` comes from cheatah (the engine under test). Backtracking

304// engines may throw at match time (boost's complexity guard) — a throw skips that engine.

305struct BoolParity {

306 std::string pat;

307 std::string_view hay;

308 const char* label;

309 bool with_std = true;

310 bool with_boost = true;

311};

312

313template <eng::Engine E>

314void check_bool_one(const BoolParity& p, bool full, bool want) {

315 auto re = eng::try_compile<E>(p.pat);

316 if (!re) return; // engine rejects the pattern: nothing to compare

317 try {

318 const bool got = full ? E::full(*re, p.hay) : E::search(*re, p.hay);

319 if (got != want)

320 die(std::string(E::name) + (full ? " full_match" : " search") + " disagrees on '" + p.pat +

321 "' over " + p.label + " (cheatah=" + (want ? "true" : "false") + ")");

322 } catch (const std::exception&) {

323 // match-time throw (backtracker complexity guard): no answer to compare

324 }

325}

326

327void check_bool(const BoolParity& p, bool full = false) {

328 auto ch = eng::try_compile<eng::Cheatah>(p.pat);

329 if (!ch) die("cheatah cannot compile its own benchmark pattern '" + p.pat + "'");

330 const bool want = full ? eng::Cheatah::full(*ch, p.hay) : eng::Cheatah::search(*ch, p.hay);

331 if (p.with_std) check_bool_one<eng::Std>(p, full, want);

332 if (p.with_boost) check_bool_one<eng::Boost>(p, full, want);

333 check_bool_one<eng::Re2Def>(p, full, want);

334 check_bool_one<eng::Re2Longest>(p, full, want);

335}

336

337// find offsets must agree with the leftmost-longest oracle (RE2 longest_match + Latin-1).

338void check_find(const std::string& pat, std::string_view hay, const char* label) {

339 auto ch = eng::try_compile<eng::Cheatah>(pat);

340 auto oracle = eng::try_compile<eng::Re2Longest>(pat);

341 if (!ch || !oracle) die("find parity: '" + pat + "' must compile in cheatah and RE2");

342 std::size_t cb = 0, ce = 0, ob = 0, oe = 0;

343 const bool cf = eng::Cheatah::find(*ch, hay, cb, ce);

344 const bool of = eng::Re2Longest::find(*oracle, hay, ob, oe);

345 if (cf != of || (cf && (cb != ob || ce != oe)))

346 die("find disagrees with the RE2-longest oracle on '" + pat + "' over " + label +

347 " (cheatah " + (cf ? std::to_string(cb) + ".." + std::to_string(ce) : "none") +

348 ", oracle " + (of ? std::to_string(ob) + ".." + std::to_string(oe) : "none") + ")");

349}

350

351// Non-overlapping match counts must agree across all engines on unambiguous rows.

352void check_count(const std::string& pat, std::string_view hay, const char* label) {

353 auto ch = eng::try_compile<eng::Cheatah>(pat);

354 if (!ch) die("count parity: cheatah rejects '" + pat + "'");

355 const std::size_t want = eng::Cheatah::count_all(*ch, hay);

356 auto one = [&]<eng::Engine E>() {

357 auto re = eng::try_compile<E>(pat);

358 if (!re) return;

359 const std::size_t got = E::count_all(*re, hay);

360 if (got != want)

361 die(std::string(E::name) + " count_all disagrees on '" + pat + "' over " + label + " (" +

362 std::to_string(got) + " vs cheatah " + std::to_string(want) + ")");

363 };

364 one.template operator()<eng::Std>();

365 one.template operator()<eng::Boost>();

366 one.template operator()<eng::Re2Def>();

367 one.template operator()<eng::Re2Longest>();

368}

369

370void verify_parity(const Corpora& c) {

371 std::fprintf(stderr, "rxbench: verifying engine agreement on the benchmark corpora...\n");

372 for (const Row& r : kTable) check_bool({r.pat, *c.table, "the 4 MB log"});

373 for (const auto& [tag, hay] : c.sweep) check_bool({kSweepPat, *hay, tag});

374 for (const auto& [tag, hay] : c.shapes) check_bool({kShapePat, *hay, tag});

375 check_bool({kHugePat, *c.huge, "the 64 MB log"});

376 for (std::size_t i = 0; i < c.redos.size(); ++i) {

377 // std::regex is exponential here: only the smallest N is affordable to cross-check.

378 const bool small = c.redos[i].first.ends_with("N16");

379 check_bool({c.redos_pat[i].second, *c.redos[i].second, c.redos[i].first.c_str(),

380 /*with_std=*/small, /*with_boost=*/true});

381 }

382 for (const FullRow& r : kFull) check_bool({r.pat, r.text, r.tag}, /*full=*/true);

383 for (const Row& r : kFind) check_find(r.pat, *c.table, "the 4 MB log");

384 for (const Row& r : kFindall) check_count(r.pat, *c.slice, "the 256 KB slice");

385 for (const XlRow& r : kXl) // backtrackers verify only where they can finish a single run

386 check_bool({r.pat, *c.xl.at(r.corpus), r.tag, r.backtrackers, r.backtrackers});

387 check_find(kXlFindPat, *c.xl.at("xs"), "16M of 'x'");

388 for (const GRow& r : kExtra) {

389 const bool bt = r.backtrackers && !r.guarded; // guarded = too slow to verify, too

390 if (r.op == Op::Find) check_find(r.pat, *c.xl.at(r.corpus), r.tag);

391 else if (r.op == Op::Count) check_count(r.pat, *c.xl.at(r.corpus), r.tag);

392 else check_bool({r.pat, *c.xl.at(r.corpus), r.tag, bt, bt}, r.op == Op::Full);

393 }

394 std::fprintf(stderr, "rxbench: all engines agree on every benchmarked case.\n");

395}

396

397// ---- benchmark bodies ----------------------------------------------------------------

398

399template <eng::Engine E>

400void run_search(benchmark::State& st, const typename E::Re& re, std::string_view h, bool bytes) {

401 for (auto _ : st) {

402 benchmark::DoNotOptimize(h);

403 bool r = E::search(re, h);

404 benchmark::DoNotOptimize(&r);

405 }

406 if (bytes) st.SetBytesProcessed(static_cast<int64_t>(st.iterations()) * static_cast<int64_t>(h.size()));

407}

408

409// Adversarial rows: a backtracking engine may throw mid-run (boost's complexity guard).

410template <eng::Engine E>

411void run_search_guarded(benchmark::State& st, const typename E::Re& re, std::string_view h) {

412 for (auto _ : st) {

413 benchmark::DoNotOptimize(h);

414 try {

415 bool r = E::search(re, h);

416 benchmark::DoNotOptimize(&r);

417 } catch (const std::exception& ex) {

418 st.SkipWithMessage(std::string("threw: ") + ex.what());

419 break;

420 }

421 }

422}

423

424template <eng::Engine E>

425void run_full(benchmark::State& st, const typename E::Re& re, std::string_view h) {

426 for (auto _ : st) {

427 benchmark::DoNotOptimize(h);

428 bool r = E::full(re, h);

429 benchmark::DoNotOptimize(&r);

430 }

431}

432

433template <eng::Engine E>

434void run_find(benchmark::State& st, const typename E::Re& re, std::string_view h) {

435 for (auto _ : st) {

436 benchmark::DoNotOptimize(h);

437 std::size_t b = 0, e = 0;

438 bool r = E::find(re, h, b, e);

439 benchmark::DoNotOptimize(&r);

440 benchmark::DoNotOptimize(&b);

441 benchmark::DoNotOptimize(&e);

442 }

443}

444

445template <eng::Engine E>

446void run_count(benchmark::State& st, const typename E::Re& re, std::string_view h) {

447 for (auto _ : st) {

448 benchmark::DoNotOptimize(h);

449 std::size_t n = E::count_all(re, h);

450 benchmark::DoNotOptimize(&n);

451 }

452}

453

454template <eng::Engine E>

455void run_compile(benchmark::State& st, const std::string& pat) {

456 std::string p = pat; // mutable copy: DoNotOptimize on a const ref is deprecated (and weaker)

457 for (auto _ : st) {

458 benchmark::DoNotOptimize(p);

459 auto re = E::compile(p);

460 benchmark::DoNotOptimize(&re);

461 }

462}

463

464// ---- registration --------------------------------------------------------------------

465

466void for_each_engine(auto&& f) {

467 f.template operator()<eng::Cheatah>();

468 f.template operator()<eng::Std>();

469 f.template operator()<eng::Boost>();

470 f.template operator()<eng::Re2Def>();

471}

472

473template <eng::Engine E>

474void reg_one(const std::string& name, const char* pat, HayPtr hay, Op op) {

475 auto re = eng::try_compile<E>(pat);

476 if (!re) {

477 std::fprintf(stderr, "rxbench: %s rejects '%s' — row skipped for this engine\n", E::name, pat);

478 return;

479 }

480 benchmark::RegisterBenchmark(name.c_str(), [re, hay, op](benchmark::State& st) {

481 std::string_view h(*hay);

482 switch (op) {

483 case Op::Search: run_search<E>(st, *re, h, false); break;

484 case Op::SearchBytes: run_search<E>(st, *re, h, true); break;

485 case Op::Full: run_full<E>(st, *re, h); break;

486 case Op::Find: run_find<E>(st, *re, h); break;

487 case Op::Count: run_count<E>(st, *re, h); break;

488 }

489 });

490}

491

492void register_benchmarks(const Corpora& c) {

493 for_each_engine([&]<eng::Engine E>() {

494 for (const Row& r : kCompile) {

495 if (!eng::try_compile<E>(r.pat)) continue;

496 const std::string pat = r.pat;

497 benchmark::RegisterBenchmark((std::string("BM_compile_") + r.tag + "_" + E::name).c_str(),

498 [pat](benchmark::State& st) { run_compile<E>(st, pat); });

499 }

500 for (const auto& [tag, pat] : c.compilescale) {

501 if (!eng::try_compile<E>(pat)) continue;

502 const std::string p = pat;

503 benchmark::RegisterBenchmark((std::string("BM_compilescale_") + tag + "_" + E::name).c_str(),

504 [p](benchmark::State& st) { run_compile<E>(st, p); });

505 }

506 for (const Row& r : kTable)

507 reg_one<E>(std::string("BM_pat_") + r.tag + "_" + E::name, r.pat, c.table, Op::Search);

508 for (const auto& [tag, hay] : c.sweep)

509 reg_one<E>(std::string("BM_sweep_") + tag + "_" + E::name, kSweepPat, hay, Op::SearchBytes);

510 for (const auto& [tag, hay] : c.shapes)

511 reg_one<E>(std::string("BM_shape_") + tag + "_" + E::name, kShapePat, hay, Op::Search);

512 reg_one<E>(std::string("BM_hugescan_") + E::name, kHugePat, c.huge, Op::SearchBytes);

513 for (const Row& r : kFind)

514 reg_one<E>(std::string("BM_find_") + r.tag + "_" + E::name, r.pat, c.table, Op::Find);

515 for (const Row& r : kFindall)

516 reg_one<E>(std::string("BM_findall_") + r.tag + "_" + E::name, r.pat, c.slice, Op::Count);

517 for (const FullRow& r : kFull) {

518 auto hay = std::make_shared<const std::string>(r.text);

519 reg_one<E>(std::string("BM_full_") + r.tag + "_" + E::name, r.pat, hay, Op::Full);

520 }

521 for (std::size_t i = 0; i < c.redos.size(); ++i) {

522 const std::string& tag = c.redos[i].first;

523 const std::string& pat = c.redos_pat[i].second;

524 HayPtr hay = c.redos[i].second;

525 auto re = eng::try_compile<E>(pat);

526 if (!re) continue;

527 auto* b = benchmark::RegisterBenchmark(

528 (std::string("BM_redos_") + tag + "_" + E::name).c_str(),

529 [re, hay](benchmark::State& st) { run_search_guarded<E>(st, *re, std::string_view(*hay)); });

530 // std::regex is exponential on these rows (~seconds at N=28): one shot, not min_time.

531 if (std::string_view(E::name) == "std") b->Iterations(1);

532 }

533 const bool backtracker =

534 std::string_view(E::name) == "std" || std::string_view(E::name) == "boost";

535 for (const XlRow& r : kXl) {

536 if (backtracker && !r.backtrackers) continue; // exponential at 16 MB: unrunnable

537 HayPtr hay = c.xl.at(r.corpus);

538 auto re = eng::try_compile<E>(r.pat);

539 if (!re) continue;

540 auto* b = benchmark::RegisterBenchmark(

541 (std::string("BM_xl_") + r.tag + "_" + E::name).c_str(),

542 [re, hay](benchmark::State& st) { run_search_guarded<E>(st, *re, std::string_view(*hay)); });

543 if (backtracker) b->Iterations(1); // linear-but-slow engines: one shot is plenty

544 }

545 reg_one<E>(std::string("BM_xl_find_budget_16M_") + E::name, kXlFindPat, c.xl.at("xs"), Op::Find);

546 for (const GRow& r : kExtra) {

547 if (backtracker && !r.backtrackers) continue; // super-linear at this size

548 HayPtr hay = c.xl.at(r.corpus);

549 const std::string name = std::string("BM_") + r.section + "_" + r.tag + "_" + E::name;

550 if (r.guarded && r.op == Op::Search) {

551 auto re = eng::try_compile<E>(r.pat);

552 if (!re) continue;

553 auto* b = benchmark::RegisterBenchmark(name.c_str(), [re, hay](benchmark::State& st) {

554 run_search_guarded<E>(st, *re, std::string_view(*hay));

555 });

556 if (backtracker) b->Iterations(1); // exponential-or-slow one-shots

557 } else {

558 reg_one<E>(name, r.pat, hay, r.op);

559 }

560 }

561 });

562}

563

564// ---- tally: per-rival win/parity/loss + honest losses --------------------------------

565

566constexpr double kThreshold = 1.15; // ratio floor before a difference counts (bench_gate.sh)

567constexpr double kMinGapNs = 0.25; // absolute floor: ~one cycle; below it a ratio is noise

568

569class TallyReporter : public benchmark::ConsoleReporter {

570 public:

571 std::map<std::string, std::vector<double>> raw; // case -> per-repetition real ns

572 std::map<std::string, double> median_agg; // case -> reported median real ns

573

574 void ReportRuns(const std::vector<Run>& runs) override {

575 for (const Run& r : runs) {

576 if (r.skipped) continue;

577 const std::string name = r.run_name.str();

578 if (r.run_type == Run::RT_Aggregate) {

579 if (r.aggregate_name == "median") median_agg[name] = r.GetAdjustedRealTime();

580 } else {

581 raw[name].push_back(r.GetAdjustedRealTime());

582 }

583 }

584 ConsoleReporter::ReportRuns(runs);

585 }

586};

587

588double median_of(std::vector<double> v) {

589 std::sort(v.begin(), v.end());

590 const std::size_t n = v.size();

591 return (n % 2) ? v[n / 2] : 0.5 * (v[n / 2 - 1] + v[n / 2]);

592}

593

594// One rival's comparison in a row: ratio (rival/cheatah, >1 = cheatah faster) + verdict.

595std::string verdict_cell(double che, double rival) {

596 const char* mark = "\xE2\x9A\xAA"; // ⚪ parity

597 if (che > rival * kThreshold && (che - rival) > kMinGapNs) mark = "\xE2\x9D\x8C"; // ❌

598 else if (rival > che * kThreshold && (rival - che) > kMinGapNs) mark = "\xE2\x9C\x85"; // ✅

599 char buf[48];

600 snprintf(buf, sizeof buf, "%.2fx %s", rival / che, mark);

601 return buf;

602}

603

604// Exit status: 0, or 1 when RXBENCH_ASSERT=1 and cheatah lost at least one case to RE2.

605// RXBENCH_TABLE=<path> additionally writes the complete comparison as a Markdown table.

606int print_tally(const TallyReporter& rep) {

607 std::map<std::string, double> ns;

608 for (const auto& [name, v] : rep.raw) ns[name] = median_of(v);

609 for (const auto& [name, v] : rep.median_agg) ns[name] = v; // median aggregate wins over raw

610

611 struct Rival { const char* suffix; const char* label; int win = 0, par = 0, loss = 0; };

612 Rival rivals[] = {{"_std", "std"}, {"_boost", "boost"}, {"_re2", "re2"}};

613 std::vector<std::string> loss_lines;

614 std::string md;

615

616 std::printf("\n==== per-case medians ====\n");

617 std::printf("%-28s %12s %12s %12s %12s %11s\n", "case", "cheatah", "std", "boost", "re2", "re2/cheatah");

618 for (const auto& [name, che] : ns) {

619 constexpr std::string_view kMe = "_cheatah";

620 if (name.size() <= kMe.size() || name.substr(name.size() - kMe.size()) != kMe) continue;

621 const std::string base = name.substr(0, name.size() - kMe.size());

622 std::string cells[3], mdcells[3];

623 double re2_ratio = 0.0;

624 for (std::size_t i = 0; i < 3; ++i) {

625 auto it = ns.find(base + rivals[i].suffix);

626 if (it == ns.end()) { cells[i] = "-"; mdcells[i] = "—"; continue; }

627 const double rival = it->second;

628 cells[i] = fmt_ns(rival);

629 mdcells[i] = verdict_cell(che, rival);

630 if (i == 2) re2_ratio = rival / che;

631 if (che > rival * kThreshold && (che - rival) > kMinGapNs) {

632 ++rivals[i].loss;

633 if (i == 2)

634 loss_lines.push_back("vs re2: " + base.substr(3) + " — cheatah " + fmt_ns(che) +

635 " vs re2 " + fmt_ns(rival) + " (" +

636 std::to_string(che / rival).substr(0, 5) + "x slower)");

637 } else if (rival > che * kThreshold && (rival - che) > kMinGapNs) {

638 ++rivals[i].win;

639 } else {

640 ++rivals[i].par;

641 }

642 }

643 std::printf("%-28s %12s %12s %12s %12s %10.2fx\n", base.substr(3).c_str(), fmt_ns(che).c_str(),

644 cells[0].c_str(), cells[1].c_str(), cells[2].c_str(), re2_ratio);

645 auto trim = [](std::string s) {

646 while (!s.empty() && s.front() == ' ') s.erase(s.begin());

647 return s;

648 };

649 std::string sc[3];

650 for (std::size_t i = 0; i < 3; ++i) {

651 auto it = ns.find(base + rivals[i].suffix);

652 sc[i] = (it == ns.end()) ? std::string("—") : trim(fmt_ns(it->second));

653 }

654 md += "| " + base.substr(3) + " | " + trim(fmt_ns(che)) + " | " + sc[0] + " | " + sc[1] +

655 " | " + sc[2] + " | " + mdcells[0] + " | " + mdcells[1] + " | " + mdcells[2] + " |\n";

656 }

657

658 std::printf("\n==== tally (faster: >%.2fx and >%.2f ns apart; else parity) ====\n", kThreshold, kMinGapNs);

659 for (const Rival& r : rivals)

660 std::printf("vs %-6s %3d faster, %3d parity, %3d slower\n", r.label, r.win, r.par, r.loss);

661

662 if (loss_lines.empty()) {

663 std::printf("\nhonest losses vs re2: none — cheatah ties or beats RE2 on every case.\n");

664 } else {

665 std::printf("\nhonest losses vs re2:\n");

666 for (const std::string& l : loss_lines) std::printf(" %s\n", l.c_str());

667 }

668

669 if (const char* path = std::getenv("RXBENCH_TABLE")) {

670 std::FILE* f = std::fopen(path, "w");

671 if (f) {

672 std::time_t now = std::time(nullptr);

673 char day[16] = "unknown";

674 if (std::tm* tm = std::localtime(&now)) std::strftime(day, sizeof day, "%Y-%m-%d", tm);

675 // The full cheatah-bench-stamp, not a bare "generated on <date>" comment. The

676 // fields scripts/bench_table.purr reads are `suite:` (which region this belongs

677 // to), `commit:` + `watch:` (together: has the measured code moved since?) and

678 // `publishable:`. Without them this table is invisible to the staleness gate,

679 // which is how it sat outside the system while being the one genuinely generated

680 // table in the tree.

681 const char* commit = std::getenv("CHEATAH_BENCH_COMMIT");

682 std::fprintf(f,

683 "<!-- cheatah-bench-stamp v1\n"

684 " suite: regex-vs-engines\n"

685 " generated: %s\n"

686 " commit: %s\n"

687 " competitors: std::regex, Boost.Regex, Google RE2\n"

688 " statistic: median real time per case; ratio = rival/cheatah, "

689 ">1 means cheatah is faster\n"

690 " harness: verdicts use the %.2fx + %.2f ns band\n"

691 " watch: stdlib/regex/, stdlib/regex/bench/rxbench.cpp\n"

692 " publishable: true\n"

693 "\n PRODUCED BY:\n"

694 " RXBENCH_ASSERT=1 RXBENCH_TABLE=docs/bench/regex-vs-engines.md \\\n"

695 " ./build/regexbench/rxbench --benchmark_repetitions=7 \\\n"

696 " --benchmark_enable_random_interleaving=true \\\n"

697 " --benchmark_report_aggregates_only=true\n"

698 "-->\n\n"

700 "|---|--:|--:|--:|--:|--:|--:|--:|\n%s\n",

701 day, (commit != nullptr && commit[0] != '\0') ? commit : "unknown",

702 kThreshold, kMinGapNs, md.c_str());

703 std::fprintf(f, "**Tally** — ");

704 for (const Rival& r : rivals)

705 std::fprintf(f, "vs %s: **%d faster / %d parity / %d slower**%s", r.label, r.win,

706 r.par, r.loss, (&r == &rivals[2]) ? ".\n" : "; ");

707 if (loss_lines.empty())

708 std::fprintf(f, "\ncheatah ties or beats RE2 on **every** case.\n");

709 else {

710 std::fprintf(f, "\nLosses vs RE2:\n");

711 for (const std::string& l : loss_lines) std::fprintf(f, "- %s\n", l.c_str());

712 }

713 std::fclose(f);

714 std::printf("\ncomparison table written to %s\n", path);

715 }

716 }

717

718 // The REPRESENTATIVE table: a curated subset, curated in the INVOCATION.

719 //

720 // stdlib/regex/README.md publishes eight hand-picked cases above the full table. Picking

721 // is editorial and that is fine — what is not fine is the picking living in a Markdown

722 // file, where the numbers beside it cannot be regenerated. RXBENCH_ROWS carries both the

723 // selection and its order, and the stamp records the spec verbatim, so the published

724 // subset reproduces exactly.

725 //

726 // RXBENCH_ROWS='search_status=`status=200` on a 4 MB log;search_digits=`[0-9]+` (search)'

727 if (const char* rep_path = std::getenv("RXBENCH_REP_TABLE")) {

728 const char* spec = std::getenv("RXBENCH_ROWS");

729 std::FILE* f = std::fopen(rep_path, "w");

730 if (f && spec != nullptr) {

731 std::time_t now = std::time(nullptr);

732 char day[16] = "unknown";

733 if (std::tm* tm = std::localtime(&now)) std::strftime(day, sizeof day, "%Y-%m-%d", tm);

734 const char* commit = std::getenv("CHEATAH_BENCH_COMMIT");

735 std::fprintf(f,

736 "<!-- cheatah-bench-stamp v1\n"

737 " suite: regex-representative\n"

738 " generated: %s\n"

739 " commit: %s\n"

740 " competitors: std::regex, Boost.Regex, Google RE2\n"

741 " statistic: median real time per case; `vs RE2` = re2/cheatah\n"

742 " harness: medians of repeated runs, random-interleaved\n"

743 " watch: stdlib/regex/, stdlib/regex/bench/rxbench.cpp\n"

744 " publishable: true\n"

745 "\n PRODUCED BY:\n"

746 " RXBENCH_REP_TABLE=%s \\\n"

747 " RXBENCH_ROWS='%s' \\\n"

748 " ./build/regexbench/rxbench --benchmark_repetitions=7 \\\n"

749 " --benchmark_enable_random_interleaving=true\n"

750 "-->\n\n"

752 "|---|--:|--:|--:|--:|--:|\n",

753 day, (commit != nullptr && commit[0] != '\0') ? commit : "unknown",

754 rep_path, spec);

755

756 // ';'-separated `case=label`, emitted in the order given — ordering is curation too.

757 std::string sp(spec);

758 std::size_t i = 0;

759 while (i < sp.size()) {

760 std::size_t semi = sp.find(';', i);

761 if (semi == std::string::npos) semi = sp.size();

762 const std::string entry = sp.substr(i, semi - i);

763 i = semi + 1;

764 if (entry.empty()) continue;

765 const std::size_t eq = entry.find('=');

766 const std::string key = (eq == std::string::npos) ? entry : entry.substr(0, eq);

767 const std::string label = (eq == std::string::npos) ? entry : entry.substr(eq + 1);

768

769 auto at = [&ns](const std::string& n) -> double {

770 auto it = ns.find(n);

771 return it == ns.end() ? -1.0 : it->second;

772 };

773 const double che = at("BM_" + key + "_cheatah");

774 if (che < 0.0) {

775 // Never silently drop a curated row: a spec naming a case that did not run

776 // is a broken table, and em-dashes say so where a missing line would not.

777 std::fprintf(f, "| %s | — | — | — | — | not measured |\n", label.c_str());

778 std::fprintf(stderr, "rxbench: RXBENCH_ROWS names '%s', which produced no "

779 "measurement\n", key.c_str());

780 continue;

781 }

782 auto cell = [&](const char* suffix) {

783 const double v = at("BM_" + key + suffix);

784 return v < 0.0 ? std::string("—") : fmt_ns(v);

785 };

786 const double re2 = at("BM_" + key + "_re2");

787 char ratio[32] = "—";

788 if (re2 > 0.0) std::snprintf(ratio, sizeof ratio, "%.1f\u00d7", re2 / che);

789 std::fprintf(f, "| %s | %s | %s | %s | %s | %s |\n", label.c_str(),

790 fmt_ns(che).c_str(), cell("_std").c_str(), cell("_boost").c_str(),

791 cell("_re2").c_str(), ratio);

792 }

793 std::fclose(f);

794 std::printf("\nrepresentative table written to %s\n", rep_path);

795 }

796 }

797

798 const char* assert_env = std::getenv("RXBENCH_ASSERT");

799 if (assert_env && assert_env[0] == '1' && !loss_lines.empty()) {

800 std::printf("\nRXBENCH_ASSERT: FAILING — cheatah lost %zu case(s) to RE2.\n", loss_lines.size());

801 return 1;

802 }

803 return 0;

804}

805

806} // namespace

807

808int main(int argc, char** argv) {

809 Corpora corpora = build_corpora();

810 verify_parity(corpora);

811 benchmark::Initialize(&argc, argv);

812 if (benchmark::ReportUnrecognizedArguments(argc, argv)) return 1;

813 register_benchmarks(corpora);

814 TallyReporter reporter;

815 benchmark::RunSpecifiedBenchmarks(&reporter);

816 benchmark::Shutdown();

817 return print_tally(reporter);

818}