1 /*
2 * Copyright 2020 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
8 #include "bench/Benchmark.h"
9 #include "include/gpu/ganesh/GrDirectContext.h"
10 #include "src/core/SkPathPriv.h"
11 #include "src/core/SkRectPriv.h"
12 #include "src/gpu/ganesh/GrDirectContextPriv.h"
13 #include "src/gpu/ganesh/GrPipeline.h"
14 #include "src/gpu/ganesh/mock/GrMockOpTarget.h"
15 #include "src/gpu/ganesh/tessellate/PathTessellator.h"
16 #include "src/gpu/ganesh/tessellate/StrokeTessellator.h"
17 #include "src/gpu/tessellate/AffineMatrix.h"
18 #include "src/gpu/tessellate/MiddleOutPolygonTriangulator.h"
19 #include "src/gpu/tessellate/WangsFormula.h"
20 #include "tools/ToolUtils.h"
21
22 #include <vector>
23
24 namespace skgpu::ganesh {
25
26 // This is the number of cubics in desk_chalkboard.skp. (There are no quadratics in the chalkboard.)
27 constexpr static int kNumCubicsInChalkboard = 47182;
28
make_mock_context()29 static sk_sp<GrDirectContext> make_mock_context() {
30 GrMockOptions mockOptions;
31 mockOptions.fDrawInstancedSupport = true;
32 mockOptions.fMapBufferFlags = GrCaps::kCanMap_MapFlag;
33 mockOptions.fConfigOptions[(int)GrColorType::kAlpha_8].fRenderability =
34 GrMockOptions::ConfigOptions::Renderability::kMSAA;
35 mockOptions.fConfigOptions[(int)GrColorType::kAlpha_8].fTexturable = true;
36 mockOptions.fIntegerSupport = true;
37
38 GrContextOptions ctxOptions;
39 ctxOptions.fGpuPathRenderers = GpuPathRenderers::kTessellation;
40
41 return GrDirectContext::MakeMock(&mockOptions, ctxOptions);
42 }
43
make_cubic_path(int maxPow2)44 static SkPath make_cubic_path(int maxPow2) {
45 SkRandom rand;
46 SkPath path;
47 for (int i = 0; i < kNumCubicsInChalkboard/2; ++i) {
48 float x = std::ldexp(rand.nextF(), (i % maxPow2)) / 1e3f;
49 path.cubicTo(111.625f*x, 308.188f*x, 764.62f*x, -435.688f*x, 742.63f*x, 85.187f*x);
50 path.cubicTo(764.62f*x, -435.688f*x, 111.625f*x, 308.188f*x, 0, 0);
51 }
52 return path;
53 }
54
make_conic_path()55 static SkPath make_conic_path() {
56 SkRandom rand;
57 SkPath path;
58 for (int i = 0; i < kNumCubicsInChalkboard / 40; ++i) {
59 for (int j = -10; j <= 10; j++) {
60 const float x = std::ldexp(rand.nextF(), (i % 18)) / 1e3f;
61 const float w = std::ldexp(1 + rand.nextF(), j);
62 path.conicTo(111.625f * x, 308.188f * x, 764.62f * x, -435.688f * x, w);
63 }
64 }
65 return path;
66 }
67
make_quad_path(int maxPow2)68 [[maybe_unused]] static SkPath make_quad_path(int maxPow2) {
69 SkRandom rand;
70 SkPath path;
71 for (int i = 0; i < kNumCubicsInChalkboard; ++i) {
72 float x = std::ldexp(rand.nextF(), (i % maxPow2)) / 1e3f;
73 path.quadTo(111.625f * x, 308.188f * x, 764.62f * x, -435.688f * x);
74 }
75 return path;
76 }
77
make_line_path(int maxPow2)78 [[maybe_unused]] static SkPath make_line_path(int maxPow2) {
79 SkRandom rand;
80 SkPath path;
81 for (int i = 0; i < kNumCubicsInChalkboard; ++i) {
82 float x = std::ldexp(rand.nextF(), (i % maxPow2)) / 1e3f;
83 path.lineTo(764.62f * x, -435.688f * x);
84 }
85 return path;
86 }
87
88 // This serves as a base class for benchmarking individual methods on PathTessellateOp.
89 class PathTessellateBenchmark : public Benchmark {
90 public:
PathTessellateBenchmark(const char * subName,const SkPath & p,const SkMatrix & m)91 PathTessellateBenchmark(const char* subName, const SkPath& p, const SkMatrix& m)
92 : fPath(p), fMatrix(m) {
93 fName.printf("tessellate_%s", subName);
94 }
95
onGetName()96 const char* onGetName() override { return fName.c_str(); }
isSuitableFor(Backend backend)97 bool isSuitableFor(Backend backend) final { return backend == Backend::kNonRendering; }
98
99 protected:
onDelayedSetup()100 void onDelayedSetup() override {
101 fTarget = std::make_unique<GrMockOpTarget>(make_mock_context());
102 }
103
onDraw(int loops,SkCanvas *)104 void onDraw(int loops, SkCanvas*) final {
105 if (!fTarget->mockContext()) {
106 SkDebugf("ERROR: could not create mock context.");
107 return;
108 }
109 for (int i = 0; i < loops; ++i) {
110 this->runBench();
111 fTarget->resetAllocator();
112 }
113 }
114
115 virtual void runBench() = 0;
116
117 SkString fName;
118 std::unique_ptr<GrMockOpTarget> fTarget;
119 const SkPath fPath;
120 const SkMatrix fMatrix;
121 };
122
123 #define DEF_PATH_TESS_BENCH(NAME, PATH, MATRIX) \
124 class PathTessellateBenchmark_##NAME : public PathTessellateBenchmark { \
125 public: \
126 PathTessellateBenchmark_##NAME() : PathTessellateBenchmark(#NAME, (PATH), (MATRIX)) {} \
127 void runBench() override; \
128 }; \
129 DEF_BENCH( return new PathTessellateBenchmark_##NAME(); ); \
130 void PathTessellateBenchmark_##NAME::runBench()
131
132 static const SkMatrix gAlmostIdentity = SkMatrix::MakeAll(
133 1.0001f, 0.0001f, 0.0001f,
134 -.0001f, 0.9999f, -.0001f,
135 0, 0, 1);
136
137 DEF_PATH_TESS_BENCH(GrPathCurveTessellator, make_cubic_path(8), SkMatrix::I()) {
138 SkArenaAlloc arena(1024);
139 GrPipeline noVaryingsPipeline(GrScissorTest::kDisabled, SkBlendMode::kSrcOver,
140 skgpu::Swizzle::RGBA());
141 auto tess = PathCurveTessellator::Make(&arena,
142 fTarget->caps().shaderCaps()->fInfinitySupport);
143 tess->prepare(fTarget.get(),
144 fMatrix,
145 {gAlmostIdentity, fPath, SK_PMColor4fTRANSPARENT},
146 fPath.countVerbs());
147 }
148
149 DEF_PATH_TESS_BENCH(GrPathWedgeTessellator, make_cubic_path(8), SkMatrix::I()) {
150 SkArenaAlloc arena(1024);
151 GrPipeline noVaryingsPipeline(GrScissorTest::kDisabled, SkBlendMode::kSrcOver,
152 skgpu::Swizzle::RGBA());
153 auto tess = PathWedgeTessellator::Make(&arena,
154 fTarget->caps().shaderCaps()->fInfinitySupport);
155 tess->prepare(fTarget.get(),
156 fMatrix,
157 {gAlmostIdentity, fPath, SK_PMColor4fTRANSPARENT},
158 fPath.countVerbs());
159 }
160
benchmark_wangs_formula_cubic_log2(const SkMatrix & matrix,const SkPath & path)161 static void benchmark_wangs_formula_cubic_log2(const SkMatrix& matrix, const SkPath& path) {
162 int sum = 0;
163 wangs_formula::VectorXform xform(matrix);
164 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
165 if (verb == SkPathVerb::kCubic) {
166 sum += wangs_formula::cubic_log2(4, pts, xform);
167 }
168 }
169 // Don't let the compiler optimize away wangs_formula::cubic_log2.
170 if (sum <= 0) {
171 SK_ABORT("sum should be > 0.");
172 }
173 }
174
175 DEF_PATH_TESS_BENCH(wangs_formula_cubic_log2, make_cubic_path(18), SkMatrix::I()) {
176 benchmark_wangs_formula_cubic_log2(fMatrix, fPath);
177 }
178
179 DEF_PATH_TESS_BENCH(wangs_formula_cubic_log2_scale, make_cubic_path(18),
180 SkMatrix::Scale(1.1f, 0.9f)) {
181 benchmark_wangs_formula_cubic_log2(fMatrix, fPath);
182 }
183
184 DEF_PATH_TESS_BENCH(wangs_formula_cubic_log2_affine, make_cubic_path(18),
185 SkMatrix::MakeAll(.9f,0.9f,0, 1.1f,1.1f,0, 0,0,1)) {
186 benchmark_wangs_formula_cubic_log2(fMatrix, fPath);
187 }
188
benchmark_wangs_formula_conic(const SkMatrix & matrix,const SkPath & path)189 static void benchmark_wangs_formula_conic(const SkMatrix& matrix, const SkPath& path) {
190 int sum = 0;
191 wangs_formula::VectorXform xform(matrix);
192 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
193 if (verb == SkPathVerb::kConic) {
194 sum += wangs_formula::conic(4, pts, *w, xform);
195 }
196 }
197 // Don't let the compiler optimize away wangs_formula::conic.
198 if (sum <= 0) {
199 SK_ABORT("sum should be > 0.");
200 }
201 }
202
benchmark_wangs_formula_conic_log2(const SkMatrix & matrix,const SkPath & path)203 static void benchmark_wangs_formula_conic_log2(const SkMatrix& matrix, const SkPath& path) {
204 int sum = 0;
205 wangs_formula::VectorXform xform(matrix);
206 for (auto [verb, pts, w] : SkPathPriv::Iterate(path)) {
207 if (verb == SkPathVerb::kConic) {
208 sum += wangs_formula::conic_log2(4, pts, *w, xform);
209 }
210 }
211 // Don't let the compiler optimize away wangs_formula::conic.
212 if (sum <= 0) {
213 SK_ABORT("sum should be > 0.");
214 }
215 }
216
DEF_PATH_TESS_BENCH(wangs_formula_conic,make_conic_path (),SkMatrix::I ())217 DEF_PATH_TESS_BENCH(wangs_formula_conic, make_conic_path(), SkMatrix::I()) {
218 benchmark_wangs_formula_conic(fMatrix, fPath);
219 }
220
DEF_PATH_TESS_BENCH(wangs_formula_conic_log2,make_conic_path (),SkMatrix::I ())221 DEF_PATH_TESS_BENCH(wangs_formula_conic_log2, make_conic_path(), SkMatrix::I()) {
222 benchmark_wangs_formula_conic_log2(fMatrix, fPath);
223 }
224
225 DEF_PATH_TESS_BENCH(middle_out_triangulation,
226 ToolUtils::make_star(SkRect::MakeWH(500, 500), kNumCubicsInChalkboard),
227 SkMatrix::I()) {
228 // Conservative estimate of triangulation (see PathStencilCoverOp)
229 const int maxVerts = 3 * (kNumCubicsInChalkboard - 2);
230
231 sk_sp<const GrBuffer> buffer;
232 int baseVertex;
233 VertexWriter vertexWriter = fTarget->makeVertexWriter(
234 sizeof(SkPoint), maxVerts, &buffer, &baseVertex);
235 tess::AffineMatrix m(gAlmostIdentity);
236 for (tess::PathMiddleOutFanIter it(fPath); !it.done();) {
237 for (auto [p0, p1, p2] : it.nextStack()) {
238 vertexWriter << m.map2Points(p0, p1) << m.mapPoint(p2);
239 }
240 }
241 }
242
243 using PathStrokeList = StrokeTessellator::PathStrokeList;
244 using MakePathStrokesFn = std::vector<PathStrokeList>(*)();
245
make_simple_cubic_path()246 static std::vector<PathStrokeList> make_simple_cubic_path() {
247 auto path = SkPath().moveTo(0, 0);
248 for (int i = 0; i < kNumCubicsInChalkboard/2; ++i) {
249 path.cubicTo(100, 0, 50, 100, 100, 100);
250 path.cubicTo(0, -100, 200, 100, 0, 0);
251 }
252 SkStrokeRec stroke(SkStrokeRec::kFill_InitStyle);
253 stroke.setStrokeStyle(8);
254 stroke.setStrokeParams(SkPaint::kButt_Cap, SkPaint::kMiter_Join, 4);
255 return {{path, stroke, SK_PMColor4fWHITE}};
256 }
257
258 // Generates a list of paths that resemble the MotionMark benchmark.
make_motionmark_paths()259 static std::vector<PathStrokeList> make_motionmark_paths() {
260 std::vector<PathStrokeList> pathStrokes;
261 SkRandom rand;
262 for (int i = 0; i < 8702; ++i) {
263 // The number of paths with a given number of verbs in the MotionMark bench gets cut in half
264 // every time the number of verbs increases by 1.
265 int numVerbs = 28 - SkNextLog2(rand.nextRangeU(0, (1 << 27) - 1));
266 SkPath path;
267 for (int j = 0; j < numVerbs; ++j) {
268 switch (rand.nextU() & 3) {
269 case 0:
270 case 1:
271 path.lineTo(rand.nextRangeF(0, 150), rand.nextRangeF(0, 150));
272 break;
273 case 2:
274 if (rand.nextULessThan(10) == 0) {
275 // Cusp.
276 auto [x, y] = (path.isEmpty())
277 ? SkPoint{0,0}
278 : SkPathPriv::PointData(path)[path.countPoints() - 1];
279 path.quadTo(x + rand.nextRangeF(0, 150), y, x - rand.nextRangeF(0, 150), y);
280 } else {
281 path.quadTo(rand.nextRangeF(0, 150), rand.nextRangeF(0, 150),
282 rand.nextRangeF(0, 150), rand.nextRangeF(0, 150));
283 }
284 break;
285 case 3:
286 if (rand.nextULessThan(10) == 0) {
287 // Cusp.
288 float y = (path.isEmpty())
289 ? 0 : SkPathPriv::PointData(path)[path.countPoints() - 1].fY;
290 path.cubicTo(rand.nextRangeF(0, 150), y, rand.nextRangeF(0, 150), y,
291 rand.nextRangeF(0, 150), y);
292 } else {
293 path.cubicTo(rand.nextRangeF(0, 150), rand.nextRangeF(0, 150),
294 rand.nextRangeF(0, 150), rand.nextRangeF(0, 150),
295 rand.nextRangeF(0, 150), rand.nextRangeF(0, 150));
296 }
297 break;
298 }
299 }
300 SkStrokeRec stroke(SkStrokeRec::kFill_InitStyle);
301 // The number of paths with a given stroke width in the MotionMark bench gets cut in half
302 // every time the stroke width increases by 1.
303 float strokeWidth = 21 - log2f(rand.nextRangeF(0, 1 << 20));
304 stroke.setStrokeStyle(strokeWidth);
305 stroke.setStrokeParams(SkPaint::kButt_Cap, SkPaint::kBevel_Join, 0);
306 pathStrokes.emplace_back(path, stroke, SK_PMColor4fWHITE);
307 }
308 return pathStrokes;
309 }
310
311 using PatchAttribs = tess::PatchAttribs;
312
313 class TessPrepareBench : public Benchmark {
314 public:
TessPrepareBench(MakePathStrokesFn makePathStrokesFn,PatchAttribs attribs,float matrixScale,const char * suffix)315 TessPrepareBench(MakePathStrokesFn makePathStrokesFn,
316 PatchAttribs attribs,
317 float matrixScale,
318 const char* suffix)
319 : fMakePathStrokesFn(makePathStrokesFn)
320 , fPatchAttribs(attribs)
321 , fMatrixScale(matrixScale) {
322 fName.printf("tessellate_%s", suffix);
323 }
324
325 private:
onGetName()326 const char* onGetName() override { return fName.c_str(); }
isSuitableFor(Backend backend)327 bool isSuitableFor(Backend backend) final { return backend == Backend::kNonRendering; }
328
onDelayedSetup()329 void onDelayedSetup() override {
330 fTarget = std::make_unique<GrMockOpTarget>(make_mock_context());
331 if (!fTarget->mockContext()) {
332 SkDebugf("ERROR: could not create mock context.");
333 return;
334 }
335
336 fPathStrokes = fMakePathStrokesFn();
337 for (size_t i = 0; i < fPathStrokes.size(); ++i) {
338 if (i + 1 < fPathStrokes.size()) {
339 fPathStrokes[i].fNext = &fPathStrokes[i + 1];
340 }
341 fTotalVerbCount += fPathStrokes[i].fPath.countVerbs();
342 }
343
344 fTessellator = std::make_unique<StrokeTessellator>(fPatchAttribs);
345 }
346
onDraw(int loops,SkCanvas *)347 void onDraw(int loops, SkCanvas*) final {
348 for (int i = 0; i < loops; ++i) {
349 fTessellator->prepare(fTarget.get(),
350 SkMatrix::Scale(fMatrixScale, fMatrixScale),
351 fPathStrokes.data(),
352 fTotalVerbCount);
353 fTarget->resetAllocator();
354 }
355 }
356
357 SkString fName;
358 MakePathStrokesFn fMakePathStrokesFn;
359 const PatchAttribs fPatchAttribs;
360 float fMatrixScale;
361 std::unique_ptr<GrMockOpTarget> fTarget;
362 std::vector<PathStrokeList> fPathStrokes;
363 std::unique_ptr<StrokeTessellator> fTessellator;
364 SkArenaAlloc fPersistentArena{1024};
365 int fTotalVerbCount = 0;
366 };
367
368 DEF_BENCH(return new TessPrepareBench(
369 make_simple_cubic_path, PatchAttribs::kNone, 1,
370 "GrStrokeFixedCountTessellator");
371 )
372
373 DEF_BENCH(return new TessPrepareBench(
374 make_simple_cubic_path, PatchAttribs::kNone, 5,
375 "GrStrokeFixedCountTessellator_one_chop");
376 )
377
378 DEF_BENCH(return new TessPrepareBench(
379 make_motionmark_paths, PatchAttribs::kStrokeParams, 1,
380 "GrStrokeFixedCountTessellator_motionmark");
381 )
382
383 } // namespace skgpu::ganesh
384