Question: busy waiting?

[pfeatherstone]

This repo is great. But, what happens if a thread is waiting to enqueue/dequeue for more than say 100ms? In a busy-waiting scenario, isn't that hogging a lot of CPU resources, which could be otherwise spent by another thread? In which case, one might argue that a mutex-cvar based queue which puts threads to sleep might be more appropriate. Is there a way to hybridize this? So, would there be a way for a thread to busy-wait for say any time less than 1 micro second, then go to sleep for any time after that?

[max0x7ba]

This repo is great.

Thank you.

But, what happens if a thread is waiting to enqueue/dequeue for more than say 100ms?

The thread keeps busy-waiting.

In a busy-waiting scenario, isn't that hogging a lot of CPU resources, which could be otherwise spent by another thread?

Correct.

In which case, one might argue that a mutex-cvar based queue which puts threads to sleep might be more appropriate.

Read the README for rationale.

Is there a way to hybridize this? So, would there be a way for a thread to busy-wait for say any time less than 1 micro second, then go to sleep for any time after that?

This problem is called adaptive mutex. One implementation is tbb::spin_mutex , included in the benchmarks.

[pfeatherstone]

Ok thank you

[max0x7ba]

This problem is called adaptive mutex. One implementation is tbb::spin_mutex , included in the benchmarks.

tbb::spin_mutex isn't an adaptive mutex, my mistake.

Linux PTHREAD_MUTEX_ADAPTIVE_NP is an adaptive mutex, used by atomic_queue::AdaptiveMutex. It is commented out in the source code because it performed poorly in these particular benchmarks.

[pfeatherstone]

I'll give it a go.

The thing is, some of these lock-free queues really do suffer when one thread is just sitting there waiting for some data to arrive, coming from a socket or something, eating up all CPU resources. I know there is the usual spiel about choosing the right queue for the right problem. I was kind of hoping there would be a queue to end them all that performed well in all circumstances. But i don't think that's the case. A proper adaptive, context-aware, queue would be ideal. I was reading about modern branch prediction and it is crazy the level of optimization that is happening behind the scenes using very small information. So I was hoping that a similar kind of predictive queue, that predicted based on previous stats whether to busy-wait or sleep-wait (whatever the term is) would be possible. I don't know. I could be naive. But if my machine can predict my if-statements with 99% accuracy using a handful of bits, then why can't a queue predict whether to spin or to sleep.

[pfeatherstone]

Looking at PTHREAD_MUTEX_ADAPTIVE_NP, i wonder if you can achieve the same thing with std::mutex by simply calling std::mutex::try_lock() say 100 times, then call std::mutex::lock() if it hasn't already locked.

[pfeatherstone]

This is a bit of a tangent, but this thread is VERY interesting

[max0x7ba]

I understand that you want a solution with the benefits of non-blocking queue and blocking mutex, and with the shortfalls of none. That's a genuine desire. I don't have such a solution for you.

[pfeatherstone]

Yes that's absolutely fine. I wasn't being bossy or demanding. Simply interested in people's thoughts. Thank you very much for the discussion.