This is an archive of the discontinued LLVM Phabricator instance.

[ADT] Add deduction guide for iterator_range
ClosedPublic

Authored by steakhal on Jun 13 2023, 11:42 PM.

Diff Detail

Event Timeline

steakhal created this revision.Jun 13 2023, 11:42 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 13 2023, 11:42 PM
Herald added a subscriber: martong. · View Herald Transcript
steakhal requested review of this revision.Jun 13 2023, 11:42 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 13 2023, 11:42 PM

I have also considered adding ADL lookup support part of this patch, but that's slightly more complicated if you want to keep the ubiquitously included iterator_range header "small", I cannot simply include STLExtras here to gain the adl_begin() and adl_end().
I have considered to basically "duplicate" the adl_begin and adl_end code, but I'm still not sure.

To do that, I'd need the type_traits header for sure for the SFINAE, which again would bloat this header. It would look something like this that way:

I haven't measured the impact of this on the build times.

I have also considered adding ADL lookup support part of this patch, but that's slightly more complicated if you want to keep the ubiquitously included iterator_range header "small", I cannot simply include STLExtras here to gain the adl_begin() and adl_end().
I have considered to basically "duplicate" the adl_begin and adl_end code, but I'm still not sure.

I'd be more in favor of pulling adl_begin/end into a separate header and reusing it from both places, if STLExtras is too big of a dumping ground.

To do that, I'd need the type_traits header for sure for the SFINAE, which again would bloat this header. It would look something like this that way:

A question would be: How many translation units include iterator_range and don't transitively include type_traits somewhere along the way anyway?

steakhal updated this revision to Diff 532384.EditedJun 17 2023, 4:25 AM
  • Factor out ADL utilities
  • Add SFINAE check for iterator_range constructor

I measured the clean build time before and after the patch on my Ubuntu 22.04.1 system.
I used gcc (Ubuntu 11.3.0-1ubuntu1~22.04.1) 11.3.0 with the mold linker.

Baseline:

time cmake -S llvm -B build/rel-old -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra" -DCMAKE_BUILD_TYPE=Release
real    0m8.446s
user    0m6.587s
sys     0m1.691s

time ninja -C build/rel-old/
[5445/5445]
real    19m23.414s   1163.414s
user    431m9.467s
sys     18m20.037s

With this patch:

time cmake -S llvm -B build/rel-new -DLLVM_ENABLE_PROJECTS="clang;clang-tools-extra" -DCMAKE_BUILD_TYPE=Release
real    0m8.943s
user    0m6.956s
sys     0m1.818s

time ninja -C build/rel-new/
[5445/5445]
real    19m32.817s   1172.817s
user    433m30.939s
sys     18m20.295s

This means that we would have 0.808224759 % compile time regression with this patch. Is it acceptable?
(I only run the measurement once)

@IncludeGuardian, I've just seen a patch about improving compile times. I have no clue how to properly measure such things.
Could you also have a look at this patch, if I can include new headers from the iterator_range header?

dblaikie accepted this revision.Jun 26 2023, 3:06 PM

Seesm fine to me - measurement's probably in the noise.

This revision is now accepted and ready to land.Jun 26 2023, 3:06 PM
This revision was landed with ongoing or failed builds.Jul 3 2023, 12:30 AM
This revision was automatically updated to reflect the committed changes.
steakhal added a subscriber: asb.Jul 3 2023, 1:59 AM

@asb This commit might be interesting for LLVM-weekly.

barannikov88 added inline comments.
llvm/include/llvm/ADT/iterator_range.h
28

Would go in line with the standard name https://en.cppreference.com/w/cpp/types/is_convertible

steakhal added inline comments.Jul 3 2023, 2:33 AM
llvm/include/llvm/ADT/iterator_range.h
28

I tried to use the llvm's implementation (libcxx) of std::is_convertible here but it didn't work.
I managed to replace the requires with plain-old SFINAE, and make my implementation pass all the libcxx tests but still failed to compile the llvm-project after this.

About the typo, yea, my bad. I should have fixed that.
How about if we wait for some time to see if at least the bots won't find any semantic issues? After a couple of days, we can fix the typo as well. Otherwise, we would risk merge conflicts in case we need to revert this.

barannikov88 added inline comments.Jul 3 2023, 3:11 AM
llvm/include/llvm/ADT/iterator_range.h
28

Yeah, sounds fine. I missed it was closed.

steakhal marked 2 inline comments as done.Jul 3 2023, 7:15 AM
steakhal added inline comments.
llvm/include/llvm/ADT/iterator_range.h
28
tahonermann added inline comments.
llvm/include/llvm/ADT/iterator_range.h
49–51

Static analysis flagged this code because c is forwarded twice thereby introducing the possibility that the second callee attempts to move from a moved-from object.

In practice, this code is unlikely to be problematic because a container/range that supports moving an rvalue object into the iterator returned by its associated begin() and which has an end() that is sensitive to the identity or state of the range object would be a very strange thing indeed (I can imagine a range that models an input-range that supports moving a range object into the iterator returned by begin(), but then end() would almost certainly return a sentinel that is independent of the identity or state of the range object). Still, a double forward like this is quite strange.

There is some offline discussion happening that might result in a code review being submitted to remove one or both of the std::forward() calls.

steakhal marked an inline comment as done.Aug 8 2023, 1:46 PM
steakhal added inline comments.
llvm/include/llvm/ADT/iterator_range.h
49–51

Makes sense. The intention was to select the right overload, but indeed, its confusing.
Submit a patch for simply removing both forwards. I don't expect constructing an iterator to suddenly consume the container anyway. It wouldn't make sense.

andrew.w.kaylor added a subscriber: andrew.w.kaylor.
andrew.w.kaylor added inline comments.
llvm/include/llvm/ADT/iterator_range.h
49–51

I've uploaded D157453 to remove the std::forward.