blob: 712d37f045e357ec390130a20a385ce0dbe6e7e6 [file] [log] [blame]
robertphillips423f6462015-10-19 12:15:55 -07001/*
2 * Copyright 2015 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
Mike Kleinc0bd9f92019-04-23 12:05:21 -05008#include "bench/Benchmark.h"
9#include "include/core/SkString.h"
10#include "include/utils/SkRandom.h"
11#include "src/core/SkTTopoSort.h"
robertphillips423f6462015-10-19 12:15:55 -070012
Mike Kleinc0bd9f92019-04-23 12:05:21 -050013#include "tools/ToolUtils.h"
robertphillips423f6462015-10-19 12:15:55 -070014
15class TopoSortBench : public Benchmark {
16public:
17 TopoSortBench() { }
18
19 ~TopoSortBench() override {
robertphillips423f6462015-10-19 12:15:55 -070020 }
21
22 bool isSuitableFor(Backend backend) override {
23 return kNonRendering_Backend == backend;
24 }
25
26protected:
27 const char* onGetName() override {
28 return "sort_topo_rand";
29 }
30
31 // Delayed initialization only done if onDraw will be called.
32 void onDelayedSetup() override {
Mike Kleinea3f0142019-03-20 11:12:10 -050033 ToolUtils::TopoTestNode::AllocNodes(&fGraph, kNumElements);
robertphillips423f6462015-10-19 12:15:55 -070034
35 for (int i = kNumElements-1; i > 0; --i) {
36 int numEdges = fRand.nextU() % (kMaxEdges+1);
37
38 for (int j = 0; j < numEdges; ++j) {
39 int dep = fRand.nextU() % i;
40
Robert Phillips4150eea2018-02-07 17:08:21 -050041 fGraph[i]->dependsOn(fGraph[dep].get());
robertphillips423f6462015-10-19 12:15:55 -070042 }
43 }
44 }
45
46 void onDraw(int loops, SkCanvas*) override {
47 for (int i = 0; i < loops; ++i) {
48 for (int j = 0; j < fGraph.count(); ++j) {
49 fGraph[j]->reset();
50 }
51
Mike Kleinea3f0142019-03-20 11:12:10 -050052 ToolUtils::TopoTestNode::Shuffle(&fGraph, &fRand);
robertphillips423f6462015-10-19 12:15:55 -070053
Mike Kleinea3f0142019-03-20 11:12:10 -050054 SkDEBUGCODE(bool actualResult =) SkTTopoSort<ToolUtils::TopoTestNode>(&fGraph);
robertphillips423f6462015-10-19 12:15:55 -070055 SkASSERT(actualResult);
56
57#ifdef SK_DEBUG
58 for (int j = 0; j < fGraph.count(); ++j) {
59 SkASSERT(fGraph[j]->check());
60 }
61#endif
62 }
63 }
64
65private:
66 static const int kNumElements = 1000;
67 static const int kMaxEdges = 5;
68
Mike Kleinea3f0142019-03-20 11:12:10 -050069 SkTArray<sk_sp<ToolUtils::TopoTestNode>> fGraph;
robertphillips423f6462015-10-19 12:15:55 -070070 SkRandom fRand;
71
72 typedef Benchmark INHERITED;
73};
74
75///////////////////////////////////////////////////////////////////////////////
76
77DEF_BENCH( return new TopoSortBench(); )