Re: your MPMC queue - two problems?

[Dmitry Vyukov]

On Sat, Oct 29, 2016 at 7:25 AM, Oliver Kowalke
<oliver....@gmail.com> wrote:
> Hello Dimitry,

+lock-free mailing list

Hello Oliver,

> I'm studying your MPMC queue
> (http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue).
>
> I'm wondering how the cells are addressed in the array (functions enqueue()
> and dequeue())
>
> cell = &buffer_[pos & buffer_mask_];
>
> Shouldn't it be:
>
> cell = &buffer_[pos & (buffer_mask_ - 1)];


Why? What is the problem you are trying to fix with this change?


> Additionally I would change the indicator for a consumed cell (in function
> dequeue()) from
>
> cell->cycle.store(pos + buffer_mask, std::memory_order_release);
>
> to
>
> cell->sequence_.store(pos + 2, std::memory_order_release);

Why?

> Or do I miss something?
>
> Because I need a SPMC queue, would it make sense to use your MPMC queue and
> make enqueue_pos_ non-atomic?


Yes, if you have only 1 producer, you can make enqueue_pos_
non-atomic. And similarly, if you have only 1 consumer, you can make
dequeue_pos_ non-atomic.

[Dmitry Vyukov]

On Tue, Nov 8, 2016 at 8:24 PM, Oliver Kowalke <oliver....@gmail.com> wrote:
> 2016-11-08 17:49 GMT+01:00 Dmitry Vyukov <dvy...@gmail.com>:
>>
>> On Mon, Nov 7, 2016 at 5:05 AM, Oliver Kowalke <oliver....@gmail.com>
>> wrote:

>> > 2016-11-06 17:10 GMT+01:00 Dmitry Vyukov <dvy...@gmail.com>:
>> >>
>> >> > cell = &buffer_[pos & (buffer_mask_ - 1)];
>> >> Why? What is the problem you are trying to fix with this change?
>> >
>> >

>> > pos is incremented by the producer and because the buffer is bound we
>> > need
>> > to wrap if the last element of the buffer was accessed
>> > for a buffer with 4 elements the Index will be:
>> > 0: 0
>> > 1: 1
>> > 2: 2
>> > 3: 3
>> > 4: 0
>>
>> This is a buffer with 5 elements, not 4.
>
>
> the first number is the index/position/enqueue-position - the second number
> corresponds to the array index
> test code:
>
> int mask = 4;
> for (int pos = 0; pos < 8; ++pos) {
> std::cout << pos << ": " << (pos & (mask - 1)) << std::endl;
> }
>
> produces:
> 0: 0
> 1: 1
> 2: 2
> 3: 3
> 4: 0 // wrapped first time
> 5: 1
> 6: 2
> 7: 3
>
>
> while in the other code:
>
> int mask = 4;
> for (int pos = 0; pos < 8; ++pos) {
> std::cout << pos << ": " << (pos & mask) << std::endl;
> }
>
> produces:
> 0: 0
> 1: 0
> 2: 0
> 3: 0
> 4: 4
> 5: 4
> 6: 4
> 7: 4

+lock-free again, please keep it in CC


Did you notice that my code initializes mask to size-1:

, buffer_mask_(buffer_size - 1)

?
So if buffer size is 4, mask is 3 and (pos & mask) working fine.




>> If producer wraps around: consumer pos = X, producer pos =
>> X+buffer_size, so sequence - pos = buffer_size -> producer is not
>> allowed to write. I don't see the problem.
>
>
> sorry I was referring to cell->sequence, not the indices. In your code you
> suggest to store struct cell
> in each buffer slot. struct cell has a member named sequence. sequence is
> of type std::atomic< int > and
> used to synchronize producers and consumers.
>
> producer: cell->sequence_.store(pos + 1, std::memory_order_release);
> consumer: cell->sequence_.store(pos + buffer_mask_ + 1,
> std::memory_order_release);
>
> suppose a buffer with 4 slots - sequence would contain following values
> after access from a producer:
> mask = 4
>
> 1. round:
> array index 0 1 2 3
> pos 0 1 2 3
> sequence_ (after producer's access) 1 2 3 4
> sequence_ (after consumer's access) 5 6 7 8
>
> 2. round:
> array index 0 1 2 3
> pos 4 5
> 6 7
> sequence_ (after producer's access) 5 6 7 8
> sequence_ (after consumer's access) 9 10 11 12
>
> if a producer wraps it is only allowed the use the cell at the first element
> in the buffer if sequence_ - pos == 0, e.g.
> a consumer has dequeued the value and set sequence_ = pos + buffer_mask +
> 1, e.g. the first consumer in 1. round has set
> sequence_ = 0 + 4 +1 = 5. But the producer in 2.round is never allowed to
> enqueue its element because the condition for enqueueing
> is false: (sequence_ - pos == 0 -> 5 - 4 != 0).
>
> with a slight modification in how the consumer computes sequence_ your code
> works:
> cell->sequence_.store(pos + buffer_mask_, std::memory_order_release);
>
> 1. round:
> array index 0 1 2 3
> pos 0 1 2 3
> sequence_ (after producer's access) 1 2 3 4
> sequence_ (after consumer's access) 4 5 6 7
>
> 2. round:
> array index 0 1 2 3
> pos 4 5
> 6 7
> sequence_ (after producer's access) 5 6 7 8
> sequence_ (after consumer's access) 8 9 10 11
>
> now the conditions for producers and consumer to proceed is met


Again, you seem to assume that mask == size. When size is power of 2,
mask is calculated as size-1.

[Dmitry Vyukov]

On Mon, Nov 14, 2016 at 8:13 AM, Oliver Kowalke
<oliver....@gmail.com> wrote:

>
> 2016-11-14 7:12 GMT+01:00 Dmitry Vyukov <dvy...@gmail.com>:
>>
>> Again, you seem to assume that mask == size. When size is power of 2,
>> mask is calculated as size-1.
>
>

> Oh, you are right. Seams I was too much focused on enequeu()/dequeue(). I'm
> sorry for the noise.
>
> BTW, is it OK for you that I use your mpmc queue in my boost library (source
> contains note about you authorship and link to your website)?


+lock-free again

I am perfectly OK with that. The licence is BSD as stated in the site
footer, so if you mention my authorship that's enough.

[Gavin Lambert]

On Monday, November 14, 2016 at 9:45:15 PM UTC+13, Dmitry Vyukov wrote:

> BTW, is it OK for you that I use your mpmc queue in my boost library (source
> contains note about you authorship and link to your website)?

+lock-free again

I am perfectly OK with that. The licence is BSD as stated in the site
footer, so if you mention my authorship that's enough.

While uniform licensing is not strictly mandatory in Boost, AFAIK, I think technically to include the code in a Boost library would prefer Dmitry to allow relicensing it with the Boost license (http://www.boost.org/users/license.html).  It's very similar to the BSD license but not identical.

If either of you are interested, I have an adaptation of the queue which supports allocator_traits, movable types, and exception safety (basic or noexcept, as appropriate, and BOOST_NO_EXCEPTIONS).

It assumes at least C++11, though.  (Or technically, almost-C++11, since it's mostly tested in VS2013.)

[Dmitry Vyukov]

On Fri, Nov 25, 2016 at 6:08 AM, Gavin Lambert <uec...@gmail.com> wrote:
> On Monday, November 14, 2016 at 9:45:15 PM UTC+13, Dmitry Vyukov wrote:
>>
>> > BTW, is it OK for you that I use your mpmc queue in my boost library
>> > (source
>> > contains note about you authorship and link to your website)?
>>
>> +lock-free again
>>
>> I am perfectly OK with that. The licence is BSD as stated in the site
>> footer, so if you mention my authorship that's enough.
>
>
> While uniform licensing is not strictly mandatory in Boost, AFAIK, I think
> technically to include the code in a Boost library would prefer Dmitry to
> allow relicensing it with the Boost license
> (http://www.boost.org/users/license.html). It's very similar to the BSD
> license but not identical.

How can I do it?

[Miral Mirality]

On 25/11/2016 19:46, "Dmitry Vyukov" <dvy...@gmail.com> wrote:
> > While uniform licensing is not strictly mandatory in Boost, AFAIK, I think
> > technically to include the code in a Boost library would prefer Dmitry to
> > allow relicensing it with the Boost license
> > (http://www.boost.org/users/license.html).  It's very similar to the BSD
> > license but not identical.
>
> How can I do it?

Reading the license page and then formally stating that you're ok (or not) with it being used under those terms would probably be sufficient.

[Dmitry Vyukov]

I hereby license and permit usage of my "Bounded MPMC queue"
(http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue)
under the terms of "Boost Software License - Version 1.0 - August
17th, 2003" (http://www.boost.org/users/license.html).

[Gavin Lambert]

On Friday, November 25, 2016 at 6:08:48 PM UTC+13, I wrote:

If either of you are interested, I have an adaptation of the queue which supports allocator_traits, movable types, and exception safety (basic or noexcept, as appropriate, and BOOST_NO_EXCEPTIONS).

It assumes at least C++11, though.  (Or technically, almost-C++11, since it's mostly tested in VS2013.)

Have a look: https://gist.github.com/uecasm/b547db812ae4bba39bb1bd0443801507

(I marked it as secret just so that people don't stumble across it without the context; I don't mind it being used.)

I'm not 100% certain I have the allocator_traits officially correct (and I've omitted some constructors that would be required for stateful allocators that require initialisation), but it seems to work as expected.

With BOOST_NO_EXCEPTIONS defined the noexcept vs. except implementations end up being largely identical, although it will still exercise both paths depending on the declared types.  Didn't seem worthwhile chasing the tiny size optimisation that could potentially result from being aware of this.  A sufficiently clever compiler might do it itself, although it would surprise me.  Similarly mpmc_fixed_bounded_value could avoid the heap allocation if written differently, but sometimes that's not a good thing.

[Gavin Lambert]

FYI, I've updated the code a little; I noticed I accidentally omitted two BOOST_NOEXCEPT_EXPR required to compile on compilers more modern than VS2013.

Given the lack of response, though, I guess nobody's interested after all?

[Gavin Lambert]

FYI, updated again.  I've cleaned up the code a bit:

• Provides allocator_type typedef and get_allocator() method per AllocatorAwareContainer requirements.
• Uses allocator_traits construct/destroy only for the original type T, per AllocatorAwareContainer requirements.  (Since apparently people get grumpy when also used for node types.)
• Adds constructors to accept a stateful allocator instance (although mpmc_bounded_value has a required max_size parameter, so doesn't exactly fit the concept).
• Stores only one copy of the allocator instance (since I have been assured that it's legal to call construct for type T on an allocator instance for type X).
• Uses addressof with T, so works as expected even if T overrides operator&.

I think this is probably as close as it can get to AllocatorAwareContainer.  It is neither movable nor copyable (due to atomics) so does not implement those requirements, and does not implement the initial-insertion constructors (as that would be a very weird use-case for an atomic queue).