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 | |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 13 | static const int N = 1000; |
| 14 | |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 15 | static void rand_proc(int array[], int count) { |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 16 | SkRandom rand; |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 17 | for (int i = 0; i < count; ++i) { |
| 18 | array[i] = rand.nextS(); |
| 19 | } |
| 20 | } |
| 21 | |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 22 | static void randN_proc(int array[], int count) { |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 23 | SkRandom rand; |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 24 | int mod = N / 10; |
| 25 | for (int i = 0; i < count; ++i) { |
| 26 | array[i] = rand.nextU() % mod; |
| 27 | } |
| 28 | } |
| 29 | |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 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 { |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 51 | kRand, kRandN, kFore, kBack, kSame |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 52 | }; |
| 53 | |
| 54 | static const struct { |
| 55 | const char* fName; |
| 56 | SortProc fProc; |
| 57 | } gRec[] = { |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 58 | { "rand", rand_proc }, |
| 59 | { "rand10", randN_proc }, |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 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: |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 107 | SortBench(Type t, int n, SortType s) { |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 108 | if (n > MAX) { |
| 109 | n = MAX; |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 110 | } |
| 111 | fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName); |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 112 | fCount = n; |
| 113 | gRec[t].fProc(fUnsorted, n); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 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 | |
sugoi@google.com | 77472f0 | 2013-03-05 18:50:01 +0000 | [diff] [blame] | 123 | virtual void onDraw(SkCanvas*) { |
mtklein@google.com | c289743 | 2013-09-10 19:23:38 +0000 | [diff] [blame] | 124 | for (int i = 0; i < this->getLoops(); i++) { |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 125 | memcpy(fSorted, fUnsorted, fCount * sizeof(int)); |
| 126 | fSortProc(fSorted, fCount); |
| 127 | #ifdef SK_DEBUG |
| 128 | for (int j = 1; j < fCount; ++j) { |
| 129 | SkASSERT(fSorted[j - 1] <= fSorted[j]); |
| 130 | } |
| 131 | #endif |
| 132 | } |
| 133 | } |
| 134 | |
| 135 | private: |
| 136 | typedef SkBenchmark INHERITED; |
| 137 | }; |
| 138 | |
| 139 | /////////////////////////////////////////////////////////////////////////////// |
| 140 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 141 | static SkBenchmark* NewSkQSort(Type t) { |
| 142 | return new SortBench(t, N, kSKQSort); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 143 | } |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 144 | static SkBenchmark* NewSkHeap(Type t) { |
| 145 | return new SortBench(t, N, kSKHeap); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 146 | } |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 147 | static SkBenchmark* NewQSort(Type t) { |
| 148 | return new SortBench(t, N, kQSort); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 149 | } |
| 150 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 151 | DEF_BENCH( return NewSkQSort(kRand); ) |
| 152 | DEF_BENCH( return NewSkHeap(kRand); ) |
| 153 | DEF_BENCH( return NewQSort(kRand); ) |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 154 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 155 | DEF_BENCH( return NewSkQSort(kRandN); ) |
| 156 | DEF_BENCH( return NewSkHeap(kRandN); ) |
| 157 | DEF_BENCH( return NewQSort(kRandN); ) |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 158 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 159 | DEF_BENCH( return NewSkQSort(kFore); ) |
| 160 | DEF_BENCH( return NewSkHeap(kFore); ) |
| 161 | DEF_BENCH( return NewQSort(kFore); ) |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 162 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 163 | DEF_BENCH( return NewSkQSort(kBack); ) |
| 164 | DEF_BENCH( return NewSkHeap(kBack); ) |
| 165 | DEF_BENCH( return NewQSort(kBack); ) |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 166 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame^] | 167 | DEF_BENCH( return NewSkQSort(kSame); ) |
| 168 | DEF_BENCH( return NewSkHeap(kSame); ) |
| 169 | DEF_BENCH( return NewQSort(kSame); ) |