cc: Add rtree perftests.

cc/base/rtree_perftest.cc

+// 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 "cc/base/rtree.h"
+#include "cc/debug/lap_timer.h"
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "testing/perf/perf_test.h"
+
+namespace cc {
+namespace {
+
+static const int kTimeLimitMillis = 2000;
+static const int kWarmupRuns = 5;
+static const int kTimeCheckInterval = 10;
+
+class RTreePerfTest : public testing::Test {
+ public:
+  RTreePerfTest()
+      : timer_(kWarmupRuns,
+               base::TimeDelta::FromMilliseconds(kTimeLimitMillis),
+               kTimeCheckInterval) {}
+
+  void RunConstructTest(const std::string& test_name, int rect_count) {
+    std::vector<gfx::Rect> rects = BuildRects(rect_count);
+    timer_.Reset();
+    do {
+      RTree rtree;
+      rtree.Build(rects);
+      timer_.NextLap();
+    } while (!timer_.HasTimeLimitExpired());
+
+    perf_test::PrintResult("rtree_construct", "", test_name,
+                           timer_.LapsPerSecond(), "runs/s", true);
+  }
+
+  void RunSearchTest(const std::string& test_name, int rect_count) {
+    std::vector<gfx::Rect> queries = {
+        gfx::Rect(0, 0, 1, 1), gfx::Rect(100, 100, 2, 2),
+        gfx::Rect(-10, -10, 1, 1), gfx::Rect(0, 0, 1000, 1000)};

[danakj, 2016/12/14 20:36:44]

Maybe consider a query on the bottom/right for large sizes?

[vmpstr, 2016/12/14 20:43:13]

Done.

+    size_t query_index = 0;
+
+    std::vector<gfx::Rect> rects = BuildRects(rect_count);
+    RTree rtree;
+    rtree.Build(rects);
+
+    timer_.Reset();
+    do {
+      std::vector<size_t> results;
+      rtree.Search(queries[query_index], &results);
+      query_index = (query_index + 1) % queries.size();
+      timer_.NextLap();
+    } while (!timer_.HasTimeLimitExpired());
+
+    perf_test::PrintResult("rtree_search", "", test_name,
+                           timer_.LapsPerSecond(), "runs/s", true);
+  }
+
+  std::vector<gfx::Rect> BuildRects(int count) {
+    std::vector<gfx::Rect> result;
+    int width = std::sqrt(count);
+    int x = 0;
+    int y = 0;
+    for (int i = 0; i < count; ++i) {
+      result.push_back(gfx::Rect(x, y, 1, 1));
+      if (++x > width) {
+        x = 0;
+        ++y;
+      }
+    }
+    return result;
+  }
+
+ protected:
+  LapTimer timer_;
+};
+
+TEST_F(RTreePerfTest, Construct) {
+  RunConstructTest("100", 100);
+  RunConstructTest("1000", 1000);
+  RunConstructTest("10000", 10000);
+  RunConstructTest("100000", 100000);
+}
+
+TEST_F(RTreePerfTest, Search) {
+  RunSearchTest("100", 100);
+  RunSearchTest("1000", 1000);
+  RunSearchTest("10000", 10000);
+  RunSearchTest("100000", 100000);
+}
+
+}  // namespace
+}  // namespace cc