Introduce a FlatMap and FlatSet into WTF

third_party/WebKit/Source/wtf/SetPerfTest.cpp

+// Copyright 2016 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <array>
+#include <set>
+#include <unordered_set>
+
+#include "base/bind.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "wtf/FlatSet.h"
+#include "wtf/HashSet.h"
+
+using testing::Values;
+
+template <>
+inline std::string testing::internal::GetTypeName<std::set<int>>() {
+  return "std::set";
+}
+
+template <>
+inline std::string testing::internal::GetTypeName<std::unordered_set<int>>() {
+  return "std::unordered_set";
+}
+
+template <>
+inline std::string testing::internal::GetTypeName<WTF::FlatSet<int>>() {
+  return "WTF::FlatSet";
+}
+
+template <>
+inline std::string testing::internal::GetTypeName<WTF::HashSet<int>>() {
+  return "WTF::HashSet";
+}
+
+using AssociativeSetTypes = testing::Types<std::set<int>, WTF::FlatSet<int>>;
+using SetTypes = testing::Types<std::set<int>,
+                                std::unordered_set<int>,
+                                WTF::FlatSet<int>,
+                                WTF::HashSet<int>>;
+
+namespace WTF {
+
+class Benchmark : public testing::Test {
+ public:
+  Benchmark() {}
+  virtual ~Benchmark() {}
+
+  enum {
+    kBestOfNRuns = 10,
+    kNumPermutedInts = 1 << 15,
+  };
+
+  static void SetUpTestCase() {
+    for (size_t i = 0; i < permuted_ints_.size(); i++)
+      permuted_ints_[i] = i + 1;  // WTF::HashSet doesn't like adding 0.
+
+    // Apply a pseudo random permutation.
+    int32_t num = 1234;
+    for (size_t i = 0; i < permuted_ints_.size(); i++) {
+      num = static_cast<int32_t>((num * 16807) % 2147483647L);
+      std::swap(permuted_ints_[i], permuted_ints_[num % permuted_ints_.size()]);
+    }
+  }
+
+  void RunBenchmarkSet(base::Callback<void(size_t)> init,
+                       base::Callback<void(size_t)> run) {
+    for (size_t set_size : set_sizes_) {
+      double best_time = 0;
+      for (size_t i = 0; i < kBestOfNRuns; i++) {
+        double time = RunBenchmark(init, run, set_size);
+        if (i == 0) {
+          best_time = time;
+        } else if (time < best_time) {
+          best_time = time;
+        }
+      }
+      std::cout << "Set size " << set_size << " runtime (us) " << best_time
+                << std::endl;
+    }
+  }
+
+  static std::array<int, kNumPermutedInts> permuted_ints_;
+
+ private:
+  double RunBenchmark(base::Callback<void(size_t)> init,
+                      base::Callback<void(size_t)> run,
+                      size_t set_size) {
+    init.Run(set_size);
+    base::ThreadTicks start = base::ThreadTicks::Now();
+    base::ThreadTicks now;
+    unsigned long long num_iterations = 0;
+    do {
+      run.Run(set_size);
+      now = base::ThreadTicks::Now();
+      num_iterations++;
+    } while (now - start < base::TimeDelta::FromMilliseconds(100));
+    return (now - start).InMicroseconds() / static_cast<double>(num_iterations);
+  }
+
+  std::vector<size_t> set_sizes_ = {1,    2,    4,     8,    16,   32,
+                                    64,   128,  256,   512,  1024, 2048,
+                                    4096, 8192, 16384, 32768};
+};
+
+std::array<int, Benchmark::kNumPermutedInts> Benchmark::permuted_ints_;
+
+template <typename SetType>
+class SetBenchmark : public Benchmark {
+ public:
+  SetType set_;
+  size_t index_ = 0;
+  size_t run_ = 0;
+
+  void setClear() { set_.clear(); }
+
+  void setInsertUnique(int i) { setInsert(i); }
+
+  void setInsert(int i) { set_.insert(i); }
+
+  void setErase(int i) { set_.erase(i); }
+
+  void setEraseFront() { set_.erase(set_.begin()); }
+
+  void setEraseBack() { set_.erase(std::prev(set_.end())); }
+};
+
+template <>
+void SetBenchmark<FlatSet<int>>::setInsertUnique(int i) {
+  set_.insertUnique(i);
+}
+
+template <>
+void SetBenchmark<FlatSet<int>>::setEraseBack() {
+  set_.erase(set_.rbegin());
+}
+
+template <>
+void SetBenchmark<HashSet<int>>::setInsert(int i) {
+  set_.add(i);
+}
+
+template <>
+void SetBenchmark<HashSet<int>>::setErase(int i) {
+  set_.remove(i);
+}
+
+TYPED_TEST_CASE(SetBenchmark, SetTypes);
+
+TYPED_TEST(SetBenchmark, InsertAndErasePseudoRandom) {
+  Benchmark::RunBenchmarkSet(
+      base::Bind([](SetBenchmark<TypeParam>* fixture,
+                    size_t set_size) { fixture->setClear(); },
+                 base::Unretained(this)),
+      base::Bind(
+          [](SetBenchmark<TypeParam>* fixture, size_t set_size) {
+            const auto& permutation = Benchmark::permuted_ints_;
+            size_t& index = fixture->index_;
+
+            for (size_t i = 0; i < set_size; i++) {
+              fixture->setInsert(permutation[index++ % permutation.size()]);
+            }
+            for (size_t i = 0; i < set_size; i++) {
+              fixture->setErase(permutation[index++ % permutation.size()]);
+            }
+          },
+          base::Unretained(this)));
+}
+
+TYPED_TEST(SetBenchmark, InsertAndEraseOutsideIn) {
+  Benchmark::RunBenchmarkSet(
+      base::Bind([](SetBenchmark<TypeParam>* fixture,
+                    size_t set_size) { fixture->set_.clear(); },
+                 base::Unretained(this)),
+      base::Bind(
+          [](SetBenchmark<TypeParam>* fixture, size_t set_size) {
+            for (size_t i = 1; i < set_size; i++) {
+              fixture->setInsertUnique(set_size - i);
+              fixture->setInsertUnique(set_size + i);
+            }
+            for (size_t i = set_size - 1; i > 0; i--) {
+              fixture->setErase(set_size - i);
+              fixture->setErase(set_size + i);
+            }
+          },
+          base::Unretained(this)));
+}
+
+TYPED_TEST(SetBenchmark, InsertAndEraseInsideOut) {
+  Benchmark::RunBenchmarkSet(
+      base::Bind([](SetBenchmark<TypeParam>* fixture,
+                    size_t set_size) { fixture->set_.clear(); },
+                 base::Unretained(this)),
+      base::Bind(
+          [](SetBenchmark<TypeParam>* fixture, size_t set_size) {
+            for (size_t i = 1; i < set_size; i++) {
+              fixture->setInsertUnique(i);
+              fixture->setInsertUnique(set_size + set_size - i);
+            }
+            for (size_t i = set_size - 1; i > 0; i--) {
+              fixture->setErase(i);
+              fixture->setErase(set_size + set_size - i);
+            }
+          },
+          base::Unretained(this)));
+}
+
+TYPED_TEST(SetBenchmark, FixedSizeFind) {
+  size_t num = 0;
+  Benchmark::RunBenchmarkSet(
+      base::Bind(
+          [](SetBenchmark<TypeParam>* fixture, size_t set_size) {
+            const auto& permutation = Benchmark::permuted_ints_;
+
+            fixture->setClear();
+            for (size_t i = 0; i < set_size; i++)
+              fixture->setInsert(permutation[i % permutation.size()]);
+          },
+          base::Unretained(this)),
+      base::Bind(
+          [](SetBenchmark<TypeParam>* fixture, size_t* num, size_t set_size) {
+            const auto& permutation = Benchmark::permuted_ints_;
+
+            for (size_t i = 0; i < set_size; i++) {
+              if (fixture->set_.find(permutation[i % permutation.size()]) !=
+                  fixture->set_.end()) {
+                (*num)++;  // Prevent the compiler from optimizing stuff away.
+              }
+            }
+          },
+          base::Unretained(this), base::Unretained(&num)));
+}
+
+template <typename SetType>
+class AssociativeSetBenchmark : public SetBenchmark<SetType> {};
+
+TYPED_TEST_CASE(AssociativeSetBenchmark, AssociativeSetTypes);
+
+TYPED_TEST(AssociativeSetBenchmark, FixedSizeEraseAndInsert) {
+  Benchmark::RunBenchmarkSet(
+      base::Bind(
+          [](SetBenchmark<TypeParam>* fixture, size_t set_size) {
+            const auto& permutation = Benchmark::permuted_ints_;
+            size_t& index = fixture->index_;
+
+            fixture->setClear();
+            for (index = 0; index < set_size; index++) {
+              fixture->setInsert(permutation[index % permutation.size()]);
+            }
+          },
+          base::Unretained(this)),
+      base::Bind(
+          [](SetBenchmark<TypeParam>* fixture, size_t set_size) {
+            const auto& permutation = Benchmark::permuted_ints_;
+            size_t& index = fixture->index_;
+            size_t& run = fixture->run_;  // Necessary to ensure uniqueness.
+
+            for (size_t i = 0; i < 10000; i++) {
+              fixture->setEraseFront();
+              fixture->setInsertUnique(
+                  run + permutation[index++ % permutation.size()]);
+            }
+
+            run += permutation.size();
+          },
+          base::Unretained(this)));
+}
+
+TYPED_TEST(AssociativeSetBenchmark, InsertAndEraseOutsideIn) {
+  Benchmark::RunBenchmarkSet(
+      base::Bind([](SetBenchmark<TypeParam>* fixture,
+                    size_t set_size) { fixture->set_.clear(); },
+                 base::Unretained(this)),
+      base::Bind(
+          [](SetBenchmark<TypeParam>* fixture, size_t set_size) {
+            for (size_t i = 1; i < set_size; i++) {
+              fixture->setInsertUnique(set_size - i);
+              fixture->setInsertUnique(set_size + i);
+            }
+            for (size_t i = set_size - 1; i > 0; i--) {
+              fixture->setEraseFront();
+              fixture->setEraseBack();
+            }
+          },
+          base::Unretained(this)));
+  EXPECT_TRUE(this->set_.empty());
+}
+
+}  // namespace WTF