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