13

I was reading about the new concurrent collection classes in .NET 4 on James Michael Hare's blog, and the page talking about ConcurrentQueue<T> says:

It’s still recommended, however, that for empty checks you call IsEmpty instead of comparing Count to zero.

I'm curious - if there is a reason to use IsEmpty instead of comparing Count to 0, why does the class not internally check IsEmpty and return 0 before doing any of the expensive work to count?

E.g.:

public int Count
{
    get
    {
        // Check IsEmpty so we can bail out quicker
        if (this.IsEmpty)
            return 0;

        // Rest of "expensive" counting code
    }
}

It seems strange to suggest this if it could be "fixed" so easily with no side-effects?

4 Answers 4

16

ConcurrentQueue<T> is lock-free and uses spin waits to achieve high-performance concurrent access. The implementation simply requires that more work be done in order to return the exact count than to check if there are no items, which is why IsEmpty is recommended.

Intuitively, you can think of Count having to wait for a timeslice when no other clients are updating the queue, in order to take a snapshot and then count the items in that snapshot. IsEmpty simply has to check if there is at least one item or not. Concurrent Enqueue and TryDequeue operations are changing the count, so Count has to retry; unless the queue is transitioning between the empty and non-empty states, the return value of IsEmpty isn't changed by concurrent operations, so it doesn't have to wait.

I wrote a simple multi-threaded test app which showed that Count was ~20% slower (with both constant contention and no contention); however, both properties can be called millions of times per second so any performance difference is likely to be completely negligible in practice.

6
  • Thanks for the info, though this didn't really answer the question (I've updated the title to match the question I put in the body): Why doesn't (can't?) the implementation of Count have "if (this.IsEmpty) return 0;" to avoid this performance "gotcha"? Commented Feb 27, 2011 at 14:44
  • 3
    Maybe because slowing every call of Count by waiting potentially twice to speed up an edge case isn't wise. Commented Feb 27, 2011 at 14:50
  • @VirtualBlackFox Ofcourse, this makes total sense. If you post it in an answer I'll mark it, rather than the answer being hidden in a comment :-) Commented Feb 27, 2011 at 15:01
  • I'll leave my answer to the original question. Commented Feb 27, 2011 at 15:45
  • Was your test done with a queue that contained items, or an empty queue? The advice to use IsEmpty rather than Count when practical would make sense even if Count performed just as fast as IsEmpty in those cases where the queue was, in fact, empty.
    – supercat
    Commented Jun 7, 2012 at 20:26
9

Let me show you an overstating example:

public bool IsEmpty
{
   get { /* always costs 10s here */  }
}

public int Count
{
   get { /* always costs 15s here, no matter Count is 0 or 1 or 2... */  }
}

If they implement the Count property like this:

public int Count
{
   get
   {
       if (IsEmpty) return 0;
       //original implementation here
   }
}

Now when the final Count is 0, it costs 10s(5s less than before!great!), but for those Count is 1/2/more, it costs more than before, because checking IsEmpty costs time! So the optimization is not a good idea, because IsEmpty takes time. It will be good if IsEmpty is reading from a field directly.

EDIT I checked the implementaion of both IsEmpty and Count via reflector, both are expensive. Obviously checking IsEmpty for 0 count only will reduce the average performance speed.

1

Understanding how concurrent structures work is very important.

if (isEmpty()) ...//do whatever

if you have concurrent structure the check is close to no-op since everything can change between isEmpty and any subsequent operation.

Count iterates through the nodes (have not used c# for almost 6 years, but the java analog does the same) to calculate, so it is an expensive call. Straight answer: Checking isEmpty before Count will incur additional memory fence and effectively achieve nothing. Edit: if unclear. Count when the queue is empty costs exactly as isEmpty, however it costs a lot when the queue is not!

Count similar to isEmpty for concurrent structures has little to no meaning since the result of the call may not be useful and greatly changed.

4
  • I think you totally missed the point of the question. Writing code that uses IsEmpty and Count==0 has zero effect on concurrency, since all locking in these classes is internal. My question was about why the Count property couldn't quickly check IsEmpty internally rather than recommend to use IsEmpty. Commented Feb 27, 2011 at 15:23
  • 1
    @DanTup, it does have effect, and you have the answer, it costs a memory barrier (far from free). I didn't miss the point. Reread the answer.
    – bestsss
    Commented Feb 27, 2011 at 15:26
  • @DanTup, added extra clarification, namely: if the queue isEmpty, count is not expensive (exactly as isEmpty), however it is otherwise
    – bestsss
    Commented Feb 27, 2011 at 15:30
  • 1
    Sorry, misunderstood. I thought you meant when IsEmpty=true. When it's not, then you're right, Count would become more expensive. Commented Feb 27, 2011 at 15:33
0

IsEmpty provides some thread concurrency that if you obtain the Count value and compare it, its on your thread, but the queue could be changed.

MSDN says:

For determining whether the collection contains any items, use of this property is recommended rather than retrieving the number of items from the Count property and comparing it to 0. However, as this collection is intended to be accessed concurrently, it may be the case that another thread will modify the collection after IsEmpty returns, thus invalidating the result.

7
  • I don't get what you mean by "if you obtain the Count value and compare it, its on your thread". How is that different from calling IsEmpty, that's also on that thread. Commented Feb 27, 2011 at 12:25
  • This is exactly the same with Count. If I read Count and it returns 0, it could also be modified before my next operation. This doesn't explain why Count internally could not check IsEmpty and return 0 to avoid this "gotcha". Commented Feb 27, 2011 at 12:25
  • Or the other way around, that calling IsEmpty on the queue class (which is documented that Count is O(1)) could just use a Count==0 check. Commented Feb 27, 2011 at 12:54
  • @nos I think so too, but since it would've been easier to "optimise" this way than write about the gotcha, I wonder if there's actually a reason. Commented Feb 27, 2011 at 14:49
  • @DanTup - Danny Tuppeny According to that page, Count is O(1), there is no mentioning of .Count == 0 being "slower" than IsEmpty. He just recommends that you use IsEmpty. Using IsEmpty will clearly state that you're checking for emptyness, and if they ever change the implementation of .Count in the future, your code calling IsEmpty will presumably still be optimized. And if your code is agnostic to the type of container, IsEmpty might be more efficient for containers where .Count is slower.
    – nos
    Commented Feb 27, 2011 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.