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