Fix a performance issue with -fprint-expanded-synonyms
ClosedPublic

Authored by osa1 on May 11 2016, 2:26 PM.

Details

Summary

The type synonym expander was doing redundant work by looking at same types
again and again. This patch fixes the loop code when both of the types can be
expanded, to do O(min(n, m)) comparisons and O(n + m) expansions, where n
is expansions of the first type and m is expansions of the second type.

Reported by sjcjoosten in T10547.

Test Plan

Added a regression test that was taking several minutes to type check before
this patch.

Diff Detail

Repository
rGHC Glasgow Haskell Compiler
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.
osa1 retitled this revision from to Fix a performance issue with -fprint-expanded-synonyms.May 11 2016, 2:26 PM
osa1 edited the test plan for this revision. (Show Details)
osa1 updated the Trac tickets for this revision.
osa1 updated this object.
osa1 added a comment.May 11 2016, 2:28 PM

Apparently build bots are not working... Validating locally..

osa1 updated this revision to Diff 7527.May 11 2016, 3:02 PM
  • minor
bgamari accepted this revision.May 12 2016, 3:17 AM

Thanks for this, @osa1!

By how much does this improve things in the 15-type case? Might we be able to enable -fprint-expanded-synonyms by default now?

This revision is now accepted and ready to land.May 12 2016, 3:17 AM
osa1 updated this revision to Diff 7535.May 12 2016, 3:49 AM
  • implement ezyang's suggestion

TODO: Documentation needs updating

osa1 added a reviewer: ezyang.May 12 2016, 3:51 AM
osa1 updated this revision to Diff 7536.May 12 2016, 4:18 AM
  • reword docs.
osa1 added a comment.May 12 2016, 4:22 AM

I implemented @ezyang's suggestion which makes this even faster. @bgamari,
15-type case is pretty much instantaneous right now, I think it may be possible
to enable this by default.

I'll try enabling this on all should_fail tests of type checker to see how
it'll behave.

osa1 updated this revision to Diff 7539.May 12 2016, 7:07 AM
This comment was removed by osa1.
osa1 added a comment.May 12 2016, 7:08 AM

@ezyang, @bgamari unless you have any comments I think this is ready for landing. I tried enabling this on every should_fail typechecker test and it worked nicely, see https://ghc.haskell.org/trac/ghc/ticket/10547#comment:20.

osa1 updated this revision to Diff 7540.May 12 2016, 7:12 AM
  • fix sameShapes
simonpj accepted this revision.May 12 2016, 8:16 AM
simonpj added a reviewer: simonpj.
simonpj added a subscriber: simonpj.

Can yo make a perf test that fails with the old m*n algorithm?

More comments please!

But generally great. On by default is fine with me.

compiler/typecheck/TcErrors.hs
1824

Might you explain in more detail what is going on here??

1832

The code is compact but tricky. Can you give an example? Something like

type S a = T (a,a)
type T b = b -> Int

tyExpansions (S Bool) = [T (Bool,Bool), (Bool,Bool) -> Int]
osa1 updated this revision to Diff 7557.May 12 2016, 12:04 PM
  • improve docs for tyExpansions - give some examples
  • more comments
osa1 updated this revision to Diff 7558.May 12 2016, 2:08 PM
osa1 marked 2 inline comments as done.
  • make the regression test a perf test
osa1 updated this revision to Diff 7559.May 12 2016, 2:09 PM

(disabling lint to suppress noise)

osa1 added a comment.EditedMay 12 2016, 2:13 PM

@simonpj, I documented the parts you pointed, and added a perf test. How does it look?

I say let's make this default in another patch as it'll probably a lot of noise (need to update should_fail outputs).

ezyang accepted this revision.May 12 2016, 2:35 PM

Yes looks good. (I kind of want to bikeshed the message s/Type synonyms expanded/aka (with type synonyms expanded/ but whatever, it's clear enough).

austin accepted this revision.May 12 2016, 2:40 PM

Nice, look at that reduced allocation footprint!

osa1 updated this object.May 12 2016, 3:01 PM

Looking good. One suggestion -- but don't let me stand in the way of committing.

compiler/typecheck/TcErrors.hs
1819

...expand N times AT TOP LEVEL....

You have to say "at top level" several times; worth calling this out to explain what it means.

Also all this badly needs an example, which you have for tyExpansions.

If it were me I'd put both of these long comments in a Note and refer to the Note from here.. Then you could consolidate with a single example (or a couple).

I say let's make this default in another patch as it'll probably a lot of noise (need to update should_fail outputs).

Fine

osa1 updated this revision to Diff 7575.May 13 2016, 12:08 PM
  • reword comments
osa1 marked an inline comment as done.May 13 2016, 12:08 PM

I updated the comments once again. Can't we just look at tests for examples of how this should work? I added that to the documentation of expandSynonymsToMatch.

Fine.

(Tests are all very well, but the examples I mean are ones that help you understand the source code, what it seeks to achieve, and how it works. But I'm not going to labour the point if you think it's good as-is.)

compiler/typecheck/TcErrors.hs
1775

testsuite/tests/typecheck/should_fail

osa1 updated this revision to Diff 7578.May 13 2016, 4:08 PM
  • fix test path
osa1 marked an inline comment as done.May 13 2016, 4:10 PM
This revision was automatically updated to reflect the committed changes.