Hi Felix, On Fri, 3 Sep 2021 09:56:31 -0700 Felix Lechner <felix.lechner@lease-up.com> wrote:
[1] https://salsa.debian.org/lintian/lintian/-/commit/3410cb55a647aa3844d5f1b189a6f73975059a74
I think the code used to limit the expensive regex operations
to the first 8192 bytes of each file [1]. As regular expressions can
easily become *really* expensive with exponential-time behavior [2],
this is very likely the reason for the performance degradation.
Cheers
Timo
[1] https://salsa.debian.org/lintian/lintian/-/commit/3410cb55a647aa3844d5f1b189a6f73975059a74#d4c28deb91f037547e38e6b2dde68f4d8225b714_865_811
[2] Nested Kleene stars are the canonical example, e.g.
/^((a+)*)*$/ will become exponentially slow to reject
a string like "a"x$n."b". Sometimes, you can rewrite a
regular expression to avoid such behavior, sometimes not.
--
⢀⣴⠾⠻⢶⣦⠀ ╭────────────────────────────────────────────────────╮
⣾⠁⢠⠒⠀⣿⡁ │ Timo Röhling │
⢿⡄⠘⠷⠚⠋⠀ │ 9B03 EBB9 8300 DF97 C2B1 23BF CC8C 6BDD 1403 F4CA │
⠈⠳⣄⠀⠀⠀⠀ ╰────────────────────────────────────────────────────╯
Attachment:
signature.asc
Description: PGP signature