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