[ADT] Specialize std::swap() for SetVector

[nikic]

Summary

This is intended to address a compile-time regression from rG1eddce4177cfddc86d4696b758904443b0b4f193. A SmallPtrSet was replaced with a SetVector there, which had an unexpected large compile-time impact. It turns out that this structure is getting swapped a lot, and previously this used an optimized std::swap specialization for SmallPtrSet. Now it ends up using the default, triple-move based implementation, which is much more expensive.

This patch addresses the issue by specializing std::swap() for SetVector. I'll provide more specific compile-time numbers once I have them.

[erichkeane]

Interesting patch! I'm definitely interested in seeing the numbers. Though note this patch was made as a followup, which seems to have gotten about 1/2 of the original regression back: https://github.com/llvm/llvm-project/commit/837ca4796065ccd0ac0d20860341ac06a9645009

This makes any change to SmallSetVector no longer have an impact on this example.

[nikic]

Compile-time numbers:

Original change: https://llvm-compile-time-tracker.com/compare.php?from=db8255aee790a747f3c1fd2dfd647f8ca1d7bc79&to=1eddce4177cfddc86d4696b758904443b0b4f193&stat=instructions
Switch to SmallPtrSet as base: https://llvm-compile-time-tracker.com/compare.php?from=8c61f13a0f7cb4078b3dd4481c89b48fe4a50f77&to=837ca4796065ccd0ac0d20860341ac06a9645009&stat=instructions
This patch: https://llvm-compile-time-tracker.com/compare.php?from=35651fdd4537c081ca47acde58b6fd4b5f6997b3&to=e32a6e0aaed46e024993cc5369418ba01dfedf38&stat=instructions

So this patch recovers about half of the original regression.

llvm/include/llvm/ADT/SetVector.h

268

Something that I'm really stumped about: I initially used std::swap() here instead of the swap() member functions. However, for some reason that ends up picking up an optimized swap implementation for vector_, but not for set_ (which is the more important one really).

[nikic]

Ping

[erichkeane]

Please fix the clang-format concerns, otherwise LGTM.

llvm/include/llvm/ADT/SetVector.h

public:
   ///       SetVector interface is inconsistent with DenseSet.
   template <class STy>
   void set_subtract(const STy &S) {
     for (typename STy::const_iterator SI = S.begin(), SE = S.end(); SI != SE;
          ++SI)
       remove(*SI);
   }
 
+  void swap(SetVector<T, Vector, Set> &RHS) {
+    set_.swap(RHS.set_);
+    vector_.swap(RHS.vector_);
+  }
+
 private:
   /// A wrapper predicate designed for use with std::remove_if.
   ///
   /// This predicate wraps a predicate suitable for use with std::remove_if to
   /// call set_.erase(x) on each element which is slated for removal.
   template <typename UnaryPredicate>
   class TestAndEraseFromSet {
     UnaryPredicate P;
public:
   template<typename It>
   SmallSetVector(It Start, It End) {
     this->insert(Start, End);
   }
 };
 
 } // end namespace llvm
 
+namespace std {
+
+/// Implement std::swap in terms of SetVector swap.
+template<typename T, typename V, typename S>
+inline void
+swap(llvm::SetVector<T, V, S> &LHS, llvm::SetVector<T, V, S> &RHS) {
+  LHS.swap(RHS);
+}
+
+/// Implement std::swap in terms of SmallSetVector swap.
+template<typename T, unsigned N>
+inline void
+swap(llvm::SmallSetVector<T, N> &LHS, llvm::SmallSetVector<T, N> &RHS) {
+  LHS.swap(RHS);
+}
+
+} // end namespace std
+
 #endif // LLVM_ADT_SETVECTOR_H