Question about JCTools MPMC queue

[Sharath Gururaj]

This question is regarding JCTools MPMC queue which is a java port of Dmitry Vyukov's Mpmc C++ implementation

https://github.com/JCTools/JCTools/blob/011e1c3a6919a0fb641815c7429e0742911b9a79/jctools-core/src/main/java/org/jctools/queues/MpmcArrayQueue.java#L141

Everything inside the if condition of line 140 seems to be redundant. Here are my questions: seems 

1. the check 

pIndex - capacity >= (cIndex = lvConsumerIndex())

seems wrong to me. The >= actually be <= 

2. The inner else seems to be redundant. Under what conditions can it be that seq < pIndex but array has free capacity?? If so then we can remove the inner if..else and simply return false

Thanks

Sharath

[Nitsan Wakart]

Hi Sharath,

I have answered your questions on GitHub, and referenced from the comment on my blog:

https://github.com/JCTools/JCTools/issues/179

I'll copy here for your convenience:

1. It was a bug, fixed now by commit: 

https://github.com/JCTools/JCTools/commit/56b5e58b07266bea077ab5aa2c6e6268696b4784#diff-b871020fbeb6c92660e34a22b41c2b7dL138

This check is not part of original algo, but required to support java.util.Queue interface correctly where returning false indicated queue is full.

2. The queue can be non-full and still hit this case if a single consumer is 'stuck' between claiming the slot and moving the sequence. In this state other consumers can make progress, clearing more slots, thus the queue is not full.

I hope this is clear enough.

Regards,

Nitsan

--

---
You received this message because you are subscribed to the Google Groups "Scalable Synchronization Algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email to lock-free+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/fd6f1b95-9bc0-4f7c-bfc7-5e1de488a890%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Dmitry Vyukov]

Hi Sharath,

It depends on what semantics you want to get from the queue.
This check seems to lead to active spinning if we see there is a
pending consumer that started dequeue but did not finish (executed
CAS, but not updated seq).
Also, I think it makes the queue linealizable, per se it is not which
can be confusing in some cases.

Re 2: when a consumer has started an operation but did not finish it.
Moreover, an arbitrary number of other consumers might have drained
the queue completely, but producer is still stuck due to the first
pending consumer.

Re 1: that I don't know as I don't see code for lvConsumerIndex,
calcSequenceOffset and some other functions.

[Sharath Gururaj]

Thanks Nitsan and Dmitry for the clear explanation of #2

I understand it now.

However, In the case of concurrent queues, 

I'm not sure if we should interpret the offer() semantics of java in such a strict way. (returns false iff queue is full)

Because in a concurrent situation, the very question "is the queue full?" loses meaning

Even when we return false from offer(), by the time we detect the false return, other consumers can race and make the queue not full. 

There is no way to enforce a strict offer() behaviour. Maybe relaxed{Offer, Poll} methods should be the default {Offer, Poll} method

[Dmitry Vyukov]

On Fri, May 26, 2017 at 12:10 PM, Sharath Gururaj <e271...@gmail.com> wrote:
> Thanks Nitsan and Dmitry for the clear explanation of #2
> I understand it now.
>
> However, In the case of concurrent queues,
> I'm not sure if we should interpret the offer() semantics of java in such a
> strict way. (returns false iff queue is full)
> Because in a concurrent situation, the very question "is the queue full?"
> loses meaning
>
> Even when we return false from offer(), by the time we detect the false
> return, other consumers can race and make the queue not full.
> There is no way to enforce a strict offer() behaviour. Maybe relaxed{Offer,
> Poll} methods should be the default {Offer, Poll} method

I don't know semantics Java interfaces impose, but there cases like
the one you described above, but there are also other cases where the
queue is provably not-full yet Offer fails.
Consider we have a queue with capacity 2. We insert 2 elements
initially. Then start 2 threads. Each thread first removes 1 element
and then inserts 1 element. Under any interleaving of operations in
these threads, the queue is never full during insertion. Yet insertion
can fail with the original implementation of the queue.
Non-linearilizability can be very confusing.

[Nitsan Wakart]

Dmitry, thank you for such a clearly stated test case :-)

Sharath, the semantics of the interface are quite clear, and as it turns out some people lean on them. If you wish to implement concurrent queues that are compatible with JDK you need to consider this. In JCTools the decision was to clearly break from the contract with the 'relaxed' methods to avoid confusion. Where JCTools is not 100% compliant it is immediately broken(e.g. iterator is not implemented and throws an Unsupported exception, there's no confusion). I don't like the choice the JDK went with here, but it is made...