Specialise: Avoid unnecessary recomputation of free variable information
ClosedPublic

Authored by bgamari on Jun 23 2015, 5:01 PM.

Details

Summary

When examining compile times for code with large ADTs (particularly those with
many record constructors), I found that the specialiser contributed
disproportionately to the compiler runtime. Some profiling suggested that
the a great deal of time was being spent in pair_fvs being called from
consDictBind.

@simonpj pointed out that flattenDictBinds as called by specBind was
unnecessarily discarding cached free variable information, which then needed to
be recomputed by pair_fvs.

Here I refactor the specializer to retain the free variable cache whenever
possible.

Open Qustions

  • I used fst in a couple of places to extract the bindings from a DictBind. Perhaps this is a sign that DictBind has outgrown its type synonym status?
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.
bgamari updated this revision to Diff 3323.Jun 23 2015, 5:01 PM
bgamari retitled this revision from to Specialise: Avoid unnecessary recomputation of free variable information.
bgamari updated this object.
bgamari edited the test plan for this revision. (Show Details)
bgamari added reviewers: simonpj, austin.
bgamari updated the Trac tickets for this revision.
bgamari added a subscriber: simonpj.
bgamari planned changes to this revision.Jun 23 2015, 5:36 PM

Hmm, looks like I fail. Not entirely sure what's happening here. Tomorrow is another day.

simonpj added inline comments.Jun 23 2015, 6:02 PM
compiler/specialise/Specialise.hs
1026

Use snocDictBind. And make final_binds into final_bind. There is always just one!

1265

Better: make bindAuxiliaryDicts return a DictBind not a CoreBind.

@simonpj, did you notice any particular reason why this might be dropping bindings (as caught by CoreLint during validation)?

compiler/specialise/Specialise.hs
1019

@simonpj, this alternative will result in more than one bind, no?

1026

I'm not entirely sure that this is true. See above.

1265

Ahh, a lovely point. I guess this whole DictBind business was a later addition?

simonpj edited edge metadata.Jun 24 2015, 3:00 AM

@simonpj, did you notice any particular reason why this might be dropping bindings (as caught by CoreLint during validation)?

I'm afraid not! I think you need to do a bit of tracing or something

compiler/specialise/Specialise.hs
1019

You're right; I mis-read the list comprehension

bgamari updated this revision to Diff 3325.Jun 24 2015, 5:50 AM
bgamari edited edge metadata.
  • bindAuxiliaryDicts now returns DictBinds
  • Debug
bgamari updated this revision to Diff 3349.Jun 28 2015, 11:10 AM
  • Specialise: Comments
  • bindAuxiliaryDicts now returns DictBinds
  • Debug
  • Account for free-variable information of other bindings
bgamari updated this revision to Diff 3350.Jun 28 2015, 11:14 AM
  • Kill debug output
  • Fix line length
bgamari updated this revision to Diff 3352.Jun 28 2015, 11:41 AM
  • Specialise: Avoid unnecessary recomputation of free variable information
  • Specialise: Comments
  • bindAuxiliaryDicts now returns DictBinds
  • Debug
  • Account for free-variable information of other bindings
  • Kill debug output
  • Fix line length

I spotted the issue: I never computed the free variables of the second set of bindings passed to flattenDictBinds. If all goes well, this patch should now validate.

simonpj accepted this revision.Jun 29 2015, 2:17 AM
simonpj edited edge metadata.

I'm not sure what you missed the first time, but it all looks fine to me.

Let's see: this fixes some non-linear behaviour somewhere doesn't it? Worth saying this in the commit message. Unusually, I'm not sure it's worth commenting in the code, because it flows quite naturally.

Simon

This revision is now accepted and ready to land.Jun 29 2015, 2:17 AM

I've added some compiler performance comparisons to Trac #7450. Things aren't quite linear yet but they are substantially better.

This revision was automatically updated to reflect the committed changes.

I've done a bit more benchmarking on the impact of this. The result can be found on #9669 comment #13.