[Haskell-cafe] why are applicative functors (often) faster than monads? (WAS Google Summer of Code - Lock-free data structures)

[Ben]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe