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 #ifdef SK_DEBUG
14 // Windows-debug builds (at least) don't implement tail-recursion, and we have
15 // a bench that triggers a worst-case behavior in SkTQSort (w/ repeated keys)
16 // which can overflow the stack if N is too big. So we reduce it for debug
17 // builds (for which we don't care about sorting performance anyways).
18 static const int N = 100;
19 #else
20 static const int N = 1000;
21 #endif
22
rand_proc(int array[],int count)23 static void rand_proc(int array[], int count) {
24 SkRandom rand;
25 for (int i = 0; i < count; ++i) {
26 array[i] = rand.nextS();
27 }
28 }
29
randN_proc(int array[],int count)30 static void randN_proc(int array[], int count) {
31 SkRandom rand;
32 int mod = N / 10;
33 for (int i = 0; i < count; ++i) {
34 array[i] = rand.nextU() % mod;
35 }
36 }
37
forward_proc(int array[],int count)38 static void forward_proc(int array[], int count) {
39 for (int i = 0; i < count; ++i) {
40 array[i] = i;
41 }
42 }
43
backward_proc(int array[],int count)44 static void backward_proc(int array[], int count) {
45 for (int i = 0; i < count; ++i) {
46 array[i] = -i;
47 }
48 }
49
same_proc(int array[],int count)50 static void same_proc(int array[], int count) {
51 for (int i = 0; i < count; ++i) {
52 array[i] = count;
53 }
54 }
55
56 typedef void (*SortProc)(int array[], int count);
57
58 enum Type {
59 kRand, kRandN, kFore, kBack, kSame
60 };
61
62 static const struct {
63 const char* fName;
64 SortProc fProc;
65 } gRec[] = {
66 { "rand", rand_proc },
67 { "rand10", randN_proc },
68 { "forward", forward_proc },
69 { "backward", backward_proc },
70 { "repeated", same_proc },
71 };
72
skqsort_sort(int array[],int count)73 static void skqsort_sort(int array[], int count) {
74 SkTQSort<int>(array, array + count);
75 }
76
skheap_sort(int array[],int count)77 static void skheap_sort(int array[], int count) {
78 SkTHeapSort<int>(array, count);
79 }
80
81 extern "C" {
int_compare(const void * a,const void * b)82 static int int_compare(const void* a, const void* b) {
83 const int ai = *(const int*)a;
84 const int bi = *(const int*)b;
85 return ai < bi ? -1 : (ai > bi);
86 }
87 }
88
qsort_sort(int array[],int count)89 static void qsort_sort(int array[], int count) {
90 qsort(array, count, sizeof(int), int_compare);
91 }
92
93 enum SortType {
94 kSKQSort, kSKHeap, kQSort
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 };
105
106 class SortBench : public SkBenchmark {
107 SkString fName;
108 enum { MAX = 100000 };
109 int fUnsorted[MAX];
110 int fSorted[MAX];
111 int fCount;
112 SortProc fSortProc;
113
114 public:
SortBench(void * param,Type t,int n,SortType s)115 SortBench(void* param, Type t, int n, SortType s) : INHERITED(param) {
116 if (n > MAX) {
117 n = MAX;
118 }
119 fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName);
120 fCount = n;
121 gRec[t].fProc(fUnsorted, n);
122 fSortProc = gSorts[s].fProc;
123 fIsRendering = false;
124 }
125
126 protected:
onGetName()127 virtual const char* onGetName() SK_OVERRIDE {
128 return fName.c_str();
129 }
130
onDraw(SkCanvas * canvas)131 virtual void onDraw(SkCanvas* canvas) {
132 int n = SkBENCHLOOP(200);
133 for (int i = 0; i < n; i++) {
134 memcpy(fSorted, fUnsorted, fCount * sizeof(int));
135 fSortProc(fSorted, fCount);
136 #ifdef SK_DEBUG
137 for (int j = 1; j < fCount; ++j) {
138 SkASSERT(fSorted[j - 1] <= fSorted[j]);
139 }
140 #endif
141 }
142 }
143
144 private:
145 typedef SkBenchmark INHERITED;
146 };
147
148 ///////////////////////////////////////////////////////////////////////////////
149
NewSkQSort(void * param,Type t)150 static SkBenchmark* NewSkQSort(void* param, Type t) {
151 return new SortBench(param, t, N, kSKQSort);
152 }
NewSkHeap(void * param,Type t)153 static SkBenchmark* NewSkHeap(void* param, Type t) {
154 return new SortBench(param, t, N, kSKHeap);
155 }
NewQSort(void * param,Type t)156 static SkBenchmark* NewQSort(void* param, Type t) {
157 return new SortBench(param, t, N, kQSort);
158 }
159
160 DEF_BENCH( return NewSkQSort(p, kRand); )
161 DEF_BENCH( return NewSkHeap(p, kRand); )
162 DEF_BENCH( return NewQSort(p, kRand); )
163
164 DEF_BENCH( return NewSkQSort(p, kRandN); )
165 DEF_BENCH( return NewSkHeap(p, kRandN); )
166 DEF_BENCH( return NewQSort(p, kRandN); )
167
168 DEF_BENCH( return NewSkQSort(p, kFore); )
169 DEF_BENCH( return NewSkHeap(p, kFore); )
170 DEF_BENCH( return NewQSort(p, kFore); )
171
172 DEF_BENCH( return NewSkQSort(p, kBack); )
173 DEF_BENCH( return NewSkHeap(p, kBack); )
174 DEF_BENCH( return NewQSort(p, kBack); )
175
176 DEF_BENCH( return NewSkQSort(p, kSame); )
177 DEF_BENCH( return NewSkHeap(p, kSame); )
178 DEF_BENCH( return NewQSort(p, kSame); )
179