cek-pykinos-0.1.0.2: src/Cek/Pykinos/Store.hs
{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE PatternSynonyms #-}
{-# LANGUAGE RecordWildCards #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StrictData #-}
{-# OPTIONS_GHC -Wno-pattern-namespace-specifier #-}
-- |
-- Module : Cek.Pykinos.Store
-- Description : 4096-cell chunked Structure-of-Arrays Store arena for CESK machines.
--
-- Separates unboxed cell phase tags, memoized normal-form DAG pointers ('NfAddr'),
-- and auxiliary 32-bit integers from boxed payload pointers to minimize GC scanning.
--
-- === Structure-of-Arrays (SoA) Memory Layout
--
-- In traditional pointer-heavy graph reduction engines, every lazy evaluation cell
-- (thunk or indirection) is a heap closure containing an info pointer, mutable fields,
-- and payload pointers. As the heap grows, garbage collection pause times degrade
-- proportionally with the total number of cells.
--
-- 'SoAStore' eliminates per-cell heap headers by grouping cells into 4096-cell
-- contiguous memory chunks ('StoreChunk'):
--
-- * 'scUnboxed': A 36,864-byte unboxed 'MutableByteArray' holding raw bytes and
-- integers in three segregated contiguous lanes:
-- * Lane 0 (Bytes 0..4095): 4096 x 1-byte 'CellTag' values.
-- * Lane 1 (Bytes 4096..20479): 4096 x 4-byte 'Int32' memoized normal-form DAG addresses.
-- * Lane 2 (Bytes 20480..36863): 4096 x 4-byte 'Int32' auxiliary integers (literals, symbols).
-- * 'scPtrA': A 4096-slot 'SmallMutableArray' holding primary boxed payload pointers.
-- * 'scPtrB': A 4096-slot 'SmallMutableArray' holding secondary boxed payload pointers.
--
-- === Cell Lifecycle Transitions
--
-- Cells progress through strict evaluation phases tracked in Lane 0:
--
-- 1. 'CT_Thunk': Unevaluated closure @(term, env)@ stored across 'scPtrA' and 'scPtrB'.
-- 2. 'CT_Blackhole': Currently under active evaluation. Cycles trigger runtime errors.
-- 3. 'CT_WLit': Integer / word literal stored unboxed in Lane 2 with zero heap allocations.
-- 4. 'CT_WBinder': Evaluated lambda or function abstraction.
-- 5. 'CT_WRecord': Evaluated record with interned 'Pykinos.Schema.HiddenClass.SchemaId'.
-- 6. 'CT_WNeu': Neutral application or variable spine pending normalization.
module Cek.Pykinos.Store
( -- * Cell Phase Tags
CellTag(..)
, pattern CT_Thunk
, pattern CT_Blackhole
, pattern CT_WLit
, pattern CT_WBinder
, pattern CT_WRecord
, pattern CT_WNeu
, pattern CT_Unbound
-- * Store Arena Structures
, StoreChunk(..)
, SoAStore(..)
-- * Store Allocation and Initialization
, newSoAStore
, acquireSlot
, allocThunkSoA
, allocWLitSoA
, allocWNeuSoA
-- * Cell Phase and Memoization Accessors
, readCellPhaseSoA
, readMemoNfSoA
, writeMemoNfSoA
) where
import Control.Monad.ST (ST)
import Data.Bits (shiftR, (.&.))
import Data.Int (Int32)
import Data.Primitive.ByteArray
( MutableByteArray
, newByteArray
, readByteArray
, setByteArray
, writeByteArray
)
import Data.Primitive.SmallArray
( SmallMutableArray
, newSmallArray
, readSmallArray
, writeSmallArray
)
import Data.Word (Word8)
import GHC.Exts (Any, unsafeCoerce#)
-- | 1-byte cell phase opcode stored in Lane 0 of 'StoreChunk'.
newtype CellTag = CellTag { unCellTag :: Word8 }
deriving (Eq, Ord, Show)
-- | Unevaluated lazy thunk closure @(term, env)@.
pattern CT_Thunk :: CellTag
pattern CT_Thunk = CellTag 0
-- | In-progress evaluation sentinel; detects infinite recursion loops.
pattern CT_Blackhole :: CellTag
pattern CT_Blackhole = CellTag 1
-- | Evaluated unboxed integer/boolean literal.
pattern CT_WLit :: CellTag
pattern CT_WLit = CellTag 2
-- | Evaluated lambda abstraction or binder closure.
pattern CT_WBinder :: CellTag
pattern CT_WBinder = CellTag 3
-- | Evaluated flat record mapped by a 'SchemaId'.
pattern CT_WRecord :: CellTag
pattern CT_WRecord = CellTag 4
-- | Neutral term spine waiting on an unbound variable or argument.
pattern CT_WNeu :: CellTag
pattern CT_WNeu = CellTag 5
-- | Unbound / unallocated cell slot marker.
pattern CT_Unbound :: CellTag
pattern CT_Unbound = CellTag 6
-- | A 4096-cell Structure-of-Arrays Store chunk.
--
-- Layout of the 36,864-byte 'scUnboxed' 'MutableByteArray':
-- * Bytes [ 0 .. 4095]: Lane 0 — 4096 x Word8 CellTag (1 byte per cell)
-- * Bytes [ 4096 .. 20479]: Lane 1 — 4096 x Int32 Memoized NfAddr (4 bytes per cell)
-- * Bytes [20480 .. 36863]: Lane 2 — 4096 x Int32 AuxInt (4 bytes per cell)
data StoreChunk s = StoreChunk
{ scUnboxed :: !(MutableByteArray s)
-- ^ Unified contiguous unboxed memory holding tags, memoized NF addresses, and literals.
, scPtrA :: !(SmallMutableArray s Any)
-- ^ Lane 3: Primary pointer lane for AST terms, records, or closures.
, scPtrB :: !(SmallMutableArray s Any)
-- ^ Lane 4: Secondary pointer lane for environment lists or capture frames.
}
-- | Chunked SoA Store arena supporting up to 4,194,304 cells across 1024 chunks.
data SoAStore s = SoAStore
{ ssChunks :: !(SmallMutableArray s (StoreChunk s))
-- ^ Array of chunk pointers, dynamically allocated as monotonic address space expands.
, ssState :: !(MutableByteArray s)
-- ^ Store control state: Int32[0] = nextAddr counter, Int32[1] = count of allocated chunks.
}
-- | Allocate and initialize a fresh 4096-cell 'StoreChunk' with Lane 1 set to -1.
--
-- Initializing Lane 1 with -1 ensures that 'readMemoNfSoA' can detect unmemoized cells
-- with a single negative integer check.
allocStoreChunk :: ST s (StoreChunk s)
allocStoreChunk = do
mba <- newByteArray 36864
setByteArray mba 4096 16384 (0xFF :: Word8)
ptrA <- newSmallArray 4096 (unsafeCoerce# ())
ptrB <- newSmallArray 4096 (unsafeCoerce# ())
pure (StoreChunk mba ptrA ptrB)
-- | Create a new 'SoAStore' with chunk 0 pre-allocated.
newSoAStore :: ST s (SoAStore s)
newSoAStore = do
c0 <- allocStoreChunk
chunks <- newSmallArray 1024 (unsafeCoerce# ())
writeSmallArray chunks 0 c0
st <- newByteArray 8
writeByteArray st 0 (0 :: Int32)
writeByteArray st 1 (1 :: Int32)
pure (SoAStore chunks st)
-- | Acquire the next monotonic cell 'Int32' address, allocating a new chunk on boundary crossings.
--
-- Returns the global address, the enclosing 'StoreChunk', and the local intra-chunk slot index (0..4095).
{-# INLINE acquireSlot #-}
acquireSlot :: SoAStore s -> ST s (Int32, StoreChunk s, Int)
acquireSlot SoAStore{..} = do
addr :: Int32 <- readByteArray ssState 0
numC :: Int32 <- readByteArray ssState 1
writeByteArray ssState 0 (addr + 1)
let !ix = fromIntegral addr :: Int
!chunkIx = ix `shiftR` 12
!slotIx = ix .&. 0xFFF
chunk <- if chunkIx < fromIntegral numC
then readSmallArray ssChunks chunkIx
else do
c <- allocStoreChunk
writeSmallArray ssChunks chunkIx c
writeByteArray ssState 1 (numC + 1)
pure c
pure (addr, chunk, slotIx)
-- | Allocate a lazy thunk @(term, env)@ cell in the Store.
--
-- Initializes the cell phase to 'CT_Thunk' and saves the term and environment pointers.
{-# INLINE allocThunkSoA #-}
allocThunkSoA :: SoAStore s -> a -> b -> ST s Int32
allocThunkSoA store !term !env = do
(!addr, StoreChunk{..}, !slot) <- acquireSlot store
writeByteArray scUnboxed slot (unCellTag CT_Thunk)
writeSmallArray scPtrA slot (unsafeCoerce# term)
writeSmallArray scPtrB slot (unsafeCoerce# env)
pure addr
-- | Allocate an unboxed integer literal cell with zero pointer writes.
--
-- Stores the value directly in Lane 2 of 'scUnboxed', completely bypassing the GC write barrier.
{-# INLINE allocWLitSoA #-}
allocWLitSoA :: SoAStore s -> Int32 -> ST s Int32
allocWLitSoA store !litVal = do
(!addr, StoreChunk{..}, !slot) <- acquireSlot store
writeByteArray scUnboxed slot (unCellTag CT_WLit)
writeByteArray scUnboxed (5120 + slot) litVal
pure addr
-- | Allocate a fresh neutral binder symbol @WNeu sym []@ in the Store.
--
-- Records the symbol ID in Lane 2 and initializes an empty elimination spine.
{-# INLINE allocWNeuSoA #-}
allocWNeuSoA :: SoAStore s -> Int32 -> ST s Int32
allocWNeuSoA store !symId = do
(!addr, StoreChunk{..}, !slot) <- acquireSlot store
writeByteArray scUnboxed slot (unCellTag CT_WNeu)
writeByteArray scUnboxed (5120 + slot) symId
writeSmallArray scPtrA slot (unsafeCoerce# ([] :: [Any]))
pure addr
-- | Check in O(1) whether 'addr' already has a memoized normal-form DAG pointer ('NfAddr' >= 0).
{-# INLINE readMemoNfSoA #-}
readMemoNfSoA :: SoAStore s -> Int32 -> ST s Int32
readMemoNfSoA SoAStore{..} !addr = do
let !ix = fromIntegral addr :: Int
StoreChunk{..} <- readSmallArray ssChunks (ix `shiftR` 12)
readByteArray scUnboxed (1024 + (ix .&. 0xFFF))
-- | Record a memoized normal-form DAG pointer 'nfAddr' for cell 'addr'.
{-# INLINE writeMemoNfSoA #-}
writeMemoNfSoA :: SoAStore s -> Int32 -> Int32 -> ST s ()
writeMemoNfSoA SoAStore{..} !addr !nfAddr = do
let !ix = fromIntegral addr :: Int
StoreChunk{..} <- readSmallArray ssChunks (ix `shiftR` 12)
writeByteArray scUnboxed (1024 + (ix .&. 0xFFF)) nfAddr
-- | Read the unboxed 'CellTag', 'AuxInt', 'StoreChunk', and slot offset for 'addr'.
{-# INLINE readCellPhaseSoA #-}
readCellPhaseSoA :: SoAStore s -> Int32 -> ST s (CellTag, Int32, StoreChunk s, Int)
readCellPhaseSoA SoAStore{..} !addr = do
let !ix = fromIntegral addr :: Int
!slot = ix .&. 0xFFF
chunk@StoreChunk{..} <- readSmallArray ssChunks (ix `shiftR` 12)
!rawTag <- readByteArray scUnboxed slot
!aux <- readByteArray scUnboxed (5120 + slot)
pure (CellTag rawTag, aux, chunk, slot)