Capstone C: the STM queue
A bounded STM queue
A queue is a TVar [a] with a limit. A write retries while the queue is full, a read retries while it is empty, and the two together are a bounded buffer with backpressure: a producer that is faster than its consumers waits instead of growing the heap.
writeQueue queue value = do
items <- readTVar (queueItems queue)
if length items >= queueLimit queue
then retry
else writeTVar (queueItems queue) (items ++ [value])
The list is appended at the end and taken from the front, so the order is FIFO and the cost is linear in the size; the limit keeps the size small, which is the trade the STM lesson described.
The program
module Main (main) where
import Control.Concurrent.STM
data Queue = Queue
{ queueItems :: TVar [Int]
, queueLimit :: Int
}
newQueue :: Int -> IO Queue
newQueue limit = do
items <- newTVarIO []
pure (Queue items limit)
writeQueue :: Queue -> Int -> STM ()
writeQueue queue value = do
items <- readTVar (queueItems queue)
if length items >= queueLimit queue
then retry
else writeTVar (queueItems queue) (items ++ [value])
readQueue :: Queue -> STM Int
readQueue queue = do
items <- readTVar (queueItems queue)
case items of
[] -> retry
value : rest -> writeTVar (queueItems queue) rest >> pure value
main :: IO ()
main = do
queue <- newQueue 3
atomically $ mapM_ (writeQueue queue) [1, 2, 3]
first <- atomically (readQueue queue)
atomically (writeQueue queue 4)
items <- readTVarIO (queueItems queue)
print (first, items)
ghc -Wall -O1 -o queue queue.hs
./queue
(1,[2,3,4])
Reading the output
- Three values filled the queue to its limit of three.
- The first read took 1 and left two items, so the fourth write fit.
- The pair printed is the value that was read and the queue after the new write.
A fourth write without a read would retry and the thread would wait for a consumer, which is the backpressure the next lesson uses with workers.
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does
writeQueuedo when the queue is full?Answer
Retries and waits for a consumer
The retry is what gives the bounded queue its backpressure.
-
What is the queue represented by?
Answer
A TVar holding a list, plus a limit
The list and the limit are the whole state.
-
What order does the queue keep?
Answer
FIFO: appended at the end, taken from the front
The write appends and the read takes the head.
-
What does this program print?
module Main (main) where main :: IO () main = print (length [1, 2] :: Int)Answer
2
The list has two elements.
-
Why does a full queue not grow?
Answer
The write retries instead of writing
The limit and the retry are the bound.
-
What does this program print?
module Main (main) where import Control.Concurrent.STM main :: IO () main = do box <- newTVarIO [1, 2 :: Int] value <- atomically $ do items <- readTVar box case items of [] -> retry v : rest -> writeTVar box rest >> pure v print (value, [1 :: Int])Answer
(1,[1])
The read takes the head 1 and the rest is written back.
-
What is the cost of the write in this representation?
Answer
Linear in the size, because the list is appended
Appending walks the list, which the limit keeps short.
-
What does this program print?
module Main (main) where main :: IO () main = print (1 + 2 :: Int)Answer
3
One plus two is three.
-
What does backpressure mean here?
Answer
A fast producer waits instead of filling memory
The write blocks when the queue is at its limit.
-
What does this program print?
module Main (main) where main :: IO () main = print (null [1 :: Int])Answer
False
The list has an element.
The code on this page was built with GHC 9.10.3 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev