[Haskell-cafe] Google Summer of Code - Lock-free data structures

[Ben]

perhaps it is too late to suggest things for GSOC --

but stephen tetley on a different thread pointed at aaron turon's work, which there's a very interesting new concurrency framework he calls "reagents" which seems to give the best of all worlds : it is declarative and compositional like STM, but gives performance akin to hand-coded lock-free data structures.  he seems to have straddled the duality of isolation vs message-passing nicely, and can subsume things like actors and the join calculus.

http://www.ccs.neu.edu/home/turon/reagents.pdf

he has a BSD licensed library in scala at

https://github.com/aturon/ChemistrySet

if someone doesn't want to pick this up for GSOC i might have a hand at implementing it myself.

b

On Mar 29, 2012, at 6:46 AM, Tim Harris (RESEARCH) wrote:

> Hi,
> 
> Somewhat related to this...
> 
> Next month we have a paper coming up at EuroSys about a middle-ground between using STM and programming directly with CAS:
> 
> http://research.microsoft.com/en-us/um/people/tharris/papers/2012-eurosys.pdf
> 
> This was done in the context of shared memory data structures in C/C++, rather than Haskell. 
> 
> It might be interesting to see how the results carry over to Haskell, e.g. adding short forms of specialized transactions that interact correctly with normal STM-Haskell transactions.
> 
> In the paper we have some examples of using short specialized transactions for the fast paths in data structures, while keeping the full STM available as a fall-back for expressing the cases that cannot be implemented using short transactions.
> 
> --Tim
> 
> 
> 
> 
> -----Original Message-----
> From: haskell-cafe-bounces at haskell.org [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Heinrich Apfelmus
> Sent: 29 March 2012 13:30
> To: haskell-cafe at haskell.org
> Subject: Re: [Haskell-cafe] Google Summer of Code - Lock-free data structures
> 
> Florian Hartwig wrote:
>> Heinrich Apfelmus wrote:
>> 
>> So while the two are related, CAS is a machine primitive that works 
>> for a single operation and on a single word while STM is a software 
>> abstraction that isolates sequences of operations on multiple memory 
>> locations from each other.
>> 
>>> Is it possible to implement every data structure based on CAS in 
>>> terms of STM? What are the drawbacks? The other way round?
>> 
>> I think so. Atomically reading and writing a single memory location 
>> (which CAS does) is just a very simple transaction. But using a CAS 
>> instruction should be more efficient, since STM has to maintain a 
>> transaction log and commit transactions, which creates some overhead.
> 
> Ah, I see. In that case, it may be worthwhile to implement the CAS instruction in terms of STM as well and measure the performance difference this makes for the final data structure. After all, STM is a lot more compositional than CAS, so I'd like to know whether the loss of expressiveness is worth the gain in performance.
> 
> 
> Best regards,
> Heinrich Apfelmus
> 
> --
> http://apfelmus.nfshost.com
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
> 
> 
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe