pykinos-core-0.1.0.2: src/Pykinos/Mutable/SwissTable.hs
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE StrictData #-}
{-# LANGUAGE UnboxedTuples #-}
-- |
-- Module : Pykinos.Mutable.SwissTable
-- Description : Zero-GC SWAR open-addressed hash-consing table over MutableByteArray#.
--
-- Maps 128-bit unboxed keys @(Word64, Word64)@ to 32-bit unboxed IDs ('Int32')
-- with 8-slot SWAR parallel control probing and zero boxed heap pointers.
module Pykinos.Mutable.SwissTable
( SwissTable128(..)
, newSwissTable128
, lookupOrInsert128
, packNfNode128
, matchH2Swar64
) where
import Control.Monad (when)
import Control.Monad.ST (ST)
import Data.Bits
( complement
, countTrailingZeros
, unsafeShiftL
, unsafeShiftR
, xor
, (.&.)
, (.|.)
)
import Data.Int (Int32)
import Data.Primitive.ByteArray
( MutableByteArray(..)
, newByteArray
, readByteArray
, setByteArray
, writeByteArray
)
import Data.Word (Word8, Word32, Word64)
import GHC.Exts (Int(..), readWord8ArrayAsWord64#)
import GHC.Word (Word64(W64#))
import GHC.ST (ST(..))
-- | Open-addressed SwissTable with mutable unboxed slabs wrapped in a 4-slot descriptor.
-- Because all slabs are 'MutableByteArray', GHC's GC never scans the table entries.
data SwissTable128 s = SwissTable128
{ stArrays :: !(MutableByteArray s)
-- ^ Int32[0] = count, Int32[1] = cap, Int32[2] = maxLoad
, stCtrlRef :: !(SmallRef s (MutableByteArray s))
, stKeysRef :: !(SmallRef s (MutableByteArray s))
, stValsRef :: !(SmallRef s (MutableByteArray s))
}
-- | Lightweight 1-slot mutable box for swapping grown ByteArrays.
newtype SmallRef s a = SmallRef (MutableByteArray s)
ctrlEmpty :: Word8
ctrlEmpty = 0x80
-- | Allocate a power-of-two 'SwissTable128' (minimum capacity 16).
newSwissTable128 :: Int -> ST s (SwissTable128 s)
newSwissTable128 !reqCap = do
let !cap = nextPow2 (max 16 reqCap)
!maxLoad = (cap * 7) `unsafeShiftR` 3
ctrl <- newByteArray (cap + 8)
setByteArray ctrl 0 (cap + 8) ctrlEmpty
keys <- newByteArray (cap * 16)
vals <- newByteArray (cap * 4)
st <- newByteArray 12
writeByteArray st 0 (0 :: Int32)
writeByteArray st 1 (fromIntegral cap :: Int32)
writeByteArray st 2 (fromIntegral maxLoad :: Int32)
pure (SwissTable128 st (SmallRef ctrl) (SmallRef keys) (SmallRef vals))
nextPow2 :: Int -> Int
nextPow2 !n = go 16
where
go !p | p >= n = p
| otherwise = go (p `unsafeShiftL` 1)
{-# INLINE hash128 #-}
hash128 :: Word64 -> Word64 -> Word64
hash128 !kLo !kHi =
let !h0 = (kLo `xor` (kHi * 0x9E3779B97F4A7C15)) * 0xBF58476D1CE4E5B9
!h1 = (h0 `xor` (h0 `unsafeShiftR` 30)) * 0x94D049BB133111EB
in h1 `xor` (h1 `unsafeShiftR` 31)
{-# INLINE readCtrlGroup64 #-}
readCtrlGroup64 :: MutableByteArray s -> Int -> ST s Word64
readCtrlGroup64 (MutableByteArray mba#) (I# slot#) = ST $ \s0 ->
case readWord8ArrayAsWord64# mba# slot# s0 of
(# s1, w# #) -> (# s1, W64# w# #)
{-# INLINE writeCtrlByte #-}
writeCtrlByte :: MutableByteArray s -> Int -> Int -> Word8 -> ST s ()
writeCtrlByte !ctrl !cap !slot !b = do
writeByteArray ctrl slot b
when (slot < 8) $
writeByteArray ctrl (cap + slot) b
-- | Borrow-free SWAR match returning bit (8*i + 7) == 1 iff byte i equals h2.
{-# INLINE matchH2Swar64 #-}
matchH2Swar64 :: Word64 -> Word8 -> Word64
matchH2Swar64 !ctrlWord !h2 =
let !pat = 0x0101010101010101 * fromIntegral h2
!x = ctrlWord `xor` pat
!low7 = (x .&. 0x7F7F7F7F7F7F7F7F) + 0x7F7F7F7F7F7F7F7F
in complement (low7 .|. x .|. 0x7F7F7F7F7F7F7F7F)
{-# INLINE matchEmptySwar64 #-}
matchEmptySwar64 :: Word64 -> Word64
matchEmptySwar64 !ctrlWord = ctrlWord .&. 0x8080808080808080
-- | Lookup or insert a 128-bit key, returning its dense monotonic Int32 ID.
{-# INLINE lookupOrInsert128 #-}
lookupOrInsert128
:: SwissTable128 s
-> Word64
-> Word64
-> ST s Int32
lookupOrInsert128 SwissTable128{..} !keyLo !keyHi = do
let SmallRef ctrl = stCtrlRef
SmallRef keys = stKeysRef
SmallRef vals = stValsRef
cap32 :: Int32 <- readByteArray stArrays 1
let !cap = fromIntegral cap32 :: Int
!mask = cap - 1
!h = hash128 keyLo keyHi
!h1 = fromIntegral (h `unsafeShiftR` 7) :: Int
!h2 = fromIntegral (h .&. 0x7F) :: Word8
probeGroup !groupStart !step = do
!ctrlWord <- readCtrlGroup64 ctrl groupStart
let !hitMask = matchH2Swar64 ctrlWord h2
mbFound <- checkHits groupStart mask hitMask
case mbFound of
Just existingVal -> pure existingVal
Nothing -> do
let !empMask = matchEmptySwar64 ctrlWord
if empMask /= 0
then do
let !byteIdx = countTrailingZeros empMask `unsafeShiftR` 3
!slot = (groupStart + byteIdx) .&. mask
cnt :: Int32 <- readByteArray stArrays 0
writeByteArray stArrays 0 (cnt + 1)
writeCtrlByte ctrl cap slot h2
writeByteArray keys (slot * 2) keyLo
writeByteArray keys (slot * 2 + 1) keyHi
writeByteArray vals slot cnt
pure cnt
else
probeGroup ((groupStart + step) .&. mask) (step + 8)
checkHits !groupStart !msk !m
| m == 0 = pure Nothing
| otherwise = do
let !byteIdx = countTrailingZeros m `unsafeShiftR` 3
!slot = (groupStart + byteIdx) .&. msk
!kLo <- readByteArray keys (slot * 2)
!kHi <- readByteArray keys (slot * 2 + 1)
if kLo == keyLo && kHi == keyHi
then Just <$> readByteArray vals slot
else checkHits groupStart msk (m .&. (m - 1))
probeGroup (h1 .&. mask) 8
-- | Pack a fixed-arity normal-form DAG node into a 128-bit SwissTable key.
{-# INLINE packNfNode128 #-}
packNfNode128 :: Word8 -> Word32 -> Int32 -> Int32 -> Int32 -> (Word64, Word64)
packNfNode128 !tag !aux !cA !cB !cC =
let !lo = (fromIntegral tag `unsafeShiftL` 56)
.|. (fromIntegral (aux .&. 0x00FFFFFF) `unsafeShiftL` 32)
.|. fromIntegral (fromIntegral cA :: Word32)
!hi = (fromIntegral (fromIntegral cB :: Word32) `unsafeShiftL` 32)
.|. fromIntegral (fromIntegral cC :: Word32)
in (lo, hi)