1 /*
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 
8 #include "bench/Benchmark.h"
9 #include "include/core/SkString.h"
10 #include "include/utils/SkRandom.h"
11 #include "src/core/SkTTopoSort.h"
12 
13 #include "tools/ToolUtils.h"
14 
15 class TopoSortBench : public Benchmark {
16 public:
TopoSortBench()17     TopoSortBench() { }
18 
~TopoSortBench()19     ~TopoSortBench() override {
20     }
21 
isSuitableFor(Backend backend)22     bool isSuitableFor(Backend backend) override {
23         return kNonRendering_Backend == backend;
24     }
25 
26 protected:
onGetName()27     const char* onGetName() override {
28         return "sort_topo_rand";
29     }
30 
31     // Delayed initialization only done if onDraw will be called.
onDelayedSetup()32     void onDelayedSetup() override {
33         ToolUtils::TopoTestNode::AllocNodes(&fGraph, kNumElements);
34 
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 
41                 fGraph[i]->dependsOn(fGraph[dep].get());
42             }
43         }
44     }
45 
onDraw(int loops,SkCanvas *)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 
52             ToolUtils::TopoTestNode::Shuffle(&fGraph, &fRand);
53 
54             SkDEBUGCODE(bool actualResult =) SkTTopoSort<ToolUtils::TopoTestNode>(&fGraph);
55             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 
65 private:
66     static const int kNumElements = 1000;
67     static const int kMaxEdges = 5;
68 
69     SkTArray<sk_sp<ToolUtils::TopoTestNode>> fGraph;
70     SkRandom fRand;
71 
72     using INHERITED = Benchmark;
73 };
74 
75 ///////////////////////////////////////////////////////////////////////////////
76 
77 DEF_BENCH( return new TopoSortBench(); )
78