3

I am reading the docs for spsc_queue and even after reading a bit elsewhere I am not completely convinced about the meaning of "wait-free".

What exactly do they mean here

bool push(T const & t);

Pushes object t to the ringbuffer.

Note: Thread-safe and wait-free

I mean there must be some overhead for synchronisation. Is 

some_spscqueue.push(x);

guaranteed to take a constant amount of time? How does it compare to a non-thread safe queue?

PS: dont worry, I am going to measure, but due to my naive ignorance I just cant imagine a synchronisation mechanism that does not involve some kind of waiting and I am quite puzzled what "wait-free" is supposed to tell me.

Peter Cordes
  • 328,167
  • 45
  • 605
  • 847
463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185
  • 1
    Have you tried wikipedia? https://en.wikipedia.org/wiki/Non-blocking_algorithm –  Aug 10 '17 at 15:42
  • @NeilButterworth yes I did, but for example "An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes." I dont completely understand how this is different from using locks plus being sure that there is no chance of deadlock. – 463035818_is_not_an_ai Aug 10 '17 at 15:56
  • In principle, you're still missing starvation from that - wait-free algorithms can't be starved, but mutexes easily can be (ie, they generally don't exhibit "fair" scheduling behaviour under high contention). In practice, the cost of a mutex is higher (due to parking and the waiter queue). There are some situations where you _want_ parking, and it's a benefit, but pushing to a queue is probably not one of them. – Useless Aug 10 '17 at 16:00

2 Answers2

2

A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes.

(from the abstract of the Herlihy article).

See also Wikipedia, and all the other resources you immediately find by typing "wait free" into a search engine.

So wait-free doesn't mean no delay, it means you never enter a blocking wait-state, and can't be indefinitely blocked and/or starved.

In other words, wait has the specific technical meaning that your thread is either parked (and does not execute any instructions until something wakes it up), or is in a loop waiting for some external condition to be satisfied (eg. a spinlock). If it's never woken up, or if it is woken up but always finds it can't proceed and has to wait again, or if the loop never exits, then your thread is being starved and cannot make progress.

Every operation has some latency, and wait-free doesn't say anything about what that is.

How does it compare to a non-thread safe queue?

It'll almost certainly be more expensive than a wholly-unsynchronized container, because you're still doing extra work (assuming you really do only access the container from a single thread).

Useless
  • 64,155
  • 6
  • 88
  • 132
  • so the main difference compared to using mutexes is that there is no chance to run into a deadlock, but in the worst case a lock-free push may take as long as one using locks? – 463035818_is_not_an_ai Aug 10 '17 at 15:49
  • It will almost certainly be faster than a mutex. It's likely to be about as long as the initial spinlock part of an adaptive mutex, but without ever parking, and without the expensive unlock/wakeup path. However, this does mean more threads actually doing stuff, which in some cases slows down the overall system. – Useless Aug 10 '17 at 15:54
  • ok thanks, your edit made it more clear. I think I will just try and see. The question I didnt ask because i thought it is too broad / not specific is how to guarantee that the producer wont block. Lets see how far I can get with a wait-free queue.... – 463035818_is_not_an_ai Aug 10 '17 at 15:59
  • 2
    @Useless careful with those generalizations, there are enough situations where a locking algorithm can be much faster than a lockless algorithm. Most people confuse "lockless" and co with "faster". While that can be true for specific situations, locks can be exceedingly efficient and I've seen 95%+ dropped updates with CAS on contended systems. – Voo Aug 10 '17 at 20:02
  • 1
    Yep, agreed. Wait-free style has less work to do in the uncontended case, _if_ the container or algorithm fit it well. If there's contention, or if the container or algorithm don't naturally suit wait-free style, then mutexes can easily take the lead again. – Useless Aug 11 '17 at 09:26
  • I don't think this is the right answer (well the Herlihy quote is obviously right, but not the rest). _Wait_ isn't about the thread parking. That is more like _blocked_ (either parked or spinning on a spin lock). – tony Aug 15 '17 at 04:51
  • @Voo wait-free algorithms can have CAS but not CAS-loops (which is the typical use case of CAS). So they are much less likely to run into contention problems - that's the beauty of wait-free. But yes, lock-free (et al) doesn't equal faster. Only measuring can answer that. – tony Aug 15 '17 at 04:53
0

"Pushes object to the ring buffer" refers to the type of array buffer that the queue is implemented on. This is probably implemented using a circular array to store the objects in the queue. See for example:

https://en.wikipedia.org/wiki/Circular_buffer

and

http://opendatastructures.org/ods-python/2_3_ArrayQueue_Array_Based_.html

OMD_AT
  • 64
  • 3