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         sk_tool_utils::TopoTestNode::DeallocNodes(&fGraph);
     21     }
     22 
     23     bool isSuitableFor(Backend backend) override {
     24         return kNonRendering_Backend == backend;
     25     }
     26 
     27 protected:
     28     const char* onGetName() override {
     29         return "sort_topo_rand";
     30     }
     31 
     32     // Delayed initialization only done if onDraw will be called.
     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 
     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