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