[GHC] #14657: Quadratic constructor tag allocation
#14657: Quadratic constructor tag allocation -------------------------------------+------------------------------------- Reporter: niteria | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: Keywords: | Operating System: Unknown/Multiple Architecture: | Type of failure: Compile-time Unknown/Multiple | performance bug Test Case: | Blocked By: genManyConstructors | Blocking: | Related Tickets: Differential Rev(s): phab:D4289 | Wiki Page: -------------------------------------+------------------------------------- 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 -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14657> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14657: Quadratic constructor tag allocation -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | genManyConstructors Blocked By: | Blocking: Related Tickets: | Differential Rev(s): phab:D4289 Wiki Page: | -------------------------------------+------------------------------------- Changes (by niteria): * owner: (none) => niteria -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14657#comment:1> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14657: Quadratic constructor tag allocation -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | genManyConstructors Blocked By: | Blocking: Related Tickets: | Differential Rev(s): phab:D4289 Wiki Page: | -------------------------------------+------------------------------------- Comment (by Bartosz Nitka <niteria@…>): In [changeset:"dbdf77d92c9cd0bbb269137de0bf8754573cdc1e/ghc" dbdf77d/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="dbdf77d92c9cd0bbb269137de0bf8754573cdc1e" 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 }}} -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14657#comment:2> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
#14657: Quadratic constructor tag allocation -------------------------------------+------------------------------------- Reporter: niteria | Owner: niteria Type: bug | Status: closed Priority: normal | Milestone: Component: Compiler | Version: Resolution: fixed | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: Compile-time | Test Case: performance bug | genManyConstructors Blocked By: | Blocking: Related Tickets: | Differential Rev(s): phab:D4289 Wiki Page: | -------------------------------------+------------------------------------- Changes (by niteria): * status: new => closed * resolution: => fixed -- Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/14657#comment:3> GHC <http://www.haskell.org/ghc/> The Glasgow Haskell Compiler
participants (1)
-
GHC