Removing (dest != prev) check from LastUnique algorithm.

base/algorithm/benchmarks.cc

Index: base/algorithm/benchmarks.cc
diff --git a/base/algorithm/benchmarks.cc b/base/algorithm/benchmarks.cc
new file mode 100644
index 0000000000000000000000000000000000000000..b719d1e1fcca09a6e2eb2f3e0ff2e48255976230
--- /dev/null
+++ b/base/algorithm/benchmarks.cc
@@ -0,0 +1,96 @@
+// Copyright 2017 The Chromium Authors. All rights reserved.

[dyaroshev, 2017/04/08 16:48:03]

I will remove these benchmarks before merging. I've included it here to show
what was measured and to give the ability to reproduce my results.

Benchmarking was done using google benchmark library:
https://github.com/google/benchmark

Here are my results:
https://drive.google.com/file/d/0B5pZ43DhqaQDN2NwaFRvOC1hNkk/view?usp=sharing
As you can see,  we get ~30% faster with this change.

Even though these are still extremely fast operations, I think there is no good
reason to keep it slower.

[dyaroshev, 2017/04/11 10:07:10]

On 2017/04/08 16:48:03, dyaroshev wrote: 
To clarify: one_cycle_and_if - previous version. two_cycles - current version.

[brettw, 2017/04/26 21:48:51]

You can add them to the //base:base_perftests target. I don't think that target
is run by any bot. But recently I've been using the JSON parser one manually
when making changes to it. So it seels suited to what you're doing.

[dyaroshev, 2017/04/27 19:11:46]

Unfortunately, it would break your builds. Google benchmark library is not in
Chromium.
I'm thinking about adding it. You think this might be a good idea?

+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <numeric>
+#include <vector>
+
+#include "base/algorithm/sorted_ranges.h"
+#include "base/third_party/benchmark/include/benchmark/benchmark.h"
+
+namespace {
+
+template <class Iterator, class BinaryPredicate>
+Iterator PreviousLastUnique(Iterator first,
+                            Iterator last,
+                            BinaryPredicate compare) {
+  if (first == last)
+    return last;
+
+  Iterator dest = first;
+  Iterator cur = first;
+  Iterator prev = cur;
+  while (++cur != last) {
+    if (!compare(*prev, *cur)) {
+      // Non-identical one.
+      if (dest != prev)
+        *dest = std::move(*prev);
+      ++dest;
+    }
+    prev = cur;
+  }
+
+  if (dest != prev)
+    *dest = std::move(*prev);
+  return ++dest;
+}
+
+template <typename Functor>
+void LastUniqueBenchmarkManyDuplicates(benchmark::State& state, Functor impl) {
+  std::vector<int> original_input;
+
+  for (int i = 11; i < 1000000; ++i) {
+    for (int j = 0; j < i % 10; ++i)
+      original_input.push_back(i);
+  }
+
+  while (state.KeepRunning()) {
+    state.PauseTiming();
+    auto input = original_input;
+    state.ResumeTiming();
+    impl(input);
+  }
+}
+
+template <typename Functor>
+void LastUniqueBenchmarkNoDuplicates(benchmark::State& state, Functor impl) {
+  std::vector<int> original_input(1000000);
+  std::iota(original_input.begin(), original_input.end(), 0);
+
+  while (state.KeepRunning()) {
+    state.PauseTiming();
+    auto input = original_input;
+    state.ResumeTiming();
+    impl(input);
+  }
+}
+
+BENCHMARK_CAPTURE(LastUniqueBenchmarkManyDuplicates,
+                  one_cycle_and_if_many_duplicates,
+                  [](std::vector<int>& in) {
+                    PreviousLastUnique(in.begin(), in.end(),
+                                       std::equal_to<int>{});
+                  });
+
+BENCHMARK_CAPTURE(LastUniqueBenchmarkManyDuplicates,
+                  two_cycles_many_duplicates,
+                  [](std::vector<int>& in) {
+                    base::UniquePickLast(in.begin(), in.end());
+                  });
+
+BENCHMARK_CAPTURE(LastUniqueBenchmarkNoDuplicates,
+                  one_cycle_and_if_no_duplicates,
+                  [](std::vector<int>& in) {
+                    PreviousLastUnique(in.begin(), in.end(),
+                                       std::equal_to<int>{});
+                  });
+
+BENCHMARK_CAPTURE(LastUniqueBenchmarkNoDuplicates,
+                  two_cycles_no_duplicates,
+                  [](std::vector<int>& in) {
+                    base::UniquePickLast(in.begin(), in.end());
+                  });
+
+}  // namespace
+
+BENCHMARK_MAIN()