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