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

41 views
Skip to first unread message

Ryan Newton

unread,
Dec 7, 2011, 3:58:11 PM12/7/11
to parallel-haskell
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.


Cheers,
   -Ryan


Simon Marlow

unread,
Dec 8, 2011, 3:25:02 AM12/8/11
to rrne...@gmail.com, parallel-haskell

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

unread,
Dec 9, 2011, 1:47:52 AM12/9/11
to Simon Marlow, parallel-haskell

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:



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:


You can try this specific revision:
    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

unread,
Dec 9, 2011, 4:13:01 AM12/9/11
to rrne...@gmail.com, parallel-haskell
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

unread,
Dec 23, 2011, 10:48:37 AM12/23/11
to Simon Marlow, parallel-haskell
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.)

Reply all
Reply to author
Forward
0 new messages