A collection of different packages for CAS based data structures.
Haskell Shell C Makefile
Latest commit 0ea12fc May 9, 2016 @rrnewton Merge branch 'ghc-8.0'
Failed to load latest commit information.
DequeTester Remove outdated submodules Feb 4, 2014
Obsolete_Deprecated/IORefCAS Refactor/reorganization: rename all folders to match the package names. Feb 3, 2014
abstract-deque-tests Refactor: pull all tests out of abstract-deque and into their own pac… Feb 4, 2014
atomic-primops-foreign bump base upper bound for atomic-primops-foreign May 4, 2015
atomic-primops Merge branch 'ghc-8.0' May 9, 2016
chaselev-deque whitespace changes May 4, 2015
experimental minor: correct IORef->Ref error in the EDSL_sums prototype Oct 19, 2012
lockfree-queue Update lockfree-queue package to move tests into a subdir. Aug 18, 2014
mega-deque Refactor: pull all tests out of abstract-deque and into their own pac… Feb 4, 2014
vector-atomics/Data/Vector/Unboxed typo fix Sep 6, 2014
.gitignore minor: gitignore update Mar 8, 2012
.jenkins_common.sh create a separate list of packages under test as oppsoed to just packaes May 5, 2015
.jenkins_script1.sh create a separate list of packages under test as oppsoed to just packaes May 5, 2015
.jenkins_script2.sh create a separate list of packages under test as oppsoed to just packaes May 5, 2015
.travis.yml Take the specific nightly off of the allowed-failures list Aug 24, 2015
.travis_install.sh Debugging stack w/ resolver=ghc Aug 24, 2015
.travis_script.sh Add tests with nightly and ghc resolvers. Activate caching. Aug 24, 2015
stack.yaml Add stack.yaml and remove some upper bounds from atomic-primops-vector. Aug 10, 2015


Build Status and unit tests

  • Jenkins: Build Status -- Basic primops only, i.e. atomic-primops package:
  • Jenkins: Build Status -- all Queue and Deque data structures in this package.
  • Travis: Build Status -- combined build&test for all packages in the repo.

Contents of this Repository

This is a multi-package repository. The following directories each correspond to exactly one cabal package:

  • [abstract-deque]: AbstractDeque - abstract interface for single and double ended queues, plus reference implementation in pure Haskell
  • [lockefree-queue]: classic Michael & Scott algorithm for single ended queues
  • [chaselev-deque]: work-stealing "1.5" ended deques.
  • [mega-deque]: a package that picks the best implementation for the interface constraints, which are expressed at the type level.
  • [atomic-primops]: safe CAS/FAA on various kinds of mutable locations
  • [atomic-primops-foreign]: Add on package that provides an FFI based implementation of counters.

Please see the .cabal files for more detailed descriptions of each package.

How to Test and Install

First, to use compare-and-swap based data structures, you should be using GHC 7.4.1 or later. Some of these libaries will be forced to "fake it" on earlier versions of GHC.

You can install all of the packages in your user's .cabal directory with the following command:


You may also want to build the tests at the same time:

./install_all.sh --enable-tests

There are currently [2012.02.29] some problems with cabal failing to automatically install dependencies for tests (as opposed to libraries). You may have to manually install some packages via cabal (e.g. test-framework-HUnit).

If you take a look at that install_all.sh script, you'll notice you can also configure which executables for cabal and ghc it uses, for example:

GHC=ghc-7.4.1 CABAL=cabal-0.10.2 ./install_all.sh --enable-tests

Next, you can run the tests like this:


That test should complete successfully with a zero exit code.

Note that if you have trouble building test-suites through cabal, you can build them manually with GHC using a command like the following:

cd MichaelScott/
ghc-7.4.1 -O2 -threaded -rtsopts Test.hs -o Test.exe

Building with Profiling for debugging:

ghc-7.4.1 -prof -osuf=o_p -O2 -threaded -rtsopts Test.hs -o Test.exe

You might have to reinstall some of the dependencies with profiling enabled:

cabal install -p hostname xml regex-base regex-posix ansi-terminal ansi-wl-pprint test-framework test-framework-hunit --reinstall

Reinstalling with profiling can be REALLY annoying once the libraries are already installed. For example, if you forget a dependency above it will complete most of the compile, giving you the "profiling version not available" error only later on, resulting in a quadratic compilation process as you reinstall, add one more dep, reinstall, repeat.



  • It would be nice to add a binding to TBB concurrent queues or other foreign implementations (for storable types).

  • Test on windows. (It hasn't been tried.)