Re: Lockless Queue in C# slower than Locked Queue in C# - C# Discussion Boards

Re: Lockless Queue in C# slower than Locked Queue in C#

6-Jan-09 20:52

I've got a multi-threaded implementation of a lockless queue in C# using Interlocked.CompareExchange() and a multi-threaded implementation of a locked queue that uses lock() when it comes to enqueueing and dequeueing items. Essentially, what happens is that I use System.Threading.ThreadPool.QueueUserWorkItem() to queue 5-10 pieces of work (some function), which enqueues and dequeues from the lockless/locked queue several hundred thousand times.

A lot of articles have explained that using a lockless queue can improve performance when it comes to accessing a data structure, but I'm finding that the locked queue (which is simpler) ends up being faster. From a theoretical standpoint, I understand that synchronization primitives may be expensive, which is part of the reason why lockless should be faster. On the other hand, a lockless implementation with 5 operations working at the same time works by having one operation try and succeed, while for the other operations, they will have to redo their work again since the original data may have changed. That seems like a lot of waste to me and (again, from a theoretical standpoint) not faster than a locked implementation or even a single-threaded implementation.

Also, just to give some context, I'm only using a dumb queue. There's nothing special or intensive about what I'm doing, it's just creating a node to add to the queue, and taking a node out. In the locked multi-threaded implementation, only the node creation part is not inside the lock(). Everything else is (essentially) single-threaded since it has to wait for the lock before adding or removing a node.

Is anyone able to explain why I'm getting the performance results that I'm getting, and generally, what advantages there are to lockless aside from what I'm already expecting (faster multi-threaded queue access).

Luc Pattyn6-Jan-09 22:58

Luc Pattyn

6-Jan-09 22:58

Hi,

my best guess would be your test code is too simple: if all the test does is adding and removing queue entries, without any real calculations in between, then most CPU cycles are spent in the spin-loop inside Interlocked. IMO Interlocked is intended to and will work fine when contentions are rare, not when you create them all the time; under light contention conditions, I expect it to work more efficient than any other synchronization scheme.

To confirm this, you should try and come up with a test where extra CPU cycles are required to process the nodes; I would recommend adding something until you see the number of queue/dequeue operations go down by at least 80%, then for that computational load compare again the two schemes.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Love, happiness and fewer bugs for 2009!

Re: Lockless Queue in C# slower than Locked Queue in C#

Cyrilix6-Jan-09 23:28

Re: Lockless Queue in C# slower than Locked Queue in C#

6-Jan-09 23:28

I put another variable in my lockless queue to measure the retry count (the number of times it has to spin again because something changed), and in my test bench, it seems that an additional 50% of operations are done, so 100 enqueues ends up being something like 100 successful operations and 50 respins, approximately. I'm not sure how well my numbers compare with other implementations, but that does seem like a lot. It seems from the result that the lockless implementation works best with little contention, but I'm curious to know the theory behind it.

Luc Pattyn6-Jan-09 23:36

Luc Pattyn

6-Jan-09 23:36

Cyrilix wrote:
measure the retry count (the number of times it has to spin again because something changed)

Not sure I understand what you mean. Care to share some code here?

Cyrilix wrote:
I'm curious to know the theory behind it.

You could use reflector to investigate how it has been implemented in .NET although I expect you would also need to study the IL specification and still will be kept in the dark on how the native code looks (it is very likely they use special assembly instructions in the end).

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Love, happiness and fewer bugs for 2009!

Re: Lockless Queue in C# slower than Locked Queue in C#

Cyrilix7-Jan-09 1:18

Re: Lockless Queue in C# slower than Locked Queue in C#

7-Jan-09 1:18

My internet was down for a little so I couldn't post right away.

public void Enqueue(T data)
{
    LockFreeQueueNode<T> tempTail = null;
    LockFreeQueueNode<T> tempTailNext = null;
    LockFreeQueueNode<T> newNode = new LockFreeQueueNode<T>(data);
    newNode.Data = data;
    do
    {
        tempTail = tail;
        tempTailNext = tempTail.NextNode;
        if (tempTail == tail)
        {
            if (tempTailNext == null)
            {
                // If the tail node we are referring to is really the last
                // node in the queue (i.e. its next node is null), then
                // try to point its next node to our new node
                //
                if (Interlocked.CompareExchange(ref tempTail.NextNode, newNode, tempTailNext) == tempTailNext)
                    break;
            }
            else
            {
                // This condition occurs when we have failed to update
                // the tail's next node. And the next time we try to update
                // the next node, the next node is pointing to a new node
                // updated by other thread. But the other thread has not yet
                // re-pointed the tail to its new node.
                // So we try to re-point to the tail node to the next node of the
                // current tail
                //
                Interlocked.CompareExchange(ref tail, tempTailNext, tempTail);
            }
        }
        Interlocked.Increment(ref retryCount);
    } while (true);

    // If we were able to successfully change the next node of the current tail node
    // to point to our new node, then re-point the tail node also to our new node
    //
    Interlocked.CompareExchange(ref tail, newNode, tempTail);
    Interlocked.Increment(ref count);
}

I believe this code was actually taken somewhere from a Codeproject article (but I happened to find it online from a different source). The part that's in bold is the important line that I added to measure the retry count, basically everytime we are unable to break out of the while loop and need to retry the operation again.

Luc Pattyn7-Jan-09 1:58

Luc Pattyn

7-Jan-09 1:58

Hi,

OK, if retryCount goes up it tells me nothing much is happening outside your queue; you and I agree on
"lockless implementation works best with little contention" and to reduce contention a lot of things should be going on outside the queue.

Smile | :)

Luc Pattyn [Forum Guidelines] [My Articles]

Love, happiness and fewer bugs for 2009!

Re: Lockless Queue in C# slower than Locked Queue in C#

Daniel Grunwald7-Jan-09 2:37

Daniel Grunwald

7-Jan-09 2:37

Contention is always bad, but generally lockless code should be faster under contention than using locks.
With lockless code, when multiple threads use CompareExchange concurrently, at least one will succeed. So you're not wasting any time compared to the locked version.

Did you include the Interlocked.Increment(ref retryCount) when timing?
Like locks, interlocked operations aren't cheap, so you should avoid doing too many of them. Do you really need "count"?
Currently you're doing at least 3 interlocked operations per insertion - maybe a lock really is faster in this case.

And what hardware did you test it on? How many cores? Are you using hyper-threading?

You might be better off by slowing down the retry operation - on hyper-threaded processors, retrying too often slows down the other thread running on that processor. And in general, all threads constantly accessing memory isn't a good idea. Try adding a small Thread.SpinWait when retrying.

Re: Lockless Queue in C# slower than Locked Queue in C#

Cyrilix7-Jan-09 9:02

Re: Lockless Queue in C# slower than Locked Queue in C#

7-Jan-09 9:02

Yes, I include everything when timing. I also saw that count could be eliminated to no negative effect on the algorithm itself. I just wouldn't have anything to keep track of approximately what the count is, which is OK.

The hardware that I'm running it on is an Athlon64 X2 4400+ (2.2 GHz) with 2 cores and no hyper-threading. One thing I did was instead of slowing down the retry, I slowed down the enqueue/dequeue rate, by adding some other intensive math in between. This reduces the contention rate significantly. Before, I'd have about 50% extra operations... slowing it down to a reasonable level drops the amount of additional operations down to 4-6%. Under such a case, the lockless algorithm is equal or better to the lock algorithm.

One question though, what do you mean to imply when you say "With lockless code, when multiple threads us CompareExchange concurrently, at least one will succeed." Isn't it the same with locks? When multiple threads try to enter a critical section, at least one, and only one will succeed. The others will wait their turn.

ben.Kloosterman2-Feb-10 19:53

ben.Kloosterman

2-Feb-10 19:53

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

Re: Lockless Queue in C# slower than Locked Queue in C#

Cyrilix3-Feb-10 7:40

converting c header file in c#

3-Feb-10 7:40

I see what you mean. The second interlocked operation was removed (because it was more or less useless for a real data structure), but the implementation could be better. Thanks for the tip.

lawrenceinba6-Jan-09 20:31

6-Jan-09 20:31

dear friends

how to convert a header file in c language into its c# equalent

this is my code.... help me out guys just give me ideas

void nrerror(char error_text[]);

int *ivector(int nl, int nh);
double *dvector(int nl,int nh);
char *cvector(int nl, int nh);

int **imatrix(int nrl,int nrh,int ncl,int nch);
double **dmatrix(int nrl,int nrh,int ncl,int nch);

void print_iMatrix(FILE *fp, int **imatrix, int rows, int cols);
void print_dMatrix(FILE *fp, double **dmatrix, int rows, int cols);

void free_dvector(double*v,int nl,int nh);
void free_cvector(char * c,int nl,int nh);
void free_ivector(int * v,int nl,int nh);

void free_imatrix(int **m ,int nrl,int nrh,int ncl,int nch);
void free_dmatrix(double ** m,int nrl,int nrh,int ncl,int nch);

N a v a n e e t h6-Jan-09 20:48

N a v a n e e t h

6-Jan-09 20:48

lawrenceinba wrote:
int *ivector(int nl, int nh);

if you don't want to use unsafe code, just use int. int ivector(int nl, int nh); will be the equivalent. But in C#, this function will return the value not the pointer.

lawrenceinba wrote:
int **imatrix(int nrl,int nrh,int ncl,int nch);

Same like the above. You can use ref or out with the parameters and assign value to there. Let your method return void. It is same pattern like int.TryParse(string,out int)

In C#, all primitive types are passed by value. To make it pass by reference, you have to use ref or out with it. So all pointer variables (int*,double*) should be marked with ref or out to pass as reference.

Navaneeth

How to use google | Ask smart questions

Guffa6-Jan-09 20:52

Guffa

6-Jan-09 20:52

C# doesn't use header files.

What is it that you are trying to do? Convert a C program to C# without any knowledge of C#?

Despite everything, the person most likely to be fooling you next is yourself.

lawrenceinba6-Jan-09 20:59

6-Jan-09 20:59

ya i know but.... im asking to create a dll file.. for library

ya im a beginner in c#

going on studing stuff abt c#.... s i have to convert a c++ code to c#

N a v a n e e t h6-Jan-09 21:14

N a v a n e e t h

6-Jan-09 21:14

lawrenceinba wrote:
going on studing stuff abt c#.... s i have to convert a c++ code to c#

I'd suggest to try something simple as you are a beginner.

Navaneeth

How to use google | Ask smart questions

lawrenceinba6-Jan-09 21:19

6-Jan-09 21:19

ya ill go step by step only.. but i have to complete it in three months... so hopefully ill finish it if members here clears my doubts

Dragonfly_Lee6-Jan-09 22:24

Dragonfly_Lee

6-Jan-09 22:24

It is quite a chanllenge job for a beginner. If you really want to do this, I am afraid you need a third-party tool, however, I could not remember the name very well. Maybe you can turn to managed C++.

Tan Li

I Love KongFu~

lawrenceinba6-Jan-09 22:35

6-Jan-09 22:35

dear friend

im a beginner only in c#

got enough knowledge in c & c++

so i'll do it

i need help only in c#

Dragonfly_Lee6-Jan-09 22:46

Dragonfly_Lee

6-Jan-09 22:46

Well, I did not mean unmanaged C++, which is different form C++ in .net world. Just for you information.

Tan Li

I Love KongFu~