divyanshus2404 commented on PR #71711: URL: https://github.com/apache/airflow/pull/71711#issuecomment-5438321792
You're right, and thanks for the concrete payload — I've dropped the linear-time claim. Reproduced it: with `"secret" * n` as a single token the timing clearly quadruples as the input doubles, so it is still O(n²). | `"secret" * n` | this PR | |---|---| | 6,019 chars | 39ms | | 12,019 chars | 149ms | | 24,019 chars | 598ms | | 48,019 chars | 2,424ms | The anchor removes the retry-at-every-offset factor, but a token packing many keyword occurrences still forces the inner `\S*?` to rescan from each one, so the worst case remains quadratic — just with a much smaller constant. On that same payload the previous pattern was 32.8ms at 319 chars and 5,511ms at 2,419 chars, so it degrades far more steeply, but "mitigated" is the accurate word rather than "linear". Updated accordingly: - Title no longer says linear — now "Reduce `_mask_cmd` backtracking on large inputs". - The code comment states plainly that this is not strictly O(n) and why. - `test_masks_passwords_is_linear_on_large_input` renamed to `test_masks_passwords_stays_fast_on_large_input`. - Added `test_masks_passwords_stays_fast_on_repeated_keywords` using your input shape, sized so it stays quick while still catching a regression to the old pattern. If you'd prefer a genuinely linear implementation I'm happy to do it — splitting on whitespace and testing each token for the keyword before matching is O(n) with no pathological case, at the cost of more code than a single pattern. Let me know which trade-off you'd rather have here. --- Drafted-by: Claude Code; reviewed by @divyanshus2404 before posting -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
