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 | |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 8 | #include "Benchmark.h" |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 9 | #include "SkRandom.h" |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 10 | #include "SkString.h" |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 11 | #include "SkTSort.h" |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 12 | |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 13 | static const int N = 1000; |
| 14 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 15 | static void rand_proc(int array[N]) { |
commit-bot@chromium.org | e0e7cfe | 2013-09-09 20:09:12 +0000 | [diff] [blame] | 16 | SkRandom rand; |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 17 | for (int i = 0; i < N; ++i) { |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 18 | array[i] = rand.nextS(); |
| 19 | } |
| 20 | } |
| 21 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 22 | static void randN_proc(int array[N]) { |
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; |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 25 | for (int i = 0; i < N; ++i) { |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 26 | array[i] = rand.nextU() % mod; |
| 27 | } |
| 28 | } |
| 29 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 30 | static void forward_proc(int array[N]) { |
| 31 | for (int i = 0; i < N; ++i) { |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 32 | array[i] = i; |
| 33 | } |
| 34 | } |
| 35 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 36 | static void backward_proc(int array[N]) { |
| 37 | for (int i = 0; i < N; ++i) { |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 38 | array[i] = -i; |
| 39 | } |
| 40 | } |
| 41 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 42 | static void same_proc(int array[N]) { |
| 43 | for (int i = 0; i < N; ++i) { |
| 44 | array[i] = N; |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 45 | } |
| 46 | } |
| 47 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 48 | typedef void (*SortProc)(int array[N]); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 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 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 65 | static void skqsort_sort(int array[N]) { |
| 66 | // End is inclusive for SkTQSort! |
| 67 | SkTQSort<int>(array, array + N - 1); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 68 | } |
| 69 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 70 | static void skheap_sort(int array[N]) { |
| 71 | SkTHeapSort<int>(array, N); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 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 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 82 | static void qsort_sort(int array[N]) { |
| 83 | qsort(array, N, sizeof(int), int_compare); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 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 | |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 99 | class SortBench : public Benchmark { |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 100 | SkString fName; |
| 101 | const Type fType; |
| 102 | const SortProc fSortProc; |
| 103 | SkAutoTMalloc<int> fUnsorted; |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 104 | |
| 105 | public: |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 106 | SortBench(Type t, SortType s) : fType(t), fSortProc(gSorts[s].fProc) { |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 107 | fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 108 | } |
| 109 | |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 110 | bool isSuitableFor(Backend backend) override { |
commit-bot@chromium.org | 644629c | 2013-11-21 06:21:58 +0000 | [diff] [blame] | 111 | return backend == kNonRendering_Backend; |
| 112 | } |
| 113 | |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 114 | protected: |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 115 | const char* onGetName() override { |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 116 | return fName.c_str(); |
| 117 | } |
| 118 | |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 119 | // Delayed initialization only done if onDraw will be called. |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 120 | void onPreDraw() override { |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 121 | fUnsorted.reset(N); |
| 122 | gRec[fType].fProc(fUnsorted.get()); |
| 123 | } |
| 124 | |
mtklein | 36352bf | 2015-03-25 18:17:31 -0700 | [diff] [blame^] | 125 | void onDraw(const int loops, SkCanvas*) override { |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 126 | SkAutoTMalloc<int> sorted(N); |
commit-bot@chromium.org | 3361471 | 2013-12-03 18:17:16 +0000 | [diff] [blame] | 127 | for (int i = 0; i < loops; i++) { |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 128 | memcpy(sorted.get(), fUnsorted.get(), N*sizeof(int)); |
| 129 | fSortProc(sorted.get()); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 130 | #ifdef SK_DEBUG |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 131 | for (int j = 1; j < N; ++j) { |
| 132 | SkASSERT(sorted[j - 1] <= sorted[j]); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 133 | } |
| 134 | #endif |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | private: |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 139 | typedef Benchmark INHERITED; |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 140 | }; |
| 141 | |
| 142 | /////////////////////////////////////////////////////////////////////////////// |
| 143 | |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 144 | static Benchmark* NewSkQSort(Type t) { |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 145 | return new SortBench(t, kSKQSort); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 146 | } |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 147 | static Benchmark* NewSkHeap(Type t) { |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 148 | return new SortBench(t, kSKHeap); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 149 | } |
tfarina | f168b86 | 2014-06-19 12:32:29 -0700 | [diff] [blame] | 150 | static Benchmark* NewQSort(Type t) { |
mtklein@google.com | b352627 | 2013-09-17 19:37:34 +0000 | [diff] [blame] | 151 | return new SortBench(t, kQSort); |
mike@reedtribe.org | a3f1c8e | 2013-01-23 02:23:40 +0000 | [diff] [blame] | 152 | } |
| 153 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame] | 154 | DEF_BENCH( return NewSkQSort(kRand); ) |
| 155 | DEF_BENCH( return NewSkHeap(kRand); ) |
| 156 | DEF_BENCH( return NewQSort(kRand); ) |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 157 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame] | 158 | DEF_BENCH( return NewSkQSort(kRandN); ) |
| 159 | DEF_BENCH( return NewSkHeap(kRandN); ) |
| 160 | DEF_BENCH( return NewQSort(kRandN); ) |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 161 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame] | 162 | DEF_BENCH( return NewSkQSort(kFore); ) |
| 163 | DEF_BENCH( return NewSkHeap(kFore); ) |
| 164 | DEF_BENCH( return NewQSort(kFore); ) |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 165 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame] | 166 | DEF_BENCH( return NewSkQSort(kBack); ) |
| 167 | DEF_BENCH( return NewSkHeap(kBack); ) |
| 168 | DEF_BENCH( return NewQSort(kBack); ) |
reed@google.com | eebdd96 | 2013-01-23 14:52:12 +0000 | [diff] [blame] | 169 | |
mtklein@google.com | 410e6e8 | 2013-09-13 19:52:27 +0000 | [diff] [blame] | 170 | DEF_BENCH( return NewSkQSort(kSame); ) |
| 171 | DEF_BENCH( return NewSkHeap(kSame); ) |
| 172 | DEF_BENCH( return NewQSort(kSame); ) |