| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
|
| """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() |
|
|
