OLD | NEW |
| (Empty) |
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-li
ke 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 tha
t 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 dynami
cally 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 { | |
33 virtual bool isSuitableFor(Backend b) SK_OVERRIDE { return b == kNonRenderin
g_Backend; } | |
34 virtual const char* onGetName() SK_OVERRIDE { return Impl::kName; } | |
35 virtual void onDraw(const int loops, SkCanvas*) SK_OVERRIDE { Impl::bench(lo
ops); } | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
107 BENCH(ChunkAlloc_Push) { | |
108 SkChunkAlloc s(4096); | |
109 for (int i = 0; i < K*loops; i++) s.allocThrow(sizeof(int)); | |
110 } | |
111 | |
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 | |
117 BENCH(TArray_Push) { | |
118 SkTArray<int, true> s; | |
119 for (int i = 0; i < K*loops; i++) s.push_back(i); | |
120 } | |
121 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 } | |
OLD | NEW |