Fix quadratic behavior of prepareAlts
ClosedPublic

Authored by niteria on Jan 14 2018, 4:08 PM.

Details

Summary

This code is quadratic and a simple test case I used
managed to tickle it.

The example (same one as Trac #14667) looks like this:

module A10000 where

 data A = A
   | A00001
   | A00002
 ...
   | A10000

 f :: A -> Int
 f A00001 = 19900001
 f A00002 = 19900002
 ...
 f A10000 = 19910000

Applied on top of a fix for Trac #14667, it gives a 30% compile time
improvement.

Test Plan

./validate

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.
niteria created this revision.Jan 14 2018, 4:08 PM

Looks good, thank you.

compiler/coreSyn/CoreUtils.hs
660

...so we can use UniqSet rather than Set (more efficient)

niteria added inline comments.Jan 15 2018, 4:10 AM
compiler/coreSyn/CoreUtils.hs
660

I'm not sure if you're suggesting I change anything:
(1) the comment
(2) try to refactor filterAlts to use UniqSet

simonpj added inline comments.Jan 15 2018, 4:19 AM
compiler/coreSyn/CoreUtils.hs
660

I was just suggesting an extra bit to the comment, because I stumbled on "why are there two different kinds of sets used here?".

niteria added inline comments.Jan 15 2018, 5:04 AM
compiler/coreSyn/CoreUtils.hs
660

Makes sense, will do, thanks!

bgamari requested changes to this revision.Jan 15 2018, 10:35 AM

Bumping out of review queue.

This revision now requires changes to proceed.Jan 15 2018, 10:35 AM
This revision was automatically updated to reflect the committed changes.