This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement the changes to node-based containers from P1206 (`ranges::to`):
ClosedPublic

Authored by var-const on May 4 2023, 2:37 AM.

Details

Summary
  • 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)

Diff Detail

Event Timeline

var-const created this revision.May 4 2023, 2:37 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 4 2023, 2:37 AM
var-const requested review of this revision.May 4 2023, 2:37 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 4 2023, 2:37 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 519403.May 4 2023, 2:45 AM

Add forgotten SFINAE checks for sequence containers (for list and forward_list).

ldionne requested changes to this revision.Jul 7 2023, 1:32 PM
ldionne added a subscriber: ldionne.

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.

This revision now requires changes to proceed.Jul 7 2023, 1:32 PM
var-const updated this revision to Diff 540623.Jul 14 2023, 8:02 PM
var-const marked 8 inline comments as done.

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.

var-const updated this revision to Diff 540629.Jul 14 2023, 8:42 PM
var-const marked an inline comment as done.

Address the remaining feedback.

var-const updated this revision to Diff 540630.Jul 14 2023, 8:42 PM

Rebase.

libcxx/include/unordered_map
1643

Thanks! This exposed a few issues.

Fix the CI.

ldionne accepted this revision.Jul 17 2023, 11:19 AM

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.

This revision is now accepted and ready to land.Jul 17 2023, 11:19 AM
var-const updated this revision to Diff 541292.Jul 17 2023, 6:13 PM

Address feedback, rebase, try to fix the CI.

var-const updated this revision to Diff 541296.Jul 17 2023, 6:20 PM
var-const marked an inline comment as done.

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).

Poke the CI.

Fix bad merge.

Undo the forwarding change for now.