Unbox the `SetM` array (#528)
authorDavid Feuer <David.Feuer@gmail.com>
Tue, 6 Feb 2018 23:08:12 +0000 (18:08 -0500)
committerGitHub <noreply@github.com>
Tue, 6 Feb 2018 23:08:12 +0000 (18:08 -0500)
`Data.Graph` uses a mutable array to track which vertices have
been visited. This was implemented using an `STArray s Vertex Bool`.
This is obviously bad, because the garbage collector will have to
trace the array if it's alive during a collection. Using an unboxed
array instead should always be better. Indeed, doing so will also
dramatically reduce the size of the array, from the number of
vertices in the graph to that divided by the word size. Each array
operation is slightly more complex, but we'll surely win from
memory locality and such anyway.

Data/Graph.hs

index 5e4c6b0..a02a262 100644 (file)
@@ -72,7 +72,7 @@ module Data.Graph(
 -- Extensions
 #if USE_ST_MONAD
 import Control.Monad.ST
-import Data.Array.ST (STArray, newArray, readArray, writeArray)
+import Data.Array.ST (STUArray, newArray, readArray, writeArray)
 #else
 import Data.IntSet (IntSet)
 import qualified Data.IntSet as Set
@@ -372,7 +372,7 @@ chop (Node v ts : us)
 
 -- Use the ST monad if available, for constant-time primitives.
 
-newtype SetM s a = SetM { runSetM :: STArray s Vertex Bool -> ST s a }
+newtype SetM s a = SetM { runSetM :: STUArray s Vertex Bool -> ST s a }
 
 instance Monad (SetM s) where
     return = pure