bench/TopoSortBench.cpp

   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(); )