This is an archive of the discontinued LLVM Phabricator instance.

[ADT] Add `llvm::range_size` function for generic ranges
ClosedPublic

Authored by kuhar on Mar 16 2023, 9:13 AM.

Details

Summary

This function follows std::ranges::size from C++20. It is intended
mainly for generic code that does not know the exact range type.
I did not modify the existing llvm::size function because it has a strict
guarantee of O(1) running time, and we cannot guarantee that when we delegate
size check to user-defined size functions.

Use range_size to optimize size checks in zip* and enumerate
functions. Before that, we would have to perform linear scans for ranges
without random access iterators.

This is the last change I have planned in the series that overhauls
zip* and enumerate.

Diff Detail

Event Timeline

kuhar created this revision.Mar 16 2023, 9:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 16 2023, 9:13 AM
kuhar requested review of this revision.Mar 16 2023, 9:13 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 16 2023, 9:13 AM

Would std::distance suffice?

kuhar added a comment.Mar 16 2023, 9:31 AM

Would std::distance suffice?

It does work and this is what we use in the assertions now. The issue is that this degrades to a linear scan over some iterator types (e.g., with sets/maps)

dblaikie added inline comments.Mar 16 2023, 12:37 PM
llvm/include/llvm/ADT/STLExtras.h
1770–1784

Rather than detecting both member and non-member, could we standardize on non-member, like adl_begin/adl_end works? Could expose adl_size to match adl_begin/end too, in addition to this wrapper that has the fallback to distance.

1793–1794

I'd guess this can be trivially optimized from the generic std::distance call? Maybe not worth the special case?

kuhar added inline comments.Mar 16 2023, 12:41 PM
llvm/include/llvm/ADT/STLExtras.h
1770–1784

Good idea. I wonder why std::ranges::size doesn't do it too.

1793–1794

Once we go through std::size it should cover it too. This will make this diverge from std::ranges::size but I don't think anyone will notice the difference, and our implementation will become simpler.

kuhar updated this revision to Diff 505908.Mar 16 2023, 1:02 PM

Use adl_size to simplify the implementation and reduce branching.

kuhar marked 2 inline comments as done.Mar 16 2023, 1:02 PM
zero9178 accepted this revision.Mar 21 2023, 5:01 AM

LGTM with tiny note

llvm/include/llvm/ADT/STLExtras.h
2420

Guessing you still need to rebase this ontop of https://reviews.llvm.org/D146340?
Does that happen to also fix the compiler bug from that revision or will we still require the workaround using the intializer list?

This revision is now accepted and ready to land.Mar 21 2023, 5:01 AM
kuhar added inline comments.Mar 21 2023, 7:32 AM
llvm/include/llvm/ADT/STLExtras.h
2420

Yes, this needs rebasing. I've just checked and the workaround is still necessary.

kuhar marked an inline comment as done.Mar 21 2023, 8:13 AM
dblaikie accepted this revision.Mar 21 2023, 9:33 AM

Looks good, thanks!

This revision was landed with ongoing or failed builds.Mar 21 2023, 10:00 AM
This revision was automatically updated to reflect the committed changes.