Testing a Non-blocking Queue

views:

213

answers:

+2 Q:

Testing a Non-blocking Queue

I've ported the non-blocking queue psuedocode here to C#. The code below is meant as a near verbatim copy of the paper.

What approach would you take to test the implementation?

Note: I'm running in VS2010 so I don't have CHESS support yet.

Edit:

I've removed the code in question so some unsuspecting developer doesn't use it -- it required quite a few changes to get it bug free... and I still wasn't 100% confident that it was bug free. With brute force testing I could not get it to perform better than a lock based solution.

Also, since I'm targeting 3.5 I thought I was SOL with the 4.0 concurrent queue. The 3.5 RX framework includes a ConcurrentQueue so this was indeed just a fun little programming exercise and nothing more.

+1 A:

If you're using VS 2010 and .NET 4, you can use ConcurrentQueue<T>.

Reed Copsey 2010-04-19 19:03:30

the question was how to test their implementation.

Andrey 2010-04-19 19:04:42

Yes, but if the port is avoidable, and you can get a good, tested implementation for free, it'll avoid the reason for the question entirely...

Reed Copsey 2010-04-19 19:07:52

Unfortunately I'm targeting .NET 3.5. I actually took a look at their .NET 4.0 implementation in reflector and the queue in question takes a completely different approach; it's the algorithm Joe Duffy recommended in his Parallel Data Structures article...

jsw 2010-04-19 19:25:29

@jsw: This, btw, is also included for .NET 3.5 in the Rx Framework, and available here: http://msdn.microsoft.com/en-us/devlabs/ee794896.aspx

Reed Copsey 2010-04-19 20:10:51

+1 A:

when i tried to create non-blocking queue i tested queue this way. i created 10 threads and concurrently called Enqueue 1000 times. At the end i checked size of queue, it was != 10 000. Or sometimes it threw exceptions. Then i tried concurrent deques. Same result. This clearly means that queue is not thread safe.

Andrey 2010-04-19 19:04:08

ansaurus

tags:

views:

answers:

Testing a Non-blocking Queue

related questions