1/*
2 * Copyright 2021 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 "experimental/graphite/src/geom/IntersectionTree.h"
9#include "include/core/SkPaint.h"
10#include "include/core/SkPath.h"
11#include "include/utils/SkRandom.h"
12#include "src/core/SkMathPriv.h"
13#include "tools/ToolUtils.h"
14#include "tools/flags/CommandLineFlags.h"
15
16static DEFINE_string(intersectionTreeFile, "",
17                     "svg or skp for the IntersectionTree bench to sniff paths from.");
18
19namespace skgpu {
20
21class IntersectionTreeBench : public Benchmark {
22protected:
23    const char* onGetName() final { return fName.c_str(); }
24
25    bool isSuitableFor(Backend backend) override {
26        return backend == kNonRendering_Backend;
27    }
28
29    void onDelayedSetup() final {
30        SkTArray<SkRect> rects;
31        this->gatherRects(&rects);
32        fRectCount = rects.count();
33        fRects = fAlignedAllocator.makeArray<Rect>(fRectCount);
34        for (int i = 0; i < fRectCount; ++i) {
35            fRects[i] = rects[i];
36        }
37        fRectBufferA = fAlignedAllocator.makeArray<Rect>(fRectCount);
38        fRectBufferB = fAlignedAllocator.makeArray<Rect>(fRectCount);
39    }
40
41    virtual void gatherRects(SkTArray<SkRect>* rects) = 0;
42
43    void onDraw(int loops, SkCanvas*) final {
44        for (int i = 0; i < loops; ++i) {
45            this->doBench();
46        }
47    }
48
49    void doBench() {
50        Rect* rects = fRects;
51        Rect* collided = fRectBufferA;
52        int rectCount = fRectCount;
53        fNumTrees = 0;
54        while (rectCount > 0) {
55            IntersectionTree intersectionTree;
56            int collidedCount = 0;
57            for (int i = 0; i < rectCount; ++i) {
58                if (!intersectionTree.add(rects[i])) {
59                    collided[collidedCount++] = rects[i];
60                }
61            }
62            std::swap(rects, collided);
63            if (collided == fRects) {
64                collided = fRectBufferB;
65            }
66            rectCount = collidedCount;
67            ++fNumTrees;
68        }
69    }
70
71    SkString fName;
72    SkArenaAlloc fAlignedAllocator{0};
73    int fRectCount;
74    Rect* fRects;
75    Rect* fRectBufferA;
76    Rect* fRectBufferB;
77    int fNumTrees = 0;
78};
79
80class RandomIntersectionBench : public IntersectionTreeBench {
81public:
82    RandomIntersectionBench(int numRandomRects) : fNumRandomRects(numRandomRects) {
83        fName.printf("IntersectionTree_%i", numRandomRects);
84    }
85
86private:
87    void gatherRects(SkTArray<SkRect>* rects) override {
88        SkRandom rand;
89        for (int i = 0; i < fNumRandomRects; ++i) {
90            rects->push_back(SkRect::MakeXYWH(rand.nextRangeF(0, 2000),
91                                              rand.nextRangeF(0, 2000),
92                                              rand.nextRangeF(0, 70),
93                                              rand.nextRangeF(0, 70)));
94        }
95    }
96
97    const int fNumRandomRects;
98};
99
100class FileIntersectionBench : public IntersectionTreeBench {
101public:
102    FileIntersectionBench() {
103        if (FLAGS_intersectionTreeFile.isEmpty()) {
104            return;
105        }
106        const char* filename = strrchr(FLAGS_intersectionTreeFile[0], '/');
107        if (filename) {
108            ++filename;
109        } else {
110            filename = FLAGS_intersectionTreeFile[0];
111        }
112        fName.printf("IntersectionTree_file_%s", filename);
113    }
114
115private:
116    bool isSuitableFor(Backend backend) final {
117        if (FLAGS_intersectionTreeFile.isEmpty()) {
118            return false;
119        }
120        return IntersectionTreeBench::isSuitableFor(backend);
121    }
122
123    void gatherRects(SkTArray<SkRect>* rects) override {
124        if (FLAGS_intersectionTreeFile.isEmpty()) {
125            return;
126        }
127        ToolUtils::sniff_paths(FLAGS_intersectionTreeFile[0], [&](const SkMatrix& matrix,
128                                                                  const SkPath& path,
129                                                                  const SkPaint& paint) {
130            if (paint.getStyle() == SkPaint::kStroke_Style) {
131                return;  // Goes to stroker.
132            }
133            if (path.isConvex()) {
134                return;  // Goes to convex renderer.
135            }
136            int numVerbs = path.countVerbs();
137            SkRect drawBounds = matrix.mapRect(path.getBounds());
138            float gpuFragmentWork = drawBounds.height() * drawBounds.width();
139            float cpuTessellationWork = numVerbs * SkNextLog2(numVerbs);  // N log N.
140            constexpr static float kCpuWeight = 512;
141            constexpr static float kMinNumPixelsToTriangulate = 256 * 256;
142            if (cpuTessellationWork * kCpuWeight + kMinNumPixelsToTriangulate < gpuFragmentWork) {
143                return;  // Goes to inner triangulator.
144            }
145            rects->push_back(drawBounds);
146        });
147        SkDebugf(">> Found %i stencil/cover paths in %s <<\n",
148                 rects->count(), FLAGS_intersectionTreeFile[0]);
149    }
150
151    void onPerCanvasPostDraw(SkCanvas*) override {
152        if (FLAGS_intersectionTreeFile.isEmpty()) {
153            return;
154        }
155        SkDebugf(">> Reordered %s into %i different stencil/cover draws <<\n",
156                 FLAGS_intersectionTreeFile[0], fNumTrees);
157    }
158};
159
160}  // namespace skgpu
161
162DEF_BENCH( return new skgpu::RandomIntersectionBench(100); )
163DEF_BENCH( return new skgpu::RandomIntersectionBench(500); )
164DEF_BENCH( return new skgpu::RandomIntersectionBench(1000); )
165DEF_BENCH( return new skgpu::RandomIntersectionBench(5000); )
166DEF_BENCH( return new skgpu::RandomIntersectionBench(10000); )
167DEF_BENCH( return new skgpu::FileIntersectionBench(); )  // Sniffs --intersectionTreeFile
168