| vmpstr | 0d69452 | 2016-12-14 23:37:19 | [diff] [blame] | 1 | // Copyright 2016 The Chromium Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style license that can be |
| 3 | // found in the LICENSE file. |
| 4 | |
| chrishtr | 82b5d950 | 2017-03-20 18:25:33 | [diff] [blame^] | 5 | #include "cc/base/lap_timer.h" |
| vmpstr | 0d69452 | 2016-12-14 23:37:19 | [diff] [blame] | 6 | #include "cc/base/rtree.h" |
| vmpstr | 0d69452 | 2016-12-14 23:37:19 | [diff] [blame] | 7 | |
| 8 | #include "testing/gtest/include/gtest/gtest.h" |
| 9 | #include "testing/perf/perf_test.h" |
| 10 | |
| 11 | namespace cc { |
| 12 | namespace { |
| 13 | |
| 14 | static const int kTimeLimitMillis = 2000; |
| 15 | static const int kWarmupRuns = 5; |
| 16 | static const int kTimeCheckInterval = 10; |
| 17 | |
| 18 | class RTreePerfTest : public testing::Test { |
| 19 | public: |
| 20 | RTreePerfTest() |
| 21 | : timer_(kWarmupRuns, |
| 22 | base::TimeDelta::FromMilliseconds(kTimeLimitMillis), |
| 23 | kTimeCheckInterval) {} |
| 24 | |
| 25 | void RunConstructTest(const std::string& test_name, int rect_count) { |
| 26 | std::vector<gfx::Rect> rects = BuildRects(rect_count); |
| 27 | timer_.Reset(); |
| 28 | do { |
| 29 | RTree rtree; |
| 30 | rtree.Build(rects); |
| 31 | timer_.NextLap(); |
| 32 | } while (!timer_.HasTimeLimitExpired()); |
| 33 | |
| 34 | perf_test::PrintResult("rtree_construct", "", test_name, |
| 35 | timer_.LapsPerSecond(), "runs/s", true); |
| 36 | } |
| 37 | |
| 38 | void RunSearchTest(const std::string& test_name, int rect_count) { |
| 39 | int large_query = std::sqrt(rect_count); |
| 40 | |
| 41 | std::vector<gfx::Rect> queries = { |
| 42 | gfx::Rect(0, 0, 1, 1), gfx::Rect(100, 100, 2, 2), |
| 43 | gfx::Rect(-10, -10, 1, 1), gfx::Rect(0, 0, 1000, 1000), |
| 44 | gfx::Rect(large_query - 2, large_query - 2, 1, 1)}; |
| 45 | size_t query_index = 0; |
| 46 | |
| 47 | std::vector<gfx::Rect> rects = BuildRects(rect_count); |
| 48 | RTree rtree; |
| 49 | rtree.Build(rects); |
| 50 | |
| 51 | timer_.Reset(); |
| 52 | do { |
| 53 | std::vector<size_t> results; |
| 54 | rtree.Search(queries[query_index], &results); |
| 55 | query_index = (query_index + 1) % queries.size(); |
| 56 | timer_.NextLap(); |
| 57 | } while (!timer_.HasTimeLimitExpired()); |
| 58 | |
| 59 | perf_test::PrintResult("rtree_search", "", test_name, |
| 60 | timer_.LapsPerSecond(), "runs/s", true); |
| 61 | } |
| 62 | |
| 63 | std::vector<gfx::Rect> BuildRects(int count) { |
| 64 | std::vector<gfx::Rect> result; |
| 65 | int width = std::sqrt(count); |
| 66 | int x = 0; |
| 67 | int y = 0; |
| 68 | for (int i = 0; i < count; ++i) { |
| 69 | result.push_back(gfx::Rect(x, y, 1, 1)); |
| 70 | if (++x > width) { |
| 71 | x = 0; |
| 72 | ++y; |
| 73 | } |
| 74 | } |
| 75 | return result; |
| 76 | } |
| 77 | |
| 78 | protected: |
| 79 | LapTimer timer_; |
| 80 | }; |
| 81 | |
| 82 | TEST_F(RTreePerfTest, Construct) { |
| 83 | RunConstructTest("100", 100); |
| 84 | RunConstructTest("1000", 1000); |
| 85 | RunConstructTest("10000", 10000); |
| 86 | RunConstructTest("100000", 100000); |
| 87 | } |
| 88 | |
| 89 | TEST_F(RTreePerfTest, Search) { |
| 90 | RunSearchTest("100", 100); |
| 91 | RunSearchTest("1000", 1000); |
| 92 | RunSearchTest("10000", 10000); |
| 93 | RunSearchTest("100000", 100000); |
| 94 | } |
| 95 | |
| 96 | } // namespace |
| 97 | } // namespace cc |