P0260 R17 C++ Concurrent Queues

[jensmaurer]

P0260R3 C++ Concurrent Queues (Lawrence Crowl, Chris Mysen)

[jensmaurer]

LEWG-I in Kona

[brycelelbach]

Kona 2019-02 LEWGI Minutes

P0260R3 Concurrent Communication Queues

Champion: Lawrence Crowl

Minute Taker: Ronan Keryell

Start Overview: 16:37

Start Discussion: 16:45

Maybe don’t constraint success to be 0.
Replace the std::pair returned by share_queue_ends with a custom struct with named members.

Start Polling: 16:48

POLL: Split into two papers:

• A paper on the one concrete queue type in P0260, buffer_queue.
• A follow-on paper containing everything else in P0260.

Strongly For	Weakly For	Neutral	Weakly Against	Strongly Against
6	0	3	2	0

Attendance: 14

That has consensus.

End: 17:07

[wg21bot]

P0260R4 C++ Concurrent Queues (Lawrence Crowl, Chris Mysen)

[brycelelbach]

Prague 2020-02 LEWGI Minutes

P1958R0 Concurrent Buffer Queue: Design Review

Chair: Bryce Adelstein Lelbach

Champion: Lawrence Crowl

Minute Taker: Conor Hoekstra

Start Review: 2020-02-12 08:45

Examples: Add to paper.

Implementation experience: Yes, in paper.

Usage experience: Yes, in paper.

Prior art: Add to paper.

Wording: Yes.

is_lock_free:

• There are many different types of queues: multi consumer/multi producer, single consumer/multi producer, etc.
• Is is_lock_free descriptive enough?
  • What if producers are lock free, but consumers must take a lock.
  • For a concrete class like this, it makes sense.
• Add is_always_lock_free.
• Should this be static?
  • SG1 decided they didn't want per instance properties.
• Should we just remove it?

What are the requirements on the value type? Answer: [conqueues.concept.elemreq]

• The first paragraph of should just be "element types must be Movable".
• Why do we need the second paragraph? Answer: Because you have to reuse the slot.
  • But doesn't this fall out of "valid but unspecified" wording? Is this really needed.

Exceptions during value_pop:

• You pop a value with value_pop.
• As you are returning from the function, you have to copy the value to the result.
• If that copy throws, you've lost that element.

Does copy elision solve the value_pop exception problem?
Answer: No, it makes it worse. You've got big_object bo = queue.pop(); (a copy-elided pop), it throws halfway through, and leaves the object in a bad state.

Can we require that if it throws in value_pop, you put it back in the queue?
Answer: The problem is that putting it back might throw too.

POLL: We are okay with value_pop potentially losing elements of the queue if element copy construction throws.

Strongly For	Weakly For	Neutral	Weakly Against	Strongly Against
1	4	6	3	0

Attendance: 18

# of Authors: 1

Author Position: SF

That has no consensus.

When does push(&&)/wait_push(&&)/try_push(&&) not consume the input?

• When the queue is full for try_push, otherwise only when an exception is thrown.
• Use after std::move can trigger warnings, but may be valid with this interface if it's a maybe consuming interface.
• What's the precedent in the standard? What does std::vector do?
  • std::vector::push_back has both && and const& overloads, but for std::vector, the && overload only fails to consume if there's an exception.

The alternative to a maybe-consuming && interface with const& overloads is an interface that takes things by value.

POLL: We are okay with concurrent queue's try_push(Value&&) which only consumes the argument if the queue is not full (this is the status quo in the paper).

Strongly For	Weakly For	Neutral	Weakly Against	Strongly Against
1	4	1	2	5

Attendance: 18

# of Authors: 1

Author Position: SF

That has no consensus.

SA: I don't want to loose the try functionality, but I don't like the semantics of this API. I'd be okay with an always consuming interface.

Potential solutions for try_push maybe-consuming semantics (vote as many times as you like):

• Maybe-consuming && overload and const& overload (status quo).
• Remove it (removes functionality SG1 desires).
• Replace the &&/const& overloads with a single by-value overload.
• Make the && overload always consume the object

POLL: Acceptable potential solutions for try_push(&&) consumption semantics (vote as many times as you like):

Options	Votes
0: Maybe-consuming try_push(&&) (status quo).	5
1: Always-consuming try_push(&&), but returns the input on failure.	12
2: Always-consuming try_push(&&).	9
3: Remove try_push(&&) (removes functionality SG1 desires).	6

Attendance: 17

# of Authors: 1

Author Position: 0, 1

Prior art for 2: Intel TBB concurrent_queue.

Resume After Break: 2020-02-12 10:48

Minute Taker: Ben Craig

Precedent for status APIs in the standard library?

Why have just is_closed, is_empty, is_full which return bool? Should we add a status that returns queue_op_status?

• Without status, you could write is_closed() || is_empty() || is_full() and have it return false, because the status could change in between each of the calls.
• But, queue_op_status represents the status of an operation, not the queue; for example, it has success.

is_empty/is_full are really only useful if you are the only thread accessing the queue.

Are the status mutually exclusive? Answer: No; you could be closed and empty, for example.

Perhaps only allow is_empty/is_full when the queue is closed.

queue_op_status could be a bitmask, so that you could return both empty and closed.

POLL: We are okay with standard library concurrent queues having is_empty and is_full.

Strongly For	Weakly For	Neutral	Weakly Against	Strongly Against
2	6	7	4	0

Attendance: 23

# of Authors: 1

Author Position: SF

That has weeeeaaak consensus.

try_pop/wait_pop return status:

• success if it popped an element.
• empty if the queue is open and empty (no element was popped).
• closed if the queue is closed and empty (no element was popped).

POLL: We are okay with the status quo states returned by try_pop and wait_pop.

NO OBJECTION TO UNANIMOUS CONSENT.

Attendance: 23

Should we add timed try wait interfaces for consistency? Did SG1 consider this? Answer: SG1 did talk about this. They didn't want to deal with it in version 1.

Are the non-blocking/blocking interfaces consistent with the standard library?

TS questions:

• Are the exception guarantees on value_pop acceptable?
• Is the maybe-consuming nature of try_push acceptable?
• Do we need operations with deadlines for a concurrent queue?
• Do we need buffer_queue to support allocators?
• Do we need buffer_queue to be an allocator aware container?

What happens if the distance between the iterators in the range constructor is greater than the maximum number of elements specified?

• Not specified today.
• Author suggests that it should be an error during construction.

Should we specify whether or this requires (instead of just supports) a fixed size queue implementation (with an allocation ahead of time)? Answer: No, we should probably seek to preserve implementation freedom here and allow implementations to do either.

• Is the noexceptness of this class consistent with an implementation that grows until the max size.

POLL: Require buffer_queue to allocate all storage only once.

Strongly For	Weakly For	Neutral	Weakly Against	Strongly Against
6	7	4	0	0

Attendance: 24

# of Authors: 1

Author Position: WF

That has unanimous consent.

POLL: Require buffer_queue to allocate all storage during construction (which allows *_pop and *_push to be made conditionally noexcept)

Strongly For	Weakly For	Neutral	Weakly Against	Strongly Against
6	8	4	0	0

Attendance: 24

# of Authors: 1

Author Position: N

That has unanimous consent.

Post poll, we discovered new information - we can't actually make *_pop and *_push conditionally noexcept, if for no other reason because mutex operations can throw (and the queue may be implemented with mutexes).

POLL: Require buffer_queue to allocate all storage during construction.

NO OBJECTION TO UNANIMOUS CONSENT.

Attendance: 24

# of Authors: 1

That has unanimous consent.

Should concurrent queues support allocators?

We've required all allocation to happen up front, which eliminates some concurrency concerns around adding allocator support. But, because of container allocator-awareness, the allocator has to be passed through to the elements, and thus concurrent calls to your allocator may occur.

POLL: In the Technical Specification, buffer_queue should support allocators.

Strongly For	Weakly For	Neutral	Weakly Against	Strongly Against
0	4	7	5	1

Attendance: 24

# of Authors: 1

Author Position: A

POLL: In the Technical Specification, concurrent queues should have a is_lock_free interface.

Strongly For	Weakly For	Neutral	Weakly Against	Strongly Against
0	3	9	2	0

Attendance: 22

# of Authors: 1

Author Position: N

That has no consensus.

End: 11:55

CONSENSUS: Bring a revision of P1958R0 (Concurrent Buffer Queue), with the guidance below, to LEWGI for further design review.

• Explore P0059 ring_buffer prior art and document it in paper.
• Consider removing value_pop to increase consensus.
• Consider removing is_empty and is_full to increase consensus.
• Consider removing is_lock_free to increase consensus.
• If is_lock_free remains, add is_always_lock_free (a la atomic<T>).
• Remove the maybe-consuming try_push(&&).
• Investigate prior art (such as TBB's concurrent_queue) and add either:
  • An always-consuming try_push(&&) which returns queue_op_status, or
  • An always-consuming try_push(&&) which returns the input on failure.
• Require buffer_queue to allocate all storage only once.
• Require buffer_queue to allocate all storage during construction.
• Instead of throwing queue_op_status objects add an standard library exception type and throw that. Use future_error as a model for this exception type, but inherit from an exception in <exception> not <stdexcept> (aka don't inherit from logic_error as future_error does) to minimize dependencies and remain freestanding-in-practice.