Sau mười phần hiểu regex hoạt động thế nào, giờ là lúc dùng hiểu biết đó để làm nó nhanh. Tin tốt: một regex chậm hiếm khi do máy yếu — gần như luôn do mẫu viết chưa khéo, và sửa mẫu thường cho kết quả cải thiện gấp hàng nghìn lần chứ không phải vài phần trăm. Bài này (phần 11 loạt Regex) đo thật bốn kỹ thuật tối ưu, từ cái tiết kiệm khiêm tốn tới cái cứu bạn khỏi ReDoS. Nhưng trước hết, nguyên tắc số một: đo trước khi tối ưu — vì như bạn sẽ thấy, có mẹo giúp khổng lồ trong ca này lại vô ích hoặc phản tác dụng trong ca khác.

Bốn kỹ thuật

  • Biên dịch một lần: re.compile mẫu ngoài vòng lặp và tái dùng, đừng gọi mẫu thô mỗi lần.
  • Lớp phủ định [^x]* thay cho lazy .*?: diễn đạt "tới x thì dừng" một cách tường minh.
  • Atomic group (?>...) / possessive a++: khóa kết quả của một phần khớp, cấm engine quay lui — chặn backtracking thảm họa (phần 6).
  • Neo (\A, ^): khi biết chuỗi phải bắt đầu ở đâu, neo mẫu để engine không thử mọi vị trí.

Ảnh chụp đoạn mã nền tối minh hoạ tối ưu regex bốn mẹo đo được đo trước khi tối ưu compile một lần lớp phủ định atomic possessive neo loại sớm, một biên dịch một lần tái dùng đừng biên dịch trong vòng lặp rc bằng re compile mẫu w cộng a còng w cộng chấm w cộng biên dịch một lần ngoài vòng lặp for x trong items rc match x tái dùng đối tượng đã biên dịch tệ gọi re match mẫu x trong vòng lặp phân tích lại mẫu mỗi lần, hai lớp phủ định mũ x sao thay cho chấm sao hỏi lazy nhỏ hơn mũ lớn hơn sao lớn hơn mọi ký tự trừ lớn hơn diễn đạt thẳng tới lớn hơn thì dừng nhỏ hơn chấm sao hỏi lớn hơn lazy ăn từng ký tự rồi thử lớn hơn chậm hơn chút và nguy hiểm hơn với input xấu phủ định vừa nhanh vừa an toàn hơn, ba atomic group possessive chặn backtracking thảm họa a cộng đóng ngoặc cộng đô la bẫy ReDoS bài 06 backtrack mũ trên aaaa chấm than a cộng cộng đô la possessive a cộng ăn chắc không nhả lại không backtrack dấu hỏi lớn hơn a cộng đóng ngoặc cộng đô la atomic group khóa lại kết quả nhóm cấm quay lui python re 3.11 hỗ trợ cả hai biến mẫu nguy hiểm thành an toàn, bốn neo giúp engine loại sớm khi khớp phải ở đầu backslash A w 30 Z neo đầu chuỗi engine chỉ thử ở vị trí 0 w 30 Z không neo thử ở từng vị trí của input dài neo khi biết chuỗi phải bắt đầu ở đó cắt hết các lần thử vô ích nhưng mũ với re MULTILINE thì kiểm mỗi dòng không phải lúc nào cũng lợi

Hình 1: Bốn kỹ thuật tối ưu regex — biên dịch một lần rồi tái dùng; lớp phủ định [^>]* thay lazy .*?; atomic (?>...)/possessive a++ chặn backtracking; neo \A/^ để loại sớm khi biết chuỗi phải bắt đầu ở đó.

Đo thật: từ khiêm tốn tới khổng lồ

Mình đo thời gian bằng time.perf_counter trên Python 3.11 (lấy giá trị nhỏ nhất qua nhiều lần chạy):

Ảnh chụp bảng kết quả chạy thật tối ưu regex output thật go-lab python 3.11 time perf_counter, a biên dịch một lần vs mẫu thô mỗi lần 200000 lần match compile 1 lần 21.52ms mẫu thô mỗi lần 39.50ms chậm hơn 1.84x dù python có cache nhỏ phân tích lại mẫu vẫn tốn compile một lần vẫn lợi, b lớp phủ định vs lazy trên 5000 thẻ chênh nhỏ báo thật nhỏ hơn mũ lớn hơn sao lớn hơn phủ định 0.409ms 10000 thẻ nhỏ hơn chấm sao hỏi lớn hơn lazy 0.436ms lazy chậm hơn 1.07x trên input lành chênh nhỏ giá trị thật của phủ định là tránh backtrack thảm họa với input xấu bài 06 không chỉ nhanh hơn chút, c atomic possessive chặn backtracking khác biệt khổng lồ input độc a nhân 26 cộng chấm than a cộng đóng ngoặc cộng đô la backtrack 2222.26ms bẫy ReDoS a cộng cộng đô la possessive 0.33us nhanh hơn khoảng 6.7 triệu lần dấu hỏi lớn hơn a cộng đóng ngoặc cộng đô la atomic 0.92us cũng chặn backtrack python 3.11 hỗ trợ a cộng cộng và dấu hỏi lớn hơn viên thuốc giải ReDoS ngay trong mẫu, d neo backslash A loại sớm trên 2 triệu ký tự không khớp backslash A w 30 Z neo 0.21us chỉ thử 1 vị trí đầu chuỗi w 30 Z không neo 68.520ms thử ở khoảng 2 triệu vị trí neo nhanh hơn khoảng 329182x

Hình 2: Chạy thật — (a) compile một lần 21.52ms vs mẫu thô 39.50ms (1.84x); (b) [^>]* 0.409ms vs .*? 0.436ms (chỉ 1.07x — chênh nhỏ); (c) (a+)+$ 2222.26ms vs possessive a++$ 0.33µs (~6.7 triệu lần) và atomic (?>a+)+$ 0.92µs; (d) neo \A\w{30}Z 0.21µs vs \w{30}Z 68.52ms (~329182x).

  • (a) Biên dịch một lần — lợi vừa phải nhưng có thật: gọi rc.match() với rc đã compile 200.000 lần mất 21.52ms, còn gọi re.match(r'...', x) mẫu thô mỗi lần mất 39.50ms — chậm hơn 1.84x. Python có cache nội bộ nên chênh không quá lớn, nhưng việc phân tích lại chuỗi mẫu (tra cache, băm) vẫn tốn. Với mẫu chạy trong vòng nóng, compile một lần là thói quen đúng.
  • (b) Lớp phủ định — chênh nhỏ, nhưng giá trị nằm ở chỗ khác (báo thật): <[^>]*> mất 0.409ms, <.*?> mất 0.436ms — lazy chỉ chậm hơn 1.07x. Trên input lành như thế này, khác biệt tốc độ khiêm tốn. Nhưng giá trị thật của lớp phủ định không chủ yếu là nhanh hơn chút — mà là tránh backtracking thảm họa với input xấu (phần 6). Đây là ví dụ cho nguyên tắc "đo trước khi tối ưu": nếu chỉ nhìn con số này, bạn tưởng phủ định không đáng; nhìn cả khía cạnh an toàn mới thấy nó đáng.
  • (c) Atomic/possessive — khác biệt khổng lồ: đây là ngôi sao. Mẫu độc (a+)+$ trên 'a'*26+'!' mất 2222ms (backtracking mũ, ReDoS). Nhưng possessive a++$ chỉ mất 0.33µs — nhanh hơn ~6.7 triệu lần — và atomic (?>a+)+$ mất 0.92µs. Cả hai chặn backtracking: a++ ăn hết a rồi không nhả lại, nên khi $ hỏng, engine bỏ cuộc ngay thay vì thử mọi cách chia. Python 3.11+ hỗ trợ cả a++ lẫn (?>...) — đây là viên thuốc giải ReDoS ngay trong mẫu, không cần đổi engine.
  • (d) Neo loại sớm — khổng lồ, khi dùng đúng: mẫu \w{30}Z trên 2 triệu ký tự a (không khớp) mất 68.52ms vì engine thử khớp ở mỗi trong ~2 triệu vị trí. Neo \A\w{30}Z chỉ mất 0.21µs — nhanh hơn ~329182 lần — vì \A bảo engine chỉ thử ở vị trí đầu chuỗi. Nhưng nhớ bài 3: nếu dùng ^ với cờ re.MULTILINE, engine phải kiểm mỗi đầu dòng, và neo có thể không nhanh hơn (thậm chí chậm hơn). Neo giúp khi bạn biết chắc chuỗi phải bắt đầu ở đó.

Đánh đổi cần cân nhắc

Đo trước, đừng đoán — vì "mẹo tối ưu" phụ thuộc dữ liệu. Bài này chứng minh chính điều đó: lớp phủ định chỉ nhanh hơn 1.07x trên input lành nhưng cứu mạng với input xấu; neo nhanh hơn 329 nghìn lần khi khớp ở đầu nhưng có thể phản tác dụng với re.MULTILINE. Đừng áp mẹo một cách máy móc — profile với dữ liệu thật của bạn (như bài profiling ở loạt Debug) rồi mới quyết. Một "tối ưu" sai ngữ cảnh làm code khó đọc mà chẳng nhanh hơn.

Possessive/atomic đổi tốc độ lấy ngữ nghĩa — có thể làm mẫu không khớp thứ lẽ ra khớp. a++ không nhả lại a nào, nên nếu phần sau cần mượn lại một a thì mẫu sẽ thất bại (đúng như thiết kế — đó là cách nó chặn backtracking). Ví dụ ".++" có thể không khớp "abc" nếu bạn cần dấu " cuối. Dùng possessive khi bạn chắc phần đó không cần nhả lại; nếu không, bạn đổi ReDoS lấy bug khớp hụt.

Cách tối ưu triệt để nhất thường là đổi engine, không phải chỉnh mẫu. Nếu regex chạy trên input không tin cậy và bạn lo ReDoS, đổi sang RE2/Go (phần 7) loại rủi ro tận gốc mà không cần khéo léo từng mẫu. Các mẹo trong bài này quý khi bạn phải dùng engine backtracking (cần lookaround/backreference); nhưng nếu không cần chúng, một engine tuyến tính đơn giản hơn và an toàn hơn mọi mẹo.

Ba ý mang về

  1. Đo trước khi tối ưu — mẹo phụ thuộc dữ liệu: đo thật lớp phủ định chỉ nhanh hơn 1.07x trên input lành, còn neo nhanh hơn 329182x khi khớp ở đầu nhưng có thể phản tác dụng với re.MULTILINE; đừng áp mẹo máy móc.
  2. Atomic/possessive là viên thuốc giải ReDoS ngay trong mẫu: đo thật (a+)+$ mất 2222ms nhưng a++$ chỉ 0.33µs (~6.7 triệu lần) và (?>a+)+$ 0.92µs — Python 3.11+ hỗ trợ; nhưng chúng đổi ngữ nghĩa (không nhả lại), dùng khi chắc phần đó không cần backtrack.
  3. Biên dịch một lần và neo đúng chỗ là thói quen rẻ mà lợi: đo thật compile một lần nhanh hơn 1.84x, neo \A loại sớm cắt 68ms còn 0.21µs; và nhớ cách triệt để nhất chống ReDoS vẫn là đổi sang engine tuyến tính (RE2) khi không cần lookaround/backreference.

Nguồn

Phần sau — bài cuối loạt — ta mang mọi thứ ra thực chiến: grep -P, ripgrep, phân tích log thật; đâu là lúc nên dùng regex và đâu là lúc nên dừng lại; kèm tổng kết cả loạt.