[ADT] Avoid needless iterator copies in `zippy`

[kuhar]

Summary

Make zip_common increment and decrement iterators in place.

This improves performance with iterator types that have non-triviall
copy constructors.

[zero9178]

llvm/include/llvm/ADT/STLExtras.h

789

ultra nit: We only usually use explicit casts to void for silencing unused variable warning don't we? Looks a bit odd here imo

llvm/unittests/ADT/IteratorTest.cpp

731

How fragile is this test? Isn't the initial copy count more or less an implementation detail of zippy? Would it maybe suffice to create the zippy range before the loop, record the count, then do the loop, and then ensure that the count after the loop is equal to before?

[kuhar]

Address comments. Rebase.

[kuhar]

llvm/include/llvm/ADT/STLExtras.h

789

I added (void) to avoid potential warnings about unused return values, but thinking about it again, it's probably signal that shouldn't be ignored in the first place. Thanks!

llvm/unittests/ADT/IteratorTest.cpp

731

The number of copies in the loop is still >0 (4 to be exact), but I followed your suggestion and separated the pre-loop count from the in-loop count.

[zero9178]

LGTM thanks!

llvm/unittests/ADT/IteratorTest.cpp

731

Ahh I see, these seem to come from the begin and end calls that the for-range loop desugars to. One could probably separate the counting of those too, but I think the current method is fine.

llvm/include/llvm/ADT/STLExtras.h

using zip_traits = iterator_facade_base<
     // instance, the second field's difference_type were non-numeric while the
     // first is.
     typename ZipTupleType<Iters...>::type *,
     typename ZipTupleType<Iters...>::type>;
 
 template <typename ZipType, typename... Iters>
 struct zip_common : public zip_traits<ZipType, Iters...> {
   using Base = zip_traits<ZipType, Iters...>;
+  using IndexSequence = std::index_sequence_for<Iters...>;
   using value_type = typename Base::value_type;
 
   std::tuple<Iters...> iterators;
 
 protected:
   template <size_t... Ns> value_type deref(std::index_sequence<Ns...>) const {
     return value_type(*std::get<Ns>(iterators)...);
   }
 
-  template <size_t... Ns>
-  decltype(iterators) tup_inc(std::index_sequence<Ns...>) const {
-    return std::tuple<Iters...>(std::next(std::get<Ns>(iterators))...);
+  template <size_t... Ns> void tup_inc(std::index_sequence<Ns...>) {
+    (++std::get<Ns>(iterators), ...);
   }
 
-  template <size_t... Ns>
-  decltype(iterators) tup_dec(std::index_sequence<Ns...>) const {
-    return std::tuple<Iters...>(std::prev(std::get<Ns>(iterators))...);
+  template <size_t... Ns> void tup_dec(std::index_sequence<Ns...>) {
+    (--std::get<Ns>(iterators), ...);
   }
 
   template <size_t... Ns>
   bool test_all_equals(const zip_common &other,
                        std::index_sequence<Ns...>) const {
     return ((std::get<Ns>(this->iterators) == std::get<Ns>(other.iterators)) &&
             ...);
   }
 
 public:
   zip_common(Iters &&... ts) : iterators(std::forward<Iters>(ts)...) {}
 
-  value_type operator*() const {
-    return deref(std::index_sequence_for<Iters...>{});
-  }
+  value_type operator*() const { return deref(IndexSequence{}); }
 
   ZipType &operator++() {
-    iterators = tup_inc(std::index_sequence_for<Iters...>{});
-    return *reinterpret_cast<ZipType *>(this);
+    tup_inc(IndexSequence{});
+    return static_cast<ZipType &>(*this);
   }
 
   ZipType &operator--() {
     static_assert(Base::IsBidirectional,
                   "All inner iterators must be at least bidirectional.");
-    iterators = tup_dec(std::index_sequence_for<Iters...>{});
-    return *reinterpret_cast<ZipType *>(this);
+    tup_dec(IndexSequence{});
+    return static_cast<ZipType &>(*this);
   }
 
   /// Return true if all the iterator are matching `other`'s iterators.
   bool all_equals(zip_common &other) {
-    return test_all_equals(other, std::index_sequence_for<Iters...>{});
+    return test_all_equals(other, IndexSequence{});
   }
 };
 
 template <typename... Iters>
 struct zip_first : zip_common<zip_first<Iters...>, Iters...> {
   using zip_common<zip_first, Iters...>::zip_common;
 
   bool operator==(const zip_first &other) const {

llvm/unittests/ADT/IteratorTest.cpp

for (auto tup : make_filter_range(reverse(zipped), odds)) {
     EXPECT_TRUE(get<0>(tup) & 0x01);
     get<0>(tup) += 1;
   }
 
   // Ensure that in-place mutation works.
   EXPECT_TRUE(all_of(ascending, [](unsigned n) { return (n & 0x01) == 0; }));
 }
 
+// Int iterator that keeps track of the number of its copies.
+struct CountingIntIterator : IntIterator {
+  unsigned *cnt;
+
+  CountingIntIterator(int *it, unsigned &counter)
+      : IntIterator(it), cnt(&counter) {}
+
+  CountingIntIterator(const CountingIntIterator &other)
+      : IntIterator(other.I), cnt(other.cnt) {
+    ++(*cnt);
+  }
+  CountingIntIterator &operator=(const CountingIntIterator &other) {
+    this->I = other.I;
+    this->cnt = other.cnt;
+    ++(*cnt);
+    return *this;
+  }
+};
+
+// Check that the iterators do not get copied with each `zippy` iterator
+// increment.
+TEST(ZipIteratorTest, IteratorCopies) {
+  std::vector<int> ints(1000, 42);
+  unsigned total_copy_count = 0;
+  CountingIntIterator begin(ints.data(), total_copy_count);
+  CountingIntIterator end(ints.data() + ints.size(), total_copy_count);
+
+  size_t iters = 0;
+  auto zippy = zip_equal(ints, llvm::make_range(begin, end));
+  const unsigned creation_copy_count = total_copy_count;
+
+  for (auto [a, b] : zippy) {
+    EXPECT_EQ(a, b);
+    ++iters;
+  }
+  EXPECT_EQ(iters, ints.size());
+
+  // We expect the number of copies to be much smaller than the number of loop
+  // iterations.
+  unsigned loop_copy_count = total_copy_count - creation_copy_count;
+  EXPECT_LT(loop_copy_count, 10u);
+}
+
 TEST(RangeTest, Distance) {
   std::vector<int> v1;
   std::vector<int> v2{1, 2, 3};
 
   EXPECT_EQ(std::distance(v1.begin(), v1.end()), size(v1));
   EXPECT_EQ(std::distance(v2.begin(), v2.end()), size(v2));
 }
 
 } // anonymous namespace