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 "bench/Benchmark.h"
9 #include "include/core/SkString.h"
10 #include "include/private/base/SkTemplates.h"
11 #include "src/base/SkRandom.h"
12 #include "src/base/SkTSort.h"
13
14 #include <algorithm>
15 #include <stdlib.h>
16
17 using namespace skia_private;
18
19 static const int N = 1000;
20
rand_proc(int array[N])21 static void rand_proc(int array[N]) {
22 SkRandom rand;
23 for (int i = 0; i < N; ++i) {
24 array[i] = rand.nextS();
25 }
26 }
27
randN_proc(int array[N])28 static void randN_proc(int array[N]) {
29 SkRandom rand;
30 int mod = N / 10;
31 for (int i = 0; i < N; ++i) {
32 array[i] = rand.nextU() % mod;
33 }
34 }
35
forward_proc(int array[N])36 static void forward_proc(int array[N]) {
37 for (int i = 0; i < N; ++i) {
38 array[i] = i;
39 }
40 }
41
backward_proc(int array[N])42 static void backward_proc(int array[N]) {
43 for (int i = 0; i < N; ++i) {
44 array[i] = -i;
45 }
46 }
47
same_proc(int array[N])48 static void same_proc(int array[N]) {
49 for (int i = 0; i < N; ++i) {
50 array[i] = N;
51 }
52 }
53
54 typedef void (*SortProc)(int array[N]);
55
56 enum Type {
57 kRand, kRandN, kFore, kBack, kSame
58 };
59
60 static const struct {
61 const char* fName;
62 SortProc fProc;
63 } gRec[] = {
64 { "rand", rand_proc },
65 { "rand10", randN_proc },
66 { "forward", forward_proc },
67 { "backward", backward_proc },
68 { "repeated", same_proc },
69 };
70
skqsort_sort(int array[N])71 static void skqsort_sort(int array[N]) {
72 SkTQSort<int>(array, array + N);
73 }
74
skheap_sort(int array[N])75 static void skheap_sort(int array[N]) {
76 SkTHeapSort<int>(array, N);
77 }
78
79 extern "C" {
int_compare(const void * a,const void * b)80 static int int_compare(const void* a, const void* b) {
81 const int ai = *(const int*)a;
82 const int bi = *(const int*)b;
83 return ai < bi ? -1 : (ai > bi);
84 }
85 }
86
qsort_sort(int array[N])87 static void qsort_sort(int array[N]) {
88 qsort(array, N, sizeof(int), int_compare);
89 }
90
stdsort_sort(int array[N])91 static void stdsort_sort(int array[N]) {
92 std::sort(array, array+N);
93 }
94
95 enum SortType {
96 kSKQSort, kSKHeap, kQSort, kStdSort,
97 };
98
99 static const struct {
100 const char* fName;
101 SortProc fProc;
102 } gSorts[] = {
103 { "skqsort", skqsort_sort },
104 { "skheap", skheap_sort },
105 { "qsort", qsort_sort },
106 { "stdsort", stdsort_sort },
107 };
108
109 class SortBench : public Benchmark {
110 SkString fName;
111 const Type fType;
112 const SortProc fSortProc;
113 AutoTMalloc<int> fUnsorted;
114
115 public:
SortBench(Type t,SortType s)116 SortBench(Type t, SortType s) : fType(t), fSortProc(gSorts[s].fProc) {
117 fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName);
118 }
119
isSuitableFor(Backend backend)120 bool isSuitableFor(Backend backend) override {
121 return backend == Backend::kNonRendering;
122 }
123
124 protected:
onGetName()125 const char* onGetName() override {
126 return fName.c_str();
127 }
128
129 // Delayed initialization only done if onDraw will be called.
onDelayedSetup()130 void onDelayedSetup() override {
131 fUnsorted.reset(N);
132 gRec[fType].fProc(fUnsorted.get());
133 }
134
onDraw(int loops,SkCanvas *)135 void onDraw(int loops, SkCanvas*) override {
136 AutoTMalloc<int> sorted(N);
137 for (int i = 0; i < loops; i++) {
138 memcpy(sorted.get(), fUnsorted.get(), N*sizeof(int));
139 fSortProc(sorted.get());
140 #ifdef SK_DEBUG
141 for (int j = 1; j < N; ++j) {
142 SkASSERT(sorted[j - 1] <= sorted[j]);
143 }
144 #endif
145 }
146 }
147
148 private:
149 using INHERITED = Benchmark;
150 };
151
152 ///////////////////////////////////////////////////////////////////////////////
153
NewSkQSort(Type t)154 static Benchmark* NewSkQSort(Type t) {
155 return new SortBench(t, kSKQSort);
156 }
NewSkHeap(Type t)157 static Benchmark* NewSkHeap(Type t) {
158 return new SortBench(t, kSKHeap);
159 }
NewQSort(Type t)160 static Benchmark* NewQSort(Type t) {
161 return new SortBench(t, kQSort);
162 }
NewStdSort(Type t)163 static Benchmark* NewStdSort(Type t) {
164 return new SortBench(t, kStdSort);
165 }
166
167 DEF_BENCH( return NewSkQSort(kRand); )
168 DEF_BENCH( return NewSkHeap(kRand); )
169 DEF_BENCH( return NewQSort(kRand); )
170 DEF_BENCH( return NewStdSort(kRand); )
171
172 DEF_BENCH( return NewSkQSort(kRandN); )
173 DEF_BENCH( return NewSkHeap(kRandN); )
174 DEF_BENCH( return NewQSort(kRandN); )
175 DEF_BENCH( return NewStdSort(kRandN); )
176
177 DEF_BENCH( return NewSkQSort(kFore); )
178 DEF_BENCH( return NewSkHeap(kFore); )
179 DEF_BENCH( return NewQSort(kFore); )
180 DEF_BENCH( return NewStdSort(kFore); )
181
182 DEF_BENCH( return NewSkQSort(kBack); )
183 DEF_BENCH( return NewSkHeap(kBack); )
184 DEF_BENCH( return NewQSort(kBack); )
185 DEF_BENCH( return NewStdSort(kBack); )
186
187 DEF_BENCH( return NewSkQSort(kSame); )
188 DEF_BENCH( return NewSkHeap(kSame); )
189 DEF_BENCH( return NewQSort(kSame); )
190 DEF_BENCH( return NewStdSort(kSame); )
191