Optimize scc as hard as possible

[treeowl]

I don't know what can be done here, but GHC uses it, and that makes it a top Data.Graph priority.

[jwaldmann]

The implementation is literally (?) from (e.g.,) Cormen, Leiserson, Rivest: Introduction to Algorithms, Section 23.5 (ninth edition), and O(vertices + edges) is optimal. So this is about the hidden constant factor?

Is there reason to believe that this is critical for GHC? (does scc show up in profiles?)

Does GHC really use Data.Graph? E.g., https://gitlab.haskell.org/ghc/ghc/-/blob/master/compiler/GHC/Data/Graph/Directed.hs seems like a copy/re-implementation. But, yes:

import qualified Data.Graph as G
...
scc :: IntGraph -> [SCC Vertex]
scc graph = map decode forest
  where
    forest = {-# SCC "Digraph.scc" #-} G.scc graph
    ...

So, let's look at these profiles...

[treeowl]

Good point.

[meooow25]

Yes it would be good to know how much time GHC spends in scc.

If we want to improve it we could implement and see if Tarjan's or path-based algorithm (from Wikipedia: https://en.wikipedia.org/wiki/Strongly_connected_component#Algorithms) have a lower constant factor.