Home | History | Annotate | Download | only in bench 
      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:
     17     TopoSortBench() { }
     18 
     19     ~TopoSortBench() override {
     20     }
     21 
     22     bool isSuitableFor(Backend backend) override {
     23         return kNonRendering_Backend == backend;
     24     }
     25 
     26 protected:
     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 {
     33         sk_tool_utils::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 
     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             sk_tool_utils::TopoTestNode::Shuffle(&fGraph, &fRand);
     53 
     54             SkDEBUGCODE(bool actualResult =) SkTTopoSort<sk_tool_utils::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<sk_tool_utils::TopoTestNode>> fGraph;
     70     SkRandom fRand;
     71 
     72     typedef Benchmark INHERITED;
     73 };
     74 
     75 ///////////////////////////////////////////////////////////////////////////////
     76 
     77 DEF_BENCH( return new TopoSortBench(); )
     78