|
|
#+title: Adventures in GHC build times
|
|
|
#+author: doyougnu
|
|
|
#+date: <2021-07-09 Fri>
|
|
|
|
|
|
* What
|
|
|
This page serves as a central repository for the effort to track and improve
|
|
|
GHC compiler performance, where performance in this context specifically means
|
|
|
build times. I (Jeff) will try to track ideas, issues, and relevant merge
|
|
|
requests for future work as well.
|
|
|
|
|
|
* Ideas
|
|
|
|
|
|
** IntMap becomes unbalanced
|
|
|
|
|
|
*** Hypothesis
|
|
|
~IntMap~ is used throughout the compiler, typically storing ~Unique~ for
|
|
|
keys. The idea here is that the ~IntMap~ is becoming very unbalanced. While
|
|
|
this isn't a problem in and of itself because under the hood ~IntMap~'s are
|
|
|
Patricia trie in specific cases if the keys share a long prefix of bits
|
|
|
then the spine of the tree needs to be rebuilt for every insertion, thus
|
|
|
leading to performance degradation. See [[https://gitlab.haskell.org/ghc/ghc/-/issues/19820#note_351497][this comment]] for a more precise
|
|
|
discussion.
|
|
|
|
|
|
*** Status
|
|
|
Unconfirmed. In progress, working on [[*Courses of Action][novel intmap implementation]]
|
|
|
|
|
|
*** Evidence
|
|
|
To gather evidence that the unbalancing is happening we need to either
|
|
|
inspect the heap or print the trees during a build. Any other ideas
|
|
|
appreciated.
|
|
|
|
|
|
*** The Fix
|
|
|
The current ~Unique~ implementation is big endian, i.e., it stores the "key"
|
|
|
in the most significant bits of an ~Int~. There are several paths forward:
|
|
|
|
|
|
1. hash the keys to make the probability of a long prefix more unlikely
|
|
|
thereby increasing
|
|
|
2. move the keys to little endian to observe a difference
|
|
|
|
|
|
*** Relevant Issues
|
|
|
- https://gitlab.haskell.org/ghc/ghc/-/issues/19820
|
|
|
- https://gitlab.haskell.org/ghc/ghc/-/issues/18541#note_292432 see Sylvain
|
|
|
Henry's comment on ~IntMap.lookup~
|
|
|
- https://github.com/haskell/containers/pull/340#issuecomment-610400875
|
|
|
|
|
|
*** Relevant Merge Requests
|
|
|
(1) has been tried in [[https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5068][!5068]] by [[https://gitlab.haskell.org/sgraf812][@sgraf812]], who implemented the key hash but
|
|
|
didn't fix compilation errors
|
|
|
|
|
|
*** Courses of Action
|
|
|
1. Retrieve direct evidence of the tree becoming unbalanced
|
|
|
2. Revive [[https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5068][!5068]], fix the compilation errors and benchmark
|
|
|
3. Create a patch with [[https://github.com/haskell/containers/pull/340][novel IntMap implementation]] and benchmark
|
|
|
4. Use a mutable map for the bits of the compiler which are already in IO.
|
|
|
This hasn't been tried but would be a significant change as we would have
|
|
|
to add the ~hashtables~ package as a boot or core library (not sure
|
|
|
which). Although [[https://github.com/haskell-perf/dictionaries][benchmarks by Chris Done]] indicate a 1000x speedup over
|
|
|
pure IntMap's.
|
|
|
5. Ed Kmett has also experimented with Clojure-style RRB trees in his [[https://github.com/ekmett/transients][here]].
|
|
|
The implementation is unfinished and there are no benchmarks. We could
|
|
|
finish the implementation, benchmark it against the standard ~IntMap~, if
|
|
|
it looks good then patch it into the compiler and benchmark.
|
|
|
|
|
|
** IntMap ~lookup~ performs allocation
|
|
|
|
|
|
*** Hypothesis
|
|
|
IntMap lookup performs allocation due to the key being specialized in its
|
|
|
definition. See SPJ's breakdown [[https://gitlab.haskell.org/ghc/ghc/-/issues/20069][here]].
|
|
|
|
|
|
*** Status
|
|
|
Confirmed without direct evidence.
|
|
|
|
|
|
*** Evidence
|
|
|
By inspection of source code. Also noticed in [[https://gitlab.haskell.org/ghc/ghc/-/issues/18541#note_292432][this comment]], however not
|
|
|
confirmed with direct evidence. See Sebastian's [[https://gitlab.haskell.org/ghc/ghc/-/issues/20069#note_362952][comment]] about the ~go~
|
|
|
closure.
|
|
|
|
|
|
*** The Fix
|
|
|
Sylvain Henry has a patch [[https://gitlab.haskell.org/ghc/ghc/-/issues/18541#note_292432][here]] but only tested the intmap-benchmarks.
|
|
|
|
|
|
*** Relevant Issues
|
|
|
- https://gitlab.haskell.org/ghc/ghc/-/issues/19820 The low-hanging fruit
|
|
|
issue kicked off by Richard Eisenberg's ticky ticky profile.
|
|
|
- https://gitlab.haskell.org/ghc/ghc/-/issues/18541#note_292432 see Sylvain
|
|
|
Henry's comment on ~IntMap.lookup~
|
|
|
- https://gitlab.haskell.org/ghc/ghc/-/issues/20069 SPJ's IntMap issue
|
|
|
|
|
|
*** Relevant Merge Requests
|
|
|
|
|
|
*** Relevant Patches
|
|
|
- see https://gitlab.haskell.org/ghc/ghc/-/issues/18541#note_292432
|
|
|
|
|
|
*** Courses of Action
|
|
|
- Implement and benchmark Sylvain Henry's patch, benchmark it for building
|
|
|
entire packages not just the intmap-benchmark
|
|
|
|
|
|
|
|
|
** Avoid allocations in substitutions in the simplifier
|
|
|
|
|
|
*** Hypothesis
|
|
|
Benchmarking indicates that a large amount of allocations occur in the
|
|
|
simplifier. We should seek to understand why that is the case.
|
|
|
|
|
|
*** Status
|
|
|
Unexplored
|
|
|
|
|
|
*** Evidence
|
|
|
|
|
|
*** The Fix
|
|
|
|
|
|
*** Relevant Issues
|
|
|
- [[https://gitlab.haskell.org/ghc/ghc/-/issues/19537][Opportunity for increased sharing during substitution]]
|
|
|
- [[https://gitlab.haskell.org/ghc/ghc/-/issues/19538][Annotating Core to avoid unnecessary traversal of large subexpressions]]
|
|
|
|
|
|
*** Relevant Merge Requests
|
|
|
- Sylvain Henry implemented a fix only in ~Tidy~ in [[https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5267][!5267]] but there is a bug
|
|
|
and some variables aren't correctly renamed leading to test failures.
|
|
|
|
|
|
*** Relevant Patches
|
|
|
|
|
|
*** Courses of Action
|
|
|
1. Read through [[https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5267][!5267]]
|
|
|
2. Fix [[https://gitlab.haskell.org/ghc/ghc/-/merge_requests/5267][!5267]] benchmark it. Try it out in ~GHC.Core.substExpr~ and
|
|
|
~GHC.Core.TyCo.Subst~
|
|
|
|
|
|
** Optimize the pretty printing during code generation
|
|
|
|
|
|
*** Hypothesis
|
|
|
Code generation is a significant chunk of compile time. According to Matt
|
|
|
Pickering some pretty printing functions perform a lot of allocation during
|
|
|
this phase which leads to a slow down.
|
|
|
|
|
|
*** Status
|
|
|
Unexplored
|
|
|
|
|
|
*** Evidence
|
|
|
|
|
|
*** The Fix
|
|
|
We'll need to optimize pretty printing. Exactly what needs optimization, and
|
|
|
how is to be determined.
|
|
|
|
|
|
*** Relevant Issues
|
|
|
|
|
|
*** Relevant Merge Requests
|
|
|
|
|
|
*** Relevant Patches
|
|
|
|
|
|
*** Courses of Action
|
|
|
1. benchmark pretty printing during code generation to identify candidate
|
|
|
functions for optimization.
|
|
|
2. Ticky profile these functions to get some hard evidence.
|
|
|
|
|
|
* Knowledge Sharing
|
|
|
It would be nice to know:
|
|
|
|
|
|
** Is every IntMap necessary?
|
|
|
- Consider this passage from Richard Eisenberg, in ghc-devs Vol215 issue 5:
|
|
|
#+begin_quote
|
|
|
One piece I'm curious about, reading this thread: why do we have so many IntMaps
|
|
|
and operations on them? Name lookup is a fundamental operation a compiler must
|
|
|
do, and that would use an IntMap: good. But maybe there are other IntMaps used
|
|
|
that are less necessary. A key example: whenever we do substitution, we track an
|
|
|
InScopeSet, which is really just an IntMap. This InScopeSet remembers the name
|
|
|
of all variables in scope, useful when we need to create a new variable name
|
|
|
(this is done by uniqAway). Yet perhaps the tracking of these in-scope variables
|
|
|
is very expensive and comprises much of the IntMap time. Might it be better just
|
|
|
to always work in a monad capable of giving fresh names? We actually don't even
|
|
|
need a monad, if that's too annoying. Instead, we could just pass around an
|
|
|
infinite list of fresh uniques. This would still be clutterful, but if it grants
|
|
|
us a big speed improvement, the clutter might be worth it.
|
|
|
|
|
|
The high-level piece here is that there may be good things that come from
|
|
|
understanding where these IntMaps arise.
|
|
|
#+end_quote |