- add the from_range_t constructors and the related deduction guides;
- add the insert_range/assign_range/etc. member functions.
(Note: this patch is split from https://reviews.llvm.org/D142335)
Details
Details
- Reviewers
ldionne - Group Reviewers
Restricted Project - Commits
- rGef70fe4d264d: [libc++][ranges] Implement the changes to node-based containers from P1206…
Diff Detail
Diff Detail
- Repository
- rG LLVM Github Monorepo
Event Timeline
Comment Actions
Thanks! I don't have a lot of comments, the patch is quite large but there's a lot of mechanical changes that don't differ from class to class, which makes this easier to review.
| libcxx/include/list | ||
|---|---|---|
| 786–788 | Maybe we can use prepend_range(...) here instead? It would make it the same as what we do for forward_list. | |
| 918 | IDK if you should be using insert(...) here. However, either all of these new methods should lower to insert(...), or none of them should (and then they should probably be for loops with emplace_foo(...)). | |
| libcxx/include/map | ||
| 1125 | __tree also has __assign_unique(_ForwardIterator, _ForwardIterator); available, I'm wondering whether that should be used instead. I think we have some benchmarks for std::map, it would be worth adding some simple benchmark for the from_range constructor and checking which approach is fastest. | |
| libcxx/include/unordered_map | ||
| 1643 | Can you validate whether you tested these enable_ifs in your deduction guide test? I think you want to add that stuff to AssociativeContainerDeductionGuidesSfinaeAway. | |
| libcxx/test/std/containers/associative/from_range_associative_containers.h | ||
| 28 | This concept doesn't seem to cover ctors of the form map(from_range_t, R&& rg, const Allocator& a)). Only those that specify the comparator. | |
| 172 | Same comment as above. | |
| libcxx/test/std/containers/associative/multiset/multiset.cons/from_range.pass.cpp | ||
| 19 | Uber-nitpick but we generally try to have the synopsis comment above the includes. Applies here and elsewhere. | |
| libcxx/test/std/containers/insert_range_maps_sets.h | ||
| 254 | Or something similar? Full has a connotation that we don't want to have here. It kinda implies "no more capacity", to steal your words. FullContainer & friends should also change accordingly. | |
| libcxx/test/std/containers/unord/unord.set/unord.set.cnstr/deduct.pass.cpp | ||
| 260–264 | If this is true, this would need a LWG issue. We can add it as a comment here. | |
Comment Actions
Address most feedback.
| libcxx/include/list | ||
|---|---|---|
| 786–788 | I copied this implementation from the existing constructor taking 2 iterators. The amount of work between the two possible implementations is comparable, but the implementation relying on insertion contains exception cleanup code that isn't in emplace_back. However, despite that, a quick benchmark shows that the difference between the two implementations seems to be within fluctuation (attached below). Given these results, prepend_range seems preferable as it's slightly simpler and also consistent with forward_list like you mentioned. However, let's discuss whether we want the extra exception cleanup code. prepend_range version: ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BM_ConstructRange/list_char/1024 20033 ns 20008 ns 36195 BM_ConstructRange/list_size_t/1024 20726 ns 20704 ns 35864 BM_ConstructRange/list_string/1024 105972 ns 105897 ns 6653 ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BM_ConstructRange/list_char/1024 20545 ns 20520 ns 30527 BM_ConstructRange/list_size_t/1024 20966 ns 20949 ns 35016 BM_ConstructRange/list_string/1024 106834 ns 106774 ns 6637 ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BM_ConstructRange/list_char/1024 20083 ns 20069 ns 36502 BM_ConstructRange/list_size_t/1024 20106 ns 20090 ns 35770 BM_ConstructRange/list_string/1024 105067 ns 104821 ns 6891 ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BM_ConstructRange/list_char/1024 19772 ns 19754 ns 36000 BM_ConstructRange/list_size_t/1024 21022 ns 20775 ns 34938 BM_ConstructRange/list_string/1024 104036 ns 103966 ns 6803 emplace_back version: ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BM_ConstructRange/list_char/1024 20099 ns 20076 ns 35770 BM_ConstructRange/list_size_t/1024 20770 ns 20742 ns 35921 BM_ConstructRange/list_string/1024 108025 ns 107948 ns 6793 ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BM_ConstructRange/list_char/1024 19628 ns 19598 ns 36649 BM_ConstructRange/list_size_t/1024 19334 ns 19313 ns 36364 BM_ConstructRange/list_string/1024 108159 ns 108050 ns 6654 ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BM_ConstructRange/list_char/1024 19960 ns 19945 ns 36955 BM_ConstructRange/list_size_t/1024 19963 ns 19943 ns 35697 BM_ConstructRange/list_string/1024 108664 ns 108599 ns 6715 ----------------------------------------------------------------------------- Benchmark Time CPU Iterations ----------------------------------------------------------------------------- BM_ConstructRange/list_char/1024 19666 ns 19651 ns 36989 BM_ConstructRange/list_size_t/1024 19662 ns 19642 ns 35865 BM_ConstructRange/list_string/1024 106818 ns 106769 ns 6660 | |
| 918 | Now that the constructor delegates to prepend_range, I think all the new methods are consistent -- please let me know if I'm missing something. | |
| libcxx/include/map | ||
| 1125 | Unfortunately, this won't work with the current implementation of __assign_unique (not sure how easy it would be to fix) because it requires the same value_type between the tree and the range: static_assert((is_same<_ItValueType, __container_value_type>::value),
"__assign_unique may only be called with the containers value type");I was curious whether it would be worthwhile to only use __assign_unique when the types are the same, but a quick benchmark seems to show it's slightly slower: insert version: ------------------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------------------ BM_ConstructorRange_MapSize=10 28.9 ns 28.8 ns 24417130 BM_ConstructorRange_MapSize=100 36.5 ns 36.5 ns 19146900 BM_ConstructorRange_MapSize=1000 41.7 ns 41.6 ns 16424000 BM_ConstructorRange_MapSize=10000 44.7 ns 43.8 ns 16480000 BM_ConstructorRange_MapSize=100000 49.6 ns 49.5 ns 13600000 BM_ConstructorRange_MapSize=1000000 61.3 ns 61.3 ns 11000000 ------------------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------------------ BM_ConstructorRange_MapSize=10 29.1 ns 29.1 ns 24092580 BM_ConstructorRange_MapSize=100 36.6 ns 36.6 ns 19129200 BM_ConstructorRange_MapSize=1000 42.1 ns 42.1 ns 16727000 BM_ConstructorRange_MapSize=10000 43.0 ns 43.0 ns 16330000 BM_ConstructorRange_MapSize=100000 49.2 ns 49.2 ns 14200000 BM_ConstructorRange_MapSize=1000000 61.8 ns 61.6 ns 11000000 ------------------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------------------ BM_ConstructorRange_MapSize=10 28.9 ns 28.9 ns 24372670 BM_ConstructorRange_MapSize=100 36.6 ns 36.6 ns 18847000 BM_ConstructorRange_MapSize=1000 42.5 ns 42.4 ns 16661000 BM_ConstructorRange_MapSize=10000 43.3 ns 43.2 ns 16360000 BM_ConstructorRange_MapSize=100000 50.6 ns 50.5 ns 10000000 BM_ConstructorRange_MapSize=1000000 61.2 ns 61.2 ns 11000000 __assign_unique version: ------------------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------------------ BM_ConstructorRange_MapSize=10 29.0 ns 28.9 ns 23895680 BM_ConstructorRange_MapSize=100 37.4 ns 37.3 ns 18793700 BM_ConstructorRange_MapSize=1000 46.7 ns 44.1 ns 16486000 BM_ConstructorRange_MapSize=10000 49.4 ns 48.6 ns 12520000 BM_ConstructorRange_MapSize=100000 59.3 ns 58.8 ns 12100000 BM_ConstructorRange_MapSize=1000000 71.7 ns 71.3 ns 9000000 ------------------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------------------ BM_ConstructorRange_MapSize=10 28.6 ns 28.6 ns 24516420 BM_ConstructorRange_MapSize=100 37.3 ns 37.3 ns 18762400 BM_ConstructorRange_MapSize=1000 43.5 ns 43.5 ns 16397000 BM_ConstructorRange_MapSize=10000 47.2 ns 47.1 ns 14680000 BM_ConstructorRange_MapSize=100000 55.8 ns 55.7 ns 12100000 BM_ConstructorRange_MapSize=1000000 72.4 ns 72.4 ns 10000000 ------------------------------------------------------------------------------ Benchmark Time CPU Iterations ------------------------------------------------------------------------------ BM_ConstructorRange_MapSize=10 29.0 ns 29.0 ns 24206630 BM_ConstructorRange_MapSize=100 37.4 ns 37.4 ns 18692600 BM_ConstructorRange_MapSize=1000 43.5 ns 43.5 ns 16093000 BM_ConstructorRange_MapSize=10000 48.0 ns 48.0 ns 14340000 BM_ConstructorRange_MapSize=100000 60.2 ns 59.8 ns 12100000 BM_ConstructorRange_MapSize=1000000 70.2 ns 70.0 ns 10000000 | |
| libcxx/test/std/containers/unord/unord.set/unord.set.cnstr/deduct.pass.cpp | ||
| 260–264 | Long story short, there is an LWG issue to add these constructors: https://cplusplus.github.io/LWG/issue2713. It's not voted in yet, but looks like it has been making steady progress. I'm going to leave these constructors unimplemented for now so that we're consistent with the current state of the Standard. | |
Comment Actions
LGTM w/ comments applied and CI passing.
| libcxx/include/list | ||
|---|---|---|
| 786–788 | If prepend_range and the other operations have the strong exception safety guarantee, we should make sure to test that. Regarding whether to use prepend_range or not in this constructor, I think we should, but only for consistency, since the strong exception safety guarantee isn't relevant. | |
Comment Actions
Remove some unnecessary calls to std::forward
| libcxx/include/list | ||
|---|---|---|
| 786–788 | Added a test similar to what I recently added for forward_list (and also added the new range methods to the forward_list test). | |