Data.Concurrent.Deque.ChaseLev

Chase-Lev work stealing Deques

This implementation derives directly from the pseudocode in the 2005 SPAA paper:

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.170.1097&rep=rep1&type=pdf

TODO: local topBound optimization. TODO: Do the more optimized version of growCirc

Documentation

data ChaseLevDeque a

Instances

DequeClass ChaseLevDeque

PopL ChaseLevDeque

newQ :: IO (ChaseLevDeque elt)

nullQ :: ChaseLevDeque elt -> IO Bool

pushL :: ChaseLevDeque a -> a -> IO ()

For a work-stealing queue pushL is the ``local'' push. Thus only a single thread should perform this operation.

tryPopL :: ChaseLevDeque elt -> IO (Maybe elt)

tryPopR :: ChaseLevDeque elt -> IO (Maybe elt)

This is the steal operation. Multiple threads may concurrently attempt steals from the same thread.

approxSize :: ChaseLevDeque elt -> IO Int

Return a lower bound on the size at some point in the recent past.

dbgInspectCLD :: Show a => ChaseLevDeque a -> IO String