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