Should a lockfree queue use a condition variable?

Question

Suppose I have a lockfree queue in a multithreaded setting. I already provide a try_dequeue() method which allows for an optional failure (communicated via the return type) if the queue is empty.

I've found it convenient to have an always-succeeding T dequeue() method which will not return while the queue is empty. As a consumer, I don't really care when I get my product, I just want to know as soon as one's available.

My implementation of dequeue() is pretty simple:

while (true) {
 if (try_dequeue succeeded) return result;
 std::unique_lock<std::mutex> lk(mtx_);
 cond_.wait(lk, [this]{ return !empty(); });
}

Where cond_ is signalled by enqueuers and mtx_ guards cond_.

The excess serialization and between-dequeuer contention caused by lk seems to slow things down. empty() certainly doesn't need anything to be locked.

In any case, does cond_ seem out of place here? The only reason I'm hesitant to remove it is the case where there's a dequeuer (or multiple dequeuers) that are waiting for a new item to come in and are spinning idly on the CPU with no indication for the enqueuing thread to get priority.

It would seem that perhaps this_thread::yield() is more appropriate here, but the standard only guarantees that the method is a hint, so there is a possibility of starving here.

It appears that boost::lockfree::queue does not provide a dequeue-like method at all. Hopefully the nuclear option is avoidable.

As user rwong points out, we may consider a solution to this problem as a "hybrid" or "semi-blocking" approach because it would be desirable to have dequeuers block on empty queues, yet it would also be nice for enqueuers not to have to make a full context switch to the kernel at the same time.

Note: Yes, technically the inclusion of mtx_ in the queue removes the lockfree attribute, but I think this is an accurate characterization anyway since dequeue() is the only method that uses mtx_ (enqueuers signal without locking).

• Robert Harvey: "It appears that boost::lockfree::queue does not provide a dequeue-like method at all" - That wouldn't make much sense, would it? Isn't that what consume_one() does?
• ratchet freak: @RobertHarvey check the description, non-blocking and "returns true, if one element was consumed"
• Robert Harvey: @ratchetfreak: It also says "if pop operation is successful, object will be copied to ret"
• VF1: @RobertHarvey I don't think consume_one() is like dequeue() - the latter is never supposed to fail, whereas the former can return false.
• Robert Harvey: Then I think you need to be clear that you require the method signature to be exactly the same. It would be easy enough to wrap consume_one() to get the dequeue() method you want, I think.

Answer 1

You can use try_lock for signaling the cond_ when enqueueing. This will have a race condition that can be circumvented by making the wait timed.

The idea is that if the try_lock fails then either another enqueuer is also trying to wake the dequeuers so we might as well let him do the work or the dequeuer is trying to wait and he may or may not have check the condition yet. If he hasn't then fine he'll see the queue isn't empty and release and try again, if he has checked then he'll check again after the timeout expires.

• VF1: The problem isn't that the condition variable approach is slow when the queue is near-empty, the slowdown (compared to this_thread::yield mentioned in my question) occurs when dequeuers are contending over a queue that's filled with items already.
• ratchet freak: @VF1 if there are items in the queue then they shouldn't even be touching the lock (or thread::yield).
• VF1: Yeah, I realized that just after I couldn't edit my comment; good point. I'm still not seeing what the try_lock does that cond_.signal() doesn't, though.
• ratchet freak: @VF1 it lets the enqueuer skip signaling if the lock is already held at the danger of a missed signal for a dequeuer.