hashtables 1.0.1.6 → 1.0.1.7
raw patch · 9 files changed
+165/−101 lines, 9 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- benchmark/hashtable-benchmark.cabal +4/−3
- benchmark/src/Criterion/Collection/Internal/Types.hs +1/−1
- benchmark/src/Criterion/Collection/Sample.hs +1/−1
- benchmark/src/Main.hs +81/−27
- hashtables.cabal +2/−2
- src/Data/HashTable/Internal/CacheLine.hs +63/−62
- src/Data/HashTable/Internal/Utils.hs +10/−2
- src/Data/HashTable/ST/Basic.hs +1/−1
- test/hashtables-test.cabal +2/−2
benchmark/hashtable-benchmark.cabal view
@@ -1,5 +1,6 @@ Name: hashtable-benchmark-Version: 0.1+Version: 0.2+Copyright: (c) 2011-2012, Google, Inc. Synopsis: Benchmarks for hashtables License: BSD3 License-file: LICENSE@@ -18,8 +19,8 @@ build-depends: base == 4.*, base16-bytestring == 0.1.*,- bytestring == 0.9.*,- containers == 0.4.*,+ bytestring >= 0.9 && <0.11,+ containers >= 0.4 && <0.6, criterion >= 0.5 && <0.7, csv == 0.1.*, deepseq >= 1.1 && <1.4,
benchmark/src/Criterion/Collection/Internal/Types.hs view
@@ -60,7 +60,7 @@ -------------------------------------------------------------------------------data (NFData op) => Workload op = Workload {+data Workload op = Workload { -- | \"Setup work\" is work that you do to prepopulate a data structure -- to a certain size before testing begins. setupWork :: !(Vector op)
benchmark/src/Criterion/Collection/Sample.hs view
@@ -59,7 +59,7 @@ ++ ">" -------------------------------------------------------------------------------data (NFData op) => Benchmark op = Benchmark {+data Benchmark op = Benchmark { benchmarkName :: String , dataStructures :: [(String, DataStructure op)] , inputSizes :: [Int]
benchmark/src/Main.hs view
@@ -1,4 +1,6 @@-{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-}+{-# LANGUAGE GeneralizedNewtypeDeriving #-} module Main (main) where @@ -7,9 +9,11 @@ import Data.ByteString (ByteString) import qualified Data.ByteString.Base16 as B16 import Data.Hashable+import Data.IORef import Control.DeepSeq import Control.Monad import Control.Monad.ST+import Control.Monad.Trans import qualified Data.HashMap.Strict as UC import qualified Data.HashTable as H import qualified Data.Map as Map@@ -26,27 +30,29 @@ -------------------------------------------------------------------------------dataMap :: DataStructure (Operation ByteString)+dataMap :: (Ord k, Eq k) => DataStructure (Operation k) dataMap = setupData Map.empty f where f !m !op = case op of (Insert k v) -> let !m' = Map.insert k v m in m' (Lookup k) -> let !_ = Map.lookup k m in m (Delete k) -> let !m' = Map.delete k m in m'+{-# INLINE dataMap #-} -------------------------------------------------------------------------------hashMap :: DataStructure (Operation ByteString)+hashMap :: (Hashable k, Eq k) => DataStructure (Operation k) hashMap = setupData UC.empty f where f !m !op = case op of (Insert k v) -> let !m' = UC.insert k v m in m' (Lookup k) -> let !_ = UC.lookup k m in m (Delete k) -> let !m' = UC.delete k m in m'+{-# INLINE hashMap #-} -------------------------------------------------------------------------------hashTable :: DataStructure (Operation ByteString)+hashTable :: (Hashable k, Eq k) => DataStructure (Operation k) hashTable = setupDataIO (const (H.new (==) (toEnum . (.&. 0x7fffffff) . hash))) f where f !m !op = case op of@@ -57,10 +63,11 @@ (Delete k) -> do !_ <- H.delete m k return m+{-# INLINE hashTable #-} -------------------------------------------------------------------------------basicHashTable :: DataStructure (Operation ByteString)+basicHashTable :: (Hashable k, Eq k) => DataStructure (Operation k) basicHashTable = setupDataIO (IOH.newSized :: Int -> IO (IOH.BasicHashTable k v)) f where@@ -70,10 +77,11 @@ !_ <- IOH.lookup m k return m (Delete k) -> IOH.delete m k >> return m+{-# INLINE basicHashTable #-} ------------------------------------------------------------------------------- -cuckooHashTable :: DataStructure (Operation ByteString)+------------------------------------------------------------------------------+cuckooHashTable :: (Hashable k, Eq k) => DataStructure (Operation k) cuckooHashTable = setupDataIO (IOH.newSized :: Int -> IO (IOH.CuckooHashTable k v)) f where@@ -83,10 +91,11 @@ !_ <- IOH.lookup m k return m (Delete k) -> IOH.delete m k >> return m+{-# INLINE cuckooHashTable #-} -------------------------------------------------------------------------------linearHashTable :: DataStructure (Operation ByteString)+linearHashTable :: (Hashable k, Eq k) => DataStructure (Operation k) linearHashTable = setupDataIO (IOH.newSized :: Int -> IO (IOH.LinearHashTable k v)) f@@ -97,8 +106,10 @@ !_ <- IOH.lookup m k return m (Delete k) -> IOH.delete m k >> return m+{-# INLINE linearHashTable #-} +------------------------------------------------------------------------------ mkByteString :: GenIO -> IO ByteString mkByteString rng = do n <- uniformR (4,16) rng@@ -110,19 +121,41 @@ instance NFData ByteString where rnf s = rnf $! B.unpack s +------------------------------------------------------------------------------+mkConsecutiveIntegers :: IORef Int -> GenIO -> IO Int+mkConsecutiveIntegers ref _ = do+ !i <- atomicModifyIORef ref f+ return $! i+ where+ f !i = let !j = i+1 in (j,j) --- testStructures = [ ("Data.CuckooHashTable" , cuckooHashTable)--- ] --- testStructures = [ ("Data.Map" , dataMap )--- , ("Data.Hashtable" , hashTable )--- , ("Data.BasicHashTable" , basicHashTable )--- , ("Data.LinearHashTable" , linearHashTable)--- ]+------------------------------------------------------------------------------+newtype IntMix = IntMix Int+ deriving (Num, Read, Show, Ord, Eq, NFData) --- testStructures = [ ("Data.BasicHashTable" , basicHashTable )--- ] +------------------------------------------------------------------------------+instance Hashable IntMix where+ hash (IntMix a) = hashWithSalt 1102951999 a+ hashWithSalt salt (IntMix a) = hashWithSalt salt a+++------------------------------------------------------------------------------+loadConsecutiveIntegersWorkload :: WorkloadGenerator (Operation Int)+loadConsecutiveIntegersWorkload size = do+ ref <- liftIO $ newIORef 0+ loadOnly (mkConsecutiveIntegers ref) size+++------------------------------------------------------------------------------+loadConsecutiveIntegersWorkload' :: WorkloadGenerator (Operation IntMix)+loadConsecutiveIntegersWorkload' size = do+ ref <- liftIO $ newIORef 0+ loadOnly (\rng -> IntMix `fmap` mkConsecutiveIntegers ref rng) size+++------------------------------------------------------------------------------ testStructures = [ ("Data.Map" , dataMap ) , ("Data.Hashtable" , hashTable ) , ("Data.HashMap" , hashMap )@@ -131,11 +164,21 @@ , ("Data.CuckooHashTable" , cuckooHashTable) ] --- testStructures = [ ("Data.Hashtable" , hashTable )--- , ("Data.LinearHashTable" , linearHashTable)--- ]+intStructures = [ ("Data.Map" , dataMap )+ , ("Data.Hashtable" , hashTable )+ , ("Data.HashMap" , hashMap )+ , ("Data.BasicHashTable" , basicHashTable )+ , ("Data.CuckooHashTable", cuckooHashTable)+ ] +intStructures' = [ ("Data.Map" , dataMap )+ , ("Data.Hashtable" , hashTable )+ , ("Data.HashMap" , hashMap )+ , ("Data.BasicHashTable" , basicHashTable )+ , ("Data.CuckooHashTable", cuckooHashTable)+ ] + testSizes = [ 250 , 500 , 1000@@ -151,14 +194,7 @@ , 1024000 , 2048000 ] --- testSizes = [ 1024000--- , 2048000--- ] --- testSizes = [ 256000--- , 512000--- ]- ------------------------------------------------------------------------------ lookupBenchmark :: Benchmark (Operation ByteString) lookupBenchmark = Benchmark "Lookup Performance"@@ -175,8 +211,22 @@ (loadOnly mkByteString) +------------------------------------------------------------------------------+consecutiveIntBenchmark :: Benchmark (Operation Int)+consecutiveIntBenchmark = Benchmark "Insert consecutive ints"+ intStructures+ testSizes+ loadConsecutiveIntegersWorkload + ------------------------------------------------------------------------------+consecutiveIntWithMixBenchmark :: Benchmark (Operation IntMix)+consecutiveIntWithMixBenchmark = Benchmark "Insert consecutive ints (mixed)"+ intStructures'+ testSizes+ loadConsecutiveIntegersWorkload'++------------------------------------------------------------------------------ main :: IO () main = do args <- getArgs@@ -186,4 +236,8 @@ let cfg = defaultCriterionCollectionConfig runBenchmark PerBatch Mutating insertBenchmark cfg (fmap (++".insert") fn) runBenchmark PerBatch Pure lookupBenchmark cfg (fmap (++".lookup") fn)+ runBenchmark PerBatch Mutating consecutiveIntBenchmark cfg+ (fmap (++".int") fn)+ runBenchmark PerBatch Mutating consecutiveIntWithMixBenchmark cfg+ (fmap (++".intmix") fn)
hashtables.cabal view
@@ -1,12 +1,12 @@ Name: hashtables-Version: 1.0.1.6+Version: 1.0.1.7 Synopsis: Mutable hash tables in the ST monad Homepage: http://github.com/gregorycollins/hashtables License: BSD3 License-file: LICENSE Author: Gregory Collins Maintainer: greg@gregorycollins.net-Copyright: (c) 2011, Google, Inc.+Copyright: (c) 2011-2012, Google, Inc. Category: Data Build-type: Simple Cabal-version: >= 1.8
src/Data/HashTable/Internal/CacheLine.hs view
@@ -3,7 +3,7 @@ {-# LANGUAGE ForeignFunctionInterface #-} {-# LANGUAGE MagicHash #-} -module Data.HashTable.Internal.CacheLine +module Data.HashTable.Internal.CacheLine ( cacheLineSearch , cacheLineSearch2 , cacheLineSearch3@@ -24,6 +24,7 @@ import qualified Data.HashTable.Internal.IntArray as M #ifndef NO_C_SEARCH+import Control.Monad import Foreign.C.Types #else import Data.Bits@@ -43,36 +44,36 @@ #ifndef NO_C_SEARCH foreign import ccall unsafe "lineSearch32"- c_lineSearch32 :: Ptr a -> CInt -> CUInt -> IO Int+ c_lineSearch32 :: Ptr a -> CInt -> CUInt -> IO CInt foreign import ccall unsafe "lineSearch64"- c_lineSearch64 :: Ptr a -> CInt -> CULong -> IO Int+ c_lineSearch64 :: Ptr a -> CInt -> CULong -> IO CInt foreign import ccall unsafe "lineSearch32_2"- c_lineSearch32_2 :: Ptr a -> CInt -> CUInt -> CUInt -> IO Int+ c_lineSearch32_2 :: Ptr a -> CInt -> CUInt -> CUInt -> IO CInt foreign import ccall unsafe "lineSearch64_2"- c_lineSearch64_2 :: Ptr a -> CInt -> CULong -> CULong -> IO Int+ c_lineSearch64_2 :: Ptr a -> CInt -> CULong -> CULong -> IO CInt foreign import ccall unsafe "lineSearch32_3"- c_lineSearch32_3 :: Ptr a -> CInt -> CUInt -> CUInt -> CUInt -> IO Int+ c_lineSearch32_3 :: Ptr a -> CInt -> CUInt -> CUInt -> CUInt -> IO CInt foreign import ccall unsafe "lineSearch64_3"- c_lineSearch64_3 :: Ptr a -> CInt -> CULong -> CULong -> CULong -> IO Int+ c_lineSearch64_3 :: Ptr a -> CInt -> CULong -> CULong -> CULong -> IO CInt foreign import ccall unsafe "forwardSearch32_2"- c_forwardSearch32_2 :: Ptr a -> CInt -> CInt -> CUInt -> CUInt -> IO Int+ c_forwardSearch32_2 :: Ptr a -> CInt -> CInt -> CUInt -> CUInt -> IO CInt foreign import ccall unsafe "forwardSearch32_3" c_forwardSearch32_3 :: Ptr a -> CInt -> CInt -> CUInt -> CUInt -> CUInt- -> IO Int+ -> IO CInt foreign import ccall unsafe "forwardSearch64_2"- c_forwardSearch64_2 :: Ptr a -> CInt -> CInt -> CULong -> CULong -> IO Int+ c_forwardSearch64_2 :: Ptr a -> CInt -> CInt -> CULong -> CULong -> IO CInt foreign import ccall unsafe "forwardSearch64_3" c_forwardSearch64_3 :: Ptr a -> CInt -> CInt -> CULong -> CULong -> CULong- -> IO Int+ -> IO CInt foreign import ccall unsafe "prefetchCacheLine32_read" prefetchCacheLine32_read :: Ptr a -> CInt -> IO ()@@ -111,8 +112,8 @@ {-# INLINE forwardSearch2 #-} forwardSearch2 :: IntArray s -> Int -> Int -> Int -> Int -> ST s Int-forwardSearch2 !vec !start !end !x1 !x2 = - unsafeIOToST c+forwardSearch2 !vec !start !end !x1 !x2 =+ liftM fromEnum $! unsafeIOToST c where c32 = c_forwardSearch32_2 (M.toPtr vec) (fI start) (fI end) (fI x1) (fI x2) c64 = c_forwardSearch64_2 (M.toPtr vec) (fI start) (fI end) (fI x1) (fI x2)@@ -121,8 +122,8 @@ {-# INLINE forwardSearch3 #-} forwardSearch3 :: IntArray s -> Int -> Int -> Int -> Int -> Int -> ST s Int-forwardSearch3 !vec !start !end !x1 !x2 !x3 = - unsafeIOToST c+forwardSearch3 !vec !start !end !x1 !x2 !x3 =+ liftM fromEnum $! unsafeIOToST c where c32 = c_forwardSearch32_3 (M.toPtr vec) (fI start) (fI end) (fI x1) (fI x2) (fI x3)@@ -134,7 +135,7 @@ {-# INLINE lineSearch #-} lineSearch :: IntArray s -> Int -> Int -> ST s Int lineSearch !vec !start !value =- unsafeIOToST c+ liftM fromEnum $! unsafeIOToST c where c32 = c_lineSearch32 (M.toPtr vec) (fI start) (fI value) c64 = c_lineSearch64 (M.toPtr vec) (fI start) (fI value)@@ -143,7 +144,7 @@ {-# INLINE lineSearch2 #-} lineSearch2 :: IntArray s -> Int -> Int -> Int -> ST s Int lineSearch2 !vec !start !x1 !x2 =- unsafeIOToST c+ liftM fromEnum $! unsafeIOToST c where c32 = c_lineSearch32_2 (M.toPtr vec) (fI start) (fI x1) (fI x2) c64 = c_lineSearch64_2 (M.toPtr vec) (fI start) (fI x1) (fI x2)@@ -152,7 +153,7 @@ {-# INLINE lineSearch3 #-} lineSearch3 :: IntArray s -> Int -> Int -> Int -> Int -> ST s Int lineSearch3 !vec !start !x1 !x2 !x3 =- unsafeIOToST c+ liftM fromEnum $! unsafeIOToST c where c32 = c_lineSearch32_3 (M.toPtr vec) (fI start) (fI x1) (fI x2) (fI x3) c64 = c_lineSearch64_3 (M.toPtr vec) (fI start) (fI x1) (fI x2) (fI x3)@@ -200,7 +201,7 @@ !m# = sign# x# !r# = (int2Word# (m# +# x#)) `xor#` int2Word# m# - + {-# INLINE mask# #-} -- | Returns 0xfff..fff (aka -1) if a# == b#, 0 otherwise. mask# :: Int# -> Int# -> Int#@@ -356,8 +357,8 @@ !nmm# = not# mm# !rv# = mm# `or#` (nmm# `and#` (int2Word# (start# +# p#))) {-# INLINE lineResult# #-}- + lineSearch :: IntArray s -- ^ vector to search -> Int -- ^ start index -> Int -- ^ value to search for@@ -538,27 +539,27 @@ `and#` int2Word# 0x2#) (I# x3#) <- M.readArray vec $! start + 2- let !p3# = p2# `or#` ((maskw# x3# v# `or#` maskw# x3# v2#) + let !p3# = p2# `or#` ((maskw# x3# v# `or#` maskw# x3# v2#) `and#` int2Word# 0x4#) (I# x4#) <- M.readArray vec $! start + 3- let !p4# = p3# `or#` ((maskw# x4# v# `or#` maskw# x4# v2#) + let !p4# = p3# `or#` ((maskw# x4# v# `or#` maskw# x4# v2#) `and#` int2Word# 0x8#) (I# x5#) <- M.readArray vec $! start + 4- let !p5# = p4# `or#` ((maskw# x5# v# `or#` maskw# x5# v2#) + let !p5# = p4# `or#` ((maskw# x5# v# `or#` maskw# x5# v2#) `and#` int2Word# 0x10#) (I# x6#) <- M.readArray vec $! start + 5- let !p6# = p5# `or#` ((maskw# x6# v# `or#` maskw# x6# v2#) + let !p6# = p5# `or#` ((maskw# x6# v# `or#` maskw# x6# v2#) `and#` int2Word# 0x20#) (I# x7#) <- M.readArray vec $! start + 6- let !p7# = p6# `or#` ((maskw# x7# v# `or#` maskw# x7# v2#) + let !p7# = p6# `or#` ((maskw# x7# v# `or#` maskw# x7# v2#) `and#` int2Word# 0x40#) (I# x8#) <- M.readArray vec $! start + 7- let !p8# = p7# `or#` ((maskw# x8# v# `or#` maskw# x8# v2#) + let !p8# = p7# `or#` ((maskw# x8# v# `or#` maskw# x8# v2#) `and#` int2Word# 0x80#) return $! lineResult# p8# start@@ -576,63 +577,63 @@ let !p1# = (maskw# x1# v# `or#` maskw# x1# v2#) `and#` int2Word# 0x1# (I# x2#) <- M.readArray vec $! start + 1- let !p2# = p1# `or#` ((maskw# x2# v# `or#` maskw# x2# v2#) + let !p2# = p1# `or#` ((maskw# x2# v# `or#` maskw# x2# v2#) `and#` int2Word# 0x2#) (I# x3#) <- M.readArray vec $! start + 2- let !p3# = p2# `or#` ((maskw# x3# v# `or#` maskw# x3# v2#) + let !p3# = p2# `or#` ((maskw# x3# v# `or#` maskw# x3# v2#) `and#` int2Word# 0x4#) (I# x4#) <- M.readArray vec $! start + 3- let !p4# = p3# `or#` ((maskw# x4# v# `or#` maskw# x4# v2#) + let !p4# = p3# `or#` ((maskw# x4# v# `or#` maskw# x4# v2#) `and#` int2Word# 0x8#) (I# x5#) <- M.readArray vec $! start + 4- let !p5# = p4# `or#` ((maskw# x5# v# `or#` maskw# x5# v2#) + let !p5# = p4# `or#` ((maskw# x5# v# `or#` maskw# x5# v2#) `and#` int2Word# 0x10#) (I# x6#) <- M.readArray vec $! start + 5- let !p6# = p5# `or#` ((maskw# x6# v# `or#` maskw# x6# v2#) + let !p6# = p5# `or#` ((maskw# x6# v# `or#` maskw# x6# v2#) `and#` int2Word# 0x20#) (I# x7#) <- M.readArray vec $! start + 6- let !p7# = p6# `or#` ((maskw# x7# v# `or#` maskw# x7# v2#) + let !p7# = p6# `or#` ((maskw# x7# v# `or#` maskw# x7# v2#) `and#` int2Word# 0x40#) (I# x8#) <- M.readArray vec $! start + 7- let !p8# = p7# `or#` ((maskw# x8# v# `or#` maskw# x8# v2#) + let !p8# = p7# `or#` ((maskw# x8# v# `or#` maskw# x8# v2#) `and#` int2Word# 0x80#) (I# x9#) <- M.readArray vec $! start + 8- let !p9# = p8# `or#` ((maskw# x9# v# `or#` maskw# x9# v2#) + let !p9# = p8# `or#` ((maskw# x9# v# `or#` maskw# x9# v2#) `and#` int2Word# 0x100#) (I# x10#) <- M.readArray vec $! start + 9- let !p10# = p9# `or#` ((maskw# x10# v# `or#` maskw# x10# v2#) + let !p10# = p9# `or#` ((maskw# x10# v# `or#` maskw# x10# v2#) `and#` int2Word# 0x200#) (I# x11#) <- M.readArray vec $! start + 10- let !p11# = p10# `or#` ((maskw# x11# v# `or#` maskw# x11# v2#) + let !p11# = p10# `or#` ((maskw# x11# v# `or#` maskw# x11# v2#) `and#` int2Word# 0x400#) (I# x12#) <- M.readArray vec $! start + 11- let !p12# = p11# `or#` ((maskw# x12# v# `or#` maskw# x12# v2#) + let !p12# = p11# `or#` ((maskw# x12# v# `or#` maskw# x12# v2#) `and#` int2Word# 0x800#) (I# x13#) <- M.readArray vec $! start + 12- let !p13# = p12# `or#` ((maskw# x13# v# `or#` maskw# x13# v2#) + let !p13# = p12# `or#` ((maskw# x13# v# `or#` maskw# x13# v2#) `and#` int2Word# 0x1000#) (I# x14#) <- M.readArray vec $! start + 13- let !p14# = p13# `or#` ((maskw# x14# v# `or#` maskw# x14# v2#) + let !p14# = p13# `or#` ((maskw# x14# v# `or#` maskw# x14# v2#) `and#` int2Word# 0x2000#) (I# x15#) <- M.readArray vec $! start + 14- let !p15# = p14# `or#` ((maskw# x15# v# `or#` maskw# x15# v2#) + let !p15# = p14# `or#` ((maskw# x15# v# `or#` maskw# x15# v2#) `and#` int2Word# 0x4000#) (I# x16#) <- M.readArray vec $! start + 15- let !p16# = p15# `or#` ((maskw# x16# v# `or#` maskw# x16# v2#) + let !p16# = p15# `or#` ((maskw# x16# v# `or#` maskw# x16# v2#) `and#` int2Word# 0x8000#) return $! lineResult# p16# start@@ -726,32 +727,32 @@ (I# x3#) <- M.readArray vec $! start + 2 let !p3# = p2# `or#`- ((maskw# x3# v# `or#` maskw# x3# v2# `or#` maskw# x3# v3#) + ((maskw# x3# v# `or#` maskw# x3# v2# `or#` maskw# x3# v3#) `and#` int2Word# 0x4#) (I# x4#) <- M.readArray vec $! start + 3 let !p4# = p3# `or#`- ((maskw# x4# v# `or#` maskw# x4# v2# `or#` maskw# x4# v3#) + ((maskw# x4# v# `or#` maskw# x4# v2# `or#` maskw# x4# v3#) `and#` int2Word# 0x8#) (I# x5#) <- M.readArray vec $! start + 4 let !p5# = p4# `or#`- ((maskw# x5# v# `or#` maskw# x5# v2# `or#` maskw# x5# v3#) + ((maskw# x5# v# `or#` maskw# x5# v2# `or#` maskw# x5# v3#) `and#` int2Word# 0x10#) (I# x6#) <- M.readArray vec $! start + 5 let !p6# = p5# `or#`- ((maskw# x6# v# `or#` maskw# x6# v2# `or#` maskw# x6# v3#) + ((maskw# x6# v# `or#` maskw# x6# v2# `or#` maskw# x6# v3#) `and#` int2Word# 0x20#) (I# x7#) <- M.readArray vec $! start + 6 let !p7# = p6# `or#`- ((maskw# x7# v# `or#` maskw# x7# v2# `or#` maskw# x7# v3#) + ((maskw# x7# v# `or#` maskw# x7# v2# `or#` maskw# x7# v3#) `and#` int2Word# 0x40#) (I# x8#) <- M.readArray vec $! start + 7 let !p8# = p7# `or#`- ((maskw# x8# v# `or#` maskw# x8# v2# `or#` maskw# x8# v3#) + ((maskw# x8# v# `or#` maskw# x8# v2# `or#` maskw# x8# v3#) `and#` int2Word# 0x80#) return $! lineResult# p8# start@@ -772,77 +773,77 @@ (I# x2#) <- M.readArray vec $! start + 1 let !p2# = p1# `or#`- ((maskw# x2# v# `or#` maskw# x2# v2# `or#` maskw# x2# v3#) + ((maskw# x2# v# `or#` maskw# x2# v2# `or#` maskw# x2# v3#) `and#` int2Word# 0x2#) (I# x3#) <- M.readArray vec $! start + 2 let !p3# = p2# `or#`- ((maskw# x3# v# `or#` maskw# x3# v2# `or#` maskw# x3# v3#) + ((maskw# x3# v# `or#` maskw# x3# v2# `or#` maskw# x3# v3#) `and#` int2Word# 0x4#) (I# x4#) <- M.readArray vec $! start + 3 let !p4# = p3# `or#`- ((maskw# x4# v# `or#` maskw# x4# v2# `or#` maskw# x4# v3#) + ((maskw# x4# v# `or#` maskw# x4# v2# `or#` maskw# x4# v3#) `and#` int2Word# 0x8#) (I# x5#) <- M.readArray vec $! start + 4 let !p5# = p4# `or#`- ((maskw# x5# v# `or#` maskw# x5# v2# `or#` maskw# x5# v3#) + ((maskw# x5# v# `or#` maskw# x5# v2# `or#` maskw# x5# v3#) `and#` int2Word# 0x10#) (I# x6#) <- M.readArray vec $! start + 5 let !p6# = p5# `or#`- ((maskw# x6# v# `or#` maskw# x6# v2# `or#` maskw# x6# v3#) + ((maskw# x6# v# `or#` maskw# x6# v2# `or#` maskw# x6# v3#) `and#` int2Word# 0x20#) (I# x7#) <- M.readArray vec $! start + 6 let !p7# = p6# `or#`- ((maskw# x7# v# `or#` maskw# x7# v2# `or#` maskw# x7# v3#) + ((maskw# x7# v# `or#` maskw# x7# v2# `or#` maskw# x7# v3#) `and#` int2Word# 0x40#) (I# x8#) <- M.readArray vec $! start + 7 let !p8# = p7# `or#`- ((maskw# x8# v# `or#` maskw# x8# v2# `or#` maskw# x8# v3#) + ((maskw# x8# v# `or#` maskw# x8# v2# `or#` maskw# x8# v3#) `and#` int2Word# 0x80#) (I# x9#) <- M.readArray vec $! start + 8 let !p9# = p8# `or#`- ((maskw# x9# v# `or#` maskw# x9# v2# `or#` maskw# x9# v3#) + ((maskw# x9# v# `or#` maskw# x9# v2# `or#` maskw# x9# v3#) `and#` int2Word# 0x100#) (I# x10#) <- M.readArray vec $! start + 9 let !p10# = p9# `or#`- ((maskw# x10# v# `or#` maskw# x10# v2# `or#` maskw# x10# v3#) + ((maskw# x10# v# `or#` maskw# x10# v2# `or#` maskw# x10# v3#) `and#` int2Word# 0x200#) (I# x11#) <- M.readArray vec $! start + 10 let !p11# = p10# `or#`- ((maskw# x11# v# `or#` maskw# x11# v2# `or#` maskw# x11# v3#) + ((maskw# x11# v# `or#` maskw# x11# v2# `or#` maskw# x11# v3#) `and#` int2Word# 0x400#) (I# x12#) <- M.readArray vec $! start + 11 let !p12# = p11# `or#`- ((maskw# x12# v# `or#` maskw# x12# v2# `or#` maskw# x12# v3#) + ((maskw# x12# v# `or#` maskw# x12# v2# `or#` maskw# x12# v3#) `and#` int2Word# 0x800#) (I# x13#) <- M.readArray vec $! start + 12 let !p13# = p12# `or#`- ((maskw# x13# v# `or#` maskw# x13# v2# `or#` maskw# x13# v3#) + ((maskw# x13# v# `or#` maskw# x13# v2# `or#` maskw# x13# v3#) `and#` int2Word# 0x1000#) (I# x14#) <- M.readArray vec $! start + 13 let !p14# = p13# `or#`- ((maskw# x14# v# `or#` maskw# x14# v2# `or#` maskw# x14# v3#) + ((maskw# x14# v# `or#` maskw# x14# v2# `or#` maskw# x14# v3#) `and#` int2Word# 0x2000#) (I# x15#) <- M.readArray vec $! start + 14 let !p15# = p14# `or#`- ((maskw# x15# v# `or#` maskw# x15# v2# `or#` maskw# x15# v3#) + ((maskw# x15# v# `or#` maskw# x15# v2# `or#` maskw# x15# v3#) `and#` int2Word# 0x4000#) (I# x16#) <- M.readArray vec $! start + 15 let !p16# = p15# `or#`- ((maskw# x16# v# `or#` maskw# x16# v2# `or#` maskw# x16# v3#) + ((maskw# x16# v# `or#` maskw# x16# v2# `or#` maskw# x16# v3#) `and#` int2Word# 0x8000#) return $! lineResult# p16# start
src/Data/HashTable/Internal/Utils.hs view
@@ -6,6 +6,7 @@ ( whichBucket , nextBestPrime , bumpSize+ , shiftL , shiftRL , iShiftL , iShiftRL@@ -20,12 +21,13 @@ , forceSameType ) where -import Data.Bits+import Data.Bits hiding (shiftL) import Data.Vector (Vector) import qualified Data.Vector as V #if __GLASGOW_HASKELL__ >= 503 import GHC.Exts #else+import qualified Data.Bits import Data.Word #endif @@ -244,6 +246,7 @@ ------------------------------------------------------------------------------+shiftL :: Word -> Int -> Word shiftRL :: Word -> Int -> Word iShiftL :: Int -> Int -> Int iShiftRL :: Int -> Int -> Int@@ -251,6 +254,10 @@ {-------------------------------------------------------------------- GHC: use unboxing to get @shiftRL@ inlined. --------------------------------------------------------------------}+{-# INLINE shiftL #-}+shiftL (W# x) (I# i)+ = W# (shiftL# x i)+ {-# INLINE shiftRL #-} shiftRL (W# x) (I# i) = W# (shiftRL# x i)@@ -264,9 +271,10 @@ = I# (iShiftRL# x i) #else+shiftL x i = Data.Bits.shiftL x i shiftRL x i = shiftR x i iShiftL x i = shiftL x i-iShiftRL x i = shiftRL x i+iShiftRL x i = shiftRL x i #endif
src/Data/HashTable/ST/Basic.hs view
@@ -484,7 +484,7 @@ -- because the table isn't full, we know that there must be either -- an empty or a deleted marker somewhere in the table. Assert this -- here.- assert (idx > 0) $ return ()+ assert (idx >= 0) $ return () h0 <- U.readArray hashes idx debug $ "h0 was " ++ show h0
test/hashtables-test.cabal view
@@ -1,8 +1,8 @@ Name: hashtables-test-Version: 0.1+Version: 0.2 Author: Gregory Collins Maintainer: greg@gregorycollins.net-Copyright: (c) 2011, Google, Inc.+Copyright: (c) 2011-2012, Google, Inc. Category: Data Build-type: Simple Cabal-version: >= 1.8