Skip to content

Instantly share code, notes, and snippets.

@alllex
Last active May 2, 2020 03:35
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save alllex/439480b7e80303f19ddc to your computer and use it in GitHub Desktop.
Haskell GSoC 2015 Proposal STM Data Structures

Abstract

The goal of this project is to develop high quality concurrent STM data structures using recent developments in lock-free data structures as a guide but relying on STM for simple and clear concurrent semantics.

Outline

This article provides a great overview on concurrent data structures. As one can see there are several different operations used for implementing those structures. One way to do it is to apply Software Transactional Memory.

There are already a lot data structures at Hackage:

Unfortunately some of them are not yet fully completed. Others present itselves as control flow structures. The idea is to pick a couple and turn them to concurrent data structures with appropriate API.

Concurrent data structures can be implemented with a broad range of "granularity". Mostly structures are built upon STM are pure Haskell values hiding behind TVars. The idea is to push this TVar down the abstraction. For example turning

data TQueue a = TQueue (TVar [a])

to

data TList a = Nil | TNode a (TVar (TList a))
data TLQueue a = TLQueue
    { queueHead :: TVar (TList a)
    , queueTail :: TVar (TVar (TList a))
    } 

Such transformations could make implementation more scalable. A complete example can be found here. It is also possible to employ ideas from lock-free implementations to avoid unnecessary contention in STM.

Papers

Timeline

April 27 - May 27: Studying related papers.

May 28 - June 28: Implementation of Priority Queue along with its benchmarking.

June 29 - July 15: Work-stealing queue implementation.

July 16 - July 30: Implementation and benchmarking of Concurrent Bag.

August 1 - August 17: Wrapping up results and preparing packages to be published at Hackage.

About me

I'm a third year student at Saint-Petersburg State University at Software Engineering Department. I've discovered FP about 3 years ago working with F# for the first year. As a result I've implemented parser-combinator library as analogue of fparsec for our own simple PL.

I have an university course on Operating Systems. From there I've got theoretical knowledge of multi-threading, dead-locks and basics of concurrency. Programming course which I took a year ago involved writing simple multi-threading applications related to mathematical calculations and (another one) to make user tasks work in parallel. All of that was implemented using F#.

Then I've completed Haskell course. After that it was the only PL I've used for solving tasks at another courses where possible. I've also experimented with it writing math expression parsers (using monadic parser-combinators), Brainfuck interpreter and a bit of parallel computations. All of that can be found on my github page.

Email: alllex.semin@gmail.com

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment