Opened 6 years ago

Last modified 3 years ago

#1608 new proposed-project

Implement 2-3 concurrent data structures from the literature — at Version 1

Reported by: Ryan Newton Owned by: Ryan Newton
Priority: good Keywords: concurrency, data structures
Cc: Adam C. Foltzer Difficulty: 1 person Summer
Mentor: not-accepted Topic: misc

Description (last modified by Ryan Newton)

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.

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 Hashtables
  • 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.

Change History (1)

comment:1 Changed 6 years ago by Ryan Newton

Description: modified (diff)
Owner: set to Ryan Newton
Note: See TracTickets for help on using tickets.