{-# LANGUAGE MagicHash           #-}
{-# LANGUAGE PatternSynonyms     #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UnboxedTuples       #-}
{-# OPTIONS_HADDOCK not-home #-}

-- The use of -fregs-iterative here does a better job in the hot loop for
-- the bloomQueriesBody below. It eliminates all spilling to the stack.
-- There's just 6 stack reads in the loop now, no writes.
{-# OPTIONS_GHC -O2 -fregs-iterative -fmax-inline-alloc-size=512 #-}

-- | An implementation of batched bloom filter query, optimised for memory
-- prefetch.
module Database.LSMTree.Internal.BloomFilterQuery2 (
  bloomQueries,
  RunIxKeyIx(RunIxKeyIx),
  RunIx, KeyIx,
  -- $algorithm
  -- * Internals exposed for tests
  CandidateProbe (..),
) where

import           Prelude hiding (filter)

import           Data.Bits
import qualified Data.Primitive as P
import qualified Data.Vector as V
import qualified Data.Vector.Primitive as VP
import           Data.Word (Word64)

import           Control.Exception (assert)
import           Control.Monad.ST (ST, runST)

import           GHC.Exts (Int#, uncheckedIShiftL#, (+#))

import           Data.BloomFilter (Bloom)
import qualified Data.BloomFilter as Bloom
import qualified Data.BloomFilter.BitVec64 as BV64
import qualified Data.BloomFilter.Hash as Bloom
import qualified Data.BloomFilter.Internal as BF
import           Database.LSMTree.Internal.BloomFilterQuery1 (RunIxKeyIx (..))
import           Database.LSMTree.Internal.Serialise (SerialisedKey)
import qualified Database.LSMTree.Internal.StrictArray as P
import qualified Database.LSMTree.Internal.Vector as P

-- Bulk query
-----------------------------------------------------------

type KeyIx = Int
type RunIx = Int

-- $algorithm
--
-- == Key algorithm concepts
--
-- There is almost no opportunity for memory prefetching when looking up a
-- single key in a single Bloom filter. So this is a bulk algorithm, to do a
-- lot of work all in one go, which does create the opportunity to prefetch
-- memory. It also provides an opportunity to share key hashes across filters.
--
-- We have as inputs N bloom filters and M keys to look up in them. So overall
-- there are N * M independent bloom filter tests. The result is expected to be
-- sparse, with roughly M*(1+FPR) positive results. So we use a sparse
-- representation for the result: pairs of indexes identifying input Bloom
-- filters and input keys with a positive test result.
--
-- We aim for the number of memory operations in-flight simultaneously to be on
-- the order of 32. This trades-off memory parallelism with cache use. In
-- particular this means the algorithm must be able to use a fixed prefetch
-- \"distance\" rather than this being dependent on the input sizes. To achieve
-- this, we use a fixed size circular buffer (queue). The buffer size can be
-- tuned to optimise the prefetch behaviour: indeed we pick exactly 32.
--
-- == Micro optimisation
--
-- We use primitive arrays and arrays -- rather than vectors -- so as to
-- minimise the number of function variables, to be able to keep most things in
-- registers. Normal vectors use two additional variables, which triples
-- register pressure.
--
-- We use an Array of Strict BloomFilter. This avoids the test for WHNF in the
-- inner loop, which causes all registered to be spilled to and restored from
--the stack.
--

type Candidate = RunIxKeyIx

-- | A candidate probe point is the combination of a filter\/run index,
-- key index and hash number. This combination determines the probe location
-- in the bloom filter, which is also cached.
--
-- We store these in 'PrimArray's as a pair of 64bit words:
--
-- * Low 64bit word:
--   - 16 bits padding (always 0s)    (MSB)
--   - 16 bits for the hash number
--   - 16 bits for the filter index
--   - 16 bits for the key index      (LSB)
--
-- * High 64bit word: FilterBitIx
--
data CandidateProbe = MkCandidateProbe !Word64 !Word64

type HashNo = Int
type FilterBitIx = Int

instance P.Prim CandidateProbe where
    sizeOfType# :: Proxy CandidateProbe -> Int#
sizeOfType# Proxy CandidateProbe
_ = Int#
16#
    alignmentOfType# :: Proxy CandidateProbe -> Int#
alignmentOfType# Proxy CandidateProbe
_ = Int#
8#

    indexByteArray# :: ByteArray# -> Int# -> CandidateProbe
indexByteArray# ByteArray#
ba Int#
i =
      Word64 -> Word64 -> CandidateProbe
MkCandidateProbe
        (ByteArray# -> Int# -> Word64
forall a. Prim a => ByteArray# -> Int# -> a
P.indexByteArray# ByteArray#
ba (Int# -> Int#
indexLo Int#
i))
        (ByteArray# -> Int# -> Word64
forall a. Prim a => ByteArray# -> Int# -> a
P.indexByteArray# ByteArray#
ba (Int# -> Int#
indexHi Int#
i))
    readByteArray# :: forall s.
MutableByteArray# s
-> Int# -> State# s -> (# State# s, CandidateProbe #)
readByteArray# MutableByteArray# s
ba Int#
i State# s
s1 =
        case MutableByteArray# s -> Int# -> State# s -> (# State# s, Word64 #)
forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, Word64 #)
forall a s.
Prim a =>
MutableByteArray# s -> Int# -> State# s -> (# State# s, a #)
P.readByteArray# MutableByteArray# s
ba (Int# -> Int#
indexLo Int#
i) State# s
s1 of { (# State# s
s2, Word64
lo #) ->
        case MutableByteArray# s -> Int# -> State# s -> (# State# s, Word64 #)
forall s.
MutableByteArray# s -> Int# -> State# s -> (# State# s, Word64 #)
forall a s.
Prim a =>
MutableByteArray# s -> Int# -> State# s -> (# State# s, a #)
P.readByteArray# MutableByteArray# s
ba (Int# -> Int#
indexHi Int#
i) State# s
s2 of { (# State# s
s3, Word64
hi #) ->
        (# State# s
s3, Word64 -> Word64 -> CandidateProbe
MkCandidateProbe Word64
lo Word64
hi #)
        }}
    writeByteArray# :: forall s.
MutableByteArray# s
-> Int# -> CandidateProbe -> State# s -> State# s
writeByteArray# MutableByteArray# s
ba Int#
i (MkCandidateProbe Word64
lo Word64
hi) State# s
s =
        MutableByteArray# s -> Int# -> Word64 -> State# s -> State# s
forall s.
MutableByteArray# s -> Int# -> Word64 -> State# s -> State# s
forall a s.
Prim a =>
MutableByteArray# s -> Int# -> a -> State# s -> State# s
P.writeByteArray# MutableByteArray# s
ba (Int# -> Int#
indexHi Int#
i) Word64
hi
       (MutableByteArray# s -> Int# -> Word64 -> State# s -> State# s
forall s.
MutableByteArray# s -> Int# -> Word64 -> State# s -> State# s
forall a s.
Prim a =>
MutableByteArray# s -> Int# -> a -> State# s -> State# s
P.writeByteArray# MutableByteArray# s
ba (Int# -> Int#
indexLo Int#
i) Word64
lo State# s
s)

    indexOffAddr# :: Addr# -> Int# -> CandidateProbe
indexOffAddr# Addr#
ba Int#
i =
      Word64 -> Word64 -> CandidateProbe
MkCandidateProbe
        (Addr# -> Int# -> Word64
forall a. Prim a => Addr# -> Int# -> a
P.indexOffAddr# Addr#
ba (Int# -> Int#
indexLo Int#
i))
        (Addr# -> Int# -> Word64
forall a. Prim a => Addr# -> Int# -> a
P.indexOffAddr# Addr#
ba (Int# -> Int#
indexHi Int#
i))
    readOffAddr# :: forall s.
Addr# -> Int# -> State# s -> (# State# s, CandidateProbe #)
readOffAddr# Addr#
ba Int#
i State# s
s1 =
        case Addr# -> Int# -> State# s -> (# State# s, Word64 #)
forall s. Addr# -> Int# -> State# s -> (# State# s, Word64 #)
forall a s.
Prim a =>
Addr# -> Int# -> State# s -> (# State# s, a #)
P.readOffAddr# Addr#
ba (Int# -> Int#
indexLo Int#
i) State# s
s1 of { (# State# s
s2, Word64
lo #) ->
        case Addr# -> Int# -> State# s -> (# State# s, Word64 #)
forall s. Addr# -> Int# -> State# s -> (# State# s, Word64 #)
forall a s.
Prim a =>
Addr# -> Int# -> State# s -> (# State# s, a #)
P.readOffAddr# Addr#
ba (Int# -> Int#
indexHi Int#
i) State# s
s2 of { (# State# s
s3, Word64
hi #) ->
        (# State# s
s3, Word64 -> Word64 -> CandidateProbe
MkCandidateProbe Word64
lo Word64
hi #)
        }}
    writeOffAddr# :: forall s. Addr# -> Int# -> CandidateProbe -> State# s -> State# s
writeOffAddr# Addr#
ba Int#
i (MkCandidateProbe Word64
lo Word64
hi) State# s
s =
        Addr# -> Int# -> Word64 -> State# s -> State# s
forall s. Addr# -> Int# -> Word64 -> State# s -> State# s
forall a s. Prim a => Addr# -> Int# -> a -> State# s -> State# s
P.writeOffAddr# Addr#
ba (Int# -> Int#
indexHi Int#
i) Word64
hi
       (Addr# -> Int# -> Word64 -> State# s -> State# s
forall s. Addr# -> Int# -> Word64 -> State# s -> State# s
forall a s. Prim a => Addr# -> Int# -> a -> State# s -> State# s
P.writeOffAddr# Addr#
ba (Int# -> Int#
indexLo Int#
i) Word64
lo State# s
s)

indexLo :: Int# -> Int#
indexLo :: Int# -> Int#
indexLo Int#
i = Int# -> Int# -> Int#
uncheckedIShiftL# Int#
i Int#
1#

indexHi :: Int# -> Int#
indexHi :: Int# -> Int#
indexHi Int#
i = Int# -> Int# -> Int#
uncheckedIShiftL# Int#
i Int#
1# Int# -> Int# -> Int#
+# Int#
1#

pattern CandidateProbe :: RunIx
                       -> KeyIx
                       -> HashNo
                       -> FilterBitIx
                       -> CandidateProbe
pattern $mCandidateProbe :: forall {r}.
CandidateProbe
-> (KeyIx -> KeyIx -> KeyIx -> KeyIx -> r) -> ((# #) -> r) -> r
$bCandidateProbe :: KeyIx -> KeyIx -> KeyIx -> KeyIx -> CandidateProbe
CandidateProbe r k h p <- (unpackCandidateProbe -> (r, k, h, p))
  where
    CandidateProbe KeyIx
r KeyIx
k KeyIx
h KeyIx
p = KeyIx -> KeyIx -> KeyIx -> KeyIx -> CandidateProbe
packCandidateProbe KeyIx
r KeyIx
k KeyIx
h KeyIx
p
{-# INLINE CandidateProbe #-}
{-# COMPLETE CandidateProbe #-}

unpackCandidateProbe :: CandidateProbe -> (Int, Int, Int, Int)
unpackCandidateProbe :: CandidateProbe -> (KeyIx, KeyIx, KeyIx, KeyIx)
unpackCandidateProbe (MkCandidateProbe Word64
lo Word64
hi) =
    ( Word64 -> KeyIx
forall a b. (Integral a, Num b) => a -> b
fromIntegral ((Word64
lo Word64 -> KeyIx -> Word64
forall a. Bits a => a -> KeyIx -> a
`unsafeShiftR` KeyIx
16) Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xffff) -- run ix
    , Word64 -> KeyIx
forall a b. (Integral a, Num b) => a -> b
fromIntegral ( Word64
lo                    Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.&. Word64
0xffff) -- key ix
    , Word64 -> KeyIx
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Word64
lo Word64 -> KeyIx -> Word64
forall a. Bits a => a -> KeyIx -> a
`unsafeShiftR` KeyIx
32)            -- hashno
    , Word64 -> KeyIx
forall a b. (Integral a, Num b) => a -> b
fromIntegral  Word64
hi
    )
{-# INLINE unpackCandidateProbe #-}

packCandidateProbe :: Int -> Int -> Int -> Int -> CandidateProbe
packCandidateProbe :: KeyIx -> KeyIx -> KeyIx -> KeyIx -> CandidateProbe
packCandidateProbe KeyIx
r KeyIx
k KeyIx
h KeyIx
p =
    Bool -> CandidateProbe -> CandidateProbe
forall a. Bool -> a -> a
assert (KeyIx
r KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
>= KeyIx
0 Bool -> Bool -> Bool
&& KeyIx
r KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
<= KeyIx
0xffff) (CandidateProbe -> CandidateProbe)
-> CandidateProbe -> CandidateProbe
forall a b. (a -> b) -> a -> b
$
    Bool -> CandidateProbe -> CandidateProbe
forall a. Bool -> a -> a
assert (KeyIx
k KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
>= KeyIx
0 Bool -> Bool -> Bool
&& KeyIx
k KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
<= KeyIx
0xffff) (CandidateProbe -> CandidateProbe)
-> CandidateProbe -> CandidateProbe
forall a b. (a -> b) -> a -> b
$
    Bool -> CandidateProbe -> CandidateProbe
forall a. Bool -> a -> a
assert (KeyIx
h KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
>= KeyIx
0 Bool -> Bool -> Bool
&& KeyIx
h KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
<= KeyIx
0xffff) (CandidateProbe -> CandidateProbe)
-> CandidateProbe -> CandidateProbe
forall a b. (a -> b) -> a -> b
$
    Word64 -> Word64 -> CandidateProbe
MkCandidateProbe
      (   KeyIx -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral KeyIx
r Word64 -> KeyIx -> Word64
forall a. Bits a => a -> KeyIx -> a
`unsafeShiftL` KeyIx
16  -- run ix
      Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.|. KeyIx -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral KeyIx
k                    -- key ix
      Word64 -> Word64 -> Word64
forall a. Bits a => a -> a -> a
.|. KeyIx -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral KeyIx
h Word64 -> KeyIx -> Word64
forall a. Bits a => a -> KeyIx -> a
`unsafeShiftL` KeyIx
32) -- hashno
      (KeyIx -> Word64
forall a b. (Integral a, Num b) => a -> b
fromIntegral KeyIx
p)
{-# INLINE packCandidateProbe #-}

instance Show CandidateProbe where
  showsPrec :: KeyIx -> CandidateProbe -> ShowS
showsPrec KeyIx
_ (CandidateProbe KeyIx
r KeyIx
k KeyIx
h KeyIx
p) =
      String -> ShowS
showString String
"CandidateProbe "
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyIx -> KeyIx -> ShowS
forall a. Show a => KeyIx -> a -> ShowS
showsPrec KeyIx
11 KeyIx
r
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
' '
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyIx -> KeyIx -> ShowS
forall a. Show a => KeyIx -> a -> ShowS
showsPrec KeyIx
11 KeyIx
k
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
' '
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyIx -> KeyIx -> ShowS
forall a. Show a => KeyIx -> a -> ShowS
showsPrec KeyIx
11 KeyIx
h
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Char -> ShowS
showChar Char
' '
    ShowS -> ShowS -> ShowS
forall b c a. (b -> c) -> (a -> b) -> a -> c
. KeyIx -> KeyIx -> ShowS
forall a. Show a => KeyIx -> a -> ShowS
showsPrec KeyIx
11 KeyIx
p



bloomQueries ::
     V.Vector (Bloom SerialisedKey)
  -> V.Vector SerialisedKey
  -> VP.Vector RunIxKeyIx
bloomQueries :: Vector (Bloom SerialisedKey)
-> Vector SerialisedKey -> Vector RunIxKeyIx
bloomQueries Vector (Bloom SerialisedKey)
filters Vector SerialisedKey
keys | Vector (Bloom SerialisedKey) -> Bool
forall a. Vector a -> Bool
V.null Vector (Bloom SerialisedKey)
filters Bool -> Bool -> Bool
|| Vector SerialisedKey -> Bool
forall a. Vector a -> Bool
V.null Vector SerialisedKey
keys
                          = Vector RunIxKeyIx
forall a. Prim a => Vector a
VP.empty
bloomQueries Vector (Bloom SerialisedKey)
filters Vector SerialisedKey
keys =
  Bool -> Vector RunIxKeyIx -> Vector RunIxKeyIx
forall a. Bool -> a -> a
assert ((Bloom SerialisedKey -> Bool)
-> Vector (Bloom SerialisedKey) -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all Bloom SerialisedKey -> Bool
forall (h :: * -> *) a. Bloom' h a -> Bool
BF.bloomInvariant Vector (Bloom SerialisedKey)
filters) (Vector RunIxKeyIx -> Vector RunIxKeyIx)
-> Vector RunIxKeyIx -> Vector RunIxKeyIx
forall a b. (a -> b) -> a -> b
$
  -- in particular the bloomInvariant checks the size is > 0
  (forall s. ST s (Vector RunIxKeyIx)) -> Vector RunIxKeyIx
forall a. (forall s. ST s a) -> a
runST ((forall s. ST s (Vector RunIxKeyIx)) -> Vector RunIxKeyIx)
-> (forall s. ST s (Vector RunIxKeyIx)) -> Vector RunIxKeyIx
forall a b. (a -> b) -> a -> b
$ do
    let !keyhashes :: PrimArray (CheapHashes SerialisedKey)
keyhashes = Vector SerialisedKey -> PrimArray (CheapHashes SerialisedKey)
prepKeyHashes Vector SerialisedKey
keys
        !filters' :: StrictArray (Bloom SerialisedKey)
filters'  = Vector (Bloom SerialisedKey) -> StrictArray (Bloom SerialisedKey)
forall a. Vector a -> StrictArray a
P.vectorToStrictArray Vector (Bloom SerialisedKey)
filters
    MutablePrimArray s CandidateProbe
candidateProbes <- KeyIx -> ST s (MutablePrimArray (PrimState (ST s)) CandidateProbe)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
KeyIx -> m (MutablePrimArray (PrimState m) a)
P.newPrimArray KeyIx
0x20
    -- We deliberately do not clear this array as it will get overwritten.
    -- But for debugging, it's less confusing to initialise to all zeros.
    -- To do that, uncomment the following line:
    --P.setPrimArray 0 0x20 candidateProbes (MkCandidateProbe 0 0)

    let i_r :: KeyIx
i_r = KeyIx
0
    (KeyIx
i_w, RunIxKeyIx
nextCandidate) <-
      StrictArray (Bloom SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
-> MutablePrimArray s CandidateProbe
-> KeyIx
-> RunIxKeyIx
-> ST s (KeyIx, RunIxKeyIx)
forall s.
StrictArray (Bloom SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
-> MutablePrimArray s CandidateProbe
-> KeyIx
-> RunIxKeyIx
-> ST s (KeyIx, RunIxKeyIx)
prepInitialCandidateProbes
        StrictArray (Bloom SerialisedKey)
filters' PrimArray (CheapHashes SerialisedKey)
keyhashes
        MutablePrimArray s CandidateProbe
candidateProbes
        KeyIx
0 (KeyIx -> KeyIx -> RunIxKeyIx
RunIxKeyIx KeyIx
0 KeyIx
0)

    PrimArray RunIxKeyIx
output <- StrictArray (Bloom SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
-> MutablePrimArray s CandidateProbe
-> KeyIx
-> KeyIx
-> RunIxKeyIx
-> ST s (PrimArray RunIxKeyIx)
forall s.
StrictArray (Bloom SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
-> MutablePrimArray s CandidateProbe
-> KeyIx
-> KeyIx
-> RunIxKeyIx
-> ST s (PrimArray RunIxKeyIx)
bloomQueriesBody StrictArray (Bloom SerialisedKey)
filters' PrimArray (CheapHashes SerialisedKey)
keyhashes MutablePrimArray s CandidateProbe
candidateProbes
                               KeyIx
i_r KeyIx
i_w RunIxKeyIx
nextCandidate
    Vector RunIxKeyIx -> ST s (Vector RunIxKeyIx)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (Vector RunIxKeyIx -> ST s (Vector RunIxKeyIx))
-> Vector RunIxKeyIx -> ST s (Vector RunIxKeyIx)
forall a b. (a -> b) -> a -> b
$! PrimArray RunIxKeyIx -> Vector RunIxKeyIx
forall a. Prim a => PrimArray a -> Vector a
P.primArrayToPrimVector PrimArray RunIxKeyIx
output

prepKeyHashes :: V.Vector SerialisedKey
              -> P.PrimArray (Bloom.CheapHashes SerialisedKey)
prepKeyHashes :: Vector SerialisedKey -> PrimArray (CheapHashes SerialisedKey)
prepKeyHashes Vector SerialisedKey
keys =
    KeyIx
-> (KeyIx -> CheapHashes SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
forall a. Prim a => KeyIx -> (KeyIx -> a) -> PrimArray a
P.generatePrimArray (Vector SerialisedKey -> KeyIx
forall a. Vector a -> KeyIx
V.length Vector SerialisedKey
keys) ((KeyIx -> CheapHashes SerialisedKey)
 -> PrimArray (CheapHashes SerialisedKey))
-> (KeyIx -> CheapHashes SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
forall a b. (a -> b) -> a -> b
$ \KeyIx
i ->
      SerialisedKey -> CheapHashes SerialisedKey
forall a. Hashable a => a -> CheapHashes a
Bloom.makeCheapHashes (Vector SerialisedKey -> KeyIx -> SerialisedKey
forall a. Vector a -> KeyIx -> a
V.unsafeIndex Vector SerialisedKey
keys KeyIx
i)

prepInitialCandidateProbes ::
     P.StrictArray (Bloom SerialisedKey)
  -> P.PrimArray (Bloom.CheapHashes SerialisedKey)
     -- ^ The pre-computed \"cheap hashes\" of the keys.
  -> P.MutablePrimArray s CandidateProbe
     -- ^ The array of candidates: of FilterIx, KeyIx and HashNo. This is
     -- used as a fixed size rolling buffer.
  -> Int
     -- ^ The write index within the rolling buffer. This wraps around.
  -> RunIxKeyIx
     -- ^ The last candidate added to the rolling buffer.
  -> ST s (Int,  RunIxKeyIx)
prepInitialCandidateProbes :: forall s.
StrictArray (Bloom SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
-> MutablePrimArray s CandidateProbe
-> KeyIx
-> RunIxKeyIx
-> ST s (KeyIx, RunIxKeyIx)
prepInitialCandidateProbes
    StrictArray (Bloom SerialisedKey)
filters PrimArray (CheapHashes SerialisedKey)
keyhashes
    MutablePrimArray s CandidateProbe
candidateProbes KeyIx
i_w
    nextCandidate :: RunIxKeyIx
nextCandidate@(RunIxKeyIx KeyIx
rix KeyIx
kix)

  | KeyIx
i_w KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
< KeyIx
0x1f Bool -> Bool -> Bool
&& KeyIx
rix KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
< StrictArray (Bloom SerialisedKey) -> KeyIx
forall a. StrictArray a -> KeyIx
P.sizeofStrictArray StrictArray (Bloom SerialisedKey)
filters = do
    -- We prepare at most 31 (not 32) candidates, in the buffer of size 32.
    -- This is because we define the buffer to be empty when i_r == i_w. Hence
    -- we cannot fill all entries in the array.

    let !filter :: Bloom SerialisedKey
filter  = StrictArray (Bloom SerialisedKey) -> KeyIx -> Bloom SerialisedKey
forall a. StrictArray a -> KeyIx -> a
P.indexStrictArray StrictArray (Bloom SerialisedKey)
filters KeyIx
rix
        !keyhash :: CheapHashes SerialisedKey
keyhash = PrimArray (CheapHashes SerialisedKey)
-> KeyIx -> CheapHashes SerialisedKey
forall a. Prim a => PrimArray a -> KeyIx -> a
P.indexPrimArray PrimArray (CheapHashes SerialisedKey)
keyhashes KeyIx
kix
        !hn :: KeyIx
hn      = Bloom SerialisedKey -> KeyIx
forall (h :: * -> *) a. Bloom' h a -> KeyIx
BF.hashesN Bloom SerialisedKey
filter KeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
- KeyIx
1
        !bix :: KeyIx
bix     = (Word64 -> KeyIx
forall a b. (Integral a, Num b) => a -> b
fromIntegral :: Word64 -> Int) (Word64 -> KeyIx) -> Word64 -> KeyIx
forall a b. (a -> b) -> a -> b
$
                   CheapHashes SerialisedKey -> KeyIx -> Word64
forall {k} (a :: k). CheapHashes a -> KeyIx -> Word64
Bloom.evalCheapHashes CheapHashes SerialisedKey
keyhash KeyIx
hn
                     Word64 -> Word64 -> Word64
`BV64.unsafeRemWord64` -- size must be > 0
                   Bloom SerialisedKey -> Word64
forall (h :: * -> *) a. Bloom' h a -> Word64
BF.size Bloom SerialisedKey
filter           -- bloomInvariant ensures this
    BitVec64 -> KeyIx -> ST s ()
forall s. BitVec64 -> KeyIx -> ST s ()
BV64.prefetchIndex (Bloom SerialisedKey -> BitVec64
forall (h :: * -> *) a. Bloom' h a -> BitVec64
BF.bitArray Bloom SerialisedKey
filter) KeyIx
bix
    Bool -> ST s () -> ST s ()
forall a. Bool -> a -> a
assert ((KeyIx
rix, KeyIx
kix, KeyIx
hn, KeyIx
bix) (KeyIx, KeyIx, KeyIx, KeyIx)
-> (KeyIx, KeyIx, KeyIx, KeyIx) -> Bool
forall a. Eq a => a -> a -> Bool
== CandidateProbe -> (KeyIx, KeyIx, KeyIx, KeyIx)
unpackCandidateProbe (KeyIx -> KeyIx -> KeyIx -> KeyIx -> CandidateProbe
CandidateProbe KeyIx
rix KeyIx
kix KeyIx
hn KeyIx
bix)) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ () -> ST s ()
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return ()
    MutablePrimArray (PrimState (ST s)) CandidateProbe
-> KeyIx -> CandidateProbe -> ST s ()
forall a (m :: * -> *).
(Prim a, PrimMonad m) =>
MutablePrimArray (PrimState m) a -> KeyIx -> a -> m ()
P.writePrimArray MutablePrimArray s CandidateProbe
MutablePrimArray (PrimState (ST s)) CandidateProbe
candidateProbes KeyIx
i_w (KeyIx -> KeyIx -> KeyIx -> KeyIx -> CandidateProbe
CandidateProbe KeyIx
rix KeyIx
kix KeyIx
hn KeyIx
bix)
    StrictArray (Bloom SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
-> MutablePrimArray s CandidateProbe
-> KeyIx
-> RunIxKeyIx
-> ST s (KeyIx, RunIxKeyIx)
forall s.
StrictArray (Bloom SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
-> MutablePrimArray s CandidateProbe
-> KeyIx
-> RunIxKeyIx
-> ST s (KeyIx, RunIxKeyIx)
prepInitialCandidateProbes
      StrictArray (Bloom SerialisedKey)
filters PrimArray (CheapHashes SerialisedKey)
keyhashes
      MutablePrimArray s CandidateProbe
candidateProbes
      (KeyIx
i_wKeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+KeyIx
1)
      (PrimArray (CheapHashes SerialisedKey) -> RunIxKeyIx -> RunIxKeyIx
succCandidate PrimArray (CheapHashes SerialisedKey)
keyhashes RunIxKeyIx
nextCandidate)

    -- Filled the buffer or ran out of candidates
  | Bool
otherwise = (KeyIx, RunIxKeyIx) -> ST s (KeyIx, RunIxKeyIx)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return (KeyIx
i_w, RunIxKeyIx
nextCandidate)


{-# NOINLINE bloomQueriesBody #-}
bloomQueriesBody ::
     forall s.
     P.StrictArray (Bloom SerialisedKey)
  -> P.PrimArray (Bloom.CheapHashes SerialisedKey)
     -- ^ The pre-computed \"cheap hashes\" of the keys.
  -> P.MutablePrimArray s CandidateProbe
     -- ^ The array of candidates: of FilterIx, KeyIx, HashNo and FilterBitIx.
     -- This is used as a fixed size rolling buffer. It is used to communicate
     -- between iterations. On each iteration it is read to do the (already
     -- prefetched) memory reads. And it is written with the prefetched bit indexes for the next iteration.
  -> Int -> Int -> RunIxKeyIx
  -> ST s (P.PrimArray RunIxKeyIx)
bloomQueriesBody :: forall s.
StrictArray (Bloom SerialisedKey)
-> PrimArray (CheapHashes SerialisedKey)
-> MutablePrimArray s CandidateProbe
-> KeyIx
-> KeyIx
-> RunIxKeyIx
-> ST s (PrimArray RunIxKeyIx)
bloomQueriesBody !StrictArray (Bloom SerialisedKey)
filters !PrimArray (CheapHashes SerialisedKey)
keyhashes !MutablePrimArray s CandidateProbe
candidateProbes =
   \ !KeyIx
i_r !KeyIx
i_w !RunIxKeyIx
nextCandidate -> do
    MutablePrimArray s RunIxKeyIx
output <- KeyIx -> ST s (MutablePrimArray (PrimState (ST s)) RunIxKeyIx)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
KeyIx -> m (MutablePrimArray (PrimState m) a)
P.newPrimArray (PrimArray (CheapHashes SerialisedKey) -> KeyIx
forall a. Prim a => PrimArray a -> KeyIx
P.sizeofPrimArray PrimArray (CheapHashes SerialisedKey)
keyhashes KeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
* KeyIx
2)
    MutablePrimArray s RunIxKeyIx
output' <-
      KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> ST s (MutablePrimArray s RunIxKeyIx)
testCandidateProbe
        KeyIx
i_r KeyIx
i_w RunIxKeyIx
nextCandidate
        MutablePrimArray s RunIxKeyIx
output KeyIx
0
    MutablePrimArray (PrimState (ST s)) RunIxKeyIx
-> ST s (PrimArray RunIxKeyIx)
forall (m :: * -> *) a.
PrimMonad m =>
MutablePrimArray (PrimState m) a -> m (PrimArray a)
P.unsafeFreezePrimArray MutablePrimArray s RunIxKeyIx
MutablePrimArray (PrimState (ST s)) RunIxKeyIx
output'
  where
    {-# INLINE prepGivenCandidateProbe #-}

    -- assume buff size of 0x20, so mask of 0x1f
    testCandidateProbe, prepNextCandidateProbe ::
         Int -> Int
         -- ^ The read and write indexes within the rolling buffer. These wrap
         -- around.
      -> RunIxKeyIx
         -- ^ The run and key index of the next candidate add to the rolling buffer.
         -- When this passes the maximum then no more candidates are added, and we
         -- just drain the buffer.
      -> P.MutablePrimArray s RunIxKeyIx
         -- ^ The output array.
      -> Int
         -- ^ The output array next free index.
      -> ST s (P.MutablePrimArray s RunIxKeyIx)

    testCandidateProbe :: KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> ST s (MutablePrimArray s RunIxKeyIx)
testCandidateProbe !KeyIx
i_r !KeyIx
i_w
                       !RunIxKeyIx
nextCandidate
                       !MutablePrimArray s RunIxKeyIx
output !KeyIx
outputix =
      Bool
-> ST s (MutablePrimArray s RunIxKeyIx)
-> ST s (MutablePrimArray s RunIxKeyIx)
forall a. Bool -> a -> a
assert (KeyIx
i_r KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
>= KeyIx
0 Bool -> Bool -> Bool
&& KeyIx
i_r KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
<= KeyIx
0x1f) (ST s (MutablePrimArray s RunIxKeyIx)
 -> ST s (MutablePrimArray s RunIxKeyIx))
-> ST s (MutablePrimArray s RunIxKeyIx)
-> ST s (MutablePrimArray s RunIxKeyIx)
forall a b. (a -> b) -> a -> b
$
      Bool
-> ST s (MutablePrimArray s RunIxKeyIx)
-> ST s (MutablePrimArray s RunIxKeyIx)
forall a. Bool -> a -> a
assert (KeyIx
i_w KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
>= KeyIx
0 Bool -> Bool -> Bool
&& KeyIx
i_w KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
<= KeyIx
0x1f) (ST s (MutablePrimArray s RunIxKeyIx)
 -> ST s (MutablePrimArray s RunIxKeyIx))
-> ST s (MutablePrimArray s RunIxKeyIx)
-> ST s (MutablePrimArray s RunIxKeyIx)
forall a b. (a -> b) -> a -> b
$ do
        -- A candidate probe is the combination of a filter, key, hash no and
        -- the corresponding probe location in the bloom filter. When a candidate
        -- probe is prepared, its probe location is computed and prefetched.
        CandidateProbe
candidateProbe <- MutablePrimArray (PrimState (ST s)) CandidateProbe
-> KeyIx -> ST s CandidateProbe
forall a (m :: * -> *).
(Prim a, PrimMonad m) =>
MutablePrimArray (PrimState m) a -> KeyIx -> m a
P.readPrimArray MutablePrimArray s CandidateProbe
MutablePrimArray (PrimState (ST s)) CandidateProbe
candidateProbes KeyIx
i_r
        let CandidateProbe KeyIx
rix KeyIx
kix KeyIx
hn KeyIx
bix = CandidateProbe
candidateProbe

        -- Now test the actual Bloom filter bit to see if it's set or not.
        let filter :: Bloom SerialisedKey
filter = StrictArray (Bloom SerialisedKey) -> KeyIx -> Bloom SerialisedKey
forall a. StrictArray a -> KeyIx -> a
P.indexStrictArray StrictArray (Bloom SerialisedKey)
filters KeyIx
rix
        if BitVec64 -> KeyIx -> Bool
BV64.unsafeIndex (Bloom SerialisedKey -> BitVec64
forall (h :: * -> *) a. Bloom' h a -> BitVec64
BF.bitArray Bloom SerialisedKey
filter) KeyIx
bix

          -- The Bloom filter bit is set. Now we either keep this candidate but
          -- probe the next hash number, or if the hash number reached zero then
          -- this candidate (run index, key index) pair goes into the output, and
          -- we prepare the next candidate.
          then
            if KeyIx
hn KeyIx -> KeyIx -> Bool
forall a. Eq a => a -> a -> Bool
== KeyIx
0
              then do
                -- Output the candidate
                MutablePrimArray (PrimState (ST s)) RunIxKeyIx
-> KeyIx -> RunIxKeyIx -> ST s ()
forall a (m :: * -> *).
(Prim a, PrimMonad m) =>
MutablePrimArray (PrimState m) a -> KeyIx -> a -> m ()
P.writePrimArray MutablePrimArray s RunIxKeyIx
MutablePrimArray (PrimState (ST s)) RunIxKeyIx
output KeyIx
outputix (KeyIx -> KeyIx -> RunIxKeyIx
RunIxKeyIx KeyIx
rix KeyIx
kix)
                KeyIx
outputsz <- MutablePrimArray (PrimState (ST s)) RunIxKeyIx -> ST s KeyIx
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a -> m KeyIx
P.getSizeofMutablePrimArray MutablePrimArray s RunIxKeyIx
MutablePrimArray (PrimState (ST s)) RunIxKeyIx
output
                MutablePrimArray s RunIxKeyIx
output'  <- if KeyIx
outputixKeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+KeyIx
1 KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
< KeyIx
outputsz
                              then MutablePrimArray s RunIxKeyIx
-> ST s (MutablePrimArray s RunIxKeyIx)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return MutablePrimArray s RunIxKeyIx
output
                              else MutablePrimArray (PrimState (ST s)) RunIxKeyIx
-> KeyIx -> ST s (MutablePrimArray (PrimState (ST s)) RunIxKeyIx)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> KeyIx -> m (MutablePrimArray (PrimState m) a)
P.resizeMutablePrimArray MutablePrimArray s RunIxKeyIx
MutablePrimArray (PrimState (ST s)) RunIxKeyIx
output (KeyIx
outputsz KeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
* KeyIx
2)
                KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> ST s (MutablePrimArray s RunIxKeyIx)
prepNextCandidateProbe
                  KeyIx
i_r KeyIx
i_w RunIxKeyIx
nextCandidate
                  MutablePrimArray s RunIxKeyIx
output' (KeyIx
outputixKeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+KeyIx
1)

              else do
                -- The hashno has not reached zero, so we prepare a new candidate
                -- with the same (filter,key) pair, but with the next hashno.
                KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> KeyIx
-> KeyIx
-> KeyIx
-> Bloom SerialisedKey
-> ST s (MutablePrimArray s RunIxKeyIx)
prepGivenCandidateProbe
                  KeyIx
i_r KeyIx
i_w RunIxKeyIx
nextCandidate
                  MutablePrimArray s RunIxKeyIx
output KeyIx
outputix
                  KeyIx
rix KeyIx
kix (KeyIx
hnKeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
-KeyIx
1) Bloom SerialisedKey
filter

          -- The Bloom filter bit is not set, so abandon this filter,key pair and
          -- prepare the next candidate.
          else KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> ST s (MutablePrimArray s RunIxKeyIx)
prepNextCandidateProbe
                 KeyIx
i_r KeyIx
i_w RunIxKeyIx
nextCandidate
                 MutablePrimArray s RunIxKeyIx
output KeyIx
outputix

    prepNextCandidateProbe :: KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> ST s (MutablePrimArray s RunIxKeyIx)
prepNextCandidateProbe !KeyIx
i_r !KeyIx
i_w nextCandidate :: RunIxKeyIx
nextCandidate@(RunIxKeyIx KeyIx
rix KeyIx
kix)
                           !MutablePrimArray s RunIxKeyIx
output !KeyIx
outputix
        -- There is a next candidate. Write it into the rolling buffer at the write
        -- index, and continue with an incremented buffer read and write index.
      | KeyIx
rix KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
< StrictArray (Bloom SerialisedKey) -> KeyIx
forall a. StrictArray a -> KeyIx
P.sizeofStrictArray StrictArray (Bloom SerialisedKey)
filters =
        let filter :: Bloom SerialisedKey
filter         = StrictArray (Bloom SerialisedKey) -> KeyIx -> Bloom SerialisedKey
forall a. StrictArray a -> KeyIx -> a
P.indexStrictArray StrictArray (Bloom SerialisedKey)
filters KeyIx
rix
            hn :: KeyIx
hn             = Bloom SerialisedKey -> KeyIx
forall (h :: * -> *) a. Bloom' h a -> KeyIx
BF.hashesN Bloom SerialisedKey
filter KeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
- KeyIx
1
            nextCandidate' :: RunIxKeyIx
nextCandidate' = PrimArray (CheapHashes SerialisedKey) -> RunIxKeyIx -> RunIxKeyIx
succCandidate PrimArray (CheapHashes SerialisedKey)
keyhashes RunIxKeyIx
nextCandidate
         in KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> KeyIx
-> KeyIx
-> KeyIx
-> Bloom SerialisedKey
-> ST s (MutablePrimArray s RunIxKeyIx)
prepGivenCandidateProbe
              KeyIx
i_r KeyIx
i_w RunIxKeyIx
nextCandidate'
              MutablePrimArray s RunIxKeyIx
output KeyIx
outputix
              KeyIx
rix KeyIx
kix KeyIx
hn Bloom SerialisedKey
filter

        -- There is no next candidate but the candidate buffer is non-empty.
        -- Don't write into the candidate buffer. Continue with incrementing the
        -- buffer read pointer but not the write pointer.
      | ((KeyIx
i_r KeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+ KeyIx
1) KeyIx -> KeyIx -> KeyIx
forall a. Bits a => a -> a -> a
.&. KeyIx
0x1f) KeyIx -> KeyIx -> Bool
forall a. Eq a => a -> a -> Bool
/= KeyIx
i_w =
          KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> ST s (MutablePrimArray s RunIxKeyIx)
testCandidateProbe
            ((KeyIx
i_r KeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+ KeyIx
1) KeyIx -> KeyIx -> KeyIx
forall a. Bits a => a -> a -> a
.&. KeyIx
0x1f)
              KeyIx
i_w
            RunIxKeyIx
nextCandidate
            MutablePrimArray s RunIxKeyIx
output KeyIx
outputix

        -- There is no next candidate and the candidate buffer is empty.
        -- We're done!
      | Bool
otherwise =
          MutablePrimArray (PrimState (ST s)) RunIxKeyIx
-> KeyIx -> ST s (MutablePrimArray (PrimState (ST s)) RunIxKeyIx)
forall (m :: * -> *) a.
(PrimMonad m, Prim a) =>
MutablePrimArray (PrimState m) a
-> KeyIx -> m (MutablePrimArray (PrimState m) a)
P.resizeMutablePrimArray MutablePrimArray s RunIxKeyIx
MutablePrimArray (PrimState (ST s)) RunIxKeyIx
output KeyIx
outputix

    prepGivenCandidateProbe ::
         Int -> Int
      -> RunIxKeyIx
      -> P.MutablePrimArray s RunIxKeyIx
      -> Int
      -> Int -> Int -> Int
      -> Bloom.Bloom SerialisedKey
      -> ST s (P.MutablePrimArray s RunIxKeyIx)
    prepGivenCandidateProbe :: KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> KeyIx
-> KeyIx
-> KeyIx
-> Bloom SerialisedKey
-> ST s (MutablePrimArray s RunIxKeyIx)
prepGivenCandidateProbe !KeyIx
i_r !KeyIx
i_w
                            !RunIxKeyIx
nextCandidate
                            !MutablePrimArray s RunIxKeyIx
output !KeyIx
outputix
                            !KeyIx
rix !KeyIx
kix !KeyIx
hn !Bloom SerialisedKey
filter =
      Bool
-> ST s (MutablePrimArray s RunIxKeyIx)
-> ST s (MutablePrimArray s RunIxKeyIx)
forall a. Bool -> a -> a
assert (KeyIx
hn KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
>= KeyIx
0 Bool -> Bool -> Bool
&& KeyIx
hn KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
< Bloom SerialisedKey -> KeyIx
forall (h :: * -> *) a. Bloom' h a -> KeyIx
BF.hashesN Bloom SerialisedKey
filter) (ST s (MutablePrimArray s RunIxKeyIx)
 -> ST s (MutablePrimArray s RunIxKeyIx))
-> ST s (MutablePrimArray s RunIxKeyIx)
-> ST s (MutablePrimArray s RunIxKeyIx)
forall a b. (a -> b) -> a -> b
$ do
        let !keyhash :: CheapHashes SerialisedKey
keyhash = PrimArray (CheapHashes SerialisedKey)
-> KeyIx -> CheapHashes SerialisedKey
forall a. Prim a => PrimArray a -> KeyIx -> a
P.indexPrimArray PrimArray (CheapHashes SerialisedKey)
keyhashes KeyIx
kix
            !bix :: KeyIx
bix     = (Word64 -> KeyIx
forall a b. (Integral a, Num b) => a -> b
fromIntegral :: Word64 -> Int) (Word64 -> KeyIx) -> Word64 -> KeyIx
forall a b. (a -> b) -> a -> b
$
                       CheapHashes SerialisedKey -> KeyIx -> Word64
forall {k} (a :: k). CheapHashes a -> KeyIx -> Word64
Bloom.evalCheapHashes CheapHashes SerialisedKey
keyhash KeyIx
hn
                         Word64 -> Word64 -> Word64
`BV64.unsafeRemWord64` -- size must be > 0
                       Bloom SerialisedKey -> Word64
forall (h :: * -> *) a. Bloom' h a -> Word64
BF.size Bloom SerialisedKey
filter           -- bloomInvariant ensures this
        BitVec64 -> KeyIx -> ST s ()
forall s. BitVec64 -> KeyIx -> ST s ()
BV64.prefetchIndex (Bloom SerialisedKey -> BitVec64
forall (h :: * -> *) a. Bloom' h a -> BitVec64
BF.bitArray Bloom SerialisedKey
filter) KeyIx
bix
        MutablePrimArray (PrimState (ST s)) CandidateProbe
-> KeyIx -> CandidateProbe -> ST s ()
forall a (m :: * -> *).
(Prim a, PrimMonad m) =>
MutablePrimArray (PrimState m) a -> KeyIx -> a -> m ()
P.writePrimArray MutablePrimArray s CandidateProbe
MutablePrimArray (PrimState (ST s)) CandidateProbe
candidateProbes KeyIx
i_w (KeyIx -> KeyIx -> KeyIx -> KeyIx -> CandidateProbe
CandidateProbe KeyIx
rix KeyIx
kix KeyIx
hn KeyIx
bix)
        KeyIx
-> KeyIx
-> RunIxKeyIx
-> MutablePrimArray s RunIxKeyIx
-> KeyIx
-> ST s (MutablePrimArray s RunIxKeyIx)
testCandidateProbe
            ((KeyIx
i_r KeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+ KeyIx
1) KeyIx -> KeyIx -> KeyIx
forall a. Bits a => a -> a -> a
.&. KeyIx
0x1f)
            ((KeyIx
i_w KeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+ KeyIx
1) KeyIx -> KeyIx -> KeyIx
forall a. Bits a => a -> a -> a
.&. KeyIx
0x1f)
            -- or if we merge them: ((i_rw + 0x0101) .&. 0x1f1f)
            RunIxKeyIx
nextCandidate
            MutablePrimArray s RunIxKeyIx
output KeyIx
outputix

succCandidate :: P.PrimArray (Bloom.CheapHashes SerialisedKey)
              -> Candidate
              -> Candidate
succCandidate :: PrimArray (CheapHashes SerialisedKey) -> RunIxKeyIx -> RunIxKeyIx
succCandidate PrimArray (CheapHashes SerialisedKey)
keyhashes (RunIxKeyIx KeyIx
rix KeyIx
kix)
  | KeyIx
kixKeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+KeyIx
1 KeyIx -> KeyIx -> Bool
forall a. Ord a => a -> a -> Bool
< PrimArray (CheapHashes SerialisedKey) -> KeyIx
forall a. Prim a => PrimArray a -> KeyIx
P.sizeofPrimArray PrimArray (CheapHashes SerialisedKey)
keyhashes = KeyIx -> KeyIx -> RunIxKeyIx
RunIxKeyIx KeyIx
rix (KeyIx
kixKeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+KeyIx
1)
  | Bool
otherwise                           = KeyIx -> KeyIx -> RunIxKeyIx
RunIxKeyIx (KeyIx
rixKeyIx -> KeyIx -> KeyIx
forall a. Num a => a -> a -> a
+KeyIx
1) KeyIx
0
  --TODO: optimise with bit twiddling