#14657 closed bug (fixed)

Quadratic constructor tag allocation

Reported by: niteria Owned by: niteria
Priority: normal Milestone:
Component: Compiler Version:
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Compile-time performance bug Test Case: genManyConstructors
Blocked By: Blocking:
Related Tickets: Differential Rev(s): phab:D4289
Wiki Page:

Description

With a large data type like:

data A = A0
  | A0001
  | A0002
...
  | A9999

GHC spends a lot of time allocating constructor tags. It accounts for half of allocations for large data types like this.

The hot piece of code is in mkDataCon:

   tag = assoc "mkDataCon" (tyConDataCons rep_tycon `zip` [fIRST_TAG..]) con

Previous discussion: https://mail.haskell.org/pipermail/ghc-devs/2017-October/014974.html

Change History (3)

comment:1 Changed 20 months ago by niteria

Owner: set to niteria

comment:2 Changed 20 months ago by Bartosz Nitka <niteria@…>

In dbdf77d/ghc:

Lift constructor tag allocation out of a loop

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)

Reviewers: simonpj, bgamari

Reviewed By: simonpj

Subscribers: goldfire, rwbarton, thomie, simonmar, carter, simonpj

GHC Trac Issues: #14657

Differential Revision: https://phabricator.haskell.org/D4289

comment:3 Changed 20 months ago by niteria

Resolution: fixed
Status: newclosed
Note: See TracTickets for help on using tickets.