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