Lift constructor tag allocation out of a loop
ClosedPublic

Authored by niteria on Jan 5 2018, 11:08 AM.

Details

Summary

Before this change, for each constructor that we want
to allocate a tag for we would traverse a list of all
the constructors in a datatype to determine which tag
a constructor should get.

This is obviously quadratic and for datatypes with 10k
constructors it actually makes a big difference.

This change implements the plan outlined by @simonpj in
https://mail.haskell.org/pipermail/ghc-devs/2017-October/014974.html
which is basically about using a map and constructing it outside the
loop.

One place where things got a bit awkward was TysWiredIn.hs,
it would have been possible to just assign the tags by hand, but
that seemed error-prone to me, so I decided to go through a map
there as well.

Test Plan

./validate
On a file with 10k constructors
Before:

 8,130,522,344 bytes allocated in the heap                          
Total   time    3.682s  (  3.920s elapsed)

After:

 4,133,478,744 bytes allocated in the heap                          
Total   time    2.509s  (  2.750s elapsed)

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 5 2018, 11:08 AM
niteria edited the summary of this revision. (Show Details)Jan 5 2018, 11:09 AM
niteria edited the test plan for this revision. (Show Details)Jan 5 2018, 12:34 PM
niteria updated this revision to Diff 15036.Jan 5 2018, 1:22 PM
niteria edited the test plan for this revision. (Show Details)

add a test

simonpj accepted this revision.Jan 9 2018, 5:41 PM

A few suggestions, notably to clean up TysWiredIn. But looks good thanks.

compiler/iface/BuildTyCl.hs
111

Comment -- Maps the Name of each DataCon to its ConTag

131

Add a Note to explain the point of all this ;refer to the ticket. (If there isn't a ticket, make one :-)

compiler/prelude/TysWiredIn.hs
1106

Why not put this code into pcSpecialTyCon? Every time, the tag-map arg is just mkTyConTagMap tc where tc is the preceding tycon arg. Nothing is gained by this duplication.

1273

Similarly, can't you do this in pcDataCon?

compiler/typecheck/TcTyClsDecls.hs
1694–1696

This is the key bit: calling mkTyConTagMap here pays the tag-allocation cost once per TyCon rather than once per datacon. Worth pointing out!! (And refer to the ticket)

testsuite/tests/perf/compiler/genManyConstructors
2

Add comments to explain how this test works and what the data type looks like

This revision is now accepted and ready to land.Jan 9 2018, 5:41 PM
niteria updated the Trac tickets for this revision.Jan 10 2018, 4:53 AM
niteria marked 6 inline comments as done.Jan 10 2018, 6:15 AM
This revision was automatically updated to reflect the committed changes.