Extremely slow prettyprinting for lists of tuples

[brianhuffman]

In the current master version (5a6f9a0) this expression takes 5 seconds to evaluate at the REPL on my machine:

[ (x : Integer, x) | x <- [1..26]]

The runtime is exponential in the length, doubling with each additional element in the list. Length 28 takes about 22 seconds on my machine.

The type of x doesn't seem to matter much. Changing the type to Z 30 also takes 5 seconds. At type [8] it takes 13 seconds. Replacing one of the xs with another expression like True or () doesn't affect the time. The same slowdown occurs with a two-element record or a two-element array, although a one-element record or array makes it evaluate quickly. Going up to three elements makes it moderately slower (but definitely not 3^n slower).

[brianhuffman]

It looks like the slowdown does not occur in cryptol-2.7.0, cryptol-2.8.0, cryptol-2.10.0, or cryptol-2.11.0.

[brianhuffman]

I just finished doing a bisection. Git says that 35bb83b is the first bad commit.

Turns out it's not evaluation, it's the prettyprinter.

[brianhuffman]

Profiling shows that function layoutWadlerLeijen.best from module Prettyprinter.Internal is where almost all the runtime is spent. The number of entries is in the hundreds of millions.

[brianhuffman]

It appears that the exponential slowdown can be eliminated by replacing layoutSmart with layoutPretty in src/Cryptol/Utils/PP.hs. I'm not sure whether this leads to any undesirable differences in printed output.