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 "Benchmark.h" 9 #include "SkRandom.h" 10 #include "SkString.h" 11 #include "SkTTopoSort.h" 12 13 #include "sk_tool_utils.h" 14 15 class TopoSortBench : public Benchmark { 16 public: TopoSortBench()17 TopoSortBench() { } 18 ~TopoSortBench()19 ~TopoSortBench() override { 20 sk_tool_utils::TopoTestNode::DeallocNodes(&fGraph); 21 } 22 isSuitableFor(Backend backend)23 bool isSuitableFor(Backend backend) override { 24 return kNonRendering_Backend == backend; 25 } 26 27 protected: onGetName()28 const char* onGetName() override { 29 return "sort_topo_rand"; 30 } 31 32 // Delayed initialization only done if onDraw will be called. onDelayedSetup()33 void onDelayedSetup() override { 34 sk_tool_utils::TopoTestNode::AllocNodes(&fGraph, kNumElements); 35 36 for (int i = kNumElements-1; i > 0; --i) { 37 int numEdges = fRand.nextU() % (kMaxEdges+1); 38 39 for (int j = 0; j < numEdges; ++j) { 40 int dep = fRand.nextU() % i; 41 42 fGraph[i]->dependsOn(fGraph[dep]); 43 } 44 } 45 } 46 onDraw(int loops,SkCanvas *)47 void onDraw(int loops, SkCanvas*) override { 48 for (int i = 0; i < loops; ++i) { 49 for (int j = 0; j < fGraph.count(); ++j) { 50 fGraph[j]->reset(); 51 } 52 53 sk_tool_utils::TopoTestNode::Shuffle(&fGraph, &fRand); 54 55 SkDEBUGCODE(bool actualResult =) SkTTopoSort<sk_tool_utils::TopoTestNode>(&fGraph); 56 SkASSERT(actualResult); 57 58 #ifdef SK_DEBUG 59 for (int j = 0; j < fGraph.count(); ++j) { 60 SkASSERT(fGraph[j]->check()); 61 } 62 #endif 63 } 64 } 65 66 private: 67 static const int kNumElements = 1000; 68 static const int kMaxEdges = 5; 69 70 SkTDArray<sk_tool_utils::TopoTestNode*> fGraph; 71 SkRandom fRand; 72 73 typedef Benchmark INHERITED; 74 }; 75 76 /////////////////////////////////////////////////////////////////////////////// 77 78 DEF_BENCH( return new TopoSortBench(); ) 79