unordered-containers 0.2.3.0 → 0.2.3.1
raw patch · 6 files changed
+85/−99 lines, 6 filesdep +hashmap
Dependencies added: hashmap
Files
- Data/HashMap/Array.hs +11/−1
- Data/HashMap/Base.hs +5/−56
- Data/HashMap/Strict.hs +1/−17
- Data/HashSet.hs +2/−23
- benchmarks/Benchmarks.hs +64/−1
- unordered-containers.cabal +2/−1
Data/HashMap/Array.hs view
@@ -52,10 +52,20 @@ import Control.Applicative (Applicative) import Control.DeepSeq import Control.Monad.ST hiding (runST)-import GHC.Exts+-- GHC 7.7 exports toList/fromList from GHC.Exts+-- In order to avoid warnings on previous GHC versions, we provide+-- an explicit import list instead of only hiding the offending symbols+import GHC.Exts (Array#, Int(..), newArray#, readArray#, writeArray#,+ indexArray#, unsafeFreezeArray#, unsafeThawArray#,+ MutableArray#) import GHC.ST (ST(..)) import Prelude hiding (filter, foldr, length, map, read) import qualified Prelude++#if __GLASGOW_HASKELL__ >= 702+import GHC.Exts (sizeofArray#, copyArray#, thawArray#, sizeofMutableArray#,+ copyMutableArray#)+#endif import Data.HashMap.Unsafe (runST)
Data/HashMap/Base.hs view
@@ -79,11 +79,13 @@ import Control.DeepSeq (NFData(rnf)) import Control.Monad.ST (ST) import Data.Bits ((.&.), (.|.), complement)+import Data.Data hiding (Typeable) import qualified Data.Foldable as Foldable import qualified Data.List as L import Data.Monoid (Monoid(mempty, mappend)) import Data.Traversable (Traversable(..)) import Data.Word (Word)+import GHC.Exts ((==#), build, reallyUnsafePtrEquality#) import Prelude hiding (filter, foldr, lookup, map, null, pred) import qualified Data.HashMap.Array as A@@ -94,11 +96,6 @@ import Data.HashMap.UnsafeShift (unsafeShiftL, unsafeShiftR) import Data.Typeable (Typeable) -#if defined(__GLASGOW_HASKELL__)-import Data.Data hiding (Typeable)-import GHC.Exts ((==#), build, reallyUnsafePtrEquality#)-#endif- ------------------------------------------------------------------------ -- | Convenience function. Compute a hash value for the given value.@@ -143,7 +140,6 @@ mappend = union {-# INLINE mappend #-} -#if __GLASGOW_HASKELL__ instance (Data k, Data v, Eq k, Hashable k) => Data (HashMap k v) where gfoldl f z m = z fromList `f` toList m toConstr _ = fromListConstr@@ -158,7 +154,6 @@ hashMapDataType :: DataType hashMapDataType = mkDataType "Data.HashMap.Base.HashMap" [fromListConstr]-#endif type Hash = Word type Bitmap = Word@@ -237,14 +232,12 @@ member k m = case lookup k m of Nothing -> False Just _ -> True-#if __GLASGOW_HASKELL__ >= 700-{-# INLINEABLE member #-}-#endif+{-# INLINABLE member #-} -- | /O(log n)/ Return the value to which the specified key is mapped, -- or 'Nothing' if this map contains no mapping for the key. lookup :: (Eq k, Hashable k) => k -> HashMap k v -> Maybe v-lookup k0 = go h0 k0 0+lookup k0 m0 = go h0 k0 0 m0 where h0 = hash k0 go !_ !_ !_ Empty = Nothing@@ -259,9 +252,7 @@ go h k _ (Collision hx v) | h == hx = lookupInArray k v | otherwise = Nothing-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE lookup #-}-#endif -- | /O(log n)/ Return the value to which the specified key is mapped, -- or the default value if this map contains no mapping for the key.@@ -336,9 +327,7 @@ go h k x s t@(Collision hy v) | h == hy = Collision h (updateOrSnocWith const k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t)-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insert #-}-#endif -- | In-place update version of insert unsafeInsert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v@@ -373,9 +362,7 @@ go h k x s t@(Collision hy v) | h == hy = return $! Collision h (updateOrSnocWith const k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t)-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE unsafeInsert #-}-#endif -- | Create a map from two key-value pairs which hashes don't collide. two :: Shift -> Hash -> k -> v -> Hash -> k -> v -> ST s (HashMap k v)@@ -436,9 +423,7 @@ go h k x s t@(Collision hy v) | h == hy = Collision h (updateOrSnocWith f k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t)-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insertWith #-}-#endif -- | In-place update version of insertWith unsafeInsertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v@@ -472,9 +457,7 @@ go h k x s t@(Collision hy v) | h == hy = return $! Collision h (updateOrSnocWith f k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t)-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE unsafeInsertWith #-}-#endif -- | /O(log n)/ Remove the mapping for the specified key from this map -- if present.@@ -529,14 +512,12 @@ | otherwise -> Collision h (A.delete v i) Nothing -> t | otherwise = t-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE delete #-}-#endif -- | /O(log n)/ Adjust the value tied to a given key in this map only -- if it is present. Otherwise, leave the map alone. adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v-adjust f k0 = go h0 k0 0+adjust f k0 m0 = go h0 k0 0 m0 where h0 = hash k0 go !_ !_ !_ Empty = Empty@@ -560,9 +541,7 @@ go h k _ t@(Collision hy v) | h == hy = Collision h (updateWith f k v) | otherwise = t-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE adjust #-}-#endif ------------------------------------------------------------------------ -- * Combine@@ -571,9 +550,7 @@ -- mapping from the first will be the mapping in the result. union :: (Eq k, Hashable k) => HashMap k v -> HashMap k v -> HashMap k v union = unionWith const-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE union #-}-#endif -- | /O(n+m)/ The union of two maps. If a key occurs in both maps, -- the provided function (first argument) will be used to compute the@@ -744,9 +721,7 @@ go m k v = case lookup k b of Nothing -> insert k v m _ -> m-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE difference #-}-#endif -- | /O(n*log m)/ Intersection of two maps. Return elements of the first -- map for keys existing in the second.@@ -756,9 +731,7 @@ go m k v = case lookup k b of Just _ -> insert k v m _ -> m-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE intersection #-}-#endif -- | /O(n+m)/ Intersection of two maps. If a key occurs in both maps -- the provided function is used to combine the values from the two@@ -770,9 +743,7 @@ go m k v = case lookup k b of Just w -> insert k (f v w) m _ -> m-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE intersectionWith #-}-#endif ------------------------------------------------------------------------ -- * Folds@@ -921,28 +892,20 @@ -- | /O(n)/ Return a list of this map's elements. The list is -- produced lazily. toList :: HashMap k v -> [(k, v)]-#if defined(__GLASGOW_HASKELL__) toList t = build (\ c z -> foldrWithKey (curry c) z t)-#else-toList = foldrWithKey (\ k v xs -> (k, v) : xs) []-#endif {-# INLINE toList #-} -- | /O(n)/ Construct a map with the supplied mappings. If the list -- contains duplicate mappings, the later mappings take precedence. fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v fromList = L.foldl' (\ m (k, v) -> unsafeInsert k v m) empty-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE fromList #-}-#endif -- | /O(n*log n)/ Construct a map from a list of elements. Uses -- the provided function to merge duplicate entries. fromListWith :: (Eq k, Hashable k) => (v -> v -> v) -> [(k, v)] -> HashMap k v fromListWith f = L.foldl' (\ m (k, v) -> unsafeInsertWith f k v m) empty-#if __GLASGOW_HASKELL__ >= 700 {-# INLINE fromListWith #-}-#endif ------------------------------------------------------------------------ -- Array operations@@ -958,9 +921,7 @@ (L kx v) | k == kx -> Just v | otherwise -> go k ary (i+1) n-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE lookupInArray #-}-#endif -- | /O(n)/ Lookup the value associated with the given key in this -- array. Returns 'Nothing' if the key wasn't found.@@ -973,9 +934,7 @@ (L kx _) | k == kx -> Just i | otherwise -> go k ary (i+1) n-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE indexOf #-}-#endif updateWith :: Eq k => (v -> v) -> k -> A.Array (Leaf k v) -> A.Array (Leaf k v) updateWith f k0 ary0 = go k0 ary0 0 (A.length ary0)@@ -985,9 +944,7 @@ | otherwise = case A.index ary i of (L kx y) | k == kx -> A.update ary i (L k (f y)) | otherwise -> go k ary (i+1) n-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateWith #-}-#endif updateOrSnocWith :: Eq k => (v -> v -> v) -> k -> v -> A.Array (Leaf k v) -> A.Array (Leaf k v)@@ -1003,9 +960,7 @@ | otherwise = case A.index ary i of (L kx y) | k == kx -> A.update ary i (L k (f v y)) | otherwise -> go k v ary (i+1) n-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateOrSnocWith #-}-#endif updateOrConcatWith :: Eq k => (v -> v -> v) -> A.Array (Leaf k v) -> A.Array (Leaf k v) -> A.Array (Leaf k v) updateOrConcatWith f ary1 ary2 = A.run $ do@@ -1033,9 +988,7 @@ go (iEnd+1) (i2+1) go n1 0 return mary-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateOrConcatWith #-}-#endif ------------------------------------------------------------------------ -- Manually unrolled loops@@ -1118,9 +1071,5 @@ -- | Check if two the two arguments are the same value. N.B. This -- function might give false negatives (due to GC moving objects.) ptrEq :: a -> a -> Bool-#if defined(__GLASGOW_HASKELL__) ptrEq x y = reallyUnsafePtrEquality# x y ==# 1#-#else-ptrEq _ _ = False-#endif {-# INLINE ptrEq #-}
Data/HashMap/Strict.hs view
@@ -120,9 +120,7 @@ -- the key, the old value is replaced. insert :: (Eq k, Hashable k) => k -> v -> HashMap k v -> HashMap k v insert k !v = HM.insert k v-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insert #-}-#endif -- | /O(log n)/ Associate the value with the key in this map. If -- this map previously contained a mapping for the key, the old value@@ -162,9 +160,7 @@ go h k x s t@(Collision hy v) | h == hy = Collision h (updateOrSnocWith f k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t)-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insertWith #-}-#endif -- | In-place update version of insertWith unsafeInsertWith :: (Eq k, Hashable k) => (v -> v -> v) -> k -> v -> HashMap k v@@ -198,14 +194,12 @@ go h k x s t@(Collision hy v) | h == hy = return $! Collision h (updateOrSnocWith f k x v) | otherwise = go h k x s $ BitmapIndexed (mask hy s) (A.singleton t)-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE unsafeInsertWith #-}-#endif -- | /O(log n)/ Adjust the value tied to a given key in this map only -- if it is present. Otherwise, leave the map alone. adjust :: (Eq k, Hashable k) => (v -> v) -> k -> HashMap k v -> HashMap k v-adjust f k0 = go h0 k0 0+adjust f k0 m0 = go h0 k0 0 m0 where h0 = hash k0 go !_ !_ !_ Empty = Empty@@ -229,9 +223,7 @@ go h k _ t@(Collision hy v) | h == hy = Collision h (updateWith f k v) | otherwise = t-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE adjust #-}-#endif ------------------------------------------------------------------------ -- * Combine@@ -356,9 +348,7 @@ go m k v = case HM.lookup k b of Just w -> insert k (f v w) m _ -> m-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE intersectionWith #-}-#endif ------------------------------------------------------------------------ -- ** Lists@@ -368,9 +358,7 @@ -- precedence. fromList :: (Eq k, Hashable k) => [(k, v)] -> HashMap k v fromList = L.foldl' (\ m (k, v) -> HM.unsafeInsert k v m) empty-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE fromList #-}-#endif -- | /O(n*log n)/ Construct a map from a list of elements. Uses -- the provided function to merge duplicate entries.@@ -389,9 +377,7 @@ | otherwise = case A.index ary i of (L kx y) | k == kx -> let !v' = f y in A.update ary i (L k v') | otherwise -> go k ary (i+1) n-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateWith #-}-#endif updateOrSnocWith :: Eq k => (v -> v -> v) -> k -> v -> A.Array (Leaf k v) -> A.Array (Leaf k v)@@ -407,6 +393,4 @@ | otherwise = case A.index ary i of (L kx y) | k == kx -> let !v' = f v y in A.update ary i (L k v') | otherwise -> go k v ary (i+1) n-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE updateOrSnocWith #-}-#endif
Data/HashSet.hs view
@@ -60,20 +60,17 @@ ) where import Control.DeepSeq (NFData(..))+import Data.Data hiding (Typeable) import Data.HashMap.Base (HashMap, foldrWithKey) import Data.Hashable (Hashable) import Data.Monoid (Monoid(..))+import GHC.Exts (build) import Prelude hiding (filter, foldr, map, null) import qualified Data.Foldable as Foldable import qualified Data.HashMap.Lazy as H import qualified Data.List as List import Data.Typeable (Typeable) -#if defined(__GLASGOW_HASKELL__)-import Data.Data hiding (Typeable)-import GHC.Exts (build)-#endif- -- | A set of values. A set cannot contain duplicate values. newtype HashSet a = HashSet { asMap :: HashMap a ()@@ -103,7 +100,6 @@ showsPrec d m = showParen (d > 10) $ showString "fromList " . shows (toList m) -#if __GLASGOW_HASKELL__ instance (Data a, Eq a, Hashable a) => Data (HashSet a) where gfoldl f z m = z fromList `f` toList m toConstr _ = fromListConstr@@ -118,7 +114,6 @@ hashSetDataType :: DataType hashSetDataType = mkDataType "Data.HashSet" [fromListConstr]-#endif -- | /O(1)/ Construct an empty set. empty :: HashSet a@@ -127,9 +122,7 @@ -- | /O(1)/ Construct a set with a single element. singleton :: Hashable a => a -> HashSet a singleton a = HashSet (H.singleton a ())-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE singleton #-}-#endif -- | /O(n+m)/ Construct a set containing all elements from both sets. --@@ -162,24 +155,18 @@ member a s = case H.lookup a (asMap s) of Just _ -> True _ -> False-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE member #-}-#endif -- | /O(min(n,W))/ Add the specified value to this set. insert :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a insert a = HashSet . H.insert a () . asMap-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE insert #-}-#endif -- | /O(min(n,W))/ Remove the specified value from this set if -- present. delete :: (Eq a, Hashable a) => a -> HashSet a -> HashSet a delete a = HashSet . H.delete a . asMap-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE delete #-}-#endif -- | /O(n)/ Transform this set by applying a function to every value. -- The resulting set may be smaller than the source.@@ -191,17 +178,13 @@ -- not existing in the second. difference :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a difference (HashSet a) (HashSet b) = HashSet (H.difference a b)-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE difference #-}-#endif -- | /O(n)/ Intersection of two sets. Return elements present in both -- the first set and the second. intersection :: (Eq a, Hashable a) => HashSet a -> HashSet a -> HashSet a intersection (HashSet a) (HashSet b) = HashSet (H.intersection a b)-#if __GLASGOW_HASKELL__ >= 700 {-# INLINABLE intersection #-}-#endif -- | /O(n)/ Reduce this set by applying a binary operator to all -- elements, using the given starting value (typically the@@ -231,11 +214,7 @@ -- | /O(n)/ Return a list of this set's elements. The list is -- produced lazily. toList :: HashSet a -> [a]-#if defined(__GLASGOW_HASKELL__) toList t = build (\ c z -> foldrWithKey ((const .) c) z (asMap t))-#else-toList = foldrWithKey (\ k _ xs -> k : xs) [] . asMap-#endif {-# INLINE toList #-} -- | /O(n*min(W, n))/ Construct a set from a list of elements.
benchmarks/Benchmarks.hs view
@@ -1,4 +1,4 @@-{-# LANGUAGE CPP, GADTs #-}+{-# LANGUAGE CPP, GADTs, PackageImports #-} module Main where @@ -10,6 +10,7 @@ import Data.Bits ((.&.)) import Data.Hashable (Hashable) import qualified Data.ByteString as BS+import qualified "hashmap" Data.HashMap as IHM import qualified Data.HashMap.Strict as HM import qualified Data.IntMap as IM import qualified Data.Map as M@@ -40,6 +41,8 @@ m = M.fromList elems :: M.Map String Int mbs = M.fromList elemsBS :: M.Map BS.ByteString Int im = IM.fromList elemsI :: IM.IntMap Int+ ihm = IHM.fromList elems :: IHM.Map String Int+ ihmbs = IHM.fromList elemsBS :: IHM.Map BS.ByteString Int defaultMainWith defaultConfig (liftIO . evaluate $ rnf [B m, B mbs, B hm, B hmbs, B hmi, B im]) [@@ -80,6 +83,42 @@ ] ] + -- ** Map from the hashmap package+ , bgroup "hashmap/Map"+ [ bgroup "lookup"+ [ bench "String" $ whnf (lookupIHM keys) ihm+ , bench "ByteString" $ whnf (lookupIHM keysBS) ihmbs+ ]+ , bgroup "lookup-miss"+ [ bench "String" $ whnf (lookupIHM keys') ihm+ , bench "ByteString" $ whnf (lookupIHM keysBS') ihmbs+ ]+ , bgroup "insert"+ [ bench "String" $ whnf (insertIHM elems) IHM.empty+ , bench "ByteStringString" $ whnf (insertIHM elemsBS) IHM.empty+ ]+ , bgroup "insert-dup"+ [ bench "String" $ whnf (insertIHM elems) ihm+ , bench "ByteStringString" $ whnf (insertIHM elemsBS) ihmbs+ ]+ , bgroup "delete"+ [ bench "String" $ whnf (deleteIHM keys) ihm+ , bench "ByteString" $ whnf (deleteIHM keysBS) ihmbs+ ]+ , bgroup "delete-miss"+ [ bench "String" $ whnf (deleteIHM keys') ihm+ , bench "ByteString" $ whnf (deleteIHM keysBS') ihmbs+ ]+ , bgroup "size"+ [ bench "String" $ whnf IHM.size ihm+ , bench "ByteString" $ whnf IHM.size ihmbs+ ]+ , bgroup "fromList"+ [ bench "String" $ whnf IHM.fromList elems+ , bench "ByteString" $ whnf IHM.fromList elemsBS+ ]+ ]+ -- ** IntMap , bgroup "IntMap" [ bench "lookup" $ whnf (lookupIM keysI) im@@ -259,6 +298,30 @@ {-# SPECIALIZE deleteM :: [String] -> M.Map String Int -> M.Map String Int #-} {-# SPECIALIZE deleteM :: [BS.ByteString] -> M.Map BS.ByteString Int -> M.Map BS.ByteString Int #-}++------------------------------------------------------------------------+-- * Map from the hashmap package++lookupIHM :: (Eq k, Hashable k, Ord k) => [k] -> IHM.Map k Int -> Int+lookupIHM xs m = foldl' (\z k -> fromMaybe z (IHM.lookup k m)) 0 xs+{-# SPECIALIZE lookupIHM :: [String] -> IHM.Map String Int -> Int #-}+{-# SPECIALIZE lookupIHM :: [BS.ByteString] -> IHM.Map BS.ByteString Int+ -> Int #-}++insertIHM :: (Eq k, Hashable k, Ord k) => [(k, Int)] -> IHM.Map k Int+ -> IHM.Map k Int+insertIHM xs m0 = foldl' (\m (k, v) -> IHM.insert k v m) m0 xs+{-# SPECIALIZE insertIHM :: [(String, Int)] -> IHM.Map String Int+ -> IHM.Map String Int #-}+{-# SPECIALIZE insertIHM :: [(BS.ByteString, Int)] -> IHM.Map BS.ByteString Int+ -> IHM.Map BS.ByteString Int #-}++deleteIHM :: (Eq k, Hashable k, Ord k) => [k] -> IHM.Map k Int -> IHM.Map k Int+deleteIHM xs m0 = foldl' (\m k -> IHM.delete k m) m0 xs+{-# SPECIALIZE deleteIHM :: [String] -> IHM.Map String Int+ -> IHM.Map String Int #-}+{-# SPECIALIZE deleteIHM :: [BS.ByteString] -> IHM.Map BS.ByteString Int+ -> IHM.Map BS.ByteString Int #-} ------------------------------------------------------------------------ -- * IntMap
unordered-containers.cabal view
@@ -1,5 +1,5 @@ name: unordered-containers-version: 0.2.3.0+version: 0.2.3.1 synopsis: Efficient hashing-based container types description: Efficient hashing-based container types. The containers have been@@ -154,6 +154,7 @@ criterion, deepseq >= 1.1, hashable >= 1.0.1.1,+ hashmap, mtl, random