cc: Add rtree perftests.

This patch adds some perftests to measure RTree performance.
Sample run (on z620):

[==========] Running 2 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 2 tests from RTreePerfTest
[ RUN      ] RTreePerfTest.Construct
*RESULT rtree_construct: 100= 346091.53125 runs/s
*RESULT rtree_construct: 1000= 36854.61328125 runs/s
*RESULT rtree_construct: 10000= 3392.330322265625 runs/s
*RESULT rtree_construct: 100000= 369.79052734375 runs/s
[       OK ] RTreePerfTest.Construct (8040 ms)
[ RUN      ] RTreePerfTest.Search
*RESULT rtree_search: 100= 2992395.5 runs/s
*RESULT rtree_search: 1000= 507624.9375 runs/s
*RESULT rtree_search: 10000= 32956.60546875 runs/s
*RESULT rtree_search: 100000= 3477.254638671875 runs/s
[       OK ] RTreePerfTest.Search (8020 ms)
[----------] 2 tests from RTreePerfTest (16060 ms total)

[----------] Global test environment tear-down
[==========] 2 tests from 1 test case ran. (16060 ms total)
[  PASSED  ] 2 tests.

R=danakj@chromium.org, dskiba@chromium.org
BUG=674169
CQ_INCLUDE_TRYBOTS=master.tryserver.blink:linux_trusty_blink_rel

Review-Url: https://codereview.chromium.org/2576793002
Cr-Commit-Position: refs/heads/master@{#438675}

diff --git a/cc/BUILD.gn b/cc/BUILD.gn
index d9c52a2d..95c03c6a 100644
--- a/cc/BUILD.gn
+++ b/cc/BUILD.gn

@@ -988,6 +988,7 @@
 cc_test("cc_perftests") {
   sources = [
     "animation/animation_host_perftest.cc",
+    "base/rtree_perftest.cc",
     "ipc/cc_serialization_perftest.cc",
     "layers/layer_perftest.cc",
     "layers/picture_layer_impl_perftest.cc",

diff --git a/cc/base/DEPS b/cc/base/DEPS
index 33b4e8f..1bcb1a1 100644
--- a/cc/base/DEPS
+++ b/cc/base/DEPS

@@ -8,5 +8,9 @@
 specific_include_rules = {
   ".*unittest\.cc": [
     "+cc/test",
-  ]
+  ],
+  # Allow lap_timer.h for perftests
+  ".*perftest\.cc": [
+    "+cc/debug/lap_timer.h",
+  ],
 }

diff --git a/cc/base/rtree_perftest.cc b/cc/base/rtree_perftest.cc
new file mode 100644
index 0000000..85aee07
--- /dev/null
+++ b/cc/base/rtree_perftest.cc

@@ -0,0 +1,97 @@
+// 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) {
+    int large_query = std::sqrt(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),
+        gfx::Rect(large_query - 2, large_query - 2, 1, 1)};
+    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