[Haskell-cafe] ANN: stm-sbchan-0.1 - STM channel with maximum total size of items

Joey Adams joeyadams3.14159 at gmail.com
Tue Jul 31 20:09:07 CEST 2012

This package provides a bounded channel type for STM.  TBChan (in
stm-chans) and TBQueue (introduced in stm 2.4) are bounded channels
that limit the number of items in the channel.  SBChan, on the other
hand, limits the total size of items in the channel, where "size" is
defined by providing an instance of the ItemSize class:

    data Entry = Entry Int64 ByteString Time

    -- | Estimated amount of memory an 'Entry' requires,
    -- including channel overhead
    instance ItemSize Entry where
        itemSize (Entry _ s _) = B.length s + 200

Then, "SBChan Entry" is a channel that limits (approximately) the
amount of memory the entries take up.

SBChan can also be used as a regular count-bounded channel by using
the SBCItem newtype wrapper, where itemSize is always 1.



--- Implementation details ---

itemSize returns an Int.  I originally considered using an associated
type, so users could pick their own number type to use.  However, this
would have made the implementation harder to reason about, if we had
to worry about the user picking an ill-behaved number type like Float.
 Besides, Int is usually adequate for representing in-memory sizes.

This library takes a lot of ideas from TChan and TBChan.  I decided to
use the linked list of TVars approach that TChan uses, rather than the
pair of lists approach T(B)Queue uses, to avoid a potential problem
with code like this:

    msg <- readTBQueue
    case msg of
        Foo -> ...
        Bar -> ...

If the transaction is repeated a lot due to retries or invalidation,
and readTBQueue needs to turn around the list at this point, then
we'll end up repeating O(n) work a bunch of times.

SBChan uses stm-tlist, a library I wrote that is based on TChan's
internal representation.  Also, SBChan uses the usual trick for
reducing reader-writer contention by having two counters for capacity,
one for readers and one for writers.

More information about the Haskell-Cafe mailing list