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