Exponential runtime for layoutSmart + fillSep + sep

[brianhuffman]

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.

[sjakobi]

Many thanks for the report. I'll take a closer look when I'm back from my vacation. I should check whether the changes introduced in v1.5 or later caused a regression. brianhuffman ***@***.***> schrieb am Fr., 3. Sept. 2021, 01:12:

…

This issue is based on GaloisInc/cryptol#1274 <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. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#205>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AA36VC5FOWV4LFW2TUVTB3DUAAAGLANCNFSM5DKFGWEQ> . Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.

[sjakobi]

Indeed this appears to be a regression: Bisection leads to 9635a5d. I'll continue investigating this soon.

[sjakobi]

I suspect the problem is that the x in SLine i' x is forced too eagerly here:

prettyprinter/prettyprinter/src/Prettyprinter/Internal.hs

Lines 2000 to 2008 in 6cafb52

	Line -> let x = best i i ds
	-- Don't produce indentation if there's no
	-- following text on the same line.
	-- This prevents trailing whitespace.
	i' = case x of
	SEmpty -> 0
	SLine{} -> 0
	_ -> i
	in SLine i' x

I wonder whether making SLine lazy in the first Int field might be sufficient to fix the issue…

EDIT: I should look at a Core diff.

EDIT 2: Why exactly is only layoutSmart affected?

[quchen]

For solving this issue: Promising find. Making SLine non-strict sounds like a plan. I think it’s always been strict, maybe I added it in order to avoid the pathological »foldl (+) chain of + evaluations« performance pitfall, but that case does not seem to be very relevant in practice, we’re not stacking hundreds of line breaks in practice, certainly not to the extend that they would overflow. (We could also liberally+selectively seq most things that go into SLine later again).

The bigger picture: Trimming whitespace in postprocessing might not be such a bad idea after all. Whitespace trimming is the reason for multiple hacks and complications, making everything much more complicated, especially when annotations come into play.