Its not so much the fact that its lockless but the implementation is slow.. Each enqueue and dequeue here require adding a new class ( which is the node) , a new is VERY expensive and uses a lock around the GC allocator. So you have removed the lock around enqueue and dequeue but hit the worse GC lock. A per formant lock less queue would pre-create and re-use its nodes OR manage its own memory with structs and unsafe. An array based queue would not require new nodes and only needed to new when growing the array and hence would offer much better base performance but is harder to make lock less. secondly you are making it worse with a second interlock. Interlocks are not cheap they cause the pipeline to stall and lock they are cheaper than a full lock , note however most full locks just use an interlock on a variable and block if it is in use , since an enqueue without a new is FAST the lock will not really be active long and the other lock implementations ends up just being an interlock compare. Now adding to a queue is probably a very cheap operation maybe 10 cycles so probably no contention with only 5 threads if they do normal work. ( In a bench mark it generate contention but this is not a real scenario a program would spend very little time doing the enqueue and dequeue.

Ben