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 };
+
+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(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,
+                          TestOrder order,
+                          RangeInsertMethod method) {
+  flat_set<int> set(GetInputs(initial_size, TestOrder::ASCENDING),
+                    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) +
+                            "\tTestOrder: " + to_string(order) +
+                            "\tMethod: " + to_string(method);
+  int input_start = std::max(0.0, initial_size - pct_overlap / 100.0 * n_items);
+  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);
+}
+
+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 t = 0; t < 4; ++t) {
+          for (int m = 0; m < 4; ++m) {
+            test_range_insertion(1 << i, 1 << n, o * 10,
+                                 static_cast<TestOrder>(t),
+                                 static_cast<RangeInsertMethod>(m));
+          }
+        }
+      }
+    }
+  }
+}
+
+}  // namespace base