bench/SortBench.cpp

   1 /*
   2  * Copyright 2013 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 "SkTSort.h"
  12
  13 static const int N = 1000;
  14
  15 static void rand_proc(int array[N]) {
  16     SkRandom rand;
  17     for (int i = 0; i < N; ++i) {
  18         array[i] = rand.nextS();
  19     }
  20 }
  21
  22 static void randN_proc(int array[N]) {
  23     SkRandom rand;
  24     int mod = N / 10;
  25     for (int i = 0; i < N; ++i) {
  26         array[i] = rand.nextU() % mod;
  27     }
  28 }
  29
  30 static void forward_proc(int array[N]) {
  31     for (int i = 0; i < N; ++i) {
  32         array[i] = i;
  33     }
  34 }
  35
  36 static void backward_proc(int array[N]) {
  37     for (int i = 0; i < N; ++i) {
  38         array[i] = -i;
  39     }
  40 }
  41
  42 static void same_proc(int array[N]) {
  43     for (int i = 0; i < N; ++i) {
  44         array[i] = N;
  45     }
  46 }
  47
  48 typedef void (*SortProc)(int array[N]);
  49
  50 enum Type {
  51     kRand, kRandN, kFore, kBack, kSame
  52 };
  53
  54 static const struct {
  55     const char* fName;
  56     SortProc    fProc;
  57 } gRec[] = {
  58     { "rand", rand_proc },
  59     { "rand10", randN_proc },
  60     { "forward", forward_proc },
  61     { "backward", backward_proc },
  62     { "repeated", same_proc },
  63 };
  64
  65 static void skqsort_sort(int array[N]) {
  66     // End is inclusive for SkTQSort!
  67     SkTQSort<int>(array, array + N - 1);
  68 }
  69
  70 static void skheap_sort(int array[N]) {
  71     SkTHeapSort<int>(array, N);
  72 }
  73
  74 extern "C" {
  75     static int int_compare(const void* a, const void* b) {
  76         const int ai = *(const int*)a;
  77         const int bi = *(const int*)b;
  78         return ai < bi ? -1 : (ai > bi);
  79     }
  80 }
  81
  82 static void qsort_sort(int array[N]) {
  83     qsort(array, N, sizeof(int), int_compare);
  84 }
  85
  86 enum SortType {
  87     kSKQSort, kSKHeap, kQSort
  88 };
  89
  90 static const struct {
  91     const char* fName;
  92     SortProc    fProc;
  93 } gSorts[] = {
  94     { "skqsort", skqsort_sort },
  95     { "skheap", skheap_sort },
  96     { "qsort", qsort_sort },
  97 };
  98
  99 class SortBench : public Benchmark {
 100     SkString           fName;
 101     const Type         fType;
 102     const SortProc     fSortProc;
 103     SkAutoTMalloc<int> fUnsorted;
 104
 105 public:
 106     SortBench(Type t, SortType s) : fType(t), fSortProc(gSorts[s].fProc) {
 107         fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName);
 108     }
 109
 110     bool isSuitableFor(Backend backend) override {
 111         return backend == kNonRendering_Backend;
 112     }
 113
 114 protected:
 115     const char* onGetName() override {
 116         return fName.c_str();
 117     }
 118
 119     // Delayed initialization only done if onDraw will be called.
 120     void onPreDraw() override {
 121         fUnsorted.reset(N);
 122         gRec[fType].fProc(fUnsorted.get());
 123     }
 124
 125     void onDraw(const int loops, SkCanvas*) override {
 126         SkAutoTMalloc<int> sorted(N);
 127         for (int i = 0; i < loops; i++) {
 128             memcpy(sorted.get(), fUnsorted.get(), N*sizeof(int));
 129             fSortProc(sorted.get());
 130 #ifdef SK_DEBUG
 131             for (int j = 1; j < N; ++j) {
 132                 SkASSERT(sorted[j - 1] <= sorted[j]);
 133             }
 134 #endif
 135         }
 136     }
 137
 138 private:
 139     typedef Benchmark INHERITED;
 140 };
 141
 142 ///////////////////////////////////////////////////////////////////////////////
 143
 144 static Benchmark* NewSkQSort(Type t) {
 145     return new SortBench(t, kSKQSort);
 146 }
 147 static Benchmark* NewSkHeap(Type t) {
 148     return new SortBench(t, kSKHeap);
 149 }
 150 static Benchmark* NewQSort(Type t) {
 151     return new SortBench(t, kQSort);
 152 }
 153
 154 DEF_BENCH( return NewSkQSort(kRand); )
 155 DEF_BENCH( return NewSkHeap(kRand); )
 156 DEF_BENCH( return NewQSort(kRand); )
 157
 158 DEF_BENCH( return NewSkQSort(kRandN); )
 159 DEF_BENCH( return NewSkHeap(kRandN); )
 160 DEF_BENCH( return NewQSort(kRandN); )
 161
 162 DEF_BENCH( return NewSkQSort(kFore); )
 163 DEF_BENCH( return NewSkHeap(kFore); )
 164 DEF_BENCH( return NewQSort(kFore); )
 165
 166 DEF_BENCH( return NewSkQSort(kBack); )
 167 DEF_BENCH( return NewSkHeap(kBack); )
 168 DEF_BENCH( return NewQSort(kBack); )
 169
 170 DEF_BENCH( return NewSkQSort(kSame); )
 171 DEF_BENCH( return NewSkHeap(kSame); )
 172 DEF_BENCH( return NewQSort(kSame); )