A lock-free concurrent queue alone would be worth a summer project IMO. G On Mon, Mar 19, 2012 at 3:25 AM, Florian Hartwig < florian.j.hartwig@gmail.com> wrote:

...

On Mar 18, 2012 6:39 PM, "Florian Hartwig" wrote:

...

GSoC stretches over 13 weeks. I would estimate that implementing a data structure, writing tests, benchmarks, documentation etc. should not take more than 3 weeks (it is supposed to be full-time work, after all), which means that I could implement 4 of them in the time available and still have some slack.

Don't underestimate the time required for performance tuning, and be careful to leave yourself learning time, unless you have already extensively used ThreadScope, read GHC Core, and worked with low-level strictness, unpacking, possibly even rewrite rules. I suspect that the measurable performance benefit from lockless data structures might be tricky to tease out of the noise created by unintentional strictness or unboxing issues. And we'd be much happier with one or two really production quality implementations

On 19 March 2012 00:59, Chris Smith wrote: than

...

even six or seven at a student project level.

-- Chris Smith

Thank you, Hofstadter's law definitely rears its head in many of my projects. I do have some experience with ThreadScope and strictness issues, but you I agree that I'm probably underestimating the time I need to learn. I also agree that my focus would be on quality rather than quantity. I quite like the modularity of this project, because it minimises the chance of having a lot of half-finished but useless code at the end of summer.

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

-- Gregory Collins

The MichaelScott lockefree queues in that repository pass tests and should work. Additional stress testing and feedback would be appreciated. There are some other queues in the literature that might be worth implementing but I think other data structures are higher priority. As Adam Foltzer mentioned in the trac ticket a really good structure would be the concurrent bags from this paper: http://www.cse.chalmers.se/~tsigas/papers/Lock%20Free%20Bag%20SPAA11.pdf We separately did a C implementation of those and they performed really well in our bake-off of producer consumer data structures (vs. TBB queues, and many other implementations). By the way, we can share the code for this little bake-off as a performance baseline for the Haskell versions. I'm less familiar with the literature on concurrent hash tables. TBB's have been a little bit underwhelming in performance. But it's definitely an important structure. Ditto for priority queues. In any case, I welcome your interest in the topic, Florian! Cheers, -Ryan On Mon, Mar 19, 2012 at 7:33 AM, Florian Hartwig < florian.j.hartwig@gmail.com> wrote:

On 19 March 2012 09:56, Gregory Collins wrote:

...

A lock-free concurrent queue alone would be worth a summer project IMO.

G

Ryan Newton is already doing that (https://github.com/rrnewton/haskell-lockfree-queue).

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Tue, Mar 20, 2012 at 2:53 AM, Florian Hartwig < florian.j.hartwig@gmail.com> wrote:

On 19 March 2012 11:46, Ryan Newton wrote:

...

As Adam Foltzer mentioned in the trac ticket a really good structure would be the concurrent bags from this paper:

http://www.cse.chalmers.se/~tsigas/papers/Lock%20Free%20Bag%20SPAA11.pdf

Looks like they rely on thread-local storage, which would have to be worked around in Haskell somehow.

I've just read the paper and they look both useful and interesting to implement. Adam mentioned that GHC would need to be extended first, and I can't really judge how much work that would be. Can anyone chime in on how feasible that is?

GHC already has a CAS primitive on MutVar#, it just needs to be extended to MutableArray# and MutableByteArray# (at all of the bit-widths the CAS instruction would support, e.g. see readWordXxArray# in http://www.haskell.org/ghc/docs/latest/html/libraries/ghc-prim-0.2.0.0/GHC-P...). The implementation should be almost identical to casMutVar#. In particular I think you need: casMutArray# :: MutableArray# s a -> Int# -> a -> a -> State# s -> (# State# s, Int#, a #) casWord16MutByteArray :: MutableByteArray# s -> Int# -> Word# -> Word# -> State# s -> (# State# s, Int#, Word#) and equivalents for Word32. Word64, Int16, Int32, Int64. G -- Gregory Collins

GHC already has a CAS primitive on MutVar#, it just needs to be extended to MutableArray# and MutableByteArray# (at all of the bit-widths the CAS instruction would support, e.g. see readWordXxArray# in http://www.haskell.org/ghc/docs/latest/html/libraries/ghc-prim-0.2.0.0/GHC-P...). The implementation should be almost identical to casMutVar#. In particular I think you need: casMutArray# :: MutableArray# s a -> Int# -> a -> a -> State# s -> (# State# s, Int#, a #) casWord16MutByteArray :: MutableByteArray# s -> Int# -> Word# -> Word# -> State# s -> (# State# s, Int#, Word#)

FYI, I started working on adding these. I'm hoping to have it working in GHC HEAD for any students who need to use it. To my knowledge the only two patches required to implement casMutVar# were these two (plus the preexisting cas() definition in SMP.h): https://github.com/ghc/ghc/commit/521b792553bacbdb0eec138b150ab0626ea6f36b https://github.com/ghc/ghc/commit/606f6e1cfcb2e79abaadcc5ed643817d2a4585d8 The latter is a bugfix to the former. Florian, your proposal looks good to me ( http://www.google-melange.com/gsoc/proposal/review/google/gsoc2012/florianha...). You touched on the major things we need to know. I just read in your proposal that you started looking into the casMutArray# issue as well. How far have you gotten with that? Do you want to work on this together a bit? I've got an implementation of a casArray# primop that passes a basic test, but I'm not sure if the GC write barrier is correct: https://github.com/rrnewton/ghc/commit/18ed460be111b47a759486677960093d71eef... The ByteArray versions will be more annoying, requiring more variations, but they are also less essential, because the user can always use ForeignPtr and bits-atomic in this case, and I believe for our concurrent data structures we want to store arbitrary pointers (hence casArray#). Cheers, -Ryan

On 29 March 2012 at 12:01 PM, Heinrich Apfelmus <apfelmus at quantentunnel.de> wrote:

Since I don't know much about concurrency, I have a simple question: what is the difference between atomic compare-and-swap and software transactional memory? Both are lock-free?

Well, terminology-wise it would probably be more accurate to say that you can implement lock-free algorithms using both (i.e. it's not really CAS and STM that are lock-free, but the algorithms implemented using them). But maybe this is a pedantic distinction. As to the difference between the two: CAS is just a machine instruction that takes an old "expected" value, a new value and an address and updates the memory pointed to by the address iff it contains the old/expected value. All this happens atomically, so you avoid the potential conflicts between threads concurrently reading from and writing to the same address. STM is much higher-level. It's an abstraction that allows the programmer to treat any sequence of reads and writes as a single atomic operation. This is, as the name says, implemented in software. 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. I hope this makes some sense. Cheers, Florian

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.

There's one annoying hitch with doing apples-to-apples comparisons here. The problem is that CAS falls short of being a hardware-accelerated version of a simple transaction (read TVar, (==) against expected value, conditionally update TVar), because CAS is based on pointer equality rather than true equality. (eq? rather than equal? for any Schemers out there.) For this reason our "Fake" version of CAS -- for older GHCs and for performance comparison -- has to use reallyUnsafePointerEquality#: http://hackage.haskell.org/packages/archive/IORefCAS/0.2/doc/html/Data-CAS-I... But we do provide a "CASable" type class in that package which is precisely for comparing the performance of: - Hardware CAS - Fake CAS -- atomicModifyIORef + ptrEquality - Foreign CAS -- gcc intrinsic + function call Cheers, -Ryan

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.pd...

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@haskell.org [mailto:haskell-cafe-bounces@haskell.org] On Behalf Of Heinrich Apfelmus Sent: 29 March 2012 13:30 To: haskell-cafe@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

+1 -- the reagents model is interesting and it would be good to see a Haskell implementation. On Thu, Apr 5, 2012 at 3:05 PM, Ben Gamari wrote:

Ben writes:

...

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.

Keep use in the loop if you do. I have a very nice application that has been needing a nicer approach to concurrency than IORefs but really can't afford STM.

Cheers,

- Ben

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

heinrich and all -- thanks for the illuminating comments, as usual. i've had a little bit of time to play around with this and here's what i've concluded (hopefully i'm not mistaken.) 1 - while composeability makes STM a great silver bullet, there are other composable lower level paradigms. aaron has identified a few fundamental algorithms that appear to be composable, and used a lot in concurrent algorithms / data structures : k-CAS, exponential backoff, helping and elimination. 2 - k-CAS (and more generally k-RMW) is composable. i'm not exactly sure if i'd call k-CAS monadic but it is at least applicative (i'm not sure what the exact definition of k-CAS is. a bunch of 1-CASs done atomically seems applicative; allowing them to interact seems monadic. certainly k-RMW is monadic.) while it is possible to implement STM on top of k-CAS and vice versa, k-CAS can get you closer to the metal, and if you can special case 1-CAS to hardware you will win on a lot of benchmarks. a lot of concurrent algorithms only need 1-CAS. 3 - backoff, elimination and helping help scalability a lot, so you want support for them. elimination and helping require communication between transactions, whereas STM is all about isolation, so reagents are fundamentally different in this regard. reagents as implemented in the paper are not entirely monadic (by accident, i think the author intended them to be.) as far as i can see he uses an applicative form of k-CAS, and the reagents on top of it are applicative : his "computed" combinator (monadic bind) does not allow post-composition (it has no continuation.) there is no reason why it could not be built on top of a monadic k-RMW and be fully monadic. however he is able to recognize and special-case 1-CAS, which gives great performance of course. however, this does bring up a general question : why are applicative functors (often) faster than monads? malcolm wallace mentioned this is true for polyparse, and heinrich mentioned this is true more generally. is there a yoga by which one can write monadic functors which have a specialized, faster applicative implementation? right now i'm reading up on k-CAS / k-RMW implementations, and i think i'm going to start writing that monad before moving on to elimination / helping. i'm finding a two things difficult : - it is hard to represent a unified transaction log because of heterogeneous types, and - allowing a fully monadic interface makes it hard for me to special case 1-CAS (or applicative k-CAS.) there are workarounds for the first issue (separate logs for each reference, or a global clock as in Transactional Locking II.) for the second, right now i'm wondering if i'm going to have to write a compiler for a little DSL; i'd like to be able to exploit applicative performance gains generally, and special case 1-CAS. best, ben On Apr 6, 2012, at 5:38 AM, Heinrich Apfelmus wrote:

Ben wrote:

...

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.

That looks great! While I didn't take the time to understand the concurrency model in detail, the overall idea is to use arrows that can be run atomically

runAtomically :: Reagent a b -> (a -> IO b)

This is very similar to STM: combining computations within the monad/arrow is atomic while combining computations "outside" the monad/arrow can interleave them.

runAtomically (f . g) -- atomic runAtomically f . runAtomically g -- interleaving

Actually, it turns out that the Reagent arrow is also a monad, but the author seems to claim that the "static" arrow style enables certain optimizations. I haven't checked his model in detail to see whether this is really the case and how exactly it differs from STM, but we know that situations like this happen for parser combinators. Maybe it's enough to recast reagents as an applicative functor?

To summarize: the way I understand it is that it's apparently possible to improve the STM monad by turning it into an arrow. (I refer to "STM" in a very liberal sense here: whether memory is transactional or not is unimportant, the only thing that matters is a computation that composes atomically.)

Best regards, Heinrich Apfelmus

-- http://apfelmus.nfshost.com

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

i'm not sure what your email is pointing at. if it is unclear, i understand the difference between applicative and monadic. i suppose the easy answer to why applicative can be faster than monadic is that you can give a more specialized instance declaration. i was just wondering if there was a way to make a monad recognize when it is being used applicatively, but that is probably hard in general. b On Apr 20, 2012, at 2:54 PM, KC wrote:

Think of the differences (and similarities) of Applicative Functors and Monads and the extra context that monads carry around.

-- -- Regards, KC

the sequencing matters for applicative functors. from McBride and Patterson [1]: "The idea is that 'pure' embeds pure computations into the pure fragment of an effectful world -- the resulting computations may thus be shunted around freely, as long as the order of the genuinely effectful computations is preserved." it is interesting to note that sequencing only matters a little for k-CAS : you just have to read before you write, but you can do the reads and writes in any order (as long as it is ultimately atomic.) b [1] McBride C, Patterson R. "Applicative programming with effects" Journal of Functional Programming 18:1 (2008), pages 1-13. On Apr 20, 2012, at 4:41 PM, KC wrote:

Sorry, I thought you or someone was asking why are Applicative Functors faster in general than Monads.

Functional programming is structured function calling to achieve a result where the functions can be evaluated in an unspecified order; I thought Applicative Functors had the same unspecified evaluation order; whereas, Monads could carry some sequencing of computations which has the extra overhead of continuation passing.

Do I have that correct?

On Fri, Apr 20, 2012 at 4:05 PM, Ben wrote: i'm not sure what your email is pointing at. if it is unclear, i understand the difference between applicative and monadic. i suppose the easy answer to why applicative can be faster than monadic is that you can give a more specialized instance declaration. i was just wondering if there was a way to make a monad recognize when it is being used applicatively, but that is probably hard in general.

b

On Apr 20, 2012, at 2:54 PM, KC wrote:

...

Think of the differences (and similarities) of Applicative Functors and Monads and the extra context that monads carry around.

-- -- Regards, KC

-- -- Regards, KC

On Thu, Mar 29, 2012 at 6:57 AM, Ryan Newton wrote:

The ByteArray versions will be more annoying, requiring more variations, but they are also less essential, because the user can always use ForeignPtr and bits-atomic in this case, and I believe for our concurrent data structures we want to store arbitrary pointers (hence casArray#).

This is true, although using bits-atomic does a function call (i.e the calls are not inlined), which would be pretty bad for performance. G -- Gregory Collins