kadena-io
Improve FloydWarshall
We use the Floyd-Warshall algorithm to calculate the diameter of chain graphs. This is mostly useful for testing, since in production, we would use known, fixed-diameter graphs.
massiv is employed in implementing the Data.DiGraph.FloydWarshall module, and its usage can be improved in a few ways.
Maximize Laziness
type DenseAdjMatrix = Array U Ix2 Int
fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix
fromAdjacencySets g = makeArray Seq (n :. n) go
where go = ...
As much as possible, we want our Array types to have the internal representation of D or DW. This avoids memory allocation until the last possible moment. When we do force them, asking for U, P, or S are generally equivalent (at least for our purposes).
floydWarshall :: Array U Ix2 Double -> Array U Ix2 Double
shortestPaths :: Array U Ix2 Int -> Array U Ix2 Double
shortestPaths = floydWarshall . computeAs U . distMatrix
Since everything is being forced as U here, a lot of extra memory is being allocated. computeAs should only be used:
- At the very end of a composition of matrix operations, or;
- Before doing a
Stencil-based operation (like convolution, etc.)
Generally, for non-Stencil ops, there should always be a way to do everything lazily (via D) until the very end.
Parallelism
At least in test environments, we can assume graph sizes of > 1000 nodes. This means a Matrix of at least 1000x1000. In my experience with Massiv, for any Matrix over 256x256, using the Par evaluation strategy quickly becomes worthwhile.
fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix
fromAdjacencySets g = makeArray Seq (n :. n) go -- should be `Par`!
Then, when compiled/ran with the correct RTS ops, we get performance boosts for free.
Stencils
The implementation of the floydWarshall function in particular allocates a new Array for each interation, which means n unnecessary allocations are occuring, where n is the width/length of the Array. Glancing at the code, it seems like this could just be rewritten as a Stencil operation and done in a single pass.
IntMap / IntSet
type AdjacencySets = HM.HashMap Int (HS.HashSet Int)
Could this be rewritten in terms of IntMap and IntSet? fromAdjacencySets uses a lot of lookup and member calls, and the Int-based structures can perform these operations about twice as fast as the hash-based ones.
➤ Lars Kuhtz commented:
When we have time it would be nice to do some benchmarks and see the effect of the different changes. I am particularly curious about the effect of adding laziness. It's not immediately obvious to me that it always pays off the delay forcing computations as much as possible, but I don't know enough about the inner workings of massiv.
➤ Lars Kuhtz commented:
👍 for using IntMap IntSet in place of HM.HashMap Int (HS.HashSet Int).
➤ Colin Woodbury commented:
I am particularly curious about the effect of adding laziness.
It's less GHC laziness and more Massiv's internal "Delayed" representation. Using D properly improves performance drastically, especially when computed with parallelism.
IntMap IntSet
This would be fine, except in how an AdjacencySets type is come upon in Data.DiGraph:
newtype DiGraph a = DiGraph { unGraph :: HM.HashMap a (HS.HashSet a) }
diameter ::Eq a => Hashable a => DiGraph a -> Maybe Natural diameter g = FW.diameter $ FW.fromAdjacencySets (unGraph ig) where vmap = HM.fromList $ zip (HS.toList $ vertices g) [0..] ig = mapVertices (vmap HM.!) gNotice the call to unGraph. The DiGraph newtype would have to be reworked (perhaps with a type family?) to allow for a different internal representation, or we'd have to eat the cost of converting the preexisting HashMap/HashSets into their Int forms.
➤ Lars Kuhtz commented:
type AdjacencySets = HM.HashMap Int (HS.HashSet Int)
This type is actually only used to convert between DiGraph and the matrix representation. So, it has to be precisely this type. It's not used for any computation.
➤ Colin Woodbury commented:
It does seem to be used:
fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix fromAdjacencySets g = makeArray Seq (n :. n) go where n = HM.size g go (i :. j) | isEdge (i, j) = 1 | isEdge (j, i) = 1 | otherwise = 0 isEdge (a, b) = maybe False (HS.member b) $ HM.lookup a gIn isEdge.
➤ Lars Kuhtz commented:
fromAdjacencySets :: AdjacencySets -> DenseAdjMatrix
That's just the conversion function between the DiGraph representation and the the representation that is used in the Floyd-Warshall algorithm.
I don't think that first converting to IntMap IntSet would speed up things.
➤ Colin Woodbury commented:
Exactly, if DiGraph needs the signature that it currently has, then we'd waste time converting to IntMap IntSet anyway.
As per discussion with Lars - keep issue, but not a high priority / technical debt
I accidentally stumbled upon this issue and though I could give a suggestion with regards to:
The implementation of the floydWarshall function in particular allocates a new Array for each interation, which means n unnecessary allocations are occuring, where n is the width/length of the Array.
There is a fairly new function in massiv that solves exactly this problem: iterateUntil Let me know if you have any questions on its usage.
