Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

changesUponFlattening can be slow #99

Closed
sjakobi opened this issue Nov 19, 2019 · 1 comment · Fixed by #116
Closed

changesUponFlattening can be slow #99

sjakobi opened this issue Nov 19, 2019 · 1 comment · Fixed by #116

Comments

@sjakobi
Copy link
Collaborator

sjakobi commented Nov 19, 2019

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:

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

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

group :: Doc ann -> Doc ann
-- See note [Group: special flattening]
group x = case changesUponFlattening x of
Nothing -> x
Just x' -> Union x' x

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
Copy link
Collaborator Author

sjakobi commented Nov 19, 2019

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.

sjakobi added a commit to sjakobi/prettyprinter that referenced this issue Nov 19, 2019
Since the first Union alternative was produced by the previous
call to to changesUponFlattening, it seems unnecessary to
scrutinize it again.

This speeds up some prettyprinter-heavy applications in dhall
by 20 to 42%.

This assumes some kind of idempotence in changesUponFlattening.

Fixes quchen#99.
sjakobi added a commit to sjakobi/prettyprinter that referenced this issue Nov 20, 2019
Since the first Union alternative was produced by the previous
call to to changesUponFlattening, it seems unnecessary to
scrutinize it again.

This speeds up some prettyprinter-heavy applications in dhall
by 20 to 42%.

This assumes some kind of idempotence in changesUponFlattening.

Fixes quchen#99.
sjakobi added a commit to sjakobi/prettyprinter that referenced this issue Jan 19, 2020
Since the first Union alternative was produced by the previous
call to to changesUponFlattening, it seems unnecessary to
scrutinize it again.

This speeds up some prettyprinter-heavy applications in dhall
by 20 to 42%.

This assumes some kind of idempotence in changesUponFlattening.

Fixes quchen#99.
sjakobi added a commit that referenced this issue Jan 22, 2020
The main idea of this patch is to represent `changesUponFlattening`'s
old `Nothing` result with two constructors:
One to indicate that the result is already flat enough, the other to indicate
that flattening is impossible, and which allows shortcuts.

This can noticeably speed up the layout of documents that heavily
that heavily use group.

Fixes #99, fixes #112.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant