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 "SkBenchmark.h"
      9 #include "SkRandom.h"
     10 #include "SkTSort.h"
     11 #include "SkString.h"
     12 
     13 static const int N = 1000;
     14 
     15 static void rand_proc(int array[], int count) {
     16     SkRandom rand;
     17     for (int i = 0; i < count; ++i) {
     18         array[i] = rand.nextS();
     19     }
     20 }
     21 
     22 static void randN_proc(int array[], int count) {
     23     SkRandom rand;
     24     int mod = N / 10;
     25     for (int i = 0; i < count; ++i) {
     26         array[i] = rand.nextU() % mod;
     27     }
     28 }
     29 
     30 static void forward_proc(int array[], int count) {
     31     for (int i = 0; i < count; ++i) {
     32         array[i] = i;
     33     }
     34 }
     35 
     36 static void backward_proc(int array[], int count) {
     37     for (int i = 0; i < count; ++i) {
     38         array[i] = -i;
     39     }
     40 }
     41 
     42 static void same_proc(int array[], int count) {
     43     for (int i = 0; i < count; ++i) {
     44         array[i] = count;
     45     }
     46 }
     47 
     48 typedef void (*SortProc)(int array[], int count);
     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[], int count) {
     66     SkTQSort<int>(array, array + count);
     67 }
     68 
     69 static void skheap_sort(int array[], int count) {
     70     SkTHeapSort<int>(array, count);
     71 }
     72 
     73 extern "C" {
     74     static int int_compare(const void* a, const void* b) {
     75         const int ai = *(const int*)a;
     76         const int bi = *(const int*)b;
     77         return ai < bi ? -1 : (ai > bi);
     78     }
     79 }
     80 
     81 static void qsort_sort(int array[], int count) {
     82     qsort(array, count, sizeof(int), int_compare);
     83 }
     84 
     85 enum SortType {
     86     kSKQSort, kSKHeap, kQSort
     87 };
     88 
     89 static const struct {
     90     const char* fName;
     91     SortProc    fProc;
     92 } gSorts[] = {
     93     { "skqsort", skqsort_sort },
     94     { "skheap", skheap_sort },
     95     { "qsort", qsort_sort },
     96 };
     97 
     98 class SortBench : public SkBenchmark {
     99     SkString    fName;
    100     enum { MAX = 100000 };
    101     int         fUnsorted[MAX];
    102     int         fSorted[MAX];
    103     int         fCount;
    104     SortProc    fSortProc;
    105 
    106 public:
    107     SortBench(void* param, Type t, int n, SortType s) : INHERITED(param) {
    108         if (n > MAX) {
    109             n = MAX;
    110         }
    111         fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName);
    112         fCount = n;
    113         gRec[t].fProc(fUnsorted, n);
    114         fSortProc = gSorts[s].fProc;
    115         fIsRendering = false;
    116     }
    117 
    118 protected:
    119     virtual const char* onGetName() SK_OVERRIDE {
    120         return fName.c_str();
    121     }
    122 
    123     virtual void onDraw(SkCanvas*) {
    124         int n = SkBENCHLOOP(200);
    125         for (int i = 0; i < n; i++) {
    126             memcpy(fSorted, fUnsorted, fCount * sizeof(int));
    127             fSortProc(fSorted, fCount);
    128 #ifdef SK_DEBUG
    129             for (int j = 1; j < fCount; ++j) {
    130                 SkASSERT(fSorted[j - 1] <= fSorted[j]);
    131             }
    132 #endif
    133         }
    134     }
    135 
    136 private:
    137     typedef SkBenchmark INHERITED;
    138 };
    139 
    140 ///////////////////////////////////////////////////////////////////////////////
    141 
    142 static SkBenchmark* NewSkQSort(void* param, Type t) {
    143     return new SortBench(param, t, N, kSKQSort);
    144 }
    145 static SkBenchmark* NewSkHeap(void* param, Type t) {
    146     return new SortBench(param, t, N, kSKHeap);
    147 }
    148 static SkBenchmark* NewQSort(void* param, Type t) {
    149     return new SortBench(param, t, N, kQSort);
    150 }
    151 
    152 DEF_BENCH( return NewSkQSort(p, kRand); )
    153 DEF_BENCH( return NewSkHeap(p, kRand); )
    154 DEF_BENCH( return NewQSort(p, kRand); )
    155 
    156 DEF_BENCH( return NewSkQSort(p, kRandN); )
    157 DEF_BENCH( return NewSkHeap(p, kRandN); )
    158 DEF_BENCH( return NewQSort(p, kRandN); )
    159 
    160 DEF_BENCH( return NewSkQSort(p, kFore); )
    161 DEF_BENCH( return NewSkHeap(p, kFore); )
    162 DEF_BENCH( return NewQSort(p, kFore); )
    163 
    164 DEF_BENCH( return NewSkQSort(p, kBack); )
    165 DEF_BENCH( return NewSkHeap(p, kBack); )
    166 DEF_BENCH( return NewQSort(p, kBack); )
    167 
    168 DEF_BENCH( return NewSkQSort(p, kSame); )
    169 DEF_BENCH( return NewSkHeap(p, kSame); )
    170 DEF_BENCH( return NewQSort(p, kSame); )
    171