edges 0.10 → 0.11

raw patch · 8 files changed

+76/−78 lines, 8 filesdep +cereal-vectordep +data-dworddep +vector-th-unboxdep ~deferred-foldsPVP ok

version bump matches the API change (PVP)

Dependencies added: cereal-vector, data-dword, vector-th-unbox

Dependency ranges changed: deferred-folds

API changes (from Hackage documentation)

Files

• edges.cabal +8/−5
• library/Edges/Cereal/Get.hs +1/−2
• library/Edges/Cereal/Put.hs +2/−2
• library/Edges/Functions.hs +8/−8
• library/Edges/NodeCounting.hs +19/−47
• library/Edges/Prelude.hs +37/−5
• library/Edges/Types.hs +1/−1
• test/Main.hs +0/−8

@@ -1,5 +1,5 @@ name: edges-version: 0.10+version: 0.11 category: Graphs synopsis: Tools for efficient immutable graphs description: A set of tools for constructing immutable graphs which are both memory and performance-efficient.@@ -15,7 +15,7 @@  library   hs-source-dirs: library-  default-extensions: Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, OverloadedLists, PatternGuards, PatternSynonyms, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeApplications, TypeFamilies, TypeOperators, UnboxedTuples+  default-extensions: Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, InstanceSigs, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, OverloadedLists, PatternGuards, PatternSynonyms, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeApplications, TypeFamilies, TypeOperators, UnboxedTuples   default-language: Haskell2010   exposed-modules:     Edges.Data@@ -37,9 +37,11 @@   build-depends:     base >=4.7 && <5,     cereal >=0.5.5 && <0.6,+    cereal-vector >=0.2.0.1 && <0.3,     contravariant >=1.4 && <2,+    data-dword >=0.3.1.2 && <0.4,     deepseq >=1.4 && <2,-    deferred-folds >=0.6 && <0.7,+    deferred-folds >=0.6.12 && <0.7,     foldl >=1.4.2 && <2,     hashable >=1.2 && <2,     monad-par >=0.3.4.8 && <0.4,@@ -53,13 +55,14 @@     semigroupoids >=5.2 && <6,     text >=1 && <2,     unordered-containers >=0.2 && <0.3,-    vector >=0.12 && <0.13+    vector >=0.12 && <0.13,+    vector-th-unbox >=0.2.1.6 && <0.3  test-suite test   type: exitcode-stdio-1.0   hs-source-dirs: test   main-is: Main.hs-  default-extensions: Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, OverloadedLists, PatternGuards, PatternSynonyms, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeApplications, TypeFamilies, TypeOperators, UnboxedTuples+  default-extensions: Arrows, BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, InstanceSigs, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, OverloadedLists, PatternGuards, PatternSynonyms, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, TemplateHaskell, TupleSections, TypeApplications, TypeFamilies, TypeOperators, UnboxedTuples   default-language: Haskell2010   build-depends:     cereal,

@@ -9,8 +9,7 @@   nodeCounts :: Get (NodeCounts entity)-nodeCounts =-  NodeCounts <$> PrimArray.cerealGetAsInMemory get+nodeCounts = NodeCounts <$> get  edges :: Get (Edges a b) edges = do

@@ -9,8 +9,8 @@   nodeCounts :: Putter (NodeCounts entity)-nodeCounts (NodeCounts pa) =-  PrimArray.cerealPutAsInMemory put pa+nodeCounts (NodeCounts vector) =+  put vector  edges :: Putter (Edges a b) edges (Edges targetSpaceValue mpaValue) = targetSpace <> mpa where

@@ -62,17 +62,17 @@   Edges bAmount $ runIdentity $ PrimMultiArray.create aAmount $ \ fold ->   Identity $ Foldl.fold fold foldable -nodeCountsList :: NodeCounts entity -> [Word64]-nodeCountsList (NodeCounts pa) = foldrPrimArray' (:) [] pa+nodeCountsList :: NodeCounts entity -> [Word128]+nodeCountsList (NodeCounts vector) = UnboxedVector.foldr (:) [] vector -nodeCountsUnboxedVector :: NodeCounts entity -> UnboxedVector.Vector Word64-nodeCountsUnboxedVector (NodeCounts pa) = PrimArray.toUnboxedVector pa+nodeCountsUnboxedVector :: NodeCounts entity -> UnboxedVector.Vector Word128+nodeCountsUnboxedVector (NodeCounts vector) = vector -unindexNodeCounts :: (Eq entity, Hashable entity) => (Int -> Maybe entity) -> NodeCounts entity -> HashMap entity Int-unindexNodeCounts lookup (NodeCounts pa) = let+unindexNodeCounts :: (Eq entity, Hashable entity) => (Int -> Maybe entity) -> NodeCounts entity -> HashMap entity Word128+unindexNodeCounts lookup (NodeCounts vector) = let   unfold = do-    index <- Unfold.intsInRange 0 (pred (sizeofPrimArray pa))+    index <- Unfold.intsInRange 0 (pred (UnboxedVector.length vector))     return $ do       entity <- lookup index-      return (entity, fromIntegral (indexPrimArray pa index))+      return (entity, fromIntegral (UnboxedVector.unsafeIndex vector index))   in Unfold.fold (Foldl.hashMapByMapMaybe id) unfold

@@ -4,7 +4,6 @@   Node,   Amount,   Edges,-  node,   nodeTargets,   targets, )@@ -19,24 +18,18 @@ import qualified PrimitiveExtras.TVarArray as TVarArray import qualified DeferredFolds.UnfoldM as UnfoldM import qualified Data.Vector.Unboxed as UnboxedVector-import qualified Control.Monad.Par.IO as Par-import qualified Control.Monad.Par as Par hiding (runParIO)+import qualified Data.Vector.Unboxed.Mutable as MutableUnboxedVector  -node :: Edges source target -> Node source -> NodeCounts source-node edges = -  nodeWithAmount (edgesSourceAmount edges)--nodeWithAmount :: Amount entity -> Node entity -> NodeCounts entity-nodeWithAmount (Amount size) (Node index) =-  NodeCounts (PrimArray.oneHot size index 1)- nodeTargets :: Edges source target -> Node source -> NodeCounts target-nodeTargets (Edges targetAmount edgesPma) (Node sourceIndex) =-  let indexUnfold = fmap fromIntegral (PrimMultiArray.toUnfoldAtM edgesPma sourceIndex)-      indexFold = PrimArray.indexCountsFold targetAmount-      countPa = UnfoldM.fold indexFold indexUnfold-      in NodeCounts countPa+nodeTargets (Edges targetAmount edgesPma) (Node sourceIndex) = do+  unsafePerformIO $ do+    targetCountsMVec <- MutableUnboxedVector.new targetAmount+    UnfoldM.forM_ (fmap fromIntegral $ PrimMultiArray.toUnfoldAtM edgesPma sourceIndex) $ \ targetIndex -> do+      targetCount <- MutableUnboxedVector.read targetCountsMVec targetIndex+      MutableUnboxedVector.unsafeWrite targetCountsMVec targetIndex (targetCount + 1)+    targetCountsVec <- UnboxedVector.unsafeFreeze targetCountsMVec+    return (NodeCounts targetCountsVec)  {-| Count the occurrences of targets based on the occurrences of sources.@@ -50,35 +43,14 @@ This function can be used to reduce the amount of computation by excluding the nodes, which don't make much difference. -}-targetsWithMinSourceAmount :: Word64 -> Edges source target -> NodeCounts source -> NodeCounts target-targetsWithMinSourceAmount minSourceCount (Edges targetAmount edgesPma) (NodeCounts sourceCountsPa) =+targetsWithMinSourceAmount :: Word128 -> Edges source target -> NodeCounts source -> NodeCounts target+targetsWithMinSourceAmount minSourceCount (Edges targetAmount edgesPma) (NodeCounts sourceCountsVec) =   unsafePerformIO $ do-    targetCountsMpa <- newPrimArray targetAmount-    forMInAscendingRange_ 0 (sizeofPrimArray sourceCountsPa) $ \ sourceIndex -> let-      sourceCount = indexPrimArray sourceCountsPa sourceIndex-      in if sourceCount >= minSourceCount-        then UnfoldM.forM_ (fmap fromIntegral $ PrimMultiArray.toUnfoldAtM edgesPma sourceIndex) $ \ targetIndex -> do-          targetCount <- readPrimArray targetCountsMpa targetIndex-          writePrimArray targetCountsMpa targetIndex (targetCount + sourceCount)-        else return ()-    targetCountsPa <- unsafeFreezePrimArray targetCountsMpa-    return (NodeCounts targetCountsPa)--{-|-Count the occurrences of targets based on the occurrences of sources.--Utilizes parallellism.--}-targetsParallelly :: Edges source target -> NodeCounts source -> NodeCounts target-targetsParallelly (Edges targetAmount edgesPma) (NodeCounts sourceCountsPa) =-  unsafePerformIO $ Par.runParIO $ do-    targetCountVarTable <- liftIO (TVarArray.new 0 targetAmount)-    Par.parFor (Par.InclusiveRange 0 (pred (sizeofPrimArray sourceCountsPa))) $ \ sourceIndex ->-      case indexPrimArray sourceCountsPa sourceIndex of-        0 -> return ()-        sourceCount ->-          liftIO $-          UnfoldM.forM_ (PrimMultiArray.toUnfoldAtM edgesPma sourceIndex) $ \ targetIndex ->-          TVarArray.modifyAt targetCountVarTable (fromIntegral targetIndex) (+ sourceCount)-    targetCountsPa <- liftIO (TVarArray.freezeAsPrimArray targetCountVarTable)-    return (NodeCounts targetCountsPa)+    targetCountsMVec <- MutableUnboxedVector.new targetAmount+    flip UnboxedVector.imapM_ sourceCountsVec $ \ sourceIndex sourceCount -> if sourceCount >= minSourceCount+      then UnfoldM.forM_ (fmap fromIntegral $ PrimMultiArray.toUnfoldAtM edgesPma sourceIndex) $ \ targetIndex -> do+        targetCount <- MutableUnboxedVector.read targetCountsMVec targetIndex+        MutableUnboxedVector.unsafeWrite targetCountsMVec targetIndex (targetCount + sourceCount)+      else return ()+    targetCountsVec <- UnboxedVector.unsafeFreeze targetCountsMVec+    return (NodeCounts targetCountsVec)

@@ -5,7 +5,6 @@   modifyTVar',   forMInAscendingRange_,   forMInDescendingRange_,-  (.),   showText,   -- * Optics   Lens,@@ -24,7 +23,7 @@ ------------------------- import Control.Applicative as Exports import Control.Arrow as Exports-import Control.Category as Exports hiding ((.))+import Control.Category as Exports import Control.Concurrent as Exports import Control.Exception as Exports import Control.Monad as Exports hiding (mapM_, sequence_, forM_, msum, mapM, sequence, forM)@@ -148,7 +147,16 @@ ------------------------- import Control.DeepSeq as Exports +-- data-dword+-------------------------+import Data.DoubleWord as Exports++-- cereal-vector+-------------------------+import Data.Vector.Serialize ()+ import qualified Data.Vector.Unboxed as UnboxedVector+import qualified Data.Vector.Unboxed.Deriving as UnboxedVectorDeriving  type UnboxedVector = UnboxedVector.Vector @@ -158,9 +166,6 @@     x <- readTVar var     writeTVar var $! f x -(.) :: Semigroupoid s => s b c -> s a b -> s a c-(.) = o- {-# INLINE forMInAscendingRange_ #-} forMInAscendingRange_ :: Applicative m => Int -> Int -> (Int -> m a) -> m () forMInAscendingRange_ !startN !endN f =@@ -200,3 +205,30 @@ {-# INLINE _Just #-} _Just :: Prism' (Maybe a) a _Just = prism Just (maybe (Left Nothing) Right)+++-- * Instances for unboxed vectors+-------------------------++UnboxedVectorDeriving.derivingUnbox "Word96"+  [t| Word96 -> (Word32, Word64) |]+  [| \ (Word96 a b) -> (a, b) |]+  [| \ (a, b) -> Word96 a b |]++UnboxedVectorDeriving.derivingUnbox "Word128"+  [t| Word128 -> (Word64, Word64) |]+  [| \ (Word128 a b) -> (a, b) |]+  [| \ (a, b) -> Word128 a b |]++UnboxedVectorDeriving.derivingUnbox "Word256"+  [t| Word256 -> (Word128, Word128) |]+  [| \ (Word256 a b) -> (a, b) |]+  [| \ (a, b) -> Word256 a b |]+++-- * Instances for "cereal"+-------------------------++instance Serialize Word96+instance Serialize Word128+instance Serialize Word256

@@ -10,7 +10,7 @@  newtype Node entity = Node Int -newtype NodeCounts entity = NodeCounts (PrimArray Word64)+newtype NodeCounts entity = NodeCounts (UnboxedVector Word128)  newtype EdgeCounts source target = EdgeCounts (PrimArray Word64) 

@@ -46,14 +46,6 @@             node = Node 1 :: Node (Proxy 1)             in               [-                testCase "0, unoptimized" $ let-                  nodeCountsList = NodeCounting.node edges1 node & Data.nodeCountsList-                  in assertEqual (show nodeCountsList) [0, 1, 0] nodeCountsList-                ,-                testCase "1, unoptimized" $ let-                  nodeCountsList = NodeCounting.node edges1 node & NodeCounting.targets edges1 & Data.nodeCountsList-                  in assertEqual (show nodeCountsList) [1, 1, 0] nodeCountsList-                ,                 testCase "1" $ let                   nodeCountsList = NodeCounting.nodeTargets edges1 node & Data.nodeCountsList                   in assertEqual (show nodeCountsList) [1, 1, 0] nodeCountsList