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 typedef Benchmark INHERITED; 73 }; 74 75 /////////////////////////////////////////////////////////////////////////////// 76 77 DEF_BENCH( return new TopoSortBench(); ) 78