diff --git a/libcxx/benchmarks/algorithms.bench.cpp b/libcxx/benchmarks/algorithms.bench.cpp
--- a/libcxx/benchmarks/algorithms.bench.cpp
+++ b/libcxx/benchmarks/algorithms.bench.cpp
@@ -14,14 +14,23 @@
 
 namespace {
 
-enum class ValueType { Uint32, String };
-struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 2> {
-  static constexpr const char* Names[] = {"uint32", "string"};
+enum class ValueType { Uint32, Uint64, Pair, Tuple, String };
+struct AllValueTypes : EnumValuesAsTuple<AllValueTypes, ValueType, 5> {
+  static constexpr const char* Names[] = {
+      "uint32", "uint64", "pair<uint32, uint32>",
+      "tuple<uint32, uint64, uint32>", "string"};
 };
 
 template <class V>
-using Value =
-    std::conditional_t<V() == ValueType::Uint32, uint32_t, std::string>;
+using Value = std::conditional_t<
+    V() == ValueType::Uint32, uint32_t,
+    std::conditional_t<
+        V() == ValueType::Uint64, uint64_t,
+        std::conditional_t<
+            V() == ValueType::Pair, std::pair<uint32_t, uint32_t>,
+            std::conditional_t<V() == ValueType::Tuple,
+                               std::tuple<uint32_t, uint64_t, uint32_t>,
+                               std::string> > > >;
 
 enum class Order {
   Random,
@@ -37,7 +46,8 @@
                                           "PipeOrgan",  "Heap"};
 };
 
-void fillValues(std::vector<uint32_t>& V, size_t N, Order O) {
+template <typename T>
+void fillValues(std::vector<T>& V, size_t N, Order O) {
   if (O == Order::SingleElement) {
     V.resize(N, 0);
   } else {
@@ -46,13 +56,49 @@
   }
 }
 
-void fillValues(std::vector<std::string>& V, size_t N, Order O) {
+template <typename T>
+void fillValues(std::vector<std::pair<T, T> >& V, size_t N, Order O) {
+  if (O == Order::SingleElement) {
+    V.resize(N, std::make_pair(0, 0));
+  } else {
+    while (V.size() < N)
+      // Half of array will have the same first element.
+      if (V.size() % 2) {
+        V.push_back(std::make_pair(V.size(), V.size()));
+      } else {
+        V.push_back(std::make_pair(0, V.size()));
+      }
+  }
+}
 
+template <typename T1, typename T2, typename T3>
+void fillValues(std::vector<std::tuple<T1, T2, T3> >& V, size_t N, Order O) {
+  if (O == Order::SingleElement) {
+    V.resize(N, std::make_tuple(0, 0, 0));
+  } else {
+    while (V.size() < N)
+      // One third of array will have the same first element.
+      // One third of array will have the same first element and the same second element.
+      switch (V.size() % 3) {
+      case 0:
+        V.push_back(std::make_tuple(V.size(), V.size(), V.size()));
+        break;
+      case 1:
+        V.push_back(std::make_tuple(0, V.size(), V.size()));
+        break;
+      case 2:
+        V.push_back(std::make_tuple(0, 0, V.size()));
+        break;
+      }
+  }
+}
+
+void fillValues(std::vector<std::string>& V, size_t N, Order O) {
   if (O == Order::SingleElement) {
-    V.resize(N, getRandomString(1024));
+    V.resize(N, getRandomString(64));
   } else {
     while (V.size() < N)
-      V.push_back(getRandomString(1024));
+      V.push_back(getRandomString(64));
   }
 }
 
@@ -85,21 +131,24 @@
   }
 }
 
+constexpr size_t TestSetElements =
+#if !TEST_HAS_FEATURE(memory_sanitizer)
+    1 << 18;
+#else
+    1 << 14;
+#endif
+
 template <class ValueType>
 std::vector<std::vector<Value<ValueType> > > makeOrderedValues(size_t N,
                                                                Order O) {
-  // Let's make sure that all random sequences of the same size are the same.
-  // That way we can compare the different algorithms with the same input.
-  static std::map<std::pair<size_t, Order>, std::vector<Value<ValueType> > >
-      Cached;
-
-  auto& Values = Cached[{N, O}];
-  if (Values.empty()) {
-    fillValues(Values, N, O);
-    sortValues(Values, O);
-  };
-  const size_t NumCopies = std::max(size_t{1}, 1000 / N);
-  return { NumCopies, Values };
+  std::vector<std::vector<Value<ValueType> > > Ret;
+  const size_t NumCopies = std::max(size_t{1}, TestSetElements / N);
+  Ret.resize(NumCopies);
+  for (auto& V : Ret) {
+    fillValues(V, N, O);
+    sortValues(V, O);
+  }
+  return Ret;
 }
 
 template <class T, class U>
@@ -111,19 +160,28 @@
   state.ResumeTiming();
 }
 
+enum class BatchSize {
+  CountElements,
+  CountBatch,
+};
+
 template <class ValueType, class F>
 void runOpOnCopies(benchmark::State& state, size_t Quantity, Order O,
-                   bool CountElements, F f) {
+                   BatchSize Count, F Body) {
   auto Copies = makeOrderedValues<ValueType>(Quantity, O);
-  const auto Orig = Copies[0];
+  auto Orig = Copies;
 
-  const size_t Batch = CountElements ? Copies.size() * Quantity : Copies.size();
+  const size_t Batch = Count == BatchSize::CountElements
+                           ? Copies.size() * Quantity
+                           : Copies.size();
   while (state.KeepRunningBatch(Batch)) {
     for (auto& Copy : Copies) {
-      f(Copy);
+      Body(Copy);
       benchmark::DoNotOptimize(Copy);
     }
-    resetCopies(state, Copies, Orig);
+    state.PauseTiming();
+    Copies = Orig;
+    state.ResumeTiming();
   }
 }
 
@@ -132,9 +190,9 @@
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
-      std::sort(Copy.begin(), Copy.end());
-    });
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements,
+        [](auto& Copy) { std::sort(Copy.begin(), Copy.end()); });
   }
 
   bool skip() const { return Order() == ::Order::Heap; }
@@ -150,9 +208,9 @@
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
-      std::stable_sort(Copy.begin(), Copy.end());
-    });
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements,
+        [](auto& Copy) { std::stable_sort(Copy.begin(), Copy.end()); });
   }
 
   bool skip() const { return Order() == ::Order::Heap; }
@@ -168,9 +226,9 @@
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
-      std::make_heap(Copy.begin(), Copy.end());
-    });
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements,
+        [](auto& Copy) { std::make_heap(Copy.begin(), Copy.end()); });
   }
 
   std::string name() const {
@@ -185,7 +243,7 @@
 
   void run(benchmark::State& state) const {
     runOpOnCopies<ValueType>(
-        state, Quantity, Order::Heap, false,
+        state, Quantity, Order::Heap, BatchSize::CountElements,
         [](auto& Copy) { std::sort_heap(Copy.begin(), Copy.end()); });
   }
 
@@ -199,10 +257,11 @@
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), false, [](auto& Copy) {
-      std::make_heap(Copy.begin(), Copy.end());
-      std::sort_heap(Copy.begin(), Copy.end());
-    });
+    runOpOnCopies<ValueType>(state, Quantity, Order(), BatchSize::CountElements,
+                             [](auto& Copy) {
+                               std::make_heap(Copy.begin(), Copy.end());
+                               std::sort_heap(Copy.begin(), Copy.end());
+                             });
   }
 
   std::string name() const {
@@ -216,11 +275,12 @@
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
-      for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
-        std::push_heap(Copy.begin(), I + 1);
-      }
-    });
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
+          for (auto I = Copy.begin(), E = Copy.end(); I != E; ++I) {
+            std::push_heap(Copy.begin(), I + 1);
+          }
+        });
   }
 
   bool skip() const { return Order() == ::Order::Heap; }
@@ -236,11 +296,12 @@
   size_t Quantity;
 
   void run(benchmark::State& state) const {
-    runOpOnCopies<ValueType>(state, Quantity, Order(), true, [](auto& Copy) {
-      for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
-        std::pop_heap(B, I);
-      }
-    });
+    runOpOnCopies<ValueType>(
+        state, Quantity, Order(), BatchSize::CountElements, [](auto& Copy) {
+          for (auto B = Copy.begin(), I = Copy.end(); I != B; --I) {
+            std::pop_heap(B, I);
+          }
+        });
   }
 
   std::string name() const {
@@ -273,4 +334,4 @@
   makeCartesianProductBenchmark<PushHeap, AllValueTypes, AllOrders>(Quantities);
   makeCartesianProductBenchmark<PopHeap, AllValueTypes>(Quantities);
   benchmark::RunSpecifiedBenchmarks();
-}
+}
\ No newline at end of file