blob: a7e8c2cd0bca4143a7db214319f309329625cd1b [file] [log] [blame]
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +00001/*
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
tfarinaf168b862014-06-19 12:32:29 -07008#include "Benchmark.h"
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +00009#include "SkRandom.h"
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000010#include "SkString.h"
tfarinaf168b862014-06-19 12:32:29 -070011#include "SkTSort.h"
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000012
reed@google.comeebdd962013-01-23 14:52:12 +000013static const int N = 1000;
14
mtklein@google.comb3526272013-09-17 19:37:34 +000015static void rand_proc(int array[N]) {
commit-bot@chromium.orge0e7cfe2013-09-09 20:09:12 +000016 SkRandom rand;
mtklein@google.comb3526272013-09-17 19:37:34 +000017 for (int i = 0; i < N; ++i) {
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000018 array[i] = rand.nextS();
19 }
20}
21
mtklein@google.comb3526272013-09-17 19:37:34 +000022static void randN_proc(int array[N]) {
commit-bot@chromium.orge0e7cfe2013-09-09 20:09:12 +000023 SkRandom rand;
reed@google.comeebdd962013-01-23 14:52:12 +000024 int mod = N / 10;
mtklein@google.comb3526272013-09-17 19:37:34 +000025 for (int i = 0; i < N; ++i) {
reed@google.comeebdd962013-01-23 14:52:12 +000026 array[i] = rand.nextU() % mod;
27 }
28}
29
mtklein@google.comb3526272013-09-17 19:37:34 +000030static void forward_proc(int array[N]) {
31 for (int i = 0; i < N; ++i) {
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000032 array[i] = i;
33 }
34}
35
mtklein@google.comb3526272013-09-17 19:37:34 +000036static void backward_proc(int array[N]) {
37 for (int i = 0; i < N; ++i) {
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000038 array[i] = -i;
39 }
40}
41
mtklein@google.comb3526272013-09-17 19:37:34 +000042static void same_proc(int array[N]) {
43 for (int i = 0; i < N; ++i) {
44 array[i] = N;
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000045 }
46}
47
mtklein@google.comb3526272013-09-17 19:37:34 +000048typedef void (*SortProc)(int array[N]);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000049
50enum Type {
reed@google.comeebdd962013-01-23 14:52:12 +000051 kRand, kRandN, kFore, kBack, kSame
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000052};
53
54static const struct {
55 const char* fName;
56 SortProc fProc;
57} gRec[] = {
reed@google.comeebdd962013-01-23 14:52:12 +000058 { "rand", rand_proc },
59 { "rand10", randN_proc },
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000060 { "forward", forward_proc },
61 { "backward", backward_proc },
62 { "repeated", same_proc },
63};
64
mtklein@google.comb3526272013-09-17 19:37:34 +000065static void skqsort_sort(int array[N]) {
66 // End is inclusive for SkTQSort!
67 SkTQSort<int>(array, array + N - 1);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000068}
69
mtklein@google.comb3526272013-09-17 19:37:34 +000070static void skheap_sort(int array[N]) {
71 SkTHeapSort<int>(array, N);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000072}
73
74extern "C" {
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
mtklein@google.comb3526272013-09-17 19:37:34 +000082static void qsort_sort(int array[N]) {
83 qsort(array, N, sizeof(int), int_compare);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +000084}
85
86enum SortType {
87 kSKQSort, kSKHeap, kQSort
88};
89
90static 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
tfarinaf168b862014-06-19 12:32:29 -070099class SortBench : public Benchmark {
mtklein@google.comb3526272013-09-17 19:37:34 +0000100 SkString fName;
101 const Type fType;
102 const SortProc fSortProc;
103 SkAutoTMalloc<int> fUnsorted;
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000104
105public:
mtklein@google.comb3526272013-09-17 19:37:34 +0000106 SortBench(Type t, SortType s) : fType(t), fSortProc(gSorts[s].fProc) {
mtklein@google.comb3526272013-09-17 19:37:34 +0000107 fName.printf("sort_%s_%s", gSorts[s].fName, gRec[t].fName);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000108 }
109
commit-bot@chromium.org644629c2013-11-21 06:21:58 +0000110 virtual bool isSuitableFor(Backend backend) SK_OVERRIDE {
111 return backend == kNonRendering_Backend;
112 }
113
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000114protected:
115 virtual const char* onGetName() SK_OVERRIDE {
116 return fName.c_str();
117 }
118
mtklein@google.comb3526272013-09-17 19:37:34 +0000119 // Delayed initialization only done if onDraw will be called.
120 virtual void onPreDraw() SK_OVERRIDE {
121 fUnsorted.reset(N);
122 gRec[fType].fProc(fUnsorted.get());
123 }
124
commit-bot@chromium.org33614712013-12-03 18:17:16 +0000125 virtual void onDraw(const int loops, SkCanvas*) SK_OVERRIDE {
mtklein@google.comb3526272013-09-17 19:37:34 +0000126 SkAutoTMalloc<int> sorted(N);
commit-bot@chromium.org33614712013-12-03 18:17:16 +0000127 for (int i = 0; i < loops; i++) {
mtklein@google.comb3526272013-09-17 19:37:34 +0000128 memcpy(sorted.get(), fUnsorted.get(), N*sizeof(int));
129 fSortProc(sorted.get());
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000130#ifdef SK_DEBUG
mtklein@google.comb3526272013-09-17 19:37:34 +0000131 for (int j = 1; j < N; ++j) {
132 SkASSERT(sorted[j - 1] <= sorted[j]);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000133 }
134#endif
135 }
136 }
137
138private:
tfarinaf168b862014-06-19 12:32:29 -0700139 typedef Benchmark INHERITED;
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000140};
141
142///////////////////////////////////////////////////////////////////////////////
143
tfarinaf168b862014-06-19 12:32:29 -0700144static Benchmark* NewSkQSort(Type t) {
mtklein@google.comb3526272013-09-17 19:37:34 +0000145 return new SortBench(t, kSKQSort);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000146}
tfarinaf168b862014-06-19 12:32:29 -0700147static Benchmark* NewSkHeap(Type t) {
mtklein@google.comb3526272013-09-17 19:37:34 +0000148 return new SortBench(t, kSKHeap);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000149}
tfarinaf168b862014-06-19 12:32:29 -0700150static Benchmark* NewQSort(Type t) {
mtklein@google.comb3526272013-09-17 19:37:34 +0000151 return new SortBench(t, kQSort);
mike@reedtribe.orga3f1c8e2013-01-23 02:23:40 +0000152}
153
mtklein@google.com410e6e82013-09-13 19:52:27 +0000154DEF_BENCH( return NewSkQSort(kRand); )
155DEF_BENCH( return NewSkHeap(kRand); )
156DEF_BENCH( return NewQSort(kRand); )
reed@google.comeebdd962013-01-23 14:52:12 +0000157
mtklein@google.com410e6e82013-09-13 19:52:27 +0000158DEF_BENCH( return NewSkQSort(kRandN); )
159DEF_BENCH( return NewSkHeap(kRandN); )
160DEF_BENCH( return NewQSort(kRandN); )
reed@google.comeebdd962013-01-23 14:52:12 +0000161
mtklein@google.com410e6e82013-09-13 19:52:27 +0000162DEF_BENCH( return NewSkQSort(kFore); )
163DEF_BENCH( return NewSkHeap(kFore); )
164DEF_BENCH( return NewQSort(kFore); )
reed@google.comeebdd962013-01-23 14:52:12 +0000165
mtklein@google.com410e6e82013-09-13 19:52:27 +0000166DEF_BENCH( return NewSkQSort(kBack); )
167DEF_BENCH( return NewSkHeap(kBack); )
168DEF_BENCH( return NewQSort(kBack); )
reed@google.comeebdd962013-01-23 14:52:12 +0000169
mtklein@google.com410e6e82013-09-13 19:52:27 +0000170DEF_BENCH( return NewSkQSort(kSame); )
171DEF_BENCH( return NewSkHeap(kSame); )
172DEF_BENCH( return NewQSort(kSame); )