Lock free stack and queue in C#

views:

2720

answers:

+6 Q:

Lock free stack and queue in C#

Does anyone know if there are any lock-free container libraries available for .NET ?

Preferably something that is proven to work and faster than the Synchronized wrappers we have in .NET.

I have found some articles on the .NET, but none of them specify any speed benchmarking, nor do they inspire much confidence in their reliability.

Thanks

+8 A:

Do you mean the container classes like they exist in the PFX framework (Parallels for .NET), ConcurrentQueue & ConcurrentStack

Pfx blog

Frederik Gheysels 2009-02-15 10:04:29

PFX looks good, but the documentation would seem to imply that ConcurrentQueue and ConcurrentStack use locks to provide thread-safety

Radu094 2009-02-15 12:32:25

I'd avoid PFX at all costs. We saw an 8-fold (that's right) degradation before realising it really isn't going to give you anything a good book will not teach you to do better..

rama-jka toti 2009-03-16 23:33:53

@Radu094: Joe Duffy's book "Concurrent Programming on Windows" states that the `ConcurrentQueue` is currently lock free.@rama-jka toti: The stuff in .NET 4 is much better than the CTP's were but I haven't tested the lock free data structures against alternatives. They are still much slower than their thread-unsafe counterparts, of course.

Jon Harrop 2010-06-15 19:13:01

+4 A:

Late, but better than never I thought I would add Julian Bucknalls articles to this list.

But he does not have performance numbers. In my testing of his structures the list scaled well compared to locking (very low kernel usage compared to ReaderWriterLock).

His blog has a series of articles on lock free structures in C#.

LOCK-FREE DATA STRUCTURES: THE STACK

Jason Short 2009-02-25 21:31:04

Kernel usage has nothing to do with CAS that he is utilising. CAS is a heavyweight hammer but in CLR you pretty much don't have many options, for now.

rama-jka toti 2009-03-16 23:30:30

CAS is light on kernel time compared to ReaderWriterLock. Compare the two in loops. One will use all user space time, the other all kernel time.

Jason Short 2009-03-23 16:30:25

You can't actually do a lock-free stack, unless you know, a priori, that your elements will not be deleted. C# I believe does garbage collection (which takes away some of the point of using lock-free!) so you get away with it. But in C, I believe that stack is broken, with the normal bug in pop.

Blank Xavier 2009-04-01 21:15:10

BTW, my comment about the stack being broken is utterly wrong.

Blank Xavier 2009-10-17 10:17:17

@Blank Xavier. Not utterly. If you were to do a naïve port to C or C++ it would be broken, and it would be hard to do a "proper" port because you've got to find some way to handle what the C# can depend on the GC handling. So yes, your comment was wrong, but not "utterly" wrong as it does address an important point about what runtime conditions the algorithm depends on.

Jon Hanna 2010-08-31 12:11:19

Any rightness was purely co-incidental :-)

Blank Xavier 2010-09-01 08:23:12

Lock free data structures are going to have issues until they modify the CLR with the mess caused by memory models, see the CLI spec.

Lock-free programming is sufficiently difficult that you shouldn't bother with it on a collection (container) level btw. True for any language out there..

rama-jka toti 2009-03-16 23:35:45

Can you elaborate on "modify the CLR"? What do you think is wrong?

Jon Harrop 2010-06-15 19:13:41

Without knowing anything about it, there is one library I stumbled across here.

Though probably not quite what you are looking for, at least there is an implementation and discussion on StackOverflow of a lock free queue structure in C# here. Going through the StackOverflow code review process might give some confidence about its safety, or provide information about how to go about building your lock-free containers yourself.

cdiggins 2009-10-09 03:10:30

http://www.liblfds.org

Written in C, but I'm guessing it's easily enough ported to C#?

Blank Xavier 2009-12-17 12:54:01

ansaurus

tags:

views:

answers:

Lock free stack and queue in C#

related questions