1 /*
2 * Copyright 2014 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
11 #include "SkChunkAlloc.h"
12 #include "SkDeque.h"
13 #include "SkTArray.h"
14 #include "SkTDArray.h"
15
16 // This file has several benchmarks using various data structures to do stack-like things:
17 // - push
18 // - push, immediately pop
19 // - push many, pop all of them
20 // - serial access
21 // - random access
22 // When a data structure doesn't suppport an operation efficiently, we leave that combination out.
23 // Where possible we hint to the data structure to allocate in 4K pages.
24 //
25 // These benchmarks may help you decide which data structure to use for a dynamically allocated
26 // ordered list of allocations that grows on one end.
27 //
28 // Current overall winner (01/2014): SkTDArray.
29 // It wins every benchmark on every machine I tried (Desktop, Nexus S, Laptop).
30
31 template <typename Impl>
32 struct StackBench : public Benchmark {
isSuitableForStackBench33 virtual bool isSuitableFor(Backend b) SK_OVERRIDE { return b == kNonRendering_Backend; }
onGetNameStackBench34 virtual const char* onGetName() SK_OVERRIDE { return Impl::kName; }
onDrawStackBench35 virtual void onDraw(const int loops, SkCanvas*) SK_OVERRIDE { Impl::bench(loops); }
36 };
37
38 #define BENCH(name) \
39 struct name { static const char* const kName; static void bench(int); }; \
40 const char* const name::kName = #name; \
41 DEF_BENCH(return new StackBench<name>();) \
42 void name::bench(int loops)
43
44 static const int K = 2049;
45
46 // Add K items, then iterate through them serially many times.
47
BENCH(Deque_Serial)48 BENCH(Deque_Serial) {
49 SkDeque s(sizeof(int), 1024);
50 for (int i = 0; i < K; i++) *(int*)s.push_back() = i;
51
52 volatile int junk = 0;
53 for (int j = 0; j < loops; j++) {
54 SkDeque::Iter it(s, SkDeque::Iter::kFront_IterStart);
55 while(void* p = it.next()) {
56 junk += *(int*)p;
57 }
58 }
59 }
60
BENCH(TArray_Serial)61 BENCH(TArray_Serial) {
62 SkTArray<int, true> s;
63 for (int i = 0; i < K; i++) s.push_back(i);
64
65 volatile int junk = 0;
66 for (int j = 0; j < loops; j++) {
67 for (int i = 0; i < s.count(); i++) junk += s[i];
68 }
69 }
70
BENCH(TDArray_Serial)71 BENCH(TDArray_Serial) {
72 SkTDArray<int> s;
73 for (int i = 0; i < K; i++) s.push(i);
74
75 volatile int junk = 0;
76 for (int j = 0; j < loops; j++) {
77 for (int i = 0; i < s.count(); i++) junk += s[i];
78 }
79 }
80
81 // Add K items, then randomly access them many times.
82
BENCH(TArray_RandomAccess)83 BENCH(TArray_RandomAccess) {
84 SkTArray<int, true> s;
85 for (int i = 0; i < K; i++) s.push_back(i);
86
87 SkRandom rand;
88 volatile int junk = 0;
89 for (int i = 0; i < K*loops; i++) {
90 junk += s[rand.nextULessThan(K)];
91 }
92 }
93
BENCH(TDArray_RandomAccess)94 BENCH(TDArray_RandomAccess) {
95 SkTDArray<int> s;
96 for (int i = 0; i < K; i++) s.push(i);
97
98 SkRandom rand;
99 volatile int junk = 0;
100 for (int i = 0; i < K*loops; i++) {
101 junk += s[rand.nextULessThan(K)];
102 }
103 }
104
105 // Push many times.
106
BENCH(ChunkAlloc_Push)107 BENCH(ChunkAlloc_Push) {
108 SkChunkAlloc s(4096);
109 for (int i = 0; i < K*loops; i++) s.allocThrow(sizeof(int));
110 }
111
BENCH(Deque_Push)112 BENCH(Deque_Push) {
113 SkDeque s(sizeof(int), 1024);
114 for (int i = 0; i < K*loops; i++) *(int*)s.push_back() = i;
115 }
116
BENCH(TArray_Push)117 BENCH(TArray_Push) {
118 SkTArray<int, true> s;
119 for (int i = 0; i < K*loops; i++) s.push_back(i);
120 }
121
BENCH(TDArray_Push)122 BENCH(TDArray_Push) {
123 SkTDArray<int> s;
124 for (int i = 0; i < K*loops; i++) s.push(i);
125 }
126
127 // Push then immediately pop many times.
128
BENCH(ChunkAlloc_PushPop)129 BENCH(ChunkAlloc_PushPop) {
130 SkChunkAlloc s(4096);
131 for (int i = 0; i < K*loops; i++) {
132 void* p = s.allocThrow(sizeof(int));
133 s.unalloc(p);
134 }
135 }
136
BENCH(Deque_PushPop)137 BENCH(Deque_PushPop) {
138 SkDeque s(sizeof(int), 1024);
139 for (int i = 0; i < K*loops; i++) {
140 *(int*)s.push_back() = i;
141 s.pop_back();
142 }
143 }
144
BENCH(TArray_PushPop)145 BENCH(TArray_PushPop) {
146 SkTArray<int, true> s;
147 for (int i = 0; i < K*loops; i++) {
148 s.push_back(i);
149 s.pop_back();
150 }
151 }
152
BENCH(TDArray_PushPop)153 BENCH(TDArray_PushPop) {
154 SkTDArray<int> s;
155 for (int i = 0; i < K*loops; i++) {
156 s.push(i);
157 s.pop();
158 }
159 }
160
161 // Push many items, then pop them all.
162
BENCH(Deque_PushAllPopAll)163 BENCH(Deque_PushAllPopAll) {
164 SkDeque s(sizeof(int), 1024);
165 for (int i = 0; i < K*loops; i++) *(int*)s.push_back() = i;
166 for (int i = 0; i < K*loops; i++) s.pop_back();
167 }
168
BENCH(TArray_PushAllPopAll)169 BENCH(TArray_PushAllPopAll) {
170 SkTArray<int, true> s;
171 for (int i = 0; i < K*loops; i++) s.push_back(i);
172 for (int i = 0; i < K*loops; i++) s.pop_back();
173 }
174
BENCH(TDArray_PushAllPopAll)175 BENCH(TDArray_PushAllPopAll) {
176 SkTDArray<int> s;
177 for (int i = 0; i < K*loops; i++) s.push(i);
178 for (int i = 0; i < K*loops; i++) s.pop();
179 }
180