hashtables 1.2.0.0 → 1.2.0.1
raw patch · 13 files changed
+143/−71 lines, 13 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- cbits/default.c +11/−10
- cbits/sse-42.c +1/−1
- changelog.md +85/−0
- hashtables.cabal +2/−1
- src/Data/HashTable/IO.hs +9/−13
- src/Data/HashTable/Internal/CacheLine.hs +0/−5
- src/Data/HashTable/Internal/CheapPseudoRandomBitStream.hs +16/−16
- src/Data/HashTable/Internal/Linear/Bucket.hs +10/−10
- src/Data/HashTable/Internal/Utils.hs +6/−0
- src/Data/HashTable/ST/Basic.hs +1/−2
- src/Data/HashTable/ST/Cuckoo.hs +1/−4
- src/Data/HashTable/ST/Linear.hs +0/−3
- test/suite/Data/HashTable/Test/Common.hs +1/−6
cbits/default.c view
@@ -2,10 +2,10 @@ #include "defs.h" -inline int32_t mask(int32_t a, int32_t b) { return -(a == b); }+static inline int32_t mask(int32_t a, int32_t b) { return -(a == b); } #if defined(__GNUC__)-inline int32_t first_bit_set(int32_t a) {+static inline int32_t first_bit_set(int32_t a) { return __builtin_ffs(a) - 1; } #else@@ -14,7 +14,7 @@ 31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 }; -inline int32_t first_bit_set(int32_t a) {+static inline int32_t first_bit_set(int32_t a) { int32_t zero_case = mask(0, a); uint32_t x = (uint32_t) (a & -a); x *= 0x077CB531;@@ -23,7 +23,8 @@ } #endif -inline uint32_t line_mask(small_hash_t* array, int start, small_hash_t x1) {+static inline uint32_t line_mask(small_hash_t* array, int start,+ small_hash_t x1) { small_hash_t* p = array + start; uint32_t m1 = 0; uint32_t m2 = 0;@@ -72,8 +73,8 @@ return (m1 | m2 | m3) >> offset; } -inline uint32_t line_mask_2(small_hash_t* array, int start,- small_hash_t x1, small_hash_t x2) {+static inline uint32_t line_mask_2(small_hash_t* array, int start,+ small_hash_t x1, small_hash_t x2) { small_hash_t* p = array + start; uint32_t m1 = 0; uint32_t m2 = 0;@@ -122,9 +123,9 @@ return (m1 | m2 | m3) >> offset; } -inline uint32_t line_mask_3(small_hash_t* array, int start,- small_hash_t x1, small_hash_t x2,- small_hash_t x3) {+static inline uint32_t line_mask_3(small_hash_t* array, int start,+ small_hash_t x1, small_hash_t x2,+ small_hash_t x3) { small_hash_t* p = array + start; uint32_t m1 = 0; uint32_t m2 = 0;@@ -173,7 +174,7 @@ } -inline int32_t line_result(uint32_t m, int start) {+static inline int32_t line_result(uint32_t m, int start) { int32_t p = first_bit_set((int32_t) m); int32_t mm = mask(p, -1); return mm | (start + p);
cbits/sse-42.c view
@@ -27,7 +27,7 @@ } #endif -inline __m128i fill(small_hash_t v) {+static inline __m128i fill(small_hash_t v) { int32_t v1 = (((int)v) << 16) | v; __m128i x = _mm_cvtsi32_si128(0); x = _mm_insert_epi32(x, v1, 0);
+ changelog.md view
@@ -0,0 +1,85 @@+# Hashtables changelog++## 1.2.0.1++ - Fixed bug in C code re: clang interpreting "inline" strictly according to+ (insane) C99 semantics: http://clang.llvm.org/compatibility.html#inline++ - Fixed a compile bug affecting versions of base older than 4.4.++ - Changed int type from Int to Word in CheapPseudoRandomBitStream to fix an+ integer overflow warning.++## 1.2.0.0++### Switch to smaller hash codes to go faster and save space.++Before, in the basic and cuckoo hash tables, we were storing full+machine-word-sized hash codes in the table so that we could quickly search a+whole cache line for a key (or a combination of keys) without branching.++It turns out that a full machine word is not really necessary for this+application; switching to a 16-bit key will very slightly increase the number+of hash collisions within buckets (meaning that we'll compare more keys), but+will pay big dividends in terms of:++ - reduced wastage of RAM++ - searching more keys at once, allowing buckets to grow bigger++ - more cache hits on the hash codes array.++### Other++ - Dependency bumps++ - Fix definitions of forwardSearch2 and forwardSearch3 in PORTABLE mode (also+ used on Windows) to match C implementations.++## 1.1.2.1+ - Fixes for GHC 7.8 compatibility.++## 1.1.2.0+ - Bump allowable versions of hashable, primitive, and vector, blacklisting+ some bad hashable versions++ - Add specialize pragmas for fromListWithSizeHint++## 1.1.0.2+ - Use CPP to allow compilation against base 4.2/4.3.++## 1.1.0.1+ - Re-added SPECIALIZE pragmas that were previously removed.++## 1.1.0.0+ - Add 'fromListWithSizeHint'+ - 'fromList': don't be strict in the list argument++## 1.0.1.8+Bump vector and primitive dependencies.++## 1.0.1.7+Fix bug in C FFI code (not correctly promoting CInt to Int).++## 1.0.1.6+Fix for benchmark suite .cabal file.++## 1.0.1.5+Added benchmark suite.++## 1.0.1.4+Bump test-framework dependency.++## 1.0.1.3+Bump testsuite dependencies.++## 1.0.1.2+Fix testsuite on Windows.++## 1.0.1.1+Build fix for Windows.++## 1.0.1.0++Bugfix for http://github.com/gregorycollins/hashtables/issues/1 (Basic.lookup+loops).
hashtables.cabal view
@@ -1,5 +1,5 @@ Name: hashtables-Version: 1.2.0.0+Version: 1.2.0.1 Synopsis: Mutable hash tables in the ST monad Homepage: http://github.com/gregorycollins/hashtables License: BSD3@@ -122,6 +122,7 @@ cbits/check.c, cbits/defs.h, cbits/sse-42-check.c,+ changelog.md, test/compute-overhead/ComputeOverhead.hs, test/hashtables-test.cabal, test/runTestsAndCoverage.sh,
src/Data/HashTable/IO.hs view
@@ -57,21 +57,17 @@ -------------------------------------------------------------------------------import Control.Monad.Primitive (PrimState)-#if MIN_VERSION_base(4,4,0)-import Control.Monad.ST (stToIO)-import Control.Monad.ST.Unsafe (unsafeIOToST)-#else-import Control.Monad.ST (stToIO, unsafeIOToST)-#endif-import Data.Hashable (Hashable)-import qualified Data.HashTable.Class as C-import Prelude hiding (lookup, mapM_)+import Control.Monad.Primitive (PrimState)+import Control.Monad.ST (stToIO)+import Data.Hashable (Hashable)+import qualified Data.HashTable.Class as C+import Prelude hiding (lookup, mapM_) -------------------------------------------------------------------------------import qualified Data.HashTable.ST.Basic as B-import qualified Data.HashTable.ST.Cuckoo as Cu-import qualified Data.HashTable.ST.Linear as L+import Data.HashTable.Internal.Utils (unsafeIOToST)+import qualified Data.HashTable.ST.Basic as B+import qualified Data.HashTable.ST.Cuckoo as Cu+import qualified Data.HashTable.ST.Linear as L ------------------------------------------------------------------------------
src/Data/HashTable/Internal/CacheLine.hs view
@@ -20,12 +20,7 @@ ) where import Control.Monad-#if MIN_VERSION_base(4,4,0) import Control.Monad.ST (ST)-import Control.Monad.ST.Unsafe-#else-import Control.Monad.ST-#endif import Data.HashTable.Internal.IntArray (Elem, IntArray) import qualified Data.HashTable.Internal.IntArray as M
src/Data/HashTable/Internal/CheapPseudoRandomBitStream.hs view
@@ -9,11 +9,11 @@ import Control.Applicative import Control.Monad.ST-import Data.Bits-import Data.Int+import Data.Bits ((.&.)) import Data.STRef-import qualified Data.Vector.Unboxed as V-import Data.Vector.Unboxed (Vector)+import Data.Vector.Unboxed (Vector)+import qualified Data.Vector.Unboxed as V+import Data.Word (Word, Word32, Word64) import Data.HashTable.Internal.Utils @@ -21,7 +21,7 @@ ------------------------------------------------------------------------------ -- Chosen by fair dice roll. Guaranteed random. More importantly, there are an -- equal number of 0 and 1 bits in both of these vectors.-random32s :: Vector Int32+random32s :: Vector Word32 random32s = V.fromList [ 0xe293c315 , 0x82e2ff62 , 0xcb1ef9ae@@ -42,7 +42,7 @@ -------------------------------------------------------------------------------random64s :: Vector Int64+random64s :: Vector Word64 random64s = V.fromList [ 0x62ef447e007e8732 , 0x149d6acb499feef8 , 0xca7725f9b404fbf8@@ -68,16 +68,16 @@ -------------------------------------------------------------------------------randoms :: Vector Int-randoms | wordSize == 32 = V.map fromEnum random32s- | otherwise = V.map fromEnum random64s+randoms :: Vector Word+randoms | wordSize == 32 = V.map fromIntegral random32s+ | otherwise = V.map fromIntegral random64s ------------------------------------------------------------------------------ data BitStream s = BitStream {- _curRandom :: !(STRef s Int)- , _bitsLeft :: !(STRef s Int)- , _randomPos :: !(STRef s Int)+ _curRandom :: !(STRef s Word)+ , _bitsLeft :: !(STRef s Int )+ , _randomPos :: !(STRef s Int ) } @@ -91,12 +91,12 @@ -------------------------------------------------------------------------------getNextBit :: BitStream s -> ST s Int+getNextBit :: BitStream s -> ST s Word getNextBit = getNBits 1 -------------------------------------------------------------------------------getNBits :: Int -> BitStream s -> ST s Int+getNBits :: Int -> BitStream s -> ST s Word getNBits nbits (BitStream crRef blRef rpRef) = do !bl <- readSTRef blRef if bl < nbits@@ -112,8 +112,8 @@ extractBits r extractBits r = do- let !b = r .&. ((1 `iShiftL` nbits) - 1)- writeSTRef crRef $! (r `iShiftRL` nbits)+ let !b = r .&. ((1 `shiftL` nbits) - 1)+ writeSTRef crRef $! (r `shiftRL` nbits) return b nextBits bl = do
src/Data/HashTable/Internal/Linear/Bucket.hs view
@@ -1,5 +1,5 @@-{-# LANGUAGE BangPatterns #-}-{-# LANGUAGE CPP #-}+{-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-} module Data.HashTable.Internal.Linear.Bucket ( Bucket,@@ -23,16 +23,16 @@ ------------------------------------------------------------------------------+import Control.Monad hiding (foldM, mapM_) import qualified Control.Monad-import Control.Monad hiding (mapM_, foldM)-import Control.Monad.ST+import Control.Monad.ST (ST) #ifdef DEBUG-import Control.Monad.ST.Unsafe+import Data.HashTable.Internal.Utils (unsafeIOToST) #endif-import Data.Maybe (fromMaybe) import Data.HashTable.Internal.Array+import Data.Maybe (fromMaybe) import Data.STRef-import Prelude hiding (lookup, mapM_)+import Prelude hiding (lookup, mapM_) ------------------------------------------------------------------------------ import Data.HashTable.Internal.UnsafeTricks @@ -192,7 +192,7 @@ debug "Bucket.snoc: spill finished, snoccing element" let (Bucket _ hwRef' keys' values') = fromKey bk- + let !hw' = hw+1 writeArray keys' hw k writeArray values' hw v@@ -296,7 +296,7 @@ | otherwise = doMap $ fromKey bucketKey where doMap (Bucket sz hwRef keys values) = do- hw <- readSTRef hwRef + hw <- readSTRef hwRef debug $ "Bucket.mapM_: hw was " ++ show hw ++ ", sz was " ++ show sz go hw 0 where@@ -316,7 +316,7 @@ | otherwise = doMap $ fromKey bucketKey where doMap (Bucket _ hwRef keys values) = do- hw <- readSTRef hwRef + hw <- readSTRef hwRef go hw seed0 0 where go !hw !seed !i | i >= hw = return seed
src/Data/HashTable/Internal/Utils.hs view
@@ -19,6 +19,7 @@ , cacheLineIntMask , cacheLineIntBits , forceSameType+ , unsafeIOToST ) where import Data.Bits hiding (shiftL)@@ -32,6 +33,11 @@ import Data.Word #endif +#if MIN_VERSION_base(4,4,0)+import Control.Monad.ST.Unsafe (unsafeIOToST)+#else+import Control.Monad.ST (unsafeIOToST)+#endif ------------------------------------------------------------------------------ wordSize :: Int
src/Data/HashTable/ST/Basic.hs view
@@ -96,8 +96,7 @@ ------------------------------------------------------------------------------ import Control.Exception (assert) import Control.Monad hiding (foldM, mapM_)-import Control.Monad.ST-import Control.Monad.ST.Unsafe+import Control.Monad.ST (ST) import Data.Bits import Data.Hashable (Hashable) import qualified Data.Hashable as H
src/Data/HashTable/ST/Cuckoo.hs view
@@ -78,9 +78,6 @@ (foldM, mapM_) import Control.Monad.ST-#ifdef DEBUG-import Control.Monad.ST.Unsafe-#endif import Data.Bits import Data.Hashable hiding (hash)@@ -534,7 +531,7 @@ where randomIdx !b = do !z <- getNBits cacheLineIntBits rng- return $! b + z+ return $! b + fromIntegral z bumpIdx !idx !h !k !v = do let !he = hashToElem h
src/Data/HashTable/ST/Linear.hs view
@@ -91,9 +91,6 @@ ------------------------------------------------------------------------------ import Control.Monad hiding (foldM, mapM_) import Control.Monad.ST-#ifdef DEBUG-import Control.Monad.ST.Unsafe-#endif import Data.Bits import Data.Hashable import Data.STRef
test/suite/Data/HashTable/Test/Common.hs view
@@ -12,12 +12,6 @@ ------------------------------------------------------------------------------ import Control.Monad (foldM_, liftM, when)--#if MIN_VERSION_base(4,4,0)-import Control.Monad.ST.Unsafe (unsafeIOToST)-#else-import Control.Monad.ST (unsafeIOToST)-#endif import Data.IORef import Data.List hiding (delete, insert, lookup)@@ -35,6 +29,7 @@ import Test.QuickCheck.Monadic ------------------------------------------------------------------------------ import qualified Data.HashTable.Class as C+import Data.HashTable.Internal.Utils (unsafeIOToST) import Data.HashTable.IO #ifndef PORTABLE