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