Flat Tree Perftest

base/containers/flat_set_perftest.cc

+// Copyright 2017 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 "base/containers/flat_set.h"
+
+#include <algorithm>
+#include <numeric>
+#include <random>
+#include <string>
+#include <vector>
+
+#include "base/memory/ptr_util.h"
+#include "base/strings/string_piece.h"
+#include "base/time/time.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "testing/perf/perf_test.h"
+
+namespace base {
+enum class TestOrder { ASCENDING, DESCENDING, INTERLEAVED, RANDOM };
+
+enum class InputRelation { SMALLER, GREATER };
+
+std::string to_string(TestOrder order) {
+  switch (order) {
+    case TestOrder::ASCENDING:
+      return "ascending";
+    case TestOrder::DESCENDING:
+      return "descending";
+    case TestOrder::INTERLEAVED:
+      return "interleaved";
+    case TestOrder::RANDOM:
+      return "random";
+    default:
+      return "";
+  }
+}
+
+std::string to_string(InputRelation rel) {
+  switch (rel) {
+    case InputRelation::SMALLER:
+      return "smaller";
+    case InputRelation::GREATER:
+      return "greater";
+    default:
+      return "";
+  }
+}
+
+std::string to_string(RangeInsertMethod method) {
+  switch (method) {
+    case RangeInsertMethod::ONE_BY_ONE:
+      return "One By One";
+    case RangeInsertMethod::STABLE_SORT_ALL:
+      return "Stable Sort All";
+    case RangeInsertMethod::STABLE_SORT_SMART:
+      return "Stable Sort Smart";
+    case RangeInsertMethod::STABLE_SORT_SMARTER:
+      return "Stable Sort Smarter";
+    default:
+      return "";
+  }
+}
+
+std::vector<int> GetInputs(int length, TestOrder order, int start = 0) {
+  std::vector<int> inputs(length);
+  std::iota(std::begin(inputs), std::end(inputs), start);
+
+  switch (order) {
+    case TestOrder::ASCENDING:
+      break;
+    case TestOrder::DESCENDING:
+      std::reverse(std::begin(inputs), std::end(inputs));
+      break;
+    case TestOrder::INTERLEAVED:
+      for (int i = 0; i < length / 2; i += 2)
+        std::swap(inputs[i], inputs[length - 1 - i]);
+      break;
+    case TestOrder::RANDOM: {
+      std::random_device rd;
+      std::mt19937 g(rd());
+      std::shuffle(std::begin(inputs), std::end(inputs), g);
+      break;
+    }
+  }
+
+  return inputs;
+}
+
+void test_range_insertion(int initial_size,
+                          int n_items,
+                          int pct_overlap,
+                          InputRelation rel,
+                          TestOrder order,
+                          RangeInsertMethod method) {
+  int set_start = 0;
+  int input_start = 0;
+
+  if (rel == InputRelation::SMALLER) {
+    set_start = std::max(0.0, n_items - pct_overlap / 100.0 * initial_size);
+  } else {
+    input_start = std::max(0.0, initial_size - pct_overlap / 100.0 * n_items);
+  }
+
+  flat_set<int> set(GetInputs(initial_size, TestOrder::ASCENDING, set_start),
+                    KEEP_FIRST_OF_DUPES);
+  std::string description = "Initial Size: " + std::to_string(initial_size) +
+                            "\tNumber of Items: " + std::to_string(n_items) +
+                            "\tPct Overlap: " + std::to_string(pct_overlap) +
+                            "\tInputRelation: " + to_string(rel) +
+                            "\tTestOrder: " + to_string(order) +
+                            "\tMethod: " + to_string(method);
+  std::vector<int> inputs = GetInputs(n_items, order, input_start);
+  TimeTicks start = TimeTicks::Now();
+  set.insert(inputs.begin(), inputs.end(), method);
+  TimeTicks end = TimeTicks::Now();
+  double duration = (end - start).InMicroseconds();
+  perf_test::PrintResult("RangeInsertionTest", "", description, duration, "us",
+                         true);
+}
+
+void test_insert_single_close_to_end(int n_items, RangeInsertMethod method) {
+  std::vector<int> inputs = GetInputs(n_items, TestOrder::ASCENDING);
+
+  std::string description = "Number of Items: " + std::to_string(n_items) +
+                            "\tMethod: " + to_string(method);
+  flat_set<int> set;
+  set.insert(inputs.back());
+  TimeTicks start = TimeTicks::Now();
+  for (auto iter = inputs.begin(); std::next(iter) != inputs.end(); ++iter) {
+    set.insert(iter, std::next(iter), method);
+  }
+  TimeTicks end = TimeTicks::Now();
+  double duration = (end - start).InMicroseconds();
+  perf_test::PrintResult("RangeInsertionTest", "", description, duration, "us",
+                         true);
+}
+
+TEST(FlatSetPerfTest, RangeInsertionTest) {
+  for (int i = 0; i < 16; ++i) {
+    for (int n = 0; n < 16; ++n) {
+      for (int o = 0; o <= 10; ++o) {
+        for (int r = 0; r < 2; ++r) {
+          for (int t = 0; t < 4; ++t) {
+            for (int m = 0; m < 4; ++m) {
+              test_range_insertion(
+                  1 << i, 1 << n, o * 10, static_cast<InputRelation>(r),
+                  static_cast<TestOrder>(t), static_cast<RangeInsertMethod>(m));
+            }
+          }
+        }
+      }
+    }
+  }
+}
+
+TEST(FlatSetPerfTest, SingleRangeInsertionTestCloseToEnd) {
+  for (int i = 0; i < 16; ++i) {
+    for (int m : {0, 1, 2, 3}) {
+      test_insert_single_close_to_end(1 << i,
+                                      static_cast<RangeInsertMethod>(m));
+    }
+  }
+}
+
+}  // namespace base