Implement 2-3 concurrent data structures from the literature

[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

[acfoltzer]

A good candidate for implementation is this concurrent bag (Sundell, Gidenstam, Papatriantafilou, Philippas 2011):  http://www.cse.chalmers.se/~tsigas/papers/Lock%20Free%20Bag%20SPAA11.pdf

In order to implement this in the manner described in the paper, we will need to extend GHC's support for compare-and-swap to operate on pointer arrays (i.e., MutableArray#), not just IO/STRefs. I've looked into what this would require, and would be happy to assist.

[kodoque]

I would really like to be mentored on this project. I have some experience with FP language, mainly Ocaml and a bit of Haskell.

[MathiasBartl]

Hi, there are currently 3 interested students, from what I assume there is enough work for everyone to go around. Would it be possible to chat on IRC, possibly on Mondays (I am on Middle European Time )

[MathiasBartl]

Ok, I can start with the concurrent bag. How about this paper:  http://tx.technion.ac.il/~dima39/publications/SALSA.pdf it also uses CAS and apparently is better.

[rrnewton]

Replying to kodoque:

I would really like to be mentored on this project. I have some experience with FP language, mainly Ocaml and a bit of Haskell.

Hi Kodoque -- I'm mailing everyone interested in this ticket, but I can't find your name/email listed elsewhere. Could you contact me?

[rrnewton]

Replying to MathiasBartl:

Ok, I can start with the concurrent bag. How about this paper:  http://tx.technion.ac.il/~dima39/publications/SALSA.pdf it also uses CAS and apparently is better.

Very interesting! This is definitely worth looking into, but I would mention a couple caveats.

• For a general purpose bag implementation we would care about situations where one node is both a producer and consumer.
• I'm slightly concerned about this paper. I can't find a date/publication venue. The Sundell paper was published in a top conference (SPAA 2011).

[MathiasBartl]

I would like to see wheter it would be possible to use Formal Verification for this Implementations, in my opinion concurrent data structures would be well suited for Formal Verification, I will talk to someone at my University about this.

[MathiasBartl]

According to:  http://www.zurich.ibm.com/pdf/sys/adv_messaging/shortConcurrentPrioQueue.pdf witch seems to be the most recent research paper. (I only tests fro 8 Cores thought) candidates for a concurrent priority queu would be : Quantizing Queue or Lock Free Skip List I would implement the Quantizing Queue,because it is given as having the best Performance in the Tests,and it uses MichaelScott? Queues, witch I believe Ryan has already implemented. The paper that is given as Source:  http://www.zurich.ibm.com/pdf/sys/adv_messaging/Tempo_ACNM07.pdf does not seem so good a place to start with for starting to implement, it does not have f.E. include any pseudocode, IIt would be helpfull to have a diffenret source. The Lock Free List as described does not support multiple entries with the same priority, unless I find a paper with a version that does remiefy this, I would exclude it.

[MathiasBartl]

I am not 100% sure about the last 2 papers.