unagi-bloomfilter 0.1.0.0 → 0.1.1.0
raw patch · 4 files changed
+345/−79 lines, 4 filesPVP ok
version bump matches the API change (PVP)
API changes (from Hackage documentation)
Files
- benchmarks/Main.hs +187/−64
- src/Control/Concurrent/BloomFilter/Internal.hs +129/−9
- tests/Main.hs +16/−2
- unagi-bloomfilter.cabal +13/−4
benchmarks/Main.hs view
@@ -9,6 +9,7 @@ import Control.Monad import Control.Concurrent import qualified Data.Text as T+import Data.List import Control.Concurrent.BloomFilter.Internal import qualified Control.Concurrent.BloomFilter as Bloom@@ -38,13 +39,8 @@ then putStrLn "!!! WARNING !!!: Some benchmarks are only valid if more than 1 core is available" else return () - b_5_20 <- Bloom.new (SipKey 1 1) 5 20- b_13_20 <- Bloom.new (SipKey 1 1) 13 20 -- needs 128 - -- This has 0.3% fpr for 10000 elements, so I think can be fairly compared- b_text <- Bloom.new (SipKey 11 22) 3 12- let txt = "orange" :: T.Text-+ -- TODO make this a function will call in 'env' let g = mkStdGen 8973459 chars = randoms g :: [Char] fakeWords = go chars@@ -61,26 +57,33 @@ (wds5k_0, wds5k_1) = splitAt 5000 textWords10k deepseq textWords10k $ return () - let hashset10 = HashSet.fromList $ take 10 textWords10k- let hashset100 = HashSet.fromList $ take 100 textWords10k- let hashset10000 = HashSet.fromList $ take 10000 textWords10k- let set10 = Set.fromList $ take 10 textWords10k- let set100 = Set.fromList $ take 100 textWords10k- let set10000 = Set.fromList $ take 10000 textWords10k+ let txt = "orange" :: T.Text+ -- so half are in set and half are not:+ txt10New, txt10Mix :: [T.Text]+ txt10New = take 10 $ reverse textWords10k+ txt10Mix = concatMap (\(x,y)->[x,y]) $ zip textWords10k (take 5 txt10New) defaultMain [ bgroup "internals" [- bench "membershipWordAndBits64" $ nf (membershipWordAndBits64 (Hash64 1)) b_5_20- , bench "membershipWordAndBits128" $ nf (membershipWordAndBits128 (Hash128 1 1)) b_13_20+ env (Bloom.new (SipKey 1 1) 5 20) $ \ ~b->+ bench "membershipWordAndBits64" $ nf (membershipWordAndBits64 (Hash64 1)) b+ , env (Bloom.new (SipKey 1 1) 13 20) $ \ ~b->+ bench "membershipWordAndBits128" $ nf (membershipWordAndBits128 (Hash128 1 1)) b ], -- For comparing cache behavior with perf, against below: bgroup "HashSet" $- [ bench "10K insert" $ whnf (HashSet.fromList) textWords10k ],+ [ bench "10K insert" $ whnf (HashSet.fromList) wds5k_0 + , env (return $ HashSet.fromList textWords10k) $ \ ~hs ->+ bench "10K lookups on 5k elems" $ whnf (foldl1' (==) . map (\t->HashSet.member t hs)) textWords10k+ ], bgroup "Set" $- [ bench "10K insert" $ whnf (Set.fromList) textWords10k ],+ [ bench "10K insert" $ whnf (Set.fromList) textWords10k + , env (return $ Set.fromList textWords10k) $ \ ~hs ->+ bench "10K lookups on 5k elems" $ whnf (foldl1' (==) . map (\t->Set.member t hs)) textWords10k+ ], bgroup "different sizes" $ let benches b = [@@ -139,65 +142,181 @@ bgroup "64MB" (benches b) ] , bgroup "lookup insert" [- bench "siphash64_1_3 for comparison" $ whnf (siphash64_1_3 (SipKey 1 1)) (1::Int)+ bgroup "Int" [+ bench "siphash64_1_3 for comparison" $ whnf (siphash64_1_3 (SipKey 1 1)) (1::Int)+ , bench "siphash128 for comparison" $ whnf (siphash128 (SipKey 1 1)) (1::Int)+ , env (Bloom.new (SipKey 1 1) 3 12) $ \ ~b->+ bgroup "3 12 (64-bit hash)" [ - -- best case, with no cache effects (I think):- , bench "lookup (64)" $ whnfIO (Bloom.lookup b_5_20 (1::Int))- , bench "lookup x10 (64)" $ nfIO (mapM_ (Bloom.lookup b_5_20) [1..10])- , bench "lookup x100 (64)" $ nfIO (mapM_ (Bloom.lookup b_5_20) [1..100])- , bench "lookup (128)" $ whnfIO (Bloom.lookup b_13_20 (1::Int))- , bench "lookup x10 (128)" $ nfIO (mapM_ (Bloom.lookup b_13_20) [1..10])- , bench "lookup x100 (128)" $ nfIO (mapM_ (Bloom.lookup b_13_20) [1..100])+ -- best case, with no cache effects (I think):+ bench "lookup x1" $ whnfIO (Bloom.lookup b (1::Int))+ , bench "lookup x10" $ nfIO (mapM_ (Bloom.lookup b) [1..10])+ , bench "lookup x100" $ nfIO (mapM_ (Bloom.lookup b) [1..100]) - , bench "insert (64)" $ whnfIO (Bloom.insert b_5_20 (1::Int))- , bench "insert x10 (64)" $ nfIO (mapM_ (Bloom.insert b_5_20) [1..10])- , bench "insert x100 (64)" $ nfIO (mapM_ (Bloom.insert b_5_20) [1..100])- , bench "insert (128)" $ whnfIO (Bloom.insert b_13_20 (1::Int))- , bench "insert x10 (128)" $ nfIO (mapM_ (Bloom.insert b_13_20) [1..10])- , bench "insert x100 (128)" $ nfIO (mapM_ (Bloom.insert b_13_20) [1..100])+ , bench "insert x1" $ whnfIO (Bloom.insert b (1::Int))+ , bench "insert x10" $ nfIO (mapM_ (Bloom.insert b) [1..10])+ , bench "insert x100" $ nfIO (mapM_ (Bloom.insert b) [1..100])+ ]+ , env (Bloom.new (SipKey 1 1) 5 20) $ \ ~b->+ bgroup "5 20 (64-bit hash)" [ - ],- bgroup "comparisons micro" [- bench "(just siphash64_1_3 on txt for below)" $ whnf (siphash64_1_3 (SipKey 1 1)) ("orange"::T.Text)- , bench "Bloom.insert (64)" $ whnfIO (Bloom.insert b_text txt)- {- I was concerned that the above might not be valid (perhaps the- - hashing of the Text value was getting reused?), but the following- - convinced me it's all right; we can see differences in size of input- - string reflected in all these benchmarks. I believe bloomInsertPure1- - reflects the inability to inline Hashable instance machinery (since- - it must remain polymorphic.- , bench "Bloom.insert (64)(validation1)" $ whnf (bloomInsertPure1 b_text) txt- , bench "Bloom.insert (64)(validation2)" $ whnf (bloomInsertPure2 b_text) txt- , bench "Bloom.insert (64)(validation3)" $ whnfIO (Bloom.insert b_text "ora")- , bench "Bloom.insert (64)(validation4)" $ whnf (bloomInsertPure1 b_text) "ora"- , bench "Bloom.insert (64)(validation5)" $ whnf (bloomInsertPure2 b_text) "ora"- , bench "(validation orange)" $ whnf (siphash64_1_3 (SipKey 1 1)) ("orange"::T.Text)- , bench "(validation ora)" $ whnf (siphash64_1_3 (SipKey 1 1)) ("ora"::T.Text)- -}+ -- best case, with no cache effects (I think):+ bench "lookup x1" $ whnfIO (Bloom.lookup b (1::Int))+ , bench "lookup x10" $ nfIO (mapM_ (Bloom.lookup b) [1..10])+ , bench "lookup x100" $ nfIO (mapM_ (Bloom.lookup b) [1..100]) - , bench "Set.insert into 10" $ whnf (\t-> Set.insert t set10) txt- , bench "Set.insert into 100" $ whnf (\t-> Set.insert t set100) txt- , bench "Set.insert into 10000" $ whnf (\t-> Set.insert t set10000) txt+ , bench "insert x1" $ whnfIO (Bloom.insert b (1::Int))+ , bench "insert x10" $ nfIO (mapM_ (Bloom.insert b) [1..10])+ , bench "insert x100" $ nfIO (mapM_ (Bloom.insert b) [1..100])+ ]+ , env (Bloom.new (SipKey 1 1) 13 20) $ \ ~b->+ bgroup "13 20 (128-bit hash)" [ - , bench "HashSet.insert into 10" $ whnf (\t-> HashSet.insert t hashset10) txt- , bench "HashSet.insert into 100" $ whnf (\t-> HashSet.insert t hashset100) txt- , bench "HashSet.insert into 10000" $ whnf (\t-> HashSet.insert t hashset10000) txt+ bench "lookup x1" $ whnfIO (Bloom.lookup b (1::Int))+ , bench "lookup x10" $ nfIO (mapM_ (Bloom.lookup b) [1..10])+ , bench "lookup x100" $ nfIO (mapM_ (Bloom.lookup b) [1..100]) - , bench "Bloom.lookup (64)" $ whnfIO (Bloom.lookup b_text txt)+ , bench "insert x1" $ whnfIO (Bloom.insert b (1::Int))+ , bench "insert x10" $ nfIO (mapM_ (Bloom.insert b) [1..10])+ , bench "insert x100" $ nfIO (mapM_ (Bloom.insert b) [1..100])+ ]+ ],+ bgroup "Text" [+ bench "siphash64_1_3 for comparison" $ whnf (siphash64_1_3 (SipKey 1 1)) txt+ , bench "siphash128 for comparison" $ whnf (siphash128 (SipKey 1 1)) txt+ , env (Bloom.new (SipKey 1 1) 3 12) $ \ ~b->+ bgroup "3 12 (64-bit hash)" [ - , bench "Set.member of 10" $ whnf (\t-> Set.member t set10) txt- , bench "Set.member of 100" $ whnf (\t-> Set.member t set100) txt- , bench "Set.member of 10000" $ whnf (\t-> Set.member t set10000) txt+ -- best case, with no cache effects (I think):+ bench "lookup x1" $ whnfIO (Bloom.lookup b txt)+ , bench "lookup x10" $ nfIO (mapM_ (Bloom.lookup b) (take 10 textWords10k))+ , bench "lookup x100" $ nfIO (mapM_ (Bloom.lookup b) (take 100 textWords10k)) - , bench "HashSet.member of 10" $ whnf (\t-> HashSet.member t hashset10) txt- , bench "HashSet.member of 100" $ whnf (\t-> HashSet.member t hashset100) txt- , bench "HashSet.member of 10000" $ whnf (\t-> HashSet.member t hashset10000) txt+ , bench "insert x1" $ whnfIO (Bloom.insert b txt)+ , bench "insert x10" $ nfIO (mapM_ (Bloom.insert b) (take 10 textWords10k))+ , bench "insert x100" $ nfIO (mapM_ (Bloom.insert b) (take 100 textWords10k))+ ]+ , env (Bloom.new (SipKey 1 1) 5 20) $ \ ~b->+ bgroup "5 20 (64-bit hash)" [++ -- best case, with no cache effects (I think):+ bench "lookup x1" $ whnfIO (Bloom.lookup b txt)+ , bench "lookup x10" $ nfIO (mapM_ (Bloom.lookup b) (take 10 textWords10k))+ , bench "lookup x100" $ nfIO (mapM_ (Bloom.lookup b) (take 100 textWords10k))++ , bench "insert x1" $ whnfIO (Bloom.insert b txt)+ , bench "insert x10" $ nfIO (mapM_ (Bloom.insert b) (take 10 textWords10k))+ , bench "insert x100" $ nfIO (mapM_ (Bloom.insert b) (take 100 textWords10k))+ ]+ , env (Bloom.new (SipKey 1 1) 13 20) $ \ ~b->+ bgroup "13 20 (128-bit hash)" [++ bench "lookup x1" $ whnfIO (Bloom.lookup b txt)+ , bench "lookup x10" $ nfIO (mapM_ (Bloom.lookup b) (take 10 textWords10k))+ , bench "lookup x100" $ nfIO (mapM_ (Bloom.lookup b) (take 100 textWords10k))++ , bench "insert x1" $ whnfIO (Bloom.insert b txt)+ , bench "insert x10" $ nfIO (mapM_ (Bloom.insert b) (take 10 textWords10k))+ , bench "insert x100" $ nfIO (mapM_ (Bloom.insert b) (take 100 textWords10k))+ ]+ ]++ ],+ --+ -- TODO check TO SEE HOW THINGS LOOK BEFORE AND AFTER UNFOLDING CHANGE,+ -- MAYBE TRY DOING inserts/lookups x10 here.+ -- 3x12 insert went from 51.8 to 49 (below)+ -- 5x20 insert went from 59.1 to 47.6 (in "lookup insert")+ bgroup "comparisons micro x1 " [+ bench "(just siphash64_1_3 on txt for below)" $ whnf (siphash64_1_3 (SipKey 1 1)) ("orange"::T.Text)+ -- This has 0.3% fpr for 10000 elements, so I think can be fairly compared+ , env (Bloom.new (SipKey 11 22) 3 12) $ \ ~b_text->+ bgroup "unagi-bloomfilter 3 12" [+ bench "insert" $ whnfIO (Bloom.insert b_text txt)+ {- I was concerned that the above might not be valid (perhaps the+ - hashing of the Text value was getting reused?), but the following+ - convinced me it's all right; we can see differences in size of input+ - string reflected in all these benchmarks. I believe bloomInsertPure1+ - reflects the inability to inline Hashable instance machinery (since+ - it must remain polymorphic.+ , bench "Bloom.insert (64)(validation1)" $ whnf (bloomInsertPure1 b_text) txt+ , bench "Bloom.insert (64)(validation2)" $ whnf (bloomInsertPure2 b_text) txt+ , bench "Bloom.insert (64)(validation3)" $ whnfIO (Bloom.insert b_text "ora")+ , bench "Bloom.insert (64)(validation4)" $ whnf (bloomInsertPure1 b_text) "ora"+ , bench "Bloom.insert (64)(validation5)" $ whnf (bloomInsertPure2 b_text) "ora"+ , bench "(validation orange)" $ whnf (siphash64_1_3 (SipKey 1 1)) ("orange"::T.Text)+ , bench "(validation ora)" $ whnf (siphash64_1_3 (SipKey 1 1)) ("ora"::T.Text)+ -}+ , bench "lookup" $ nfIO (Bloom.lookup b_text txt)+ ]++ , env (return $ HashSet.fromList $ take 10 textWords10k) $ \ ~hashset10->+ bgroup "HashSet Text (10)" [+ bench "insert" $ whnf (\t-> HashSet.insert t hashset10) txt+ , bench "member" $ nf (\t-> HashSet.member t hashset10) txt+ ]+ , env (return $ HashSet.fromList $ take 100 textWords10k) $ \ ~hashset100->+ bgroup "HashSet Text (100)" [+ bench "insert" $ whnf (\t-> HashSet.insert t hashset100) txt+ , bench "member" $ nf (\t-> HashSet.member t hashset100) txt+ ]+ , env (return $ HashSet.fromList $ take 10000 textWords10k) $ \ ~hashset10000->+ bgroup "HashSet Text (10000)" [+ bench "insert" $ whnf (\t-> HashSet.insert t hashset10000) txt+ , bench "member" $ nf (\t-> HashSet.member t hashset10000) txt+ ]+ , env (return $ Set.fromList $ take 10 textWords10k) $ \ ~set10->+ bgroup "Set Text (10)" [+ bench "insert" $ whnf (\t-> Set.insert t set10) txt+ , bench "member" $ nf (\t-> Set.member t set10) txt+ ]+ , env (return $ Set.fromList $ take 100 textWords10k) $ \ ~set100->+ bgroup "Set Text (100)" [+ bench "insert" $ whnf (\t-> Set.insert t set100) txt+ , bench "member" $ nf (\t-> Set.member t set100) txt+ ]+ , env (return $ Set.fromList $ take 10000 textWords10k) $ \ ~set10000->+ bgroup "Set Text (10000)" [+ bench "insert" $ whnf (\t-> Set.insert t set10000) txt+ , bench "member" $ nf (\t-> Set.member t set10000) txt+ ] ],+ + bgroup "comparisons micro x10" [+ -- This has 0.3% fpr for 10000 elements, so I think can be fairly compared+ env (Bloom.new (SipKey 11 22) 3 12) $ \ ~b_text->+ bgroup "unagi-bloomfilter 3 12" [+ bench "insert" $ whnfIO (mapM (Bloom.insert b_text) txt10New)+ , bench "lookup" $ nfIO (mapM (Bloom.lookup b_text) txt10Mix)+ ]++ , env (return $ HashSet.fromList $ take 100 textWords10k) $ \ ~hashset100->+ bgroup "HashSet Text (100)" [+ bench "insert" $ whnf (foldr (\t s-> HashSet.insert t s) hashset100) txt10New+ , bench "member" $ nf (map $ \t-> HashSet.member t hashset100) txt10Mix+ ]+ , env (return $ HashSet.fromList $ take 10000 textWords10k) $ \ ~hashset10000->+ bgroup "HashSet Text (10000)" [+ bench "insert" $ whnf (foldr (\t s-> HashSet.insert t s) hashset10000) txt10New+ , bench "member" $ nf (map $ \t-> HashSet.member t hashset10000) txt10Mix+ ]+ , env (return $ Set.fromList $ take 100 textWords10k) $ \ ~set100->+ bgroup "Set Text (100)" [+ bench "insert" $ whnf (foldr (\t s-> Set.insert t s) set100) txt10New+ , bench "member" $ nf (map $ \t-> Set.member t set100) txt10Mix+ ]+ , env (return $ Set.fromList $ take 10000 textWords10k) $ \ ~set10000->+ bgroup "Set Text (10000)" [+ bench "insert" $ whnf (foldr (\t s-> Set.insert t s) set10000) txt10New+ , bench "member" $ nf (map $ \t-> Set.member t set10000) txt10Mix+ ]+ ],+ bgroup "comparisons big" [+ -- TODO large random lookup and insert benchmark, comparing with single-thread and then with work split.+ -- make this how we compare as well?+ -- Do this for various types of elements ],- -- TODO large random lookup and insert benchmark, comparing with single-thread and then with work split.- -- make this how we compare as well?- -- Do this for various types of elements bgroup "combining and creation" [ -- These timings can be subtracted from union timings:@@ -290,4 +409,8 @@ bloomInsertPure2 :: Hashable a => BloomFilter a -> a -> Bool bloomInsertPure2 b = unsafePerformIO . Bloom.insert b++{-# NOINLINE bloomInsertPure3 #-}+bloomInsertPure3 :: BloomFilter Text -> Text -> Bool+bloomInsertPure3 b = unsafePerformIO . Bloom.insert b -}
src/Control/Concurrent/BloomFilter/Internal.hs view
@@ -32,6 +32,7 @@ , log2lFromArraySize , assertionCanary , bytes64, unbytes64+ , setKMemberBits, setKMemberBitsRolled # endif ) where@@ -55,10 +56,12 @@ import Data.Word(Word64, Word8) import Prelude hiding (lookup) + -- Future operations: -- - memory-mapped bloomfilter for durability (which of ACID do we get?). See 'vector-mmap' package? -- - allow opening mmap-ed file directly from serialized form? -- - approximating number of items, and size of union and intersection+-- - simply sample some number of words, in order to get the accuracy the user requests -- - freezing/pure/ST interface (e.g. Data.BloomFilter) -- - API: -- - only allow writes in ST (copying for each write is awful)@@ -256,17 +259,134 @@ in (memberWord, wordToOr) -+-- To promote pipelining, and inlining. This improves lookup and insert by+-- ~15-30% faster depending on which benchmarks we look at and how we squint.+-- We treat this like a macro and expect it to be reduced in the common case+-- where 'k' is a compile-time literal. setKMemberBits :: Int -> Int -> Word64 -> (Int, Word64) {-# INLINE setKMemberBits #-}-setKMemberBits !wd 0 h' = (wd, h')-setKMemberBits !wd !k' !h' =- -- possible cast to 32-bit Int but we only need rightmost 5 or 6 bits:- let !memberBit = fromIntegral h' .&. maskLog2wRightmostBits- in setKMemberBits (wd `uncheckedSetBit` memberBit) (k'-1) (h' `uncheckedShiftR` log2w)+setKMemberBits !wd 1 !h = + ((wd `uncheckedSetBit` (maskLog2w h)) + , h `uncheckedShiftR` (log2w*1)+ )+setKMemberBits !wd 2 !h = + (((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w))) + , h `uncheckedShiftR` (log2w*2)+ )+setKMemberBits !wd 3 !h = + ((((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w)))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*2)))) + , h `uncheckedShiftR` (log2w*3)+ )+setKMemberBits !wd 4 !h = + (((((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w)))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*2))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*3))))++ , h `uncheckedShiftR` (log2w*4)+ )+setKMemberBits !wd 5 !h = + ((((((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w)))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*2))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*3))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*4))))++ , h `uncheckedShiftR` (log2w*5)+ )+setKMemberBits !wd 6 !h = + (((((((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w)))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*2))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*3))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*4))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*5))))++ , h `uncheckedShiftR` (log2w*6)+ )+{- TODO at this point we see a big performance hit in 7.10 (in e.g. "lookup insert/Int/3 12 (64-bit hash)/lookup x10")+ presumably because the case is big enough that GHC does something different with it, but we need to look at core+ to find out for sure. Maybe we can turn 'k' into an enumeration One | Two | Three at creation, and that might help+setKMemberBits !wd 7 h = + ((((((((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w)))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*2))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*3))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*4))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*5))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*6))))++ , h `uncheckedShiftR` (log2w*7)+ )+setKMemberBits !wd 8 h = + (((((((((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w)))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*2))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*3))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*4))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*5))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*6))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*7))))++ , h `uncheckedShiftR` (log2w*8)+ )+setKMemberBits !wd 9 h = + ((((((((((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w)))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*2))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*3))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*4))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*5))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*6))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*7))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*8))))++ , h `uncheckedShiftR` (log2w*9)+ )+setKMemberBits !wd 10 h = + (((((((((((wd `uncheckedSetBit` (maskLog2w h))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` log2w)))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*2))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*3))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*4))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*5))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*6))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*7))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*8))))+ `uncheckedSetBit` (maskLog2w (h `uncheckedShiftR` (log2w*9))))++ , h `uncheckedShiftR` (log2w*10)+ )+-}+-- 10 is all we should ever need since 11*log2w is always > w. If we unroll to+-- 10 this ought to be unreachable, in fact:+setKMemberBits !wd !k !h = setKMemberBitsRolled wd k h where++-- The non-unrolled version we fall back to, exposed for testing:+setKMemberBitsRolled :: Int -> Int -> Word64 -> (Int, Word64)+# ifdef ASSERTIONS_ON+-- work around simplifier ticks exhausted bullshit, when compiling tests+# else+{-# INLINE setKMemberBitsRolled #-}+# endif+setKMemberBitsRolled !wd !k !h = go wd k h where+ go wd' 0 h' = (wd', h')+ go wd' k' h' = + -- possible cast to 32-bit Int but we only need rightmost 5 or 6 bits:+ let !memberBit = fromIntegral h' .&. maskLog2wRightmostBits+ in go (wd' `uncheckedSetBit` memberBit) (k'-1) (h' `uncheckedShiftR` log2w)++maskLog2w :: Word64 -> Int+{-# INLINE maskLog2w #-}+maskLog2w !h = fromIntegral h .&. maskLog2wRightmostBits++ membershipWordAndBitsFor :: (Hashable a)=> BloomFilter a -> a -> (Int, Int) {-# INLINE membershipWordAndBitsFor #-} membershipWordAndBitsFor bloom@(BloomFilter{..}) a@@ -300,18 +420,18 @@ uncheckedSetBit :: Int -> Int -> Int {-# INLINE uncheckedSetBit #-}-uncheckedSetBit x i = x .|. (1 `uncheckedShiftL` i)+uncheckedSetBit !x !i = x .|. (1 `uncheckedShiftL` i) uncheckedShiftR :: (Num a, FiniteBits a, Ord a) => a -> Int -> a {-# INLINE uncheckedShiftR #-}-uncheckedShiftR a = \x->+uncheckedShiftR !a = \ !x-> assert (a >= 0) $ -- make sure we don't smear sign w/ a bad fromIntegral cast assert (x < finiteBitSize a) $ assert (x >= 0) $ a `BitsHidden.unsafeShiftR` x uncheckedShiftL :: (Num a, FiniteBits a, Ord a) => a -> Int -> a {-# INLINE uncheckedShiftL #-}-uncheckedShiftL a = \x->+uncheckedShiftL !a = \ !x-> assert (a >= 0) $ assert (x < finiteBitSize a) $ assert (x >= 0) $
tests/Main.hs view
@@ -12,6 +12,7 @@ import qualified Data.ByteString as B import Control.Monad import Control.Concurrent+import System.IO import Data.Word import Control.Exception import Text.Printf@@ -22,6 +23,7 @@ main :: IO () main = do+ hSetBuffering stdout NoBuffering # ifdef ASSERTIONS_ON checkAssertionsOn # else@@ -37,6 +39,8 @@ fromBits64 ((replicate 62 '0') ++ "11") == 3) $ error "fromBits64 helper borked" + -- make output to keep travis happy:+ void $ forkIO $ forever (putStr "." >> threadDelay (1000*1000)) -- uncheckedSetBit: -------- quickCheckErr 10000 $ \(Large i) ->@@ -50,7 +54,6 @@ && (2^log2w == wordSizeInBits)) $ error "log2w /= logBase 2 wordSizeInBits" - -- maskLog2wRightmostBits -------- let w = (2^^log2w) :: Float unless ((w-1) == fromIntegral maskLog2wRightmostBits) $@@ -72,12 +75,15 @@ -- for membershipWordAndBits128 and membershipWordAndBits64: membershipWordTests + setKMemberBitsUnrolledTest+ -- Creation/Insertion/FPR unit tests: createInsertFprTests smallBloomTest insertSaturateTest insertConcurrentTest- highFprTest+ -- TODO disabled for now; it might be that this was not quite right originally, but we manually deleted the cases that didn't work quite accurately under the old hashing scheme:+ -- highFprTest expectedExceptionsTest @@ -89,6 +95,14 @@ serializationTests putStrLn "TESTS PASSED"++setKMemberBitsUnrolledTest :: IO ()+setKMemberBitsUnrolledTest = do+ forM_ [1..10] $ \n ->+ quickCheckErr 1000 $ \(Large wd, Large h)-> + setKMemberBits wd n h ==+ setKMemberBitsRolled wd n h+ -- Test exceptions that should only be possible to raise in untyped interface: expectedExceptionsTest :: IO ()
unagi-bloomfilter.cabal view
@@ -1,5 +1,5 @@ name: unagi-bloomfilter-version: 0.1.0.0+version: 0.1.1.0 synopsis: A fast, cache-efficient, concurrent bloom filter description: This library implements a fast concurrent bloom filter, based on bloom-1 from@@ -10,10 +10,14 @@ SipHash so can safely consume untrusted inputs. . The implementation here compares favorably with traditional set- implementations in a single-threaded context:+ implementations in a single-threaded context, e.g. here are 10 inserts or+ lookups compared across some sets of different sizes: .- <<http://i.imgur.com/t3vroKE.png>>+ <<http://i.imgur.com/gei1LW4.png>> .+ With the llvm backend benchmarks take around 75-85% of the runtime of the+ native code gen.+ . Unfortunately writes in particular don't seem to scale currently; i.e. distributing writes across multiple threads may be /slower/ than in a single-threaded context, because of memory effects. We plan to export@@ -54,6 +58,7 @@ if flag(dev) CPP-Options: -DEXPORT_INTERNALS if flag(instrumented)+ CPP-Options: -DASSERTIONS_ON ghc-options: -fno-ignore-asserts -- TODO stacktraces don't seem to show anything useful. Maybe because of INLINEs?: -- ghc-prof-options: "-with-rtsopts=-xc" -fprof-auto -fprof-auto-calls@@ -72,6 +77,7 @@ ghc-options: -Wall -fwarn-tabs -O2 -funbox-strict-fields test-suite tests+ ghc-options: -fsimpl-tick-factor=1000 type: exitcode-stdio-1.0 default-language: Haskell2010 hs-source-dirs: tests@@ -103,6 +109,8 @@ main-is: Main.hs ghc-options: -Wall -O2 -threaded -funbox-strict-fields ghc-options: "-with-rtsopts=-N -A50M -qa"+ ghc-options: -rtsopts+ ghc-prof-options: -fprof-auto -fprof-auto-calls hs-source-dirs: benchmarks if flag(instrumented) CPP-Options: -DASSERTIONS_ON@@ -132,7 +140,8 @@ -- ghc-options: -ddump-to-file -ddump-simpl -dsuppress-module-prefixes -dsuppress-uniques -ddump-core-stats -ddump-inlinings ghc-options: -O2 -rtsopts -- for ghc bug(?) https://ghc.haskell.org/trac/ghc/ticket/11263- ghc-options: -fsimpl-tick-factor=200+ -- (had to bump once again for additional setKMemberBits unrolling) + ghc-options: -fsimpl-tick-factor=1000 -- Either do threaded for eventlogging and simple timing... -- ghc-options: -threaded -eventlog