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

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.

  1. What does writeQueue do when the queue is full?

    Answer

    Retries and waits for a consumer

    The retry is what gives the bounded queue its backpressure.

  2. What is the queue represented by?

    Answer

    A TVar holding a list, plus a limit

    The list and the limit are the whole state.

  3. 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.

  4. What does this program print? module Main (main) where main :: IO () main = print (length [1, 2] :: Int)

    Answer

    2

    The list has two elements.

  5. Why does a full queue not grow?

    Answer

    The write retries instead of writing

    The limit and the retry are the bound.

  6. 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.

  7. 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.

  8. What does this program print? module Main (main) where main :: IO () main = print (1 + 2 :: Int)

    Answer

    3

    One plus two is three.

  9. What does backpressure mean here?

    Answer

    A fast producer waits instead of filling memory

    The write blocks when the queue is at its limit.

  10. 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

Banner image