id	summary	reporter	owner	description	type	status	priority	resolution	keywords	cc	topic	difficulty	mentor
1608	Implement 2-3 concurrent data structures from the literature	rrnewton	rrnewton	"The GHC Haskell compiler recently gained the capability to generate atomic compare-and-swap (CAS) assembly instructions. This opens up a new world of lock-free data-structure implementation possibilities.

Furthermore, it's an important time for concurrent data structures.  Not only is the need great, but the design of concurrent data structures has been a very active area in recent years, as summarized well by Nir Shavit in this article:

http://cacm.acm.org/magazines/2011/3/105308-data-structures-in-the-multicore-age/

Because Haskell objects containing pointers can't efficiently be stored outside the Haskell heap, it is necessary to reimplement these data structures for Haskell, rather than use the FFI to access external implementations. There are already a couple of data structures implemented in the following library (queues and deques) :

https://github.com/rrnewton/haskell-lockfree-queue

But, this leaves many others, such as:

* Concurrent Bags

* Concurrent Priority Queues

A good point of reference would be the libcds collection of concurrent data structures for C++ (or those that come with Java or .NET):

   http://libcds.sourceforge.net/

One of the things that makes implementing these data structures fun is that they have very short algorithmic descriptions but a high density of thought-provoking complexity.

A good GSoC project would be to implement 2-3 data structures from the literature, and benchmark them against libcds implementations.


== Interested Mentors ==

Ryan Newton

== Interested Students (Include enough identifying info to find/reach you!) ==

Sergiu Ivanov

kodoque

Mathias Bartl

Aleksandar Kodzhabashev

== UPDATE ==

This ticket has been '''REFACTORED'''. It is now specifically focused on deques, bags, or priority queues.  For anyone interested in concurrent hash-tables / hashmaps take a look at ticket #1617.

== Recommended Papers with State-of-the-art Algorithms == 

 * http://www.cse.chalmers.se/~tsigas/papers/Lock%20Free%20Bag%20SPAA11.pdf



"	proposed-project	new	not yet rated		concurrency, data structures	acfoltzer	misc	1 person Summer	not-accepted