P0260 R10 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.

[wg21bot]

P0260R5 C++ Concurrent Queues (Lawrence Crowl, Chris Mysen, Detlef Vollmann)

[brycelelbach]

SG1 reviewed this paper on 2023-02-07 at Issaquah.

The prior decision, paraphrased:

  The design of P0260R5 is appropriate for a concurrency TS
  (Was: unanimous consent.)
We are not retaking this poll.

Temperature poll for IS instead of TS:

Forward the design of P0260R5 to LEWG for C++26
  The TS questions have been addressed or are moot.
SF F N A SA
3  7 6 2 3
Not consensus
SA: see David's reflector post
SA: this doesn't meet my goal to make async APIs that hide implementation
SA: I believe this will not fit nicely in the efforts coming to fruition in C++26

Consensus improving poll?

Forward the design of P0260R5 to LEWG for C++26, if:
  Remove blocking push/pop functions (this addresses or moots the TS questions)
SF F N A SA
0  5 2 6 7
No consensus for change

This paper may proceed to a TS but not for an IS, due to concerns over blocking and integration with senders & receivers.

[brycelelbach]

It looks like we won't have time to look at this at the Issaquah meeting. Absent a paper proposing a goal and scope for a TS to include this in, Library Evolution can't look at this. If we are concerned about blocking and integration with senders, then a revision should be produced which addresses those concerns.

[ogiroux]

Begin work on Concurrency TS v3, inclusive of Concurrency TS v2, with the following scope:
  "This document describes requirements for implementations of an interface that computer programs written in 
  the C++ programming language may use to invoke algorithms with concurrent execution. The algorithms described 
  by this document are realizable across a broad class of computer architectures."
SF F N A SA
No objection to unanimous consent

Forward the concurrent queue design of P0260R5 and P1958R0 for inclusion in the new Concurrency TS v3
 With these questions for the TS to answer:
  * Is the proposed concept useful? Specifically, does it cover different implementations and does it work together with
  other concepts for concurrent queues, e.g. queues with only non-blocking functions or queues with an asynchronous interface?
  * Is the concrete queue useful without an asynchronous interface? Can an asynchronous interface be added without 
  extra overhead?
  * What other concrete implementations should be provided?
  * Is a queue that is ignorant of execution contexts from std::execution still useful?
SF F N A SA
No objection to unanimous consent

[brycelelbach]

2023-02-07 10:30 to 12:00 Issaquah Library Evolution Meeting

P0260R5: C++ Concurrent Queues

2023-02-07 10:30 to 12:00 UTC-8 Issaquah Library Evolution Minutes

Champion: Olivier Giroux (IP)

Chair: Billy Baker (IP) & Inbal Levi (IP)

Minute Taker: Ben Craig (IP)

Start: 2023-02-07 11:50 UTC-8

End: 12:02

Next Steps

Propose a scope and goals for a new Technical Specification for C++ concurrent queues and get consensus for it in the Concurrency study group.

[inbal2l]

2023-06-15 Library Evolution Varna

P0260R5: C++ Concurrent Queues

2023-06-15 Library Evolution Minutes

Chair: Fabio Fracassi, Billy Baker

Champion: Detlef Vollmann

Minute Taker: Jonathan Müller

Summary

POLL: (Re)add [is_|was_]empty() query to concurrent queue (name to be determined).

SF	F	N	A	SA
2	7	4	7	2

Attendance: 25 (P) + 4 (R)

# of Authors: 1

Author's Position: (TODO)

Outcome: No consensus.

__POLL: (Re)add is_empty_and_closed() query to concurrent queue (name to be determined).__

SF	F	N	A	SA
2	7	7	6	1

Atendance: 25 (P) + 4 (R)

# of Authors: 1

Author's Position: (TODO)

Outcome: No consensus.

The API of this facility hits several situations where LEWG does currently not have a clear guidance, in the light of new library and language features that we have now available, that were not available when we designed similar facilities before (optional/expected).

The paper should include an exploration on how the following decisions would affect the design

• use system_error(or derive from it) as the exception type
• explore interface options for try_push that prevents data loss
• Make element type require noexpect moveable
• Type erasure?

Next Steps

Feedback will be sent to the author. The paper needs another revision.

[wg21bot]

P0260R6 C++ Concurrent Queues (Detlef Vollmann, Lawrence Crowl, Chris Mysen, Gor Nishanov)

[wg21bot]

P0260R7 C++ Concurrent Queues (Detlef Vollmann, Lawrence Crowl, Chris Mysen, Gor Nishanov)

[inbal2l]

R8 will be reviewed by SG1 in Tokyo, tentatively scheduled for LEWG in St. Louis (along with P2921. P2912)

[ogiroux]

Is there an R8?

[inbal2l]

Not published in a ML but available as an R revision (P0260R8).

[wg21bot]

P0260R8 C++ Concurrent Queues (Detlef Vollmann, Lawrence Crowl, Chris Mysen, Gor Nishanov)

[wg21bot]

P0260R9 C++ Concurrent Queues (Detlef Vollmann, Lawrence Crowl, Chris Mysen, Gor Nishanov)

[ogiroux]

SG1 in St Louis

Forward the design D0260R10 to LEWG for the IS but a future version of the paper needs to address where the completion of asynchronous push/pop runs SF F N A SA 4 5 1 0 0

[inbal2l]

P0260R10 C++ Concurrent Queues (Detlef Vollmann, Lawrence Crowl, Chris Mysen, Gor Nishanov)

[inbal2l]

2024-06-27 Library Evolution St. Louis Meeting (First Afternoon session)

P0260R10 C++ Concurrent Queues

2024-06-27 Library Evolution Telecon Minutes

Champion: Detlef Vollmann Chair: Ben/Fabio Minute Taker: Mark Hoemmen

Summary

ACTION ITEM: Change <experimental/conqueue> header and experimental namespace in wording.

Next Steps

Continue the discussion in the next session.

[inbal2l]

2024-06-27 Library Evolution St. Louis Meeting (Second Afternoon session)

P0260R10 C++ Concurrent Queues

2024-06-27 Library Evolution St. Louis Minutes

Champion: Detlef Vollmann Chair: Robert/Fabio Minute Taker: Khalil Estell

Summary

POLL: Remove the user-facing concepts from P0260R10 (the author is free to use exposition-only concepts or named type requirements to achieve the same effect)

SF	F	N	A	SA
2	8	5	0	0

Attendance: 18 IP + 3 R Author's Position: 2xN Outcome: Strong consensus in favor

POLL: The next revision of P0260R10 should provide an emplacement API

SF	F	N	A	SA
5	8	2	2	0

Attendance: 17 IP + 3 R Author's Position: 1x WA 1x WF Outcome: Consensus in favor

WA (author): I want minimal interface WA: Similar reason as author, keep paper small and have that added in another paper N: Would require constructing user types while holding a lock N: Never used anything like this for types with non-trivial move constructors SF: Emplace functions are used a lot, saves an operation

POLL: bounded_concurrent_queue should be allocator-aware by providing get_allocator and making proper use of allocator_traits::construct

SF	F	N	A	SA
6	5	4	0	0

Attendance: 18 IP + 3 R Author's Position: 2x N Outcome: Strong consensus in favor

POLL: bounded_concurrent_queue should have a nested type value_type

SF	F	N	A	SA
7	7	0	0	0

Attendance: 18 IP + 3 R Author's Position: 2x SF Outcome: Unanimous consent in favor

POLL: The next revision of P0260R10 should provide a “fronts” and a “backs” (see 10.2.1 in the paper)

SF	F	N	A	SA
1	2	0	6	5

Attendance: 18 IP + 3 R Author's Position: 2x SA Outcome: Consensus against

Next Steps

The authors will apply the requested changes, the updated revision will be seen again in LEWG.