Should dfs be lazy?

[treeowl]

The original paper we base Data.Graph on expects lazy ST, but we use strict ST. Depending how the result is consumed, lazier might be better. For ordered traversals (producing lists rather than trees/forests), we can use strict ST along with unsafeInterleaveST, which may be faster.

[treeowl]

@meooow25 , you might want to experiment with this.

[meooow25]

I assume you mean something like your #882 (comment)? I'll try it out.

[treeowl]

Yeah, something like that for the listy ones (if it's not too slow). I'm a bit more skeptical about dfs itself (which needs lazy ST); we'll need benchmarks with different consumption patterns. The worst case scenario for that descends only the last tree in each forest.

[treeowl]

Is there some actual reason for topSort to be defined in terms of a postorder and not a preorder? Wouldn't it be more efficient to just define it as a preorder (no reverse)? That would produce a somewhat different ordering, but I think it would still obey the specification.

[treeowl]

Oh, I see.... No.

[treeowl]

@meooow25 You had suggested

dfs_preOrder :: Graph -> [Vertex] -> [Vertex]
dfs_preOrder g vs0 = run (bounds g) $ go vs0 (pure [])
  where
    go :: [Vertex] -> SetM s [Vertex] -> SetM s [Vertex]
    go [] acc = acc
    go (v:vs) acc = do
      visited <- contains v
      if visited
      then go vs acc
      else do
        include v
        as <- go (g!v) (go vs acc)
        pure $ v : as

This turns out not to be so good, I suspect because of the way the accumulator ends up being represented. I had better luck with this more explicit stack representation:

dfs_preOrder :: Graph -> [Vertex] -> [Vertex]
dfs_preOrder g vs0 = run (bounds g) $ go vs0 []
  where
    go :: [Vertex] -> [[Vertex]] -> SetM s [Vertex]
    go [] [] = pure []
    go [] (x : xs) = go x xs
    go (v:vs) acc = do
      visited <- contains v
      if visited
      then go vs acc
      else do
        include v
        as <- go (g!v) (vs : acc)
        pure $ v : as

The lazy version I came up with is a little slower to force fully, which I find a bit disappointing, but it may end up faster in a more complex context.

lazy_dfs_preOrder :: Graph -> [Vertex] -> [Vertex]
lazy_dfs_preOrder g vs0 = run (bounds g) $ go vs0 []
  where
    go :: [Vertex] -> [[Vertex]] -> SetM s [Vertex]
    go [] [] = pure []
    go [] (x : xs) = go x xs
    go (v:vs) acc = do
      visited <- contains v
      if visited
      then go vs acc
      else do
        include v
        as <- unsafeInterleaveSetM (go (g!v) (vs : acc))
        pure $ v : as

unsafeInterleaveSetM :: SetM s a -> SetM s a
unsafeInterleaveSetM act = SetM $ \m -> unsafeInterleaveST (runSetM act m)
{-# INLINE unsafeInterleaveSetM #-}

[meooow25]

I tried to make the current dfs lazy and found the same thing, that it is slower to force fully.

dfs :: Graph -> [Vertex] -> Forest Vertex
dfs g vs0 = fst $ run (bounds g) $ go vs0
  where
    go :: [Vertex] -> SetM s (Forest Vertex, ())
    go [] = pure ([], ())
    go (v:vs) = do
      visited <- contains v
      if visited
      then go vs
      else do
        include v
        ~(as, adone) <- unsafeInterleaveSetM $ go (g!v)
        ~(bs, bdone) <- unsafeInterleaveSetM $ adone `seq` go vs
        pure (Node v as : bs, bdone)

  dfs
    n=100,m=1000:       OK (0.86s)
      9.76 μs ± 777 ns,  35 KB allocated,  52 B  copied, 216 MB peak memory, 98% more than baseline
    n=100,m=10000:      OK (0.55s)
      53.2 μs ± 2.7 μs,  35 KB allocated,  53 B  copied, 216 MB peak memory, 18% more than baseline
    n=10000,m=100000:   OK (0.29s)
      2.44 ms ± 207 μs, 3.6 MB allocated, 751 KB copied, 216 MB peak memory, 55% more than baseline
    n=100000,m=1000000: OK (1.88s)
      121  ms ± 3.1 ms,  36 MB allocated,  33 MB copied, 216 MB peak memory, 38% more than baseline

Is there a better way to make a lazy implementation? I haven't tried lazy ST yet, I've not used it before so I need to figure it out.

[treeowl]

You've basically faked up the internal machinery of lazy ST there. The real one is splattered with NOINLINEs to avoid certain safety issues and is not likely to be faster, though I guess we could check. Sigh.