Compute critical path

[Bodigrim]

Here is a build profile for https://hackage.haskell.org/package/streams:

Legend
  ▇  Downloading
  ▇  Starting
  ▇  Building
  ▇  Haddock
  ▇  Installing

Summary
  Wall time               : 1m56s
  Dependency sum time     : 4m35s
  Total dependencies      : 20
  Parallelism level       : 2.36
  Single block resolution : 634ms

Profile
unordered-containers-0.2.19.1 [33s648ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
                   free-5.1.9 [30s560ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
          semigroupoids-5.3.7 [24s502ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
            bifunctors-5.5.13 [23s326ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
            profunctors-5.6.2 [19s391ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
       th-abstraction-0.4.5.0 [19s375ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
    indexed-traversable-0.1.2 [16s914ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
             hashable-1.4.1.0 [15s459ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
    transformers-compat-0.7.2 [13s777ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
            adjunctions-4.4.2 [11s642ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
                comonad-5.0.8 [9s294ms ] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
               tagged-0.8.6.1 [9s206ms ] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
          contravariant-1.5.5 [8s873ms ] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
         distributive-0.6.2.1 [7s433ms ] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇
               StateVar-1.2.2 [5s886ms ] │ ▇▇▇▇▇▇▇▇▇▇▇
                   boring-0.2 [5s854ms ] │ ▇▇▇▇▇▇▇▇▇▇▇
              semigroups-0.20 [5s403ms ] │ ▇▇▇▇▇▇▇▇▇▇▇
      transformers-base-0.4.6 [5s292ms ] │ ▇▇▇▇▇▇▇▇▇▇
           base-orphans-0.8.7 [4s972ms ] │ ▇▇▇▇▇▇▇▇▇▇
                   void-0.7.3 [4s707ms ] │ ▇▇▇▇▇▇▇▇

This data looks like it's unordered-containers who is a bottleneck, and one could imagine that removing this dependency might decrease observed build times. But the truth is that unordered-containers is built in parallel with kmettoverse and do not contribute into the total wall clock time at all, so its removal would not make things faster.

We could make the output of dr-cabal more actionable by highlighting the critical path in the graph of dependencies, showing actual culprits of long compilation times. E. g.,

Legend
  ▇  Downloading
  ▇  Starting
  ▇  Building
  ▇  Haddock
  ▇  Installing
  *  Critical path

Summary
  Wall time               : 1m56s
  Dependency sum time     : 4m35s
  Total dependencies      : 20
  Parallelism level       : 2.36
  Single block resolution : 634ms

Profile
unordered-containers-0.2.19.1  [33s648ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
                   free-5.1.9* [30s560ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
          semigroupoids-5.3.7* [24s502ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
            bifunctors-5.5.13* [23s326ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
            profunctors-5.6.2  [19s391ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
       th-abstraction-0.4.5.0  [19s375ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
    indexed-traversable-0.1.2* [16s914ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
             hashable-1.4.1.0  [15s459ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
    transformers-compat-0.7.2  [13s777ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
            adjunctions-4.4.2* [11s642ms] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
                comonad-5.0.8* [9s294ms ] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
               tagged-0.8.6.1  [9s206ms ] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
          contravariant-1.5.5  [8s873ms ] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇▇▇
         distributive-0.6.2.1  [7s433ms ] │ ▇▇▇▇▇▇▇▇▇▇▇▇▇
               StateVar-1.2.2  [5s886ms ] │ ▇▇▇▇▇▇▇▇▇▇▇
                   boring-0.2  [5s854ms ] │ ▇▇▇▇▇▇▇▇▇▇▇
              semigroups-0.20  [5s403ms ] │ ▇▇▇▇▇▇▇▇▇▇▇
      transformers-base-0.4.6  [5s292ms ] │ ▇▇▇▇▇▇▇▇▇▇
           base-orphans-0.8.7  [4s972ms ] │ ▇▇▇▇▇▇▇▇▇▇
                   void-0.7.3  [4s707ms ] │ ▇▇▇▇▇▇▇▇

The sum of build times along the critical path is 30.560+24.502+23.326+16.914+11.642+9.294 = 116.238, precisely explaining the total wall time 1m56s.

I scribbled a quick-and-dirty implementation at https://github.com/Bodigrim/dr-cabal.

[chshersh]

Hey, @Bodigrim 👋🏻

This sounds like a good addition to the tool 🙂 You can even highlight those libraries in bold (in addition to *) to distinguish them better from others.

Maybe it's also possible to add a couple of words in the description of what is a critical path? I mostly wonder how users can use this information and what they can do to optimise their libs or dependencies 🤔

Also, could you write a short description of the algorithm for finding a critical path? Even better in the Haddock comment 💯
I guess I didn't have enough coffee this morning so it's a bit hard to follow 🥴

Otherwise, happy to merge it! 🚢