P0447 R26 Introduction of std::hive to the standard library

[wg21bot]

P0447R4 Introduction of std::colony to the standard library (Patrice Roy, Guy Davidson, Matthew Bentley)

[brycelelbach]

Kona 2019-02 LEWGI Minutes

P0447R6 std::colony

Champion: Jonathan Wakely and Nico Josuttis

Minute Taker: Vincent Reverdy

Start Overview: 15:22

Start Discussion: 15:59

We need a list of the things in the wild like this (prior art).

Eric F will write an implementation before Cologne.

Jonathan Wakely is thinking about putting it into GCC as an extension.

Please come back with something more wording like - we need a class synopsis.

Start Polling: 16:09

POLL: We should promise more committee time to pursuing std::colony, knowing that our time is scarce and this will leave less time for other work.

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

Attendance: 16

End: 4:15

[brycelelbach]

Author has deferred discussion until Belfast; he hopes to have more usage experience by then.

[wg21bot]

P0447R8 Introduction of std::colony to the standard library (Matt Bentley)

[wg21bot]

P0447R9 Introduction of std::colony to the standard library (Matt Bentley)

[wg21bot]

P0447R10 Introduction of std::colony to the standard library (Matt Bentley)

[wg21bot]

P0447R11 Introduction of std::colony to the standard library (Matt Bentley)

[wg21bot]

P0447R12 Introduction of std::colony to the standard library (Matt Bentley)

[inbal2l]

Reviewd on LEWG mailing list on 2021-02-01. R13 is under work.

Attaching a summary of the responses (some may already be fixed on the WIP version):

1. Recommendation to be careful not to over-specify the class, and leave room for future changes in implementation. Author: This was considered, see also: "Is there active research in this problem space? Is it likely to change in future?" appendices.
2. There was a discussion regarding having colony specified at plf:: instead of std:: to allow performance improvements which require ABI-breakage, the other side is that colony is usable by a large audience.
3. Proposal suggests to reserve std::limits, consider reserving a smaller scope (possibly as a member in colony) or using colony_limits. Author: This was discussed broadly on SG14, making it a member creates ugly syntax, colony_limits is my prefered option.
4. Consider adding constexpr implementation.
5. Elaborate on the purpose of parameter "Skipfield". Author: Ment to allow changes for this template instance which prioritize lowered memory usage over performance. Use of this type by an implementation is not guaranteed, may change this to prioritize_performance / prioritize_memory_use enum.
6. Consider making (==, !=, <<, >>) hidden friends (need to be in the class synopsis)  / member functions (considering C++20 comparison rewrite rules) . (reference: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1601r0.pdf) Note by Jonathan Wakely: We have a proposal to support comparisons between containers with different types. I will update it for <=> comparisons. For now assume you don't need to overload for different priorities.
7. Consider specifying op== in terms of the std::equal Author: None of the other containers appear to do this, but I'm happy to do so if there's a consensus.
8. A broad discussion regarding: advance/next/prev, result is they are specified as hidden friends of the iterator classes.
9. Consider removing member sort() Author: Explanation under Design Decisions->Additional notes on specific functions->void sort(). To date there's been no interest in standardising the sort algorithm which colony reference implementation uses as a non-member.
10. Consider allowing different iter types in range insert and to constrain those types with an appropriate requires clause (to allow sentinel) Author: I think it's probably reasonable to expect that a new container should match functionality with the old ones in order to be a drop-in replacement in older code.
11. Remove duplication of paragraph which is included in memory()
12. Bike-shedding is welcome for reshape()

Alternatives to the name colony were also brought up, a different thread was created to discuss this.

[wg21bot]

P0447R13 Introduction of std::colony to the standard library (Matt Bentley)

[wg21bot]

P0447R14 Introduction of std::colony to the standard library (Matt Bentley)

[wg21bot]

P0447R15 Introduction of std::hive to the standard library (Matt Bentley)

[wg21bot]

P0447R16 Introduction of std::hive to the standard library (Matt Bentley)

[wg21bot]

P0447R17 Introduction of std::hive to the standard library (Matt Bentley)

[wg21bot]

P0447R18 Introduction of std::hive to the standard library (Matt Bentley)

[wg21bot]

P0447R19 Introduction of std::hive to the standard library (Matt Bentley)

[ben-craig]

2022-03-22 Library Evolution Telecon

P0447R19: std::hive

2022-03-22 Library Evolution Telecon Minutes

Chair: Ben Craig

Champion: Matt Bentley

Minute Taker: Steve Downey

Summary

POLL: Remove operator== and operator!= from hive

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
9	6	1	2	0

Attendance: 22

# of Authors: 1

Author Position: WA

Outcome: Consensus in favor of removing operator== and operator!=.

__POLL: Rename reshape to change_block_capacity_limits__

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
0	3	6	3	1

Attendance: 22

# of Authors: 1

Author Position: N

Outcome: No consensus for change

Outcome

More review (and revision) needed. LEWG should pick up at: 22.3.14.2 hive constructors, copy, and assignment [hive.cons] after discussing the changes provided in the revisions after R19.

[brycelelbach]

2022-04-05 Library Evolution Telecon

P0447R19: std::hive

2022-04-05 Library Evolution Telecon Minutes

Chair: Ben Craig

Champion: Matt Bentley

Minute Taker: Steve Downey

Summary

This was a LEWG-level review of the specification. No polls were taken. The following is an incomplete list of the recommendations provided.

The author expressed that there is no intent to do anything unusual with the allocators in the container.

There was discussion on the explicitness of multi parameter constructors. For now, do as the other containers do, and let some other paper change the status quo.

There are missing constructors that are needed to support allocator-extended construction.

Remove memory() for the time being. If the author wants to add it back, then it needs examples, and an explaination of how a custom allocator wouldn't be sufficient.

consider renaming trim() to indicate that it trims capacity ( trim_capacity()? no argument reserve()?). This is to disambiguate from string trim algorithms which change the contents of the container.

Adjust complexity requirements on several functions (clear, splice, get_iterator) from "constant" to "linear in the number of blocks"

add get_iterator(const_pointer p) [non-const] noexcept

Next Steps

The author will revise the paper in accordance with the provided feedback and return to LEWG. We will continue review at Pick up at hive.special (specialized algorithms), or the equivalent position if that no longer exists.

[brycelelbach]

2022-04-12 Library Evolution Telecon

P0447R19: std::hive

2022-04-12 Library Evolution Telecon Minutes

Chair: Ben Craig

Champion: Matt Bentley

Minute Taker: Gašper Ažman

Summary

Finished the LEWG level review of the technical specification. Discussed priority benchmarks. It was speculated that the benefits of priority::memory_use could be achieved with a combination of setting small block limits, the implementation specializing on small Ts, and allocators and extensions that can control block reclamation policies.

POLL: Remove priority template parameter from hive

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
1	7	2	1	0

Attendance: 18

# of Authors: 1

Author Position: WA

Outcome: Consensus in favor

Next Steps

Bring a new revision that addresses the polls and the review feedback. Try to have a library wording expert do an initial pass over the wording.

[ben-craig]

D0447R20: std::hive

D0447R20: std::hive

2022-05-17 Library Evolution Telecon Minutes

Chair: Ben Craig

Minute Taker: Steve Downey

Champion: Matthew Bentley

Summary

Discussed get_iterator, and reviewed complexity specifications.

Next Steps

Come back with revised paper addressing feedback

[wg21bot]

P0447R20 Introduction of std::hive to the standard library (Matt Bentley)

[brycelelbach]

Deferred for now, the author's not available right now.

[ben-craig]

2023-02-07 15:30 to 17:30 Issaquah Library Evolution Meeting

P0447R21: Introduction of std::hive to the standard library

P2596R1: Improve std::hive::reshape

P2857R0: Rebuttal to P2596

2023-02-07 15:30 to 17:30 UTC-8 Issaquah Library Evolution Minutes

Champion: Guy Davidson (P0447, P2857) & Patrice Roy (P2596)

Chair: Ben Craig

Minute Taker: Steve Downey

Start: 2023-02-07 15:45 UTC-8

Does this paper have:

• Examples? Yes
• Field experience? Yes
  • Implementation experience? Yes
  • Usage experience? Yes
  • Deployment experience? Yes
• Performance considerations? Yes
• Discussion of prior art? Yes
• Changes Library Evolution previously requested? Yes
• Wording? Yes
• Breaking changes? No
• Feature test macro? Yes
• Freestanding? No
• Format and/or iostream support? No

End: 17:10

Summary

We started with covering the revisions made to the paper. We then discussed P2596, which proposes modifications to std::hive. We looked at that wording, then heard a rebuttal of P2596. There were continued questions about whether we should be spending time on std::hive.

While there is field usage and deployment experience, there were concerns that this paper isn't providing enough evidence of existing practice in the field.

POLL: We like P2596 "Improve std::hive::reshape" enough to go through the wording

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
4	11	4	2	2

Attendance: 20 local, 12 remote

# of Authors: 1

Author Position: SF

Outcome: consensus

A: I think reshape is useful, but I don't have concrete arguments SA: Not convinced we should spend more time on this at all

POLL: Spend more committee time on std::hive

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
8	4	5	2	3

Attendance: 22 local, 11 remote

# of Authors: 2

Author Position: 2xSF?

Outcome: Not enough enough consensus to stop

POLL: Apply P2596 (Improve std::hive::reshape) to P0447R21 (Introduction of std::hive to the standard library) and return to LEWG

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
2	3	8	4	3

Attendance: 27 local, 10 remote

# of Authors:

Author Position:

Outcome: No consensus to change. 1 meeting for rebuttal to the rebuttal

Next Steps

There wasn't consensus to change the hive paper. We encourage the authors to work together to resolve the conflicts. The author of P2596 has one meeting to provide a rebuttal to the rebuttal before we attempt to move forward with P0447.

[wg21bot]

P0447R21 Introduction of std::hive to the standard library (Matt Bentley)

[ben-craig]

Should be discussed with P2857

[brycelelbach]

P0447R22 will be available in th 2023-05 mailing.

[FabioFracassi]

2023-06-16 Library Evolution Varna

P0447R22: std::hive

2023-06-16 Library Evolution Minutes

Champion: Matthew Bentley

Chair: Fabio Fracassi

Minute Taker: Robert Leahy

POLL: The wording of P0447r22 needs to be improved before we can review it.

SF	F	N	A	SA
2	1	8	5	6

Attendance: 26(P) + 5(R)

Outcome: No consensus

Chair Note: This poll was an informative poll, inside of the review session to inform whether to continue the review. The paper still needs a revision before it is seen again.

Summary

There was significant disagreement on how detailed the complexity requirements of individual operations should be specified. If we over specify we will loose implementation freedom, and potentially preclude performance improvements in the future. If we under specify we loose performance portability.

There is sustained opposition over this point, and -since performance is a motivating use case for this facility- it threatens the consent for the inclusion of this feature.

Next Steps

A small review group has volunteered to improve the wording for the next revision.

Users with additional motivating use-cases for the proposed API are encouraged to provide them.

We will continue reviewing the revised wording.

[wg21bot]

P0447R23 Introduction of std::hive to the standard library (Matt Bentley)

[inbal2l]

2023-11-07 Library Evolution Meeting Kona 2023 (First Afternoon Session)

P0447R24: Introduction of std::hive to the standard library

2023-11-07 Library Evolution Kona Minutes (first afternoon session)

Champion: Matthew Bentley

Chair: Inbal Levi / Nevin Liber

Minute Taker: Mark Zeren

Start: 2023-11-07, First Afternoon Session

Summary

We took a poll on continue working on std::hive:

POLL: We would like to devote more LEWG time to P0443 knowing that our time is scarce and this will leave less time for other work.:

SF	F	N	A	SA
7	9	8	4	4

Attendance: 28+9

# of Authors: 1

Authors’ position: SF

Outcome: consensus to continue

Next Steps

We had a discussion on the addition of "hive" into the standard library. We had a consensus in favor at 2:1 ratio.

[inbal2l]

2023-11-07 Library Evolution Meeting Kona 2023 (Second Afternoon Session)

P0447R24: Introduction of std::hive to the standard library

2023-11-07 Library Evolution Kona Minutes (second afternoon session)

Champion: Matthew Bentley

Chair: Ben Craig / Robert Leahy

Minute Taker: Robert Leahy

Start: 2023-11-07

Summary

POLL: Remove relational operators for hive iterators. Due to ABI, we likely could not add them later

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
0	2	3	5	1

Attendance: 19+5

# of Authors: 1

Author Position: WA

Outcome: No consensus for change

1 abstention

POLL: Support negative std::distance, std::ranges::distance, std::reverse_iterator, std::move_iterator and friends, but not for user supplied adaptors, for hive iterators

Attendance: 19+5

Outcome: Ask for unanimous vote. No objection to unanimous dissent. No one wants this

Next Steps

Change swap specification so that it swaps the size limits Decide if splice needs to mention that it invalidates end iterators Add constexpr to block_capacity_limits()? Work on the exception guarantees of reshape. Strongly consider sticking with the basic exception guarantee.

Next meeting, start at reshape, and cover revisions, but do not start over from the beginning of the wording

[ben-craig]

2023-11-10 Library Evolution Meeting Kona 2023

D0447R25: Introduction of std::hive to the standard library

2023-11-10 Library Evolution Kona Minutes

Champion: Matthew Bentley

Chair: Ben Craig / Inbal Levi

Minute Taker: Eddie Nolan

Summary

__POLL: Remove is_active from std::hive__

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
7	9	1	0	3

Attendance: 21+

# of Authors: 1

Author Position: SA

Outcome: Consensus for change

__POLL: Add precondition to get_iterator, requiring the pointee to belong to the current hive, which would remove the sentence about returning past-the-end iterator if the item is not found__

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
7	9	0	2	1

Attendance: 21+

# of Authors: 1

Author Position: WF

Outcome: Consensus

__POLL: Remove get_iterator from std::hive__

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
1	5	5	4	5

Attendance: 22+

# of Authors: 1

Author Position: SA

Outcome: No consensus

POLL: Modify D0447R25 (Introduction of std::hive to the standard library) by removing is_active and adding a precondition to get_iterator as described above, and then send the revised paper to LWG for C++26, to be confirmed with a Library Evolution electronic poll.

Strongly Favor	Weakly Favor	Neutral	Weakly Against	Strongly Against
12	5	3	1	0

Attendance: 26+9

# of Authors: 1

Author Position: SF

Outcome: Consensus

Next Steps

Produce a revision with the requested changes. That revision will go in LEWG electronic polling.

[inbal2l]

P0447R26 was added to LEWG 2023 December electronic poll paper (P30532R0) (Note: Please make sure to publish it in the Dec 2023 mailing list. Please make sure you also publish P0447R25, which is the revision which we provided feedback on in the discussion above)

[mattreecebentley]

P0447R26 was added to LEWG 2023 December electronic poll paper (P30532R0) (Note: Please make sure to publish it in the Dec 2023 mailing list. Please make sure you also publish P0447R25, which is the revision which we provided feedback on in the discussion above)

Hi Inbal, the version we discussed was the draft version, D0447R25 as noted above, so the new published version will be P0447R25. Please adjust the poll accordingly (I can alter the numbering if there's some problem with doing so). I will have it ready for the december mailing 👍 Cheers, Matt

[inbal2l]

@mattreecebentley - I would prefer having D0447R25 (which was seen on Friday) published as is (as it is what the polls address) and then in the same mailing list, have P0447R26 which applies the changes requested by the Friday polls. In this way, we can keep track of what was requested and when. :) Will that be OK with you? You can approach @nliber for the technicalities of submitting both R25, R26 to the same ML.

[mattreecebentley]

Cool, sounds good- Nevin says there's no issue with any of that :) M

[mattreecebentley]

Done.

[wg21bot]

P0447R24 Introduction of std::hive to the standard library (Matt Bentley)

[wg21bot]

P0447R25 Introduction of std::hive to the standard library (Matt Bentley)

[inbal2l]

P0447R26 was forwarded to LWG on LEWG 2023 December electronic poll (P3054R0)