[ADT] Make llvm::is_contained call member `contains` or `find` when available

[kuhar]

Summary

This makes it so that calling llvm::is_contained no longer degrades
performance over member contains, even though both have almost identical
names. This would be the case in most set/map classes that can check for
an element being present in O(1) or O(log n) time vs. linear scan with
std::find. For C++17 maps/sets without .contains, use .find when available,
falling back to a linear scan with std::find.

I also considered detecting member contains and triggering a
static_assert instead, but decided against it because it's just as easy
to do the right thing and call .contains. This would also make some code fail
only when compiled in the C++20 mode when more container types come with
.contains member functions.

This was actually already the case with CommandLine.h calling is_contained
on SmallPtrSet and in a recent BOLT patch.

[dblaikie]

Looks good

[nikic]

I also considered detecting member contains and triggering a
static_assert instead, but decided against it because it's just as easy
to do the right thing and call .contains.

I think I would prefer this option, so we keep the ability to distinguish O(1) contains from O(n) is_contained at a glance.

[dblaikie]

In D146061#4193557, @nikic wrote:

I also considered detecting member contains and triggering a
static_assert instead, but decided against it because it's just as easy
to do the right thing and call .contains.

I think I would prefer this option, so we keep the ability to distinguish O(1) contains from O(n) is_contained at a glance.

Yeah, that's fair - I'm OK with that too/see the value there. Only issue is in generic code where you might not know the type of a container.

[dblaikie]

In D146061#4193581, @dblaikie wrote:

In D146061#4193557, @nikic wrote:

I also considered detecting member contains and triggering a
static_assert instead, but decided against it because it's just as easy
to do the right thing and call .contains.

I think I would prefer this option, so we keep the ability to distinguish O(1) contains from O(n) is_contained at a glance.

Yeah, that's fair - I'm OK with that too/see the value there. Only issue is in generic code where you might not know the type of a container.

I'd certainly discourage uses of is_contained where the type is known to have a contains member function - maybe the generic code cases are so rare they're not worth leaving this generic functionality in where it's more likely to reduce readability in the non-generic cases.

[kuhar]

In D146061#4193557, @nikic wrote:

I also considered detecting member contains and triggering a
static_assert instead, but decided against it because it's just as easy
to do the right thing and call .contains.

I think I would prefer this option, so we keep the ability to distinguish O(1) contains from O(n) is_contained at a glance.

The way I was thinking about this is that usually the C++ standard specifies algorithms in terms of worst-case complexity and anything better is a bonus. In a completely generic context, as a user of is_contained my expectation would be that it's O(n) or better.

This situation is a bit more complicated because C++20 is added member contains functions to (unordered_)set/map, so a static assertion would cause compilation failures with some compiler flags and not the other ones. IMO this is not a huge deal but probably annoying because I'd expect the Hyrum law to apply and API usages of is_contained with these containers to creep in over time. The current patch makes this API instability problem better , as there'll be no need to have ways to essentially do the same thing.

Another thing I intended to change was to make llvm::find call member find when present. This would make it and also llvm::is_contained O(1)/O(log n) even for types that do not expose .contains today. The alternative would be to disallow llvm::find over container with member find as well, but this doesn't seem like the best choice for me.

[kuhar]

This is also consistent with how new C++ range functions are defined, e.g., https://en.cppreference.com/w/cpp/ranges/size that calls member .size when available and does iterator subtraction otherwise.

[dblaikie]

In D146061#4193671, @kuhar wrote:

In D146061#4193557, @nikic wrote:

I also considered detecting member contains and triggering a
static_assert instead, but decided against it because it's just as easy
to do the right thing and call .contains.

I think I would prefer this option, so we keep the ability to distinguish O(1) contains from O(n) is_contained at a glance.

The way I was thinking about this is that usually the C++ standard specifies algorithms in terms of worst-case complexity and anything better is a bonus. In a completely generic context, as a user of is_contained my expectation would be that it's O(n) or better.

This situation is a bit more complicated because C++20 is added member contains functions to (unordered_)set/map, so a static assertion would cause compilation failures with some compiler flags and not the other ones. IMO this is not a huge deal but probably annoying because I'd expect the Hyrum law to apply and API usages of is_contained with these containers to creep in over time. The current patch makes this API instability problem better , as there'll be no need to have ways to essentially do the same thing.

Yeah, that'd be unfortunate indeed.

Another thing I intended to change was to make llvm::find call member find when present. This would make it and also llvm::is_contained O(1)/O(log n) even for types that do not expose .contains today. The alternative would be to disallow llvm::find over container with member find as well, but this doesn't seem like the best choice for me.

This one is trickier for me - llvm::is_contained doesn't have a nearby standard equivalent ,so we can choose its behavior more flexibly. But std::find(iter, iter, value) exists in the standard library and there's value in llvm::find(range, value) being pretty close to the same/identical to the standard version - which doesn't optimize to member-find when available.

I would be inclined not to include a member-find optimization in llvm::find for that reason.

I'm undecided about whether that tips in favor of not having member-contains in llvm::is_contained.

[dblaikie]

In D146061#4193697, @kuhar wrote:

This is also consistent with how new C++ range functions are defined, e.g., https://en.cppreference.com/w/cpp/ranges/size that calls member .size when available and does iterator subtraction otherwise.

Fair - that a bunch of free function ranges functions are like this, delegating to members where available maybe tilts things in that direction.

[kuhar]

In D146061#4194439, @dblaikie wrote:

This one is trickier for me - llvm::is_contained doesn't have a nearby standard equivalent ,so we can choose its behavior more flexibly. But std::find(iter, iter, value) exists in the standard library and there's value in llvm::find(range, value) being pretty close to the same/identical to the standard version - which doesn't optimize to member-find when available.

I would be inclined not to include a member-find optimization in llvm::find for that reason.

I'm undecided about whether that tips in favor of not having member-contains in llvm::is_contained.

Then I propose we frame it like this: llvm::is_contained is the (llvm-only) canonical/generic way to check if an element is in the range. We make it 'do the right thing' by default and use .contains, .find, and std::find when available, in this order of preference. This will make it work with C++17 containers that do not have .contains, llvm and C++20+ containers with .contains, and any other range via a linear scan. WDYT?

[kazu]

In D146061#4194466, @kuhar wrote:

Then I propose we frame it like this: llvm::is_contained is the (llvm-only) canonical/generic way to check if an element is in the range.

How about something like the (llvm-only) canonical/generic way to check if an element is in the range if a template needs to work with containers that may or may not have the .contains method (like an array and a set).

I'm saying this because I personally find Foo.contains(X) a little more readable than llvm::is_contained(Foo, X), and I would like our code base to look friendly to people new to the LLVM project (with the use of function names present in C++ standards) wherever reasonable to do so. (Sure, std::set::contains is very new, but I expect people to become familiar with this over time.)

[kuhar]

In D146061#4194551, @kazu wrote:

In D146061#4194466, @kuhar wrote:

Then I propose we frame it like this: llvm::is_contained is the (llvm-only) canonical/generic way to check if an element is in the range.

How about something like the (llvm-only) canonical/generic way to check if an element is in the range if a template needs to work with containers that may or may not have the .contains method (like an array and a set).

I'm saying this because I personally find Foo.contains(X) a little more readable than llvm::is_contained(Foo, X), and I would like our code base to look friendly to people new to the LLVM project (with the use of function names present in C++ standards) wherever reasonable to do so. (Sure, std::set::contains is very new, but I expect people to become familiar with this over time.)

Sure, I agree with that. If I have map with a known type like DenseMap I'd rather call .contains(x) directly too. But this is not possible with C++17 containers std::, so I'd argue that until then is_contained(container, x) is more readable than something like container.find(x) != container.end().

[nikic]

In D146061#4194752, @kuhar wrote:

Sure, I agree with that. If I have map with a known type like DenseMap I'd rather call .contains(x) directly too. But this is not possible with C++17 containers std::, so I'd argue that until then is_contained(container, x) is more readable than something like container.find(x) != container.end().

I don't think we should promote usage of is_contained() for anything but the linear scan case. I don't want to be left guessing whether this is_contained() is a linear scan, or just a slightly different way to write container.find().

[kuhar]

In D146061#4194853, @nikic wrote:

In D146061#4194752, @kuhar wrote:

Sure, I agree with that. If I have map with a known type like DenseMap I'd rather call .contains(x) directly too. But this is not possible with C++17 containers std::, so I'd argue that until then is_contained(container, x) is more readable than something like container.find(x) != container.end().

I don't think we should promote usage of is_contained() for anything but the linear scan case. I don't want to be left guessing whether this is_contained() is a linear scan, or just a slightly different way to write container.find().

I can see this being prefered from the perspective of an experience llvm developer, but on the other hand I saw a lot of code that ended up using is_contained and llvm::find with map/set types. I found fixing those inefficiencies and re-explaining this to folks needlessly time consuming. I think defaulting to the more efficient implementation of containment check is the way to go to avoid those non-obvious performance issues, and the member functions we would delegate to are not surprising at all.

[kuhar]

Delegate to .find when .contains is not available. Improve function documentation.

[kuhar]

Fix a typo

[kuhar]

Here's an example that landed minutes ago in the tree: https://reviews.llvm.org/D145464

[Amir]

I’m fully supportive of this change. BOLT uses this interface which helps maintainabilty as it clearly states the intent and is robust wrt container type change. It’s a clear win to also have the same runtime characteristics as find.

[MaskRay]

In D146061#4194866, @kuhar wrote:

In D146061#4194853, @nikic wrote:

In D146061#4194752, @kuhar wrote:

Sure, I agree with that. If I have map with a known type like DenseMap I'd rather call .contains(x) directly too. But this is not possible with C++17 containers std::, so I'd argue that until then is_contained(container, x) is more readable than something like container.find(x) != container.end().

I don't think we should promote usage of is_contained() for anything but the linear scan case. I don't want to be left guessing whether this is_contained() is a linear scan, or just a slightly different way to write container.find().

I can see this being prefered from the perspective of an experience llvm developer, but on the other hand I saw a lot of code that ended up using is_contained and llvm::find with map/set types. I found fixing those inefficiencies and re-explaining this to folks needlessly time consuming. I think defaulting to the more efficient implementation of containment check is the way to go to avoid those non-obvious performance issues, and the member functions we would delegate to are not surprising at all.

Agreed with the analysis.

llvm/unittests/ADT/STLExtrasTest.cpp

1039

Add a find to show that contains is preferred.

[kuhar]

Update test to check that .contains(x) is preferred over .find(x) when both are available.
Use std::find instead of llvm::find to make the behavior as clear as possible.

[nikic]

In D146061#4194912, @kuhar wrote:

Here's an example that landed minutes ago in the tree: https://reviews.llvm.org/D145464

Oh wow, that's terrible. I guess I withdraw my objection then, I didn't realize that people don't know what is_contained() does.

[kazu]

LGTM. I like the fallback mechanism. We prefer to use X.contains(), but if that's not possible (or people just randomly call llvm::is_contained), llvm::is_contained is there to do the right thing for you.

[uabelho]

I ran into a fun thing with this.
In my downstream backend we have a class where we apparently implemented "contains" by calling "llvm::is_contained".
With this patch that's not a very good idea as it then just calls itself over and over again.

Just a heads up in case someone else sees a hanging compiler and bisects back to this patch.

llvm/include/llvm/ADT/STLExtras.h

 
 /// Provide wrappers to std::move which take ranges instead of having to
 /// pass begin/end explicitly.
 template <typename R, typename OutputIt>
 OutputIt move(R &&Range, OutputIt Out) {
   return std::move(adl_begin(Range), adl_end(Range), Out);
 }
 
-/// Wrapper function around std::find to detect if an element exists
-/// in a container.
+namespace detail {
+template <typename Range, typename Element>
+using check_has_member_contains_t =
+    decltype(std::declval<Range &>().contains(std::declval<const Element &>()));
+
+template <typename Range, typename Element>
+static constexpr bool HasMemberContains =
+    is_detected<check_has_member_contains_t, Range, Element>::value;
+
+template <typename Range, typename Element>
+using check_has_member_find_t =
+    decltype(std::declval<Range &>().find(std::declval<const Element &>()) !=
+             std::declval<Range &>().end());
+
+template <typename Range, typename Element>
+static constexpr bool HasMemberFind =
+    is_detected<check_has_member_find_t, Range, Element>::value;
+
+} // namespace detail
+
+/// Returns true if \p Element is found in \p Range. Delegates the check to
+/// either `.contains(Element)`, `.find(Element)`, or `std::find`, in this
+/// order of preference. This is intended as the canonical way to check if an
+/// element exists in a range in generic code or range type that does not
+/// expose a `.contains(Element)` member.
 template <typename R, typename E>
 bool is_contained(R &&Range, const E &Element) {
-  return std::find(adl_begin(Range), adl_end(Range), Element) != adl_end(Range);
+  if constexpr (detail::HasMemberContains<R, E>)
+    return Range.contains(Element);
+  else if constexpr (detail::HasMemberFind<R, E>)
+    return Range.find(Element) != Range.end();
+  else
+    return std::find(adl_begin(Range), adl_end(Range), Element) !=
+           adl_end(Range);
 }
 
 /// Returns true iff \p Element exists in \p Set. This overload takes \p Set as
 /// an initializer list and is `constexpr`-friendly.
 template <typename T, typename E>
 constexpr bool is_contained(std::initializer_list<T> Set, const E &Element) {
   // TODO: Use std::find when we switch to C++20.
   for (const T &V : Set)

llvm/include/llvm/Analysis/LoopInfoImpl.h

for (iterator I = begin(), E = end(); I != E; ++I)
     for (block_iterator BI = (*I)->block_begin(), BE = (*I)->block_end();
          BI != BE; ++BI) {
       assert(contains(*BI) &&
              "Loop does not contain all the blocks of a subloop!");
     }
 
   // Check the parent loop pointer.
   if (ParentLoop) {
-    assert(is_contained(*ParentLoop, this) &&
+    assert(is_contained(ParentLoop->getSubLoops(), this) &&
            "Loop is not a subloop of its parent!");
   }
 #endif
 }
 
 /// verifyLoop - Verify loop structure of this loop and all nested loops.
 template <class BlockT, class LoopT>
 void LoopBase<BlockT, LoopT>::verifyLoopNest(

llvm/unittests/ADT/STLExtrasTest.cpp

TEST(STLExtrasTest, IsContainedInitializerList) {
 
   EXPECT_TRUE(is_contained({1, 2, 3, 4}, 3));
   EXPECT_FALSE(is_contained({1, 2, 3, 4}, 5));
 
   static_assert(is_contained({1, 2, 3, 4}, 3), "It's there!");
   static_assert(!is_contained({1, 2, 3, 4}, 5), "It's not there :(");
 }
 
+TEST(STLExtrasTest, IsContainedMemberContains) {
+  // Check that `llvm::is_contained` uses the member `.contains()` when
+  // available. Check that `.contains()` is preferred over `.find()`.
+  struct Foo {
+    bool contains(int) const {
+      ++NumContainsCalls;
+      return ContainsResult;
+    }
+    int *begin() { return nullptr; }
+    int *end() { return nullptr; }
+    int *find(int) { return nullptr; }
+
+    bool ContainsResult = false;
+    mutable unsigned NumContainsCalls = 0;
+  } Container;
+
+  EXPECT_EQ(Container.NumContainsCalls, 0u);
+  EXPECT_FALSE(is_contained(Container, 1));
+  EXPECT_EQ(Container.NumContainsCalls, 1u);
+
+  Container.ContainsResult = true;
+  EXPECT_TRUE(is_contained(Container, 1));
+  EXPECT_EQ(Container.NumContainsCalls, 2u);
+}
+
+TEST(STLExtrasTest, IsContainedMemberFind) {
+  // Check that `llvm::is_contained` uses the member `.find(x)` when available.
+  struct Foo {
+    auto begin() { return Data.begin(); }
+    auto end() { return Data.end(); }
+    auto find(int X) {
+      ++NumFindCalls;
+      return std::find(begin(), end(), X);
+    }
+
+    std::vector<int> Data;
+    mutable unsigned NumFindCalls = 0;
+  } Container;
+
+  Container.Data = {1, 2, 3};
+
+  EXPECT_EQ(Container.NumFindCalls, 0u);
+  EXPECT_TRUE(is_contained(Container, 1));
+  EXPECT_TRUE(is_contained(Container, 3));
+  EXPECT_EQ(Container.NumFindCalls, 2u);
+
+  EXPECT_FALSE(is_contained(Container, 4));
+  EXPECT_EQ(Container.NumFindCalls, 3u);
+}
+
 TEST(STLExtrasTest, addEnumValues) {
   enum A { Zero = 0, One = 1 };
   enum B { IntMax = INT_MAX, ULongLongMax = ULLONG_MAX };
   enum class C : unsigned { Two = 2 };
 
   // Non-fixed underlying types, with same underlying types
   static_assert(addEnumValues(Zero, One) == 1,
                 "addEnumValues(Zero, One) failed.");