Nhiều người dùng regex như phép thuật mà không biết bên trong nó là gì. Thực ra engine làm hai việc: biên dịch mẫu thành một máy trạng thái, rồi chạy máy đó trên input. Bài này mở máy ra xem: python re.DEBUG in opcode thật của mẫu a(b|c)*d, và Go regexp (RE2) chứng minh nó duyệt input tuyến tính — input tăng gấp 5 thì thời gian cũng tăng gấp 5, ns mỗi ký tự gần như hằng số.
Chỉ một ký hiệu \1 mà đổi cả bản chất lý thuyết của regex. Bài này đo thật: python dùng (\w+)\s+\1 bắt đúng từ lặp 'the the', <(\w+)>...</\1> khớp thẻ đóng đúng thẻ mở; nhưng Go RE2 từ chối biên dịch \1 với lỗi 'invalid escape sequence'. Vì sao khả năng 'nhớ cái đã khớp' vượt khỏi máy trạng thái hữu hạn, buộc engine phải backtracking — và vì sao RE2 cố tình không hỗ trợ.
Mẫu (a+)+$ trông vô hại, nhưng gặp đúng input độc nó chạy chậm theo cấp số nhân. Bài này đo thật: với chuỗi 'aaaa...!', python re mất 9 giây chỉ với 28 ký tự, và thời gian gấp đôi mỗi khi thêm một 'a' — n=40 sẽ mất hàng ngàn năm. Cùng mẫu đó trên Go RE2 chỉ mất 3 micro-giây, kể cả với 100.000 ký tự. Đây là ReDoS, và cách phòng nó.
RE2 (Go, Rust, Google) chạy tuyến tính bằng cách mô phỏng mọi trạng thái cùng lúc thay vì thử-và-quay-lui. Bài này đo thật: cùng mẫu độc (a+)+b, RE2 xử lý 20 triệu ký tự trong 443ms với ns/ký tự hằng số ~22 — trong khi python treo ở 28 ký tự. Cái giá: RE2 từ chối lookahead, lookbehind và backreference, mỗi cái báo một lỗi khác nhau. Khi nào nên chọn nó.