cuckoo 0.1.0.0 → 0.2.0.0

raw patch · 8 files changed

+248/−23 lines, 8 filesdep +doctestPVP ok

version bump matches the API change (PVP)

Dependencies added: doctest

API changes (from Hackage documentation)

Files

• CHANGELOG.md +16/−0
• README.md +79/−0
• bench/SpellChecker.hs +1/−1
• cuckoo.cabal +14/−1
• src/Data/Cuckoo.hs +127/−14
• src/Data/Cuckoo/Internal.hs +3/−3
• test/Main.hs +4/−4
• test/doctest.hs +4/−0

@@ -1,5 +1,21 @@ # Revision history for cuckoo +## 0.2.0.0 -- 2019-08-20++* The PRNG from the random package is new the default. Added cabal flags for+  using `mwc-random` or `pcg-random` instead.++* Changed order of type parameters for `newCuckooHash`. The type of the monad is+  moved to the end, because its usually inferred from the context.++* Minimum capacity (in items) parameter is now 64.++* Fixed the result of `sizeInAllocatedBytes`.++* Added examples to `Data.Cuckoo` along with a doctests test-suite.++* Various documentation fixes and improvements in `Data.Cuckoo`.+ ## 0.1.0.0 -- 2019-08-06  * First version. Released on an unsuspecting world.

@@ -1,4 +1,5 @@ [![Build Status](https://travis-ci.org/larskuhtz/cuckoo.svg?branch=master)](https://travis-ci.org/larskuhtz/cuckoo)+[![Hackage](https://img.shields.io/hackage/v/cuckoo.svg?logo=haskell)](https://hackage.haskell.org/package/cuckoo)  Haskell implementation of Cuckoo filters as described in @@ -20,4 +21,82 @@ The implementation allows the user to specify the bucket size and the fingerprint size in addition to the capacity of the filter. The user can also provide custom functions for computing the primary hash and fingerprint.++## Installation++```bash+cabal v2-install cuckoo+```++For running the test-suites++```bash+cabal v2-test cuckoo+```++For running the benchmarks++```bash+cabal v2-bench cuckoo+```++## Example++```haskell+{-# LANGUAGE DataKinds #-}+{-# LANGUAGE TypeApplications #-}+{-# LANGUAGE TypeFamilies #-}++import Control.Monad (filterM)+import Data.Cuckoo+import Data.List ((\\))++-- Define CuckooFilterHash instance (this uses the default implementation)+instance CuckooFilterHash Int++main :: IO ()+main = do+    -- Create Filter for a minimum of 500000 entries+    f <- newCuckooFilter @4 @8 @Int 0 500000++    -- Insert 450000 items+    failed <- filterM (fmap not . insert f) [0..450000]++    -- Query inserted items+    missing <- filterM (fmap not . member f) [0..450000]++    -- Report results+    putStrLn $ "failed inserts: " <> show (length failed)+    putStrLn $ "false positives: " <> show (length $ failed \\ missing)+    putStrLn $ "missing: " <> show (length $ missing \\ failed)+    c <- itemCount f++    -- some properties of the filter+    putStrLn $ "capacity: " <> show (capacityInItems f)+    putStrLn $ "size in allocated bytes: " <> show (sizeInAllocatedBytes f)++    -- computing the following is slow+    putStrLn $ "item count: " <> show c+    lf <- loadFactor f+    putStrLn $ "load factor: " <> show lf+```++Which produces the following results:++```bash+$ ghc -o main -threaded -O -with-rtsopts=-N Main.hs+[1 of 1] Compiling Main             ( Main.hs, Main.o )+Linking main ...+$ ./main+failed inserts: 0+false positives: 0+missing: 0+capacity: 524288+size in allocated bytes: 524292+item count: 450001+load factor: 85.83087921142578+```++Another example can be found in the file+[bench/SpellChecker.hs](https://github.com/larskuhtz/cuckoo/blob/master/bench/SpellChecker.hs). 

@@ -60,7 +60,7 @@     putStrLn $ show t0 <> "s to count words"      ((f, failed), t1) <- stopWatch $ do-        f <- C.newCuckooFilter @IO @4 @8 0 500000+        f <- C.newCuckooFilter @4 @8 0 500000         failed <- filterM (fmap not . C.insert f) words         return (f, failed) 

@@ -1,6 +1,6 @@ cabal-version: 2.2 name: cuckoo-version: 0.1.0.0+version: 0.2.0.0 synopsis: Haskell Implementation of Cuckoo Filters Description:     Haskell implementation of Cuckoo filters as described in@@ -111,6 +111,19 @@         , hashable >=1.3         , memory >=0.14         , stopwatch >=0.1++test-suite doctests+    type: exitcode-stdio-1.0+    hs-source-dirs: test+    default-language: Haskell2010+    ghc-options:+        -Wall+        -threaded+        -with-rtsopts=-N+    main-is: doctest.hs+    build-depends:+          base >=4.11 && <4.15+        , doctest >= 0.16  benchmark spellchecker     type: exitcode-stdio-1.0

@@ -30,6 +30,45 @@ -- configurations this probability is very small for load factors smaller than -- 90 percent. --+-- = Example+--+-- > {-# LANGUAGE DataKinds #-}+-- > {-# LANGUAGE TypeApplications #-}+-- > {-# LANGUAGE TypeFamilies #-}+-- >+-- > import Control.Monad (filterM)+-- > import Data.Cuckoo+-- > import Data.List ((\\))+-- >+-- > -- Define CuckooFilterHash instance (this uses the default implementation)+-- > instance CuckooFilterHash Int+-- >+-- > main :: IO ()+-- > main = do+-- >     -- Create Filter for a minimum of 500000 entries+-- >     f <- newCuckooFilter @4 @8 @Int 0 500000+-- >+-- >     -- Insert 450000 items+-- >     failed <- filterM (fmap not . insert f) [0..450000]+-- >+-- >     -- Query inserted items+-- >     missing <- filterM (fmap not . member f) [0..450000]+-- >+-- >     -- Report results+-- >     putStrLn $ "failed inserts: " <> show (length failed)+-- >     putStrLn $ "false positives: " <> show (length $ failed \\ missing)+-- >     putStrLn $ "missing: " <> show (length $ missing \\ failed)+-- >     c <- itemCount f+-- >+-- >     -- some properties of the filter+-- >     putStrLn $ "capacity: " <> show (capacityInItems f)+-- >     putStrLn $ "size in allocated bytes: " <> show (sizeInAllocatedBytes f)+-- >+-- >     -- computing the following is slow+-- >     putStrLn $ "item count: " <> show c+-- >     lf <- loadFactor f+-- >     putStrLn $ "load factor: " <> show lf+-- module Data.Cuckoo ( -- * Hash Functions@@ -89,6 +128,10 @@  import Data.Cuckoo.Internal +-- $setup+-- >>> :set -XTypeApplications -XDataKinds -XTypeFamilies+-- >>> instance CuckooFilterHash Int+ -- -------------------------------------------------------------------------- -- -- Hash Functions @@ -122,8 +165,22 @@ -- * provide good uniformity on the lower bits of the output. -- -- The default implementations use sip hash for 'cuckooHash' and 'fnv1a' (64--- bit) for 'cuckooFingerprint'.+-- bit) for 'cuckooFingerprint' and require an instance of 'Storable'. --+-- >>> instance CuckooFilterHash Int+--+-- The following example uses the hash functions that are provided in this+-- module to define an instance for 'B.ByteString':+--+-- >>> import qualified Data.ByteString as B+-- >>> :{+-- instance CuckooFilterHash B.ByteString where+--     cuckooHash (Salt s) a = fnv1a_bytes s a+--     cuckooFingerprint (Salt s) a = sip_bytes s a+--     {-# INLINE cuckooHash #-}+--     {-# INLINE cuckooFingerprint #-}+-- :}+-- class CuckooFilterHash a where      -- | This function must provide good entropy on the lower@@ -136,10 +193,16 @@     --     cuckooFingerprint :: Salt -> a -> Word64 +    -- | Default implementation of 'cuckooHash' for types that are an instance+    -- of 'Storable'.+    --     default cuckooHash :: Storable a => Salt -> a -> Word64     cuckooHash (Salt s) a = sip s a     {-# INLINE cuckooHash #-} +    -- | Default implementation of 'cuckooFingerprint' for types that are an+    -- instance of 'Storable'.+    --     default cuckooFingerprint :: Storable a => Salt -> a -> Word64     cuckooFingerprint (Salt s) a = fnv1a s a     {-# INLINE cuckooFingerprint #-}@@ -176,6 +239,12 @@  -- | Create a new Cuckoo filter that has at least the given capacity. --+-- Enabling the @TypeApplications@ language extension provides a convenient way+-- for passing the type parameters to the function.+--+-- >>> :set -XTypeApplications -XDataKinds -XTypeFamilies+-- >>> newCuckooFilter @4 @10 @Int 0 1000+-- -- The type parameters are -- -- * bucket size @b :: Nat@,@@ -183,13 +252,11 @@ -- * content type @a :: Type@, and -- * Monad @m :: Type -> Type@, ----- Enabling the `TypeApplications` language extension provides a convenient way--- for passing the type parameters to the function.--- -- The following constraints apply: -- -- * \(0 < f \leq 32\),--- * \(0 < b\).+-- * \(0 < b\), and+-- * \(64 \leq n\), where \(n\) is the requested size. -- -- The false positive rate depends mostly on the value of @f@. It is bounded -- from above by \(\frac{2b}{2^f}\). In most cases @4@ is a good choice for @b@.@@ -200,15 +267,21 @@ -- The actual capacity may be much larger than what is requested, because the -- actual bucket count is a power of two. --+-- >>> f <- newCuckooFilter @4 @10 @Int 0 600+-- >>> capacityInItems f+-- 1024+-- >>> sizeInAllocatedBytes f+-- 1284+-- newCuckooFilter-    :: forall m b f a+    :: forall b f a m     . KnownNat b     => KnownNat f     => PrimMonad m     => Salt-        -- ^ Salt for the hash functions+        -- ^ Salt for the hash functions.     -> Natural-        -- ^ Size (must be positive)+        -- ^ Size. Must be at least 64.     -> m (CuckooFilter (PrimState m) b f a) newCuckooFilter salt n = do     check@@ -232,7 +305,7 @@         | not (w @f <= 32) = error "Fingerprint size must not be larger than 32"         | not (0 < w @b) = error "Bucket size (items per bucket) must be positive"         | not (0 < n) = error "The size (number of items) of the filter must be positive"-        | not (32 <= int n * w @f) = error "Seriously? Are you kidding me? If you need to represent such a tiny set, you'll have to pick another data structure for that"+        | not (64 <= n) = error "Seriously? Are you kidding me? If you need to represent such a tiny set, you'll have to pick another data structure for that"         | otherwise = return ()  -- -------------------------------------------------------------------------- --@@ -246,16 +319,27 @@ -- sufficient). Could we also compute the relocation slot from the hash?  -- | Insert an item into the filter and return whether the operation was--- successful. If insertion fails, the filter is unchanged.+-- successful. If insertion fails, the filter is unchanged. An item can be+-- inserted more than once. The return value indicates whether insertion was+-- successful. The operation can fail when the filter doesn't have enough space+-- for the item. -- -- This function is not thread safe. No concurrent writes or reads should occur -- while this function is executed. If this is needed a lock must be used. -- -- This function is not exception safe. The filter must not be used any more--- after an asynchronous exception has been throw during the computation of this+-- after an asynchronous exception has been thrown during the computation of this -- function. If this function is used in the presence of asynchronous exceptions -- it should be apprioriately masked. --+-- >>> f <- newCuckooFilter @4 @10 @Int 0 1000+-- >>> insert f 0+-- True+-- >>> insert f 0+-- True+-- >>> itemCount f+-- 2+-- insert     :: forall b f a m     . KnownNat f@@ -305,6 +389,14 @@ -- false positives is bounded from above by \(\frac{2b}{2^f}\) where @b@ is the number -- of items per bucket and @f@ is the size of a fingerprint in bits. --+-- >>> f <- newCuckooFilter @4 @10 @Int 0 1000+-- >>> insert f 0+-- True+-- >>> member f 0+-- True+-- >>> member f 1+-- False+-- member     :: CuckooFilterHash a     => PrimMonad m@@ -328,18 +420,39 @@ -- -------------------------------------------------------------------------- -- -- Delete --- | Delete an items from the filter.+-- | Delete an items from the filter. An item that was inserted more than once+-- can also be deleted more than once. -- -- /IMPORTANT/ An item must only be deleted if it was successfully added to the -- filter before (and hasn't been deleted since then). ----- Deleting an item that isn't in the filter will result in the filter returning+-- Deleting an item that isn't in the filter can result in the filter returning -- false negative results. -- -- This function is not thread safe. No concurrent writes must occur while this -- function is executed. If this is needed a lock must be used. Concurrent reads -- are fine. --+-- >>> f <- newCuckooFilter @4 @10 @Int 0 1000+-- >>> insert f 0+-- True+-- >>> insert f 0+-- True+-- >>> itemCount f+-- 2+-- >>> delete f 0+-- True+-- >>> itemCount f+-- 1+-- >>> member f 0+-- True+-- >>> delete f 0+-- True+-- >>> itemCount f+-- 0+-- >>> member f 0+-- False+-- delete     :: CuckooFilterHash a     => PrimMonad m@@ -503,7 +616,7 @@ -- | The total number of bytes allocated for storing items in the filter. -- sizeInAllocatedBytes :: forall b f a s . KnownNat f => KnownNat b => CuckooFilter s b f a -> Int-sizeInAllocatedBytes f = intFit @_ @Int (capacityInItems f * w @f) 8+sizeInAllocatedBytes f = intFit @_ @Int (capacityInItems f * w @f) 8 + 4 {-# INLINE sizeInAllocatedBytes #-}  -- | Number of items currently stored in the filter.

@@ -149,7 +149,7 @@     -> Word64 sip s x = r   where-    Right (BA.SipHash r) = BA.sipHash (BA.SipKey (int s) 23)+    Right (BA.SipHash r) = BA.sipHash (BA.SipKey (int s) 914279)         <$> BA.fill @BA.Bytes (sizeOf x) (BA.putStorable x) {-# INLINE sip #-} @@ -168,7 +168,7 @@     -> Word64 sip_bytes s x = r   where-    Right (BA.SipHash r) = BA.sipHash (BA.SipKey (int s) 23)+    Right (BA.SipHash r) = BA.sipHash (BA.SipKey (int s) 1043639)         <$> BA.fill @BA.Bytes (BA.length x) (BA.putBytes x) {-# INLINE sip_bytes #-} @@ -179,7 +179,7 @@ sip2 :: Storable a => Int -> a -> Word64 sip2 s x = r   where-    Right (BA.SipHash r) = BA.sipHash (BA.SipKey 61 (int s * 17))+    Right (BA.SipHash r) = BA.sipHash (BA.SipKey 994559 (int s * 713243))         <$> BA.fill @BA.Bytes (sizeOf x) (BA.putStorable x) {-# INLINE sip2 #-} 

@@ -136,7 +136,7 @@ test0 n = do     rng <- initialize 0     s <- Salt <$> uniform rng-    f <- newCuckooFilter @IO @4 @10 @a s n+    f <- newCuckooFilter @4 @10 @a s n     let go i fp = do             x <- uniform rng             fp' <- bool fp (succ fp) <$> member f x@@ -155,7 +155,7 @@ test1 n = do     rng <- initialize 0     s <- Salt <$> uniform rng-    f <- newCuckooFilter @IO @4 @10 @a s n+    f <- newCuckooFilter @4 @10 @a s n     let go i fp = do             let x = int i             fp' <- bool fp (succ fp) <$> member f x@@ -174,7 +174,7 @@ test2 n = do     rng <- initialize 0     s <- Salt <$> uniform rng-    f <- newCuckooFilter @IO @4 @10 @a s n+    f <- newCuckooFilter @4 @10 @a s n     let go i fp = do             let x = BA.pack (castEnum <$> show i)             fp' <- bool fp (succ fp) <$> member f x@@ -193,7 +193,7 @@ test3 n = do     rng <- initialize 0     s <- Salt <$> uniform rng-    f <- newCuckooFilter @IO @4 @10 @a s n+    f <- newCuckooFilter @4 @10 @a s n     let go i x fp             | int i >= int @_ @Double n * 95 / 100 = return (i, x, fp)         go i x fp = do

@@ -0,0 +1,4 @@+import Test.DocTest++main :: IO ()+main = doctest ["-isrc", "src/Data/Cuckoo.hs"]