Skip to content

Exponential runtime performance regression in GHC 8.2 + Data.Text.Lazy + Text.RE.TDFA

When using Text.RE.TDFA from the regex-tdfa package on GHC 8.2 to match trivial regexes against Data.Text.Lazy strings, I see **exponential runtime**. On GHC 8.0, or using Data.Text strict strings or String strings, the runtime is as expected.

Here's my repo with simple test code illustrating the regression and timing stats: https://github.com/ntc2/ghc-8.2.1-regex-lazy-text-bug/tree/07b7bb32c6e90e8f2d2eada4b59943f37e632d53 .

In summary, for the problematic combination of GHC version and libraries, the run times are 3s, 10s, 22s, and 40s for counting regex matches in files with 10000, 20000, 30000, and 40000 lines, respectively. For all of the unproblematic combinations -- i.e. GHC 8.0.2, String, strict Data.Text, or building with profiling -- the run time is always about 1s!

And **this is a Heisenbug**, in that the performance problem goes away if I build with profiling support!

There is the separate Issue #13745 about **compile-time regressions** in GHC 8.2 + the regex-tdfa package, that I commented on.

Edited by Nathan Collins
To upload designs, you'll need to enable LFS and have an admin enable hashed storage. More information