Implement 2-3 concurrent data structures from the literature
|Reported by:||rrnewton||Owned by:||rrnewton|
|Priority:||good||Keywords:||concurrency, data structures|
|Cc:||acfoltzer||Difficulty:||1 person Summer|
Description (last modified by 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:
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) :
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):
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 Students (Include enough identifying info to find/reach you!)
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
Change History (25)
comment:12 Changed 3 years ago by rrnewton
- Description modified (diff)
- Difficulty changed from unknown to 1 person Summer