RTreeBench.cpp 4.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138
  1. /*
  2. * Copyright 2012 Google Inc.
  3. *
  4. * Use of this source code is governed by a BSD-style license that can be
  5. * found in the LICENSE file.
  6. */
  7. #include "bench/Benchmark.h"
  8. #include "include/core/SkCanvas.h"
  9. #include "include/core/SkString.h"
  10. #include "include/utils/SkRandom.h"
  11. #include "src/core/SkRTree.h"
  12. // confine rectangles to a smallish area, so queries generally hit something, and overlap occurs:
  13. static const SkScalar GENERATE_EXTENTS = 1000.0f;
  14. static const int NUM_BUILD_RECTS = 500;
  15. static const int NUM_QUERY_RECTS = 5000;
  16. static const int GRID_WIDTH = 100;
  17. typedef SkRect (*MakeRectProc)(SkRandom&, int, int);
  18. // Time how long it takes to build an R-Tree.
  19. class RTreeBuildBench : public Benchmark {
  20. public:
  21. RTreeBuildBench(const char* name, MakeRectProc proc) : fProc(proc) {
  22. fName.printf("rtree_%s_build", name);
  23. }
  24. bool isSuitableFor(Backend backend) override {
  25. return backend == kNonRendering_Backend;
  26. }
  27. protected:
  28. const char* onGetName() override {
  29. return fName.c_str();
  30. }
  31. void onDraw(int loops, SkCanvas* canvas) override {
  32. SkRandom rand;
  33. SkAutoTMalloc<SkRect> rects(NUM_BUILD_RECTS);
  34. for (int i = 0; i < NUM_BUILD_RECTS; ++i) {
  35. rects[i] = fProc(rand, i, NUM_BUILD_RECTS);
  36. }
  37. for (int i = 0; i < loops; ++i) {
  38. SkRTree tree;
  39. tree.insert(rects.get(), NUM_BUILD_RECTS);
  40. SkASSERT(rects != nullptr); // It'd break this bench if the tree took ownership of rects.
  41. }
  42. }
  43. private:
  44. MakeRectProc fProc;
  45. SkString fName;
  46. typedef Benchmark INHERITED;
  47. };
  48. // Time how long it takes to perform queries on an R-Tree.
  49. class RTreeQueryBench : public Benchmark {
  50. public:
  51. RTreeQueryBench(const char* name, MakeRectProc proc) : fProc(proc) {
  52. fName.printf("rtree_%s_query", name);
  53. }
  54. bool isSuitableFor(Backend backend) override {
  55. return backend == kNonRendering_Backend;
  56. }
  57. protected:
  58. const char* onGetName() override {
  59. return fName.c_str();
  60. }
  61. void onDelayedSetup() override {
  62. SkRandom rand;
  63. SkAutoTMalloc<SkRect> rects(NUM_QUERY_RECTS);
  64. for (int i = 0; i < NUM_QUERY_RECTS; ++i) {
  65. rects[i] = fProc(rand, i, NUM_QUERY_RECTS);
  66. }
  67. fTree.insert(rects.get(), NUM_QUERY_RECTS);
  68. }
  69. void onDraw(int loops, SkCanvas* canvas) override {
  70. SkRandom rand;
  71. for (int i = 0; i < loops; ++i) {
  72. SkTDArray<int> hits;
  73. SkRect query;
  74. query.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS);
  75. query.fTop = rand.nextRangeF(0, GENERATE_EXTENTS);
  76. query.fRight = query.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
  77. query.fBottom = query.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/2);
  78. fTree.search(query, &hits);
  79. }
  80. }
  81. private:
  82. SkRTree fTree;
  83. MakeRectProc fProc;
  84. SkString fName;
  85. typedef Benchmark INHERITED;
  86. };
  87. static inline SkRect make_XYordered_rects(SkRandom& rand, int index, int numRects) {
  88. SkRect out;
  89. out.fLeft = SkIntToScalar(index % GRID_WIDTH);
  90. out.fTop = SkIntToScalar(index / GRID_WIDTH);
  91. out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
  92. out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
  93. return out;
  94. }
  95. static inline SkRect make_YXordered_rects(SkRandom& rand, int index, int numRects) {
  96. SkRect out;
  97. out.fLeft = SkIntToScalar(index / GRID_WIDTH);
  98. out.fTop = SkIntToScalar(index % GRID_WIDTH);
  99. out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
  100. out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/3);
  101. return out;
  102. }
  103. static inline SkRect make_random_rects(SkRandom& rand, int index, int numRects) {
  104. SkRect out;
  105. out.fLeft = rand.nextRangeF(0, GENERATE_EXTENTS);
  106. out.fTop = rand.nextRangeF(0, GENERATE_EXTENTS);
  107. out.fRight = out.fLeft + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5);
  108. out.fBottom = out.fTop + 1 + rand.nextRangeF(0, GENERATE_EXTENTS/5);
  109. return out;
  110. }
  111. static inline SkRect make_concentric_rects(SkRandom&, int index, int numRects) {
  112. return SkRect::MakeWH(SkIntToScalar(index+1), SkIntToScalar(index+1));
  113. }
  114. ///////////////////////////////////////////////////////////////////////////////
  115. DEF_BENCH(return new RTreeBuildBench("XY", &make_XYordered_rects));
  116. DEF_BENCH(return new RTreeBuildBench("YX", &make_YXordered_rects));
  117. DEF_BENCH(return new RTreeBuildBench("random", &make_random_rects));
  118. DEF_BENCH(return new RTreeBuildBench("concentric", &make_concentric_rects));
  119. DEF_BENCH(return new RTreeQueryBench("XY", &make_XYordered_rects));
  120. DEF_BENCH(return new RTreeQueryBench("YX", &make_YXordered_rects));
  121. DEF_BENCH(return new RTreeQueryBench("random", &make_random_rects));
  122. DEF_BENCH(return new RTreeQueryBench("concentric", &make_concentric_rects));