haskell-prettyprinter / haskell-prettyprinter/prettyprinter

Exponential runtime for layoutSmart + fillSep + sep

Open
#205 4 comments 0 reactions 0 assignees View on GitHub
Bug Performance
Dominant language
Haskell
Stars
309
Forks
43
Avg merge
21h 25m
Merged PRs (30d)
1

Description

This issue is based on GaloisInc/cryptol#1274. The story is that we recently ported our `cryptol` language interpreter to use `prettyprinter`, but later we noticed a severe slowdown that occurs when we print a list of tuples of any significant length. Below is a minimized example based on our pretty-printing code.
```
import Prettyprinter
import Prettyprinter.Render.String

main :: IO ()
main = putStrLn (renderString (layoutSmart defaultLayoutOptions d))
where d = fillSep (replicate 30 (sep [pretty "abc", pretty "xyz"]))
```
The above program takes about 7 seconds to run on my machine. The run-time is exponential in the length of the list passed to `fillSep`: Incrementing from 30 to 31 doubles the run-time. 33 takes about a minute.

The exponential slowdown seems to occur only with `layoutSmart`; `layoutPretty` prints this example quickly at any size.

I did not expect `layoutSmart` to have exponential worst case behavior, as I assumed that this would have been mentioned in the documentation if it was known to be the case.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.