Simply library for CAS posted, including drop-in replacement for atomicModifyIORef

[Ryan Newton]

I just released one part of the haskell-lockfree package I've been working on.  No actual data structures, yet, but this package contains a drop-in replacement for atomicModifyIORef that gets better performance in my simple tests:

   http://hackage.haskell.org/package/IORefCAS

Because it's an easy change it might be worth trying that for hot IOrefs in your parallel app.  There are some notes about performance in the README.  It looks ~4X better on a simple microbenchmark where all threads on a four-core machine are hammering (incrementing) the same atomic counter.

   https://github.com/rrnewton/haskell-lockfree-queue/blob/master/CAS/README.md

Cheers,

   -Ryan

[Simon Marlow]

Good! I suspect it might not be quite so effective when the function to
compute is more expensive, though. That's why I didn't replace the
default implementation of atomicModifyIORef when I added casMutVar#. I
like the idea of falling back to atomicModifyIORef after a few tries though.

The docs ought to be more clear that equality here means pointer equality.

Cheers,
Simon

[Ryan Newton]

The docs ought to be more clear that equality here means pointer equality.

Done and uploaded!  The amended documentation now has a link to the reallyUnsafePtrEquality# doc, so maybe it deserves a comment as well:

   http://www.haskell.org/ghc/docs/latest/html/libraries/ghc-prim-0.2.0.0/GHC-Prim.html#g:19

Good!  I suspect it might not be quite so effective when the function to compute is more expensive, though.  

True.  And in any case a better back-off strategy for managing contention in the retry-loop is warranted.

By the way, I'll be interested to hear other people's experiences especially re: crashes.  The tests for IORefCAS pass (but I need to expand them).  Yet presently the my first attempt to use them to store non-scalars (in a queue implementation: MichaelScott.hs) I'm running into interesting errors:

    Test: internal error: PAP object entered!

(GHC version 7.2.1 for x86_64_unknown_linux)

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

    Aborted

Or:

    Test: internal error: evacuate: strange closure type -958224799

(GHC version 7.2.1 for x86_64_unknown_linux)

Please report this as a GHC bug:  http://www.haskell.org/ghc/reportabug

I wrote about this earlier in an email titled   "First casMutVar# program segfaulting...".  You should be able to reproduce those by buildinng/running Test.hs under:

   https://github.com/rrnewton/haskell-lockfree-queue/tree/master/MichaelScott

You can try this specific revision:

    git clone https://github.com/rrnewton/haskell-lockfree-queue

    cd haskell-lockfree-queue

    git co c5940373a2ad7f2d5f3c3fbac7ff009e83d8839b

Note that the above errors only happen in -O0.  In -O2 they go away.  Build the test with something like this:

    ghc -O2 -DNATIVE_CAS --make Test.hs -o Test.exe -rtsopts -fforce-recomp

I don't believe there's anything wrong with the queue implementation itself, because it works fine using Data.CAS.Internal.Fake.

If I can get a bit of a sanity check first I'll go ahead and file a bug.

  -Ryan

[Simon Marlow]

On 09/12/2011 06:47, Ryan Newton wrote:

> By the way, I'll be interested to hear other people's experiences
> especially re: crashes. The tests for IORefCAS pass (but I need to
> expand them). Yet presently the my first attempt to use them to store
> non-scalars (in a queue implementation: MichaelScott.hs) I'm running
> into interesting errors:
>
> Test: internal error: PAP object entered!
> (GHC version 7.2.1 for x86_64_unknown_linux)
> Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug
> Aborted
>
> Or:
> Test: internal error: evacuate: strange closure type -958224799
> (GHC version 7.2.1 for x86_64_unknown_linux)
> Please report this as a GHC bug: http://www.haskell.org/ghc/reportabug
>
> I wrote about this earlier in an email titled "First casMutVar# program
> segfaulting...". You should be able to reproduce those by
> buildinng/running Test.hs under:
>
> https://github.com/rrnewton/haskell-lockfree-queue/tree/master/MichaelScott
>
> You can try this specific revision:
> git clone https://github.com/rrnewton/haskell-lockfree-queue

> <https://github.com/rrnewton/haskell-lockfree-queue/tree/master/MichaelScott>

> cd haskell-lockfree-queue
> git co c5940373a2ad7f2d5f3c3fbac7ff009e83d8839b
>
> Note that the above errors only happen in -O0. In -O2 they go away.
> Build the test with something like this:
> ghc -O2 -DNATIVE_CAS --make Test.hs -o Test.exe -rtsopts -fforce-recomp
>
> I don't believe there's anything wrong with the queue implementation
> itself, because it works fine using Data.CAS.Internal.Fake.
>
> If I can get a bit of a sanity check first I'll go ahead and file a bug.

My fault - I forgot the GC write barrier in the casMutVar#
implementation. Just as well we found this in time for the 7.4.1
release, but unfortunately it means casMutVar# is borked in 7.2.x.

Cheers,
Simon

[Ryan Newton]

Thanks to Simon for the fix!

FYI, I took the simple expedient of #if'ing the implementation on
__GLASGOW_HASKELL__ > 702, and falling back to the "Fake" CAS
otherwise.

The resulting package (IORefCAS 0.2) should work with either 7.2.X or
7.4.X. It is presently exhibiting a problem on 7.0.X with
unexpectedly high rates of failure for CAS, so base >= 4.4 is required
for now.

I've tested it on Mac OS and Linux under 7.2 and the new 7.4 release
candidate. I'd love it if someone could give it a try under Window.

Cheers,
-Ryan

P.S. You *should* see the test suite run faster on 7.4 than 7.2 under
any number of threads -- i.e. using the *real* CAS. (It is a
purposefully non-scalable benchmark test, so expect it to take longer
with more threads.)