lossy-chan 0.1.1.0 → 0.2.0.0
raw patch · 7 files changed
+265/−229 lines, 7 filesdep +heapsizePVP ok
version bump matches the API change (PVP)
Dependencies added: heapsize
API changes (from Hackage documentation)
- Control.Concurrent.LossyChan: instance GHC.Classes.Eq Control.Concurrent.LossyChan.ChanPos
- Control.Concurrent.LossyChan: instance GHC.Internal.Exception.Type.Exception Control.Concurrent.LossyChan.NoInChanError
- Control.Concurrent.LossyChan: instance GHC.Internal.Show.Show Control.Concurrent.LossyChan.ChanPos
- Control.Concurrent.LossyChan: instance GHC.Internal.Show.Show Control.Concurrent.LossyChan.NoInChanError
+ Control.Concurrent.LossyChan: instance GHC.Exception.Type.Exception Control.Concurrent.LossyChan.NoInChanError
+ Control.Concurrent.LossyChan: instance GHC.Show.Show Control.Concurrent.LossyChan.ChanPos
+ Control.Concurrent.LossyChan: instance GHC.Show.Show Control.Concurrent.LossyChan.NoInChanError
- Control.Concurrent.LossyChan: new :: Word32 -> IO (InChan a, OutChan a)
+ Control.Concurrent.LossyChan: new :: Word8 -> IO (InChan a, OutChan a)
Files
- CHANGELOG.md +18/−0
- README.md +4/−45
- benchmark/Benchmark/Chan.hs +2/−2
- benchmark/space.hs +1/−1
- lossy-chan.cabal +2/−1
- src/Control/Concurrent/LossyChan.hs +100/−113
- test/Main.hs +138/−67
CHANGELOG.md view
@@ -1,5 +1,23 @@ # Revision history for lossy-chan +## 0.2.0.0 -- 2026-11-19++* Change type of `new` to `Word8 -> IO (InChan a, OutChan a)`.++ This change was made to reflect the fact that the channel ring buffer uses+ a `SmallArray` and therefore the buffer length should not be much bigger than+ 128. This is now reflected in the argument type.++* Fix issue where `NoInChanError` was raised early.++ In previous versions, `receive` and `tryReceive` would raise `NoInChanError`+ if no live code path could call `out`. This was due to an error where the+ value used for liveness testing was stored in the `InChan` separately from+ the channel ring buffer and was only used in `out`. Hence, if no live code+ path could call `out`, the value used for liveness would be garbage collected+ and `receive` and `tryReceive` would erroneously raise `NoInChanError` if+ they caught up with the input channel.+ ## 0.1.1.0 -- 2026-11-12 * Support creating a new output channel from the input channel.
README.md view
@@ -103,52 +103,11 @@ The time benchmark, created using `criterion`, shows that a `lossy-chan` channel is roughly as fast as an `unagi-chan` channel, and both are significantly faster than the `base` and `stm` channels. Moreover, the buffer size doesn't appear to significanly affect the performance of a `lossy-chan` channel. -+ ### Space -The space benchmark, created using `weigh`, shows that a `lossy-chan` channel has much lower maximum residency when compared to the other channel implementations, and that its maximum residency scales with the buffer size. This is expected from the use of a ring buffer.-+The space benchmark, created using `weigh`, shows that a `lossy-chan` channel has much lower maximum residency when compared to the other channel implementations – so much so, that it had to be rendered in a separate plot.+Moreover, `lossy-chan`'s maximum residency scales up with the buffer size, as expected from the use of a ring buffer. -| Benchmark | Case | Allocated | Max Residency |-| :--------------- | :--------------------- | ---------: | ------------: |-| `base` | 1 senders, 1 receivers | 25,604,448 | 8,348,840 |-| | 2 senders, 2 receivers | 51,208,176 | 12,275,048 |-| | 3 senders, 3 receivers | 76,811,928 | 16,699,824 |-| | 4 senders, 4 receivers | 96,154,064 | 24,617,800 |-| `stm` | 1 senders, 1 receivers | 16,805,400 | 8,830,408 |-| | 2 senders, 2 receivers | 33,609,720 | 9,845,000 |-| | 3 senders, 3 receivers | 50,414,848 | 14,717,096 |-| | 4 senders, 4 receivers | 55,414,888 | 17,660,312 |-| `unagi-chan` | 1 senders, 1 receivers | 18,439,984 | 4,540,792 |-| | 2 senders, 2 receivers | 36,862,432 | 4,541,464 |-| | 3 senders, 3 receivers | 55,277,096 | 10,573,080 |-| | 4 senders, 4 receivers | 73,698,768 | 10,573,984 |-| `lossy-chan-2` | 1 senders, 1 receivers | 12,008,624 | 3,088 |-| | 2 senders, 2 receivers | 24,013,384 | 4,960 |-| | 3 senders, 3 receivers | 36,018,184 | 6,816 |-| | 4 senders, 4 receivers | 48,021,576 | 8,672 |-| `lossy-chan-4` | 1 senders, 1 receivers | 12,008,928 | 3,168 |-| | 2 senders, 2 receivers | 24,014,392 | 5,040 |-| | 3 senders, 3 receivers | 36,018,456 | 6,896 |-| | 4 senders, 4 receivers | 48,021,664 | 8,752 |-| `lossy-chan-8` | 1 senders, 1 receivers | 12,009,536 | 3,328 |-| | 2 senders, 2 receivers | 24,015,448 | 5,200 |-| | 3 senders, 3 receivers | 36,019,056 | 7,056 |-| | 4 senders, 4 receivers | 48,024,952 | 8,912 |-| `lossy-chan-16` | 1 senders, 1 receivers | 12,010,472 | 3,648 |-| | 2 senders, 2 receivers | 24,017,080 | 5,520 |-| | 3 senders, 3 receivers | 36,019,840 | 7,376 |-| | 4 senders, 4 receivers | 48,028,224 | 9,232 |-| `lossy-chan-32` | 1 senders, 1 receivers | 12,011,728 | 4,288 |-| | 2 senders, 2 receivers | 24,017,720 | 6,160 |-| | 3 senders, 3 receivers | 36,028,936 | 8,016 |-| | 4 senders, 4 receivers | 48,037,104 | 9,872 |-| `lossy-chan-64` | 1 senders, 1 receivers | 12,014,464 | 5,568 |-| | 2 senders, 2 receivers | 24,030,232 | 7,440 |-| | 3 senders, 3 receivers | 36,041,456 | 9,296 |-| | 4 senders, 4 receivers | 48,067,576 | 11,152 |-| `lossy-chan-128` | 1 senders, 1 receivers | 12,021,448 | 8,128 |-| | 2 senders, 2 receivers | 24,047,128 | 10,000 |-| | 3 senders, 3 receivers | 36,065,520 | 11,856 |-| | 4 senders, 4 receivers | 48,083,512 | 13,712 |+
benchmark/Benchmark/Chan.hs view
@@ -18,7 +18,7 @@ import Control.Concurrent.STM.TChan qualified as STM import Control.Monad.STM (atomically) import Data.Kind (Type)-import Data.Word (Word32)+import Data.Word (Word8) {- | An abstraction over channel libraries.@@ -34,7 +34,7 @@ {- | The `Chan` instance for @lossy-chan@. -}-lossyChan :: Word32 -> Chan LC.InChan LC.OutChan+lossyChan :: Word8 -> Chan LC.InChan LC.OutChan lossyChan len = MkChan { new = LC.new len
benchmark/space.hs view
@@ -15,7 +15,7 @@ main = do mainWith $ do setColumns [Case, Allocated, Max]- setFormat Markdown+ setFormat Plain wgroup "base" $ for_ [1 .. 4] $ \s -> weighChanWith baseChan s s
lossy-chan.cabal view
@@ -1,6 +1,6 @@ cabal-version: 3.0 name: lossy-chan-version: 0.1.1.0+version: 0.2.0.0 synopsis: Fast, bounded, and lossy broadcast channels backed by a ring buffer description: Fast, bounded, and /lossy/ broadcast channels backed by a ring buffer. license: BSD-3-Clause@@ -61,6 +61,7 @@ main-is: Main.hs build-depends: base >=4.16 && <5,+ heapsize, lossy-chan, tasty, tasty-hunit,
src/Control/Concurrent/LossyChan.hs view
@@ -16,10 +16,13 @@ import Control.Exception (Exception (..), mask_) import Control.Monad (when)+import Data.Functor (void)+import Data.IORef (IORef, mkWeakIORef, newIORef, readIORef)+import Data.Word (Word32, Word8) import GHC.Conc (STM (..), TVar (..), atomically, newTVar, newTVarIO, orElse, readTVar, retry, throwSTM, writeTVar)-import GHC.Exts (Int#, MutVar#, RealWorld, SmallArray#, State#, TVar#, Weak#, Word32#, deRefWeak#, indexSmallArray#, isTrue#, mkWeak#, newMutVar#, newSmallArray#, newTVar#, readTVar#, unsafeFreezeSmallArray#, word2Int#, word32ToWord#, writeSmallArray#, writeTVar#, (+#), (==#))+import GHC.Exts (Int#, RealWorld, SmallArray#, State#, TVar#, Word8#, indexSmallArray#, isTrue#, mkWeak#, newSmallArray#, newTVar#, readTVar#, unsafeFreezeSmallArray#, word2Int#, word8ToWord#, writeSmallArray#, writeTVar#, (+#), (==#)) import GHC.IO (IO (..))-import GHC.Word (Word32 (..))+import GHC.Word (Word8 (..)) #ifdef LOSSY_CHAN_SMALL_LOOP_COUNTER -- If the small-loop-counter flag is set, use Word8.@@ -27,7 +30,7 @@ type LoopCounter = Word8 #else--- Otherwise, use Word32.+-- Otherwise, use Word8. type LoopCounter = Word32 #endif @@ -47,28 +50,47 @@ will treat its current position as live, which may cause it to skip some of the messages in the buffer. -}- , next :: {-# UNPACK #-} !Word32+ , next :: {-# UNPACK #-} !Word8 {- ^ This value tracks the next position that should be read (for receivers) or written to (for senders). -}+ , done :: {-# UNPACK #-} !Word8+ {- ^+ This value tracks whether or not the `InChan` is connected.++ If the value is @0@, the `InChan` is live. Otherwise, it was garbage collected.+ -} }- deriving (Eq, Show)+ deriving (Show) {- | The initial position in a channel ring buffer. -} zero :: ChanPos-zero = MkChanPos{loop = 0, next = 0}+zero = MkChanPos{done = 0, loop = 0, next = 0} {-# INLINE zero #-} {- |+Check whether two `ChanPos` are at the same position.+-}+eqPos :: ChanPos -> ChanPos -> Bool+eqPos icPos ocPos =+ loop icPos == loop ocPos && next icPos == next ocPos++{- |+Check whether the input channel `ChanPos` is done.+-}+isDone :: ChanPos -> Bool+isDone icPos = done icPos >= 1++{- | Advance to the next channel position. -}-advance :: Word32# -> ChanPos -> ChanPos+advance :: Word8# -> ChanPos -> ChanPos advance len# MkChanPos{..}- | next < W32# len# - 1 = MkChanPos{next = next + 1, ..}- | otherwise = MkChanPos{loop = loop + 1, next = 0}+ | next < W8# len# - 1 = MkChanPos{next = next + 1, ..}+ | otherwise = MkChanPos{loop = loop + 1, next = 0, ..} {-# INLINE advance #-} {- |@@ -83,7 +105,7 @@ -- position is aheaad of the input channel. | loop ocPos == loop icPos - 1 && next ocPos >= next icPos = ocPos -- The output channel is several loops behind the input channel.- | otherwise = icPos{loop = loop icPos - 1}+ | otherwise = ocPos{loop = loop icPos - 1, next = next icPos} {-# INLINE live #-} data Entry a@@ -98,7 +120,7 @@ unpack the @TVar@ inside of a @SmallArray@. -} data ChanBuf a = MkChanBuf- { len# :: Word32#+ { len# :: Word8# -- ^ The length of the channel ring buffer. , arr# :: SmallArray# (TVar# RealWorld (Entry a)) -- ^ The array that backs the channel ring buffer.@@ -107,13 +129,13 @@ {- | Create a new channel buffer. -}-newChanBuf :: Word32 -> IO (ChanBuf a)-newChanBuf (W32# len#) = IO $ \s1# ->- case word32ToInt# len# of+newChanBuf :: Word8 -> IO (ChanBuf a)+newChanBuf (W8# len#) = IO $ \s1# ->+ case word8ToInt# len# of ilen# -> case newTVar# Empty s1# of (# s2#, var0# #) ->- case newSmallArray# (word32ToInt# len#) var0# s2# of+ case newSmallArray# (word8ToInt# len#) var0# s2# of (# s3#, mutarr# #) -> let go :: Int# -> State# RealWorld -> State# RealWorld go i# = \s4# ->@@ -130,10 +152,10 @@ {- | Read the value from the given position in a `ChanBuf`. -}-takeChanBuf :: ChanBuf a -> Word -> Word32 -> STM (Maybe a)-takeChanBuf MkChanBuf{..} ocCount (W32# i#) =+takeChanBuf :: ChanBuf a -> Word -> Word8 -> STM (Maybe a)+takeChanBuf MkChanBuf{..} ocCount (W8# i#) = STM $ \s1# ->- case indexSmallArray# arr# (word32ToInt# i#) of+ case indexSmallArray# arr# (word8ToInt# i#) of (# vari# #) -> case readTVar# vari# s1# of (# s2#, Empty #) ->@@ -149,10 +171,10 @@ {- | Read the value from the given position in a `ChanBuf`. -}-isEmptyChanBuf :: ChanBuf a -> Word32 -> STM Bool-isEmptyChanBuf MkChanBuf{..} (W32# i#) =+isEmptyChanBuf :: ChanBuf a -> Word8 -> STM Bool+isEmptyChanBuf MkChanBuf{..} (W8# i#) = STM $ \s1# ->- case indexSmallArray# arr# (word32ToInt# i#) of+ case indexSmallArray# arr# (word8ToInt# i#) of (# vari# #) -> case readTVar# vari# s1# of (# s2#, Empty #) ->@@ -163,10 +185,10 @@ {- | Write the given value to a `ChanBuf` at the given position. -}-writeChanBuf :: ChanBuf a -> Word32 -> Entry a -> STM ()-writeChanBuf MkChanBuf{..} (W32# i#) a =+writeChanBuf :: ChanBuf a -> Word8 -> Entry a -> STM ()+writeChanBuf MkChanBuf{..} (W8# i#) a = STM $ \s1# ->- case indexSmallArray# arr# (word32ToInt# i#) of+ case indexSmallArray# arr# (word8ToInt# i#) of (# vari# #) -> case writeTVar# vari# a s1# of s2# ->@@ -180,10 +202,10 @@ This function returns `Just` `True` if the entry was freed, `Just` `False` if the entry was not freed, and `Nothing` if the entry was uninitialised. -}-tryFreeChanBufAt :: ChanBuf a -> Word -> Word32 -> STM (Maybe Bool)-tryFreeChanBufAt MkChanBuf{..} ocCount (W32# i#) =+tryFreeChanBufAt :: ChanBuf a -> Word -> Word8 -> STM (Maybe Bool)+tryFreeChanBufAt MkChanBuf{..} ocCount (W8# i#) = STM $ \s1# ->- case indexSmallArray# arr# (word32ToInt# i#) of+ case indexSmallArray# arr# (word8ToInt# i#) of (# vari# #) -> case readTVar# vari# s1# of (# s2#, Empty #) ->@@ -211,16 +233,11 @@ An input channel. -} data InChan a = MkInChan- { icState :: {-# UNPACK #-} !(ChanState a)+ { icStateRef :: {-# UNPACK #-} !(IORef (ChanState a)) {- ^- The underlying channel state.+ An `IORef` to the underlying channel state. - This is shared between all input and output channels.- -}- , icLive :: {-# UNPACK #-} !Live- {- ^- When this value is dropped, the corresponding `IsLive`- values in the output channels can be used to detect it.+ This `IORef` is /never/ written and exists only to attach a finalizer. -} } @@ -228,22 +245,37 @@ An output channel. An output channel has a finalizer that frees unreachable values in the ring buffer.-The worst-case complexity of this operation is $O(N)$ where $N$ is the length of the ring buffer.+The worst-case complexity of this operation is /O(N)/ where /N/ is the length of the ring buffer. -} data OutChan a = MkOutChan- { ocState :: !(ChanState a)+ { ocState :: {-# UNPACK #-} !(ChanState a) {- ^ The underlying channel state. This is shared between all input and output channels. -}- , ocIsLive :: !IsLive- -- ^ A value used test whether the corresponding input channel is live.- , ocPosVar :: !(TVar ChanPos)+ , ocPosVar :: {-# UNPACK #-} !(TVar ChanPos) -- ^ A variable that holds this output channel's position. } {- |+Free an input channel.+-}+freeInChan :: ChanState a -> IO ()+freeInChan MkChanState{..} =+ atomically $ do+ icPos <- readTVar icPosVar+ writeTVar icPosVar icPos{done = 1}++{- |+Add a finalizer to an `IORef`.++Adapted from @mkWeakTVar in @stm@.+-}+addFinalizerIORef :: IORef a -> IO () -> IO ()+addFinalizerIORef ref finalizer = void (mkWeakIORef ref finalizer)++{- | Free an output channel. __Warning:__@@ -262,15 +294,15 @@ -- Walk the buffer to free values that have been seen by every remaining OutChan. icPos <- readTVar icPosVar ocPos <- live icPos <$> readTVar ocPosVar- let go cp- | icPos == cp = pure ()+ let go pos+ | icPos `eqPos` pos = pure () | otherwise = do- mbSuccess <- tryFreeChanBufAt buffer ocCount (next cp)+ mbSuccess <- tryFreeChanBufAt buffer ocCount (next pos) case mbSuccess of Nothing- | loop icPos == 0 && next icPos <= next cp -> go zero+ | loop icPos == 0 && next icPos <= next pos -> go zero | otherwise -> pure ()- Just True -> go (advance len# cp)+ Just True -> go (advance len# pos) Just False -> pure () go ocPos @@ -290,20 +322,20 @@ The ring buffer is represented as a @SmallArray@, so @len@ should be smaller than 128. -}-new :: Word32 -> IO (InChan a, OutChan a)+new :: Word8 -> IO (InChan a, OutChan a) new len = do -- Create the input channel. buffer <- newChanBuf len icPosVar <- newTVarIO zero ocCountVar <- newTVarIO 1- icLive <- mkLive let icState = MkChanState{..}+ icStateRef <- newIORef icState+ addFinalizerIORef icStateRef (freeInChan icState) let ic = MkInChan{..} -- Create the output channel. ocPosVar <- newTVarIO zero let ocState = icState- ocIsLive <- mkIsLive icLive let oc = MkOutChan{..} addFinalizerTVar ocPosVar (freeOutChan oc) @@ -315,7 +347,8 @@ __Warning:__ If there are no output channels, the value is discarded. -} send :: InChan a -> a -> IO ()-send MkInChan{icState = MkChanState{buffer = buffer@MkChanBuf{..}, ..}} a =+send MkInChan{..} a = do+ MkChanState{buffer = buffer@MkChanBuf{..}, ..} <- readIORef icStateRef atomically $ do ocCount <- readTVar ocCountVar when (ocCount > 0) $ do@@ -358,10 +391,14 @@ {- | @`out` i@ creates a new output channel from the input channel @i@. -This worst-case complexity of this operation is $O(N)$ where $N$ is the length of the ring buffer.+The new output channel starts receiving messages from the oldest position that still holds a live value.+This is non-determinstic, as it depends on garbage collection.++This worst-case complexity of this operation is /O(N)/ where /N/ is the length of the ring buffer. -} out :: InChan a -> IO (OutChan a)-out MkInChan{icState = icState@MkChanState{..}, ..} =+out MkInChan{..} = do+ icState@MkChanState{..} <- readIORef icStateRef -- This operation is masked to ensure that the finalizer is attached. mask_ $ do -- See `dup` for an explanation for the use of `atomically`.@@ -375,7 +412,6 @@ -- Create the output channel. let ocState = icState- ocIsLive <- mkIsLive icLive let oc = MkOutChan{..} addFinalizerTVar ocPosVar (freeOutChan oc) @@ -395,7 +431,7 @@ atomically $ do icPos <- readTVar icPosVar ocPos <- live icPos <$> readTVar ocPosVar- if icPos == ocPos+ if icPos `eqPos` ocPos then pure False else do isEmpty <- isEmptyChanBuf buffer (next ocPos)@@ -431,14 +467,13 @@ receiveT_ icPos ocPos where receiveT_ icPos ocPos- | icPos == ocPos = do- -- If the input channel is still live...- icLive <- isLive ocIsLive- if icLive- -- ...we retry.- then retry- -- Otherwise, throw an NoInChanError.- else throwSTM ErrNoInChan+ | icPos `eqPos` ocPos = do+ -- If the input channel is done...+ if isDone icPos+ -- ...throw an NoInChanError.+ then throwSTM ErrNoInChan+ -- Otherwise, we retry+ else retry | otherwise = do ocCount <- readTVar ocCountVar mbVal <- takeChanBuf buffer ocCount (next ocPos)@@ -471,57 +506,9 @@ atomically ((Just <$> receiveT o) `orElse` (pure Nothing)) {- |-This type is used to test for liveness.--The target should hold on to a value of this type, the tester can use-the corresponding `IsLive` to test whether the target is still live.--}-data Live = MkLive (MutVar# RealWorld ())--{- |-Create a value of type `Live`.--}-mkLive :: IO Live-mkLive =- IO $ \s1# ->- case newMutVar# () s1# of- (# s2#, mv# #) ->- (# s2#, MkLive mv# #)--{- |-This type is used to test for liveness.--See `Live`.--}-data IsLive = MkIsLive (Weak# (MutVar# RealWorld ()))--{- |-Create an `IsLive` value that tests whether the given `Live` value is live.--}-mkIsLive :: Live -> IO IsLive-mkIsLive (MkLive mv#) =- IO $ \s1# ->- case mkWeak# mv# mv# (\s3# -> (# s3#, () #)) s1# of- (# s2#, wmv# #) ->- (# s2#, MkIsLive wmv# #)--{- |-Test whether the `Live` value that corresponds to the given `IsLive`-value is still live.--}-isLive :: IsLive -> STM Bool-isLive (MkIsLive wmv#) =- STM $ \s1# ->- case deRefWeak# wmv# s1# of- (# s2#, flag#, _ #) ->- case flag# of- 0# -> (# s2#, False #)- _ -> (# s2#, True #)--{- |-The channel ring buffer is indexed by a `Word32`,+The channel ring buffer is indexed by a `Word8`, which we must convert to an `Int` to index the underlying `SmallArray#`. -}-word32ToInt# :: Word32# -> Int#-word32ToInt# = \i# -> word2Int# (word32ToWord# i#)-{-# INLINE word32ToInt# #-}+word8ToInt# :: Word8# -> Int#+word8ToInt# = \i# -> word2Int# (word8ToWord# i#)+{-# INLINE word8ToInt# #-}
test/Main.hs view
@@ -2,10 +2,11 @@ {-# LANGUAGE InstanceSigs #-} {-# LANGUAGE LambdaCase #-} {-# LANGUAGE TypeApplications #-}+{-# LANGUAGE ScopedTypeVariables #-} module Main where -import Control.Concurrent (threadDelay)+import Control.Concurrent (forkIO, threadDelay) import Control.Concurrent.LossyChan qualified as LC import Control.Concurrent.MVar (MVar, newEmptyMVar, putMVar, takeMVar) import Control.Exception (ArrayException (IndexOutOfBounds), assert, handle, throw)@@ -15,11 +16,12 @@ import Data.Traversable (for) import Data.Word (Word32, Word8) import GHC.Stack (HasCallStack)+import HeapSize (recursiveSize, runHeapsize) import System.Mem (performMajorGC) import System.Mem.Weak (Weak) import System.Timeout (timeout) import Test.Tasty (TestTree, defaultMain, testGroup)-import Test.Tasty.HUnit (assertFailure, testCase, (@?=))+import Test.Tasty.HUnit (assertBool, assertFailure, testCase, (@?=)) import Test.Tasty.QuickCheck (Arbitrary (..), Gen, Property, chooseBoundedIntegral, counterexample, forAll, ioProperty, label, oneof, testProperty) main :: IO ()@@ -27,10 +29,11 @@ defaultMain $ testGroup "Tests"- [ unitTests 2- , unitTests 8- , unitTests 32- , unitTests 128+ [ unitTestsFor 2+ , unitTestsFor 8+ , unitTestsFor 32+ , unitTestsFor 128+ , unitTests , propTests ] @@ -53,11 +56,11 @@ -} prop_LosslessWhenKeepingUpSimp :: Property prop_LosslessWhenKeepingUpSimp =- forAll (chooseBoundedIntegral (1, 128)) $ \n ->- forAll (chooseBoundedIntegral (1, 2 * n * maxLoop)) $ \m ->- label (if n >= m then "N >= M" else "N < M") $+ forAll (chooseBoundedIntegral (1, 128)) $ \(n :: Word8) ->+ forAll (chooseBoundedIntegral (1, 2 * word8ToWord n * maxLoop)) $ \(m :: Word) ->+ label (if word8ToWord n >= m then "N >= M" else "N < M") $ ioProperty $ do- (i, o) <- LC.new @Word32 n+ (i, o) <- LC.new @Word n let xs = [0 .. m] and <$> ( for xs $ \x -> do@@ -88,7 +91,7 @@ | otherwise = "N == 1 " mLabel :: String mLabel- | m >= n * maxLoop = "M >= N * maxLoop"+ | m >= word8ToWord n * maxLoop = "M >= N * maxLoop" | otherwise = "M < N * maxLoop" oknLabel :: String oknLabel@@ -107,8 +110,8 @@ prop_Lose1WhenLaggingByNPlus1 = forAll (chooseBoundedIntegral (1, 128)) $ \n -> ioProperty $ do- (i, o) <- LC.new @Word32 n- let xs = [0 .. n]+ (i, o) <- LC.new @Word n+ let xs = [0 .. word8ToWord n] for_ xs $ (LC.send i) mby <- LC.tryReceive o pure $@@ -122,22 +125,67 @@ prop_LoseNWhenLaggingBy2NPlus1 = forAll (chooseBoundedIntegral (1, 128)) $ \n -> ioProperty $ do- (i, o) <- LC.new @Word32 n- let xs = [0 .. 2 * n]+ (i, o) <- LC.new @Word n+ let xs = [0 .. 2 * word8ToWord n] for_ xs $ (LC.send i) mby <- LC.tryReceive o pure $ counterexample ("Expected " <> show (n + 1) <> ", but received " <> show mby) $- mby == Just (n + 1)+ mby == Just (word8ToWord n + 1) {- |-Unit tests.+Unit tests that do not depend on buffer length. -}-unitTests :: Word32 -> TestTree-unitTests n =+unitTests :: TestTree+unitTests =+ testGroup "Unit" $+ [ testCase "early free" $ do+ p1 <- newEmptyMVar+ t1 <- mkTattleTale p1+ (i, o) <- LC.new 64+ LC.send i (Left t1)+ LC.send i (Right ())+ void (LC.receive o)+ performMajorGC+ timeout 100000 (takeMVar p1)+ >>= maybe (assertFailure "t1 was not freed") pure+ , testCase "receive throws when InChan is dropped" $ do+ let handleNoChan LC.ErrNoInChan = pure $ Left LC.ErrNoInChan+ (_, o) <- LC.new @() 64+ performMajorGC+ v <- handle handleNoChan (Right <$> timeout 10000 (LC.receive o))+ case v of+ Left LC.ErrNoInChan -> pure ()+ Right _ -> assertFailure "ErrNoInChan exception not thrown."+ , testCase "receive does not throw when InChan is not dropped" $ do+ let handleNoChan LC.ErrNoInChan = pure False+ (i, o) <- LC.new @Word32 64+ performMajorGC+ _ <- forkIO $+ for_ [0 .. 256] $ \x ->+ LC.send i x+ let go :: Word32 -> IO ()+ go k+ | k >= 256 = pure ()+ | otherwise =+ timeout 10000 (LC.receive o)+ >>= maybe (pure ()) (const $ go (k + 1))+ success <- handle handleNoChan (go 0 >> pure True)+ LC.send i 0+ assertBool "ErrNoInChan was thrown" success+ , testCase "size of ChanPos is 2" $ do+ size <- runHeapsize 10 $! recursiveSize MkChanPos{done = 0, loop = 0, next = 0}+ size @?= Just 2+ ]++{- |+Unit tests for a specific buffer length.+-}+unitTestsFor :: Word8 -> TestTree+unitTestsFor n = testGroup ("Unit (with N = " <> show n <> ")") $ [ testCase "out continues from oldest live value" $ do- (i, o1) <- LC.new @Word32 n+ (i, o1) <- LC.new @Word n for_ [1, 2] (LC.send i) -- receive 1; is no longer live@@ -155,7 +203,7 @@ m2' <- LC.receive o2 m2' @?= 2 , testCase "send discards message if there are no output channels" $ do- (i, _) <- LC.new @Word32 n+ (i, _) <- LC.new @Word n performMajorGC threadDelay 1000000 LC.send i 1@@ -164,7 +212,7 @@ m2 <- LC.receive o m2 @?= 2 , testCase "send i 1 >> receive o ==> 1" $ do- (i, o) <- LC.new @Word32 n+ (i, o) <- LC.new @Word n v <- LC.send i 1 >> LC.receive o v @?= 1 , testCase "for [1,2] (\\x -> send i x >> receive 0) ==> [1,2]" $ do@@ -174,49 +222,66 @@ x2 <- LC.send i 2 >> LC.receive o x2 @?= 2 , testCase "send i 1 >> receive o >> receive o ==> block" $ do- (i, o) <- LC.new @Word32 n+ (i, o) <- LC.new @Word n v <- LC.send i 1 >> LC.receive o v @?= 1 w <- timeout 1000 (LC.receive o) w @?= Nothing , testCase "for_ [0..N] (send i) >> receive o ==> 1" $ do- (i, o) <- LC.new @Word32 n- v <- for_ [0 .. n] (LC.send i) >> LC.receive o+ (i, o) <- LC.new @Word n+ v <- for_ [0 .. word8ToWord n] (LC.send i) >> LC.receive o v @?= 1 , testCase "for_ [0..N*2] (send i) >> receive o ==> N + 1" $ do- (i, o) <- LC.new @Word32 n- v <- for_ [0 .. n * 2] (LC.send i) >> LC.receive o- v @?= n + 1+ (i, o) <- LC.new @Word n+ v <- for_ [0 .. word8ToWord n * 2] (LC.send i) >> LC.receive o+ v @?= word8ToWord n + 1 , testCase "for_ [0..N*L+1] (send i) >> receive o ==> N * (L - 1) + 1" $ do- (i, o) <- LC.new @Word32 n- v <- for_ [0 .. n * maxLoop] (LC.send i) >> LC.receive o- v @?= n * (maxLoop - 1) + 1+ (i, o) <- LC.new @Word n+ v <- for_ [0 .. word8ToWord n * maxLoop] (LC.send i) >> LC.receive o+ v @?= word8ToWord n * (maxLoop - 1) + 1 , testCase "send i 1 >> traverse receive [o1,o2] ==> [1,1]" $ do- (i, o1) <- LC.new @Word32 n+ (i, o1) <- LC.new @Word n o2 <- LC.dup o1 vs <- LC.send i 1 >> traverse LC.receive [o1, o2] vs @?= [1, 1]- , testCase "early free" $ do- p1 <- newEmptyMVar- t1 <- mkTattleTale p1- (i, o) <- LC.new n- LC.send i (Left t1)- LC.send i (Right ())- void (LC.receive o)- performMajorGC- timeout 100000 (takeMVar p1)- >>= maybe (assertFailure "t1 was not freed") pure- , testCase "receive hangs if InChan is dropped" $ do- let handleNoChan LC.ErrNoInChan = pure $ Left LC.ErrNoInChan- (_, o) <- LC.new @() n- performMajorGC- v <- handle handleNoChan (Right <$> timeout 10000 (LC.receive o))- case v of- Left LC.ErrNoInChan -> pure ()- Right _ -> assertFailure "ErrNoInChan exception not thrown." ] --------------------------------------------------------------------------------+-- ChanPos+--------------------------------------------------------------------------------++{- |+__Warning:__+This definition is copied from "Control.Concurrent.LossyChan" and should be kept+up to date. Otherwise, the heapsize test is meaningless.+-}+data ChanPos = MkChanPos+ { loop :: {-# UNPACK #-} !Word32+ {- ^+ This value tracks the current loop around the channel ring buffer, which is+ used to determine whether or not a channel position refers to a live value.++ The `maxBound` of this type determines the resilience of the `OutChan`.+ If a receiver stops at loop @N@ and does not resume until the sender has+ written @`maxBound` - 1@ or @`maxBound`@ values and the loop counter has+ wrapped around all the way back to loop @N - 1 @ or @N@, then the receiver+ will treat its current position as live, which may cause it to skip some of+ the messages in the buffer.+ -}+ , next :: {-# UNPACK #-} !Word8+ {- ^+ This value tracks the next position that should be read (for receivers) or+ written to (for senders).+ -}+ , done :: {-# UNPACK #-} !Word8+ {- ^+ This value tracks whether or not the `InChan` is connected.++ If the value is @1@, the `InChan` is done and has been garbage collected.+ -}+ }++-------------------------------------------------------------------------------- -- Maximum Loop Count -------------------------------------------------------------------------------- @@ -224,11 +289,11 @@ The maximum loop value for a @ChanPos@. This value is the `maxBound` of `Word8`. In the actual implementation,-`maxLoop` would be `maxBound` of `Word32`. To test the overflow cases,+`maxLoop` would be `maxBound` of `Word`. To test the overflow cases, build the library with @--flags=+small-loop-counter@. -}-maxLoop :: Word32-maxLoop = fromIntegral (maxBound :: Word8)+maxLoop :: Word+maxLoop = word8ToWord (maxBound :: Word8) -------------------------------------------------------------------------------- -- TattleTale@@ -275,9 +340,9 @@ This type holds the configuration for trace generation. -} data TraceConfig = MkTraceConfig- { n :: !Word32+ { n :: !Word8 -- ^ The size of the channel ring buffer.- , m :: !Word32+ , m :: !Word -- ^ The total number of messages to send. , okn :: !Int -- ^ The total number of receivers that must keep up.@@ -291,9 +356,9 @@ -} data TraceOp = -- | @`Send` x t@ sends @x@ over the `LC.InChan`.- Send !Word32+ Send !Word | -- | @`ReceiveK` k x t@ receives @x@ over the @k@'th `LC.OutChan` that must keep up.- ReceiveK !Int !Word32+ ReceiveK !Int !Word | -- | @`Receive` l t@ receives some value over the @l@'th `LC.OutChan` that may lag behind. ReceiveL !Int deriving (Show)@@ -315,11 +380,11 @@ This type holds the state of the system after at some point in a `Trace`. -} data TraceState = MkTraceState- { ic :: !Word32+ { ic :: !Word -- ^ Number of messages sent over `LC.InChan`.- , okcs :: ![Word32]+ , okcs :: ![Word] -- ^ Number of messages received per `LC.OutChan` that must keep up.- , olcs :: ![Word32]+ , olcs :: ![Word] -- ^ Number of messages received per `LC.OutChan` that may lag behind. } deriving (Show)@@ -371,8 +436,8 @@ -} genTraceConfig :: Gen TraceConfig genTraceConfig = do- n <- chooseBoundedIntegral (1, 128)- m <- chooseBoundedIntegral (2 * n, 2 * n * maxLoop)+ (n :: Word8) <- chooseBoundedIntegral (1, 128)+ (m :: Word) <- chooseBoundedIntegral (2 * word8ToWord n, 2 * word8ToWord n * maxLoop) okn <- chooseBoundedIntegral (2, 4) oln <- chooseBoundedIntegral (0, 2) pure MkTraceConfig{..}@@ -441,14 +506,11 @@ ic <= m , -- The difference between the number of sent and the number of received -- messages by channels that must keep up is at least 0 and at most n.- all (\okc -> let dm = asInt ic - asInt okc in 0 <= dm && dm <= asInt n) okcs+ all (\okc -> let dm = wordToInt ic - wordToInt okc in 0 <= dm && dm <= wordToInt (word8ToWord n)) okcs , -- The difference between the number of sent and the number of received -- messages by channels that may lag behind is at least 0.- all (\olc -> let dm = asInt ic - asInt olc in 0 <= dm) olcs+ all (\olc -> let dm = wordToInt ic - wordToInt olc in 0 <= dm) olcs ]- where- asInt :: Word32 -> Int- asInt = fromIntegral {- | Apply the given function at the given index in the given list.@@ -500,3 +562,12 @@ Send _ -> True ReceiveK k _ -> k < okn ReceiveL l -> l < oln+++word8ToWord :: Word8 -> Word+word8ToWord = fromIntegral+{-# INLINE word8ToWord #-}++wordToInt :: Word -> Int+wordToInt = fromIntegral+{-# INLINE wordToInt #-}