File size: 2,440 Bytes
d6df5f0 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 | #!/usr/bin/env python3
# SPDX-License-Identifier: AGPL-3.0-or-later
#
# snapkitty-regex
# Copyright (C) 2026 SnapKitty Collective
#
# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU Affero General Public License as published
# by the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
# GNU Affero General Public License for more details.
#
# You should have received a copy of the GNU Affero General Public License
# along with this program. If not, see <https://www.gnu.org/licenses/>.
"""Pathological benchmark: a?^n a^n against a^n.
Cox's article shows Perl needing 60+ seconds for n=29 while the Thompson
NFA needs microseconds. Here we pit snapkitty-regex against Python's
backtracking `re` on the same input. Python runs are capped with a
timeout so the demo finishes.
"""
import subprocess
import sys
import time
BIN = "./regex"
TIMEOUT = 15
def time_ours(n):
pat = "a?" * n + "a" * n
txt = "a" * n
t0 = time.perf_counter()
r = subprocess.run([BIN, pat, txt], capture_output=True)
dt = time.perf_counter() - t0
assert r.returncode == 0, f"ours failed at n={n}"
return dt
def time_pyre(n):
code = (
"import re, time; "
f"rx = re.compile('a?'*{n} + 'a'*{n}); txt = 'a'*{n}; "
"t0=time.perf_counter(); m=rx.fullmatch(txt); "
"dt=time.perf_counter()-t0; "
"assert m; print(f'{dt:.6f}')"
)
try:
r = subprocess.run([sys.executable, "-c", code],
capture_output=True, text=True, timeout=TIMEOUT)
return float(r.stdout.strip())
except subprocess.TimeoutExpired:
return None
def main():
print(f"{'n':>5} {'snapkitty-regex':>16} {'python re':>16}")
print("-" * 41)
for n in (10, 15, 20, 22, 24, 26):
ours = time_ours(n)
py = time_pyre(n)
py_s = f"{py:.6f}s" if py is not None else f">{TIMEOUT}s (timeout)"
print(f"{n:>5} {ours:>15.6f}s {py_s:>16}")
print()
print("Scaling of snapkitty-regex alone (O(m*n), no blowup):")
for n in (29, 50, 100, 200, 500):
print(f" n={n:<4} {time_ours(n):.6f}s")
if __name__ == "__main__":
main()
|