Skip to content
  • niteria's avatar
    Lift constructor tag allocation out of a loop · dbdf77d9
    niteria authored
    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
    dbdf77d9