Lift constructor tag allocation out of a loop

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



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
which is basically about using a map and constructing it outside the

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

On a file with 10k constructors

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


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

Diff Detail

rGHC Glasgow Haskell Compiler
Automatic diff as part of commit; lint not applicable.
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.


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


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


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.


Similarly, can't you do this in pcDataCon?


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)


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.