Go back to using DenseMapInfo<T>::isEqual instead of operator== in SmallSetVector

[etcwilde]

Summary

SmallSetVector used to use find and insert from from the DenseSet (using DenseMapInfo) to determine equality. Some recent changes (https://reviews.llvm.org/D152497) added a call to std::find, resulting in the use of operator==, which changes semantic behavior of the set. This change changes it back to use DenseMapInfo<value_type>::isEqual to determine equality without requiring operator== be implemented on the type.

[etcwilde]

llvm/include/llvm/ADT/SetVector.h

271–272

We can probably reduce this entire function down to a call to contains since that returns a boolean and this only returns 0 or 1. Thoughts?

[efriedma]

Hash tables don't use hash-value equality; hash collisions are a thing.

[0xdc03]

Adding onto what @efriedma said, if you do want to use hash-value equality I would suggest having value equality as well, chained using &&. Given that the "small" functionality is meant to prevent us from having to compute a hash value in the first place, I would also suggest you to measure this change on the compile time tracker, although I don't expect it to make the performance better especially because this is quite a performance-sensitive part of code...

llvm/include/llvm/ADT/SetVector.h

271–272

That makes sense to me, the reason I didn't do that was to keep the diff as insertions-only and the name count also confused me.

[etcwilde]

Sorry, should have used the the in the DenseMapInfo<T>::isEqual.

So for background, the issue that I'm running into right now is two-fold, this container used to accept types that didn't necessarily have equality (operator==) (except as defined by the DenseMapInfo), which made it very useful for storing unique non-equatable things like non-canonical types in a type system. This change means that that code doesn't compile anymore. Second, the DenseMapInfo<T>::isEqual and DenseMapInfo<T>::getHashValue from the DenseMapInfo used before aren't necessarily the same as T::operator==, which can result in different outcomes.

At least as far as I can tell, DenseMapInfo<T>::isEqual in find_if should result in the same result as before. Is there an issue with using going back to DenseMapInfo<T>::isEqual over T::operator==?

[nikic]

SetVector is templated over the set type, so using DenseMapInfo is not great.

In D156005#4524638, @etcwilde wrote:

Sorry, should have used the the in the DenseMapInfo<T>::isEqual.

So for background, the issue that I'm running into right now is two-fold, this container used to accept types that didn't necessarily have equality (operator==) (except as defined by the DenseMapInfo), which made it very useful for storing unique non-equatable things like non-canonical types in a type system. This change means that that code doesn't compile anymore. Second, the DenseMapInfo<T>::isEqual and DenseMapInfo<T>::getHashValue from the DenseMapInfo used before aren't necessarily the same as T::operator==, which can result in different outcomes.

My 2c here is that if you are implementing DenseMapInfo for a type, it needs to match operator== behavior. The only differences it should have from operator== is potentially different handling for empty / tombstone keys.

If you want to use a DenseMap with a different comparison criterion (or over a type that is not inherently comparable), then you should not implement DenseMapInfo for that type, but instead provide a separate DenseMapInfo implementation.

For example, see https://github.com/llvm/llvm-project/blob/c51c607dfc6388050ed1381a32089cd08a36ff9a/clang/include/clang/Sema/Weak.h#L37, which defines DenseMapInfoByAliasOnly for a type that is intentionally not comparable. You can see how it gets use (incidentally inside a SetVector) here: https://github.com/llvm/llvm-project/blob/c51c607dfc6388050ed1381a32089cd08a36ff9a/clang/include/clang/Sema/Sema.h#L1128 This sounds like it would be the proper thing to do in your case.

However, you can also just disable the optimization by passing N = 0 to SetVector (which is the default if you're not going through SmallSetVector). Using SetVector<T, SmallVector<T, N>, SmallDenseSet<T, N>> should give you exactly the same behavior as previously.

[etcwilde]

Updating to use the DenseMapInfo implementation of isEqual instead of the hash value to ensure we're using the same semantics that DenseMap/DenseSet use to determine equality.

[etcwilde]

Adding test that fails to build with current implementation that used to build with original SetVector insert and contains implementation.

[efriedma]

Not sure the current version addresses comments from @nikic

llvm/include/llvm/ADT/SetVector.h

 /// number of elements upto which a linear scan over the Vector will be used
 /// when searching for elements instead of checking Set, due to it being better
 /// for performance. A value of 0 means that this mode of operation is not used,
 /// and is the default value.
 template <typename T, typename Vector = std::vector<T>,
           typename Set = DenseSet<T>, unsigned N = 0>
 class SetVector {
   // Much like in SmallPtrSet, this value should not be too high to prevent
-  // excessively long linear scans from occuring.
+  // excessively long linear scans from occurring.
   static_assert(N <= 32, "Small size should be less than or equal to 32!");
 
 public:
   using value_type = typename Vector::value_type;
   using key_type = typename Set::key_type;
   using reference = value_type &;
   using const_reference = const value_type &;
   using set_type = Set;
const_reference operator[](size_type n) const {
     return vector_[n];
   }
 
   /// Insert a new element into the SetVector.
   /// \returns true if the element was inserted into the SetVector.
   bool insert(const value_type &X) {
     if constexpr (canBeSmall())
       if (isSmall()) {
-        if (llvm::find(vector_, X) == vector_.end()) {
+        auto comparator = [&X](const value_type &element) -> bool {
+          return llvm::DenseMapInfo<value_type>::isEqual(X, element);
+        };
+        if (llvm::find_if(vector_, comparator) == vector_.end()) {
           vector_.push_back(X);
           if (vector_.size() > N)
             makeBig();
           return true;
         }
         return false;
       }
 
if (I == vector_.end())
       return false;
     vector_.erase(I, vector_.end());
     return true;
   }
 
   /// Check if the SetVector contains the given key.
   bool contains(const key_type &key) const {
     if constexpr (canBeSmall())
-      if (isSmall())
-        return is_contained(vector_, key);
+      if (isSmall()) {
+        auto comparator = [&key](const value_type &element) -> bool {
+          return llvm::DenseMapInfo<value_type>::isEqual(key, element);
+        };
+        return llvm::find_if(vector_, comparator) != vector_.end();
+      }
 
     return set_.find(key) != set_.end();
   }
 
   /// Count the number of elements of a given key in the SetVector.
   /// \returns 0 if the element is not in the SetVector, 1 if it is.
   size_type count(const key_type &key) const {
-    if constexpr (canBeSmall())
-      if (isSmall())
-        return is_contained(vector_, key);
-
-    return set_.count(key);
+    return contains(key);
   }
 
   /// Completely clear the SetVector
   void clear() {
     set_.clear();
     vector_.clear();
   }
 

llvm/unittests/ADT/SetVectorTest.cpp

TEST(SetVector, ConstPtrKeyTest) {
   EXPECT_TRUE(S.set_union(T));
   EXPECT_TRUE(S.contains(&m));
   EXPECT_TRUE(S.contains((const int *)&m));
 
   S.set_subtract(T);
   EXPECT_FALSE(S.contains(&j));
   EXPECT_FALSE(S.contains((const int *)&j));
 }
+
+struct NonEquatableType {
+  int Value;
+  bool operator==(const NonEquatableType &) const = delete;
+
+  NonEquatableType(int Value): Value(Value) {}
+};
+
+namespace llvm {
+template <> struct DenseMapInfo<NonEquatableType> {
+  static inline NonEquatableType getEmptyKey() { return NonEquatableType(-1); }
+  static inline NonEquatableType getTombstoneKey() {
+    return NonEquatableType(-2);
+  }
+  static unsigned getHashValue(const NonEquatableType &Val) {
+    return Val.Value;
+  }
+
+  static bool isEqual(const NonEquatableType &LHS,
+                      const NonEquatableType &RHS) {
+    return LHS.Value == RHS.Value;
+  }
+};
+} // namespace llvm
+
+TEST(SmallSetVector, InsertNonEquatableType) {
+  SmallSetVector<NonEquatableType, 2> S;
+  S.insert(NonEquatableType(1));
+  S.insert(NonEquatableType(2));
+  S.insert(NonEquatableType(3));
+  EXPECT_TRUE(S.contains(NonEquatableType(2)));
+  EXPECT_FALSE(S.insert(NonEquatableType(3)));
+}