changesUponFlattening can be slow

[sjakobi]

In dhall-lang/dhall-haskell#1496 (comment) Gabriel describes a case where rendering a type error takes multiple seconds.

You can reproduce the issue with the following command, after adding a type error, for example by removing the Some on this line.

$ dhall type --file stable/jenkins/index.dhall --explain

These are the top cost centers:

COST CENTRE               MODULE                                SRC                                                            %time %alloc

getDecodeAction           Codec.CBOR.Decoding                   src/Codec/CBOR/Decoding.hs:311:1-55                             27.1   34.8
changesUponFlattening     Data.Text.Prettyprint.Doc.Internal    src/Data/Text/Prettyprint/Doc/Internal.hs:(553,1)-(591,21)      19.3   22.6
prettyCharacterSet        Dhall.Pretty.Internal                 src/Dhall/Pretty/Internal.hs:(502,1)-(1139,62)                   6.5    5.1
renderLazy                Data.Text.Prettyprint.Doc.Render.Text src/Data/Text/Prettyprint/Doc/Render/Text.hs:59:1-92             6.5    6.1
deserialiseIncremental    Codec.CBOR.Read                       src/Codec/CBOR/Read.hs:(165,1)-(167,46)                          4.7    3.5

Note that changesUponFlattening takes nearly 20% of the time!

So I had a closer look at this function and noticed this case:

https://github.com/quchen/prettyprinter/blob/7da3b1d32f8a74efb3bcf1b2d062f8f24a64c918/prettyprinter/src/Data/Text/Prettyprint/Doc/Internal.hs#L556

Union is introduced by group which dhall apparently uses a lot: the same profile contains over 600000 entries for group!

https://github.com/quchen/prettyprinter/blob/7da3b1d32f8a74efb3bcf1b2d062f8f24a64c918/prettyprinter/src/Data/Text/Prettyprint/Doc/Internal.hs#L526-L530

So I wondered: If changesUponFlattening is only used by group, and the Union constructor is also only introduced by group, why does changesUponFlattening have to scrutinize it at all? So I tried this change:

-    Union x _       -> changesUponFlattening x <|> Just x
+    Union x _       -> Just x

This shaves about 18% off the total time when profiling and about 42% when using the unprofiled executable (and I'm not sure where that difference comes from)!

Unfortunately it also breaks the fusion property tests, which now fail with the classic

»SFail« must not appear in a rendered »SimpleDocStream«. This is a bug in the layout algorithm! Please report this as a bug

I haven't figured out yet quite how it breaks fuse though!

[sjakobi]

Unfortunately it also breaks the fusion property tests, which now fail with the classic

I must have confused this with #91 somehow. I can't reproduce this using #96 and #98.