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 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     virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
    111         return backend == kNonRendering_Backend;
    112     }
    113 
    114 protected:
    115     virtual const char* onGetName() SK_OVERRIDE {
    116         return fName.c_str();
    117     }
    118 
    119     // Delayed initialization only done if onDraw will be called.
    120     virtual void onPreDraw() SK_OVERRIDE {
    121         fUnsorted.reset(N);
    122         gRec[fType].fProc(fUnsorted.get());
    123     }
    124 
    125     virtual void onDraw(const int loops, SkCanvas*) SK_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); )
    173