blob: 3b41cb65cebcb427d5aa1ecd0baa7da4b87e3c96 [file] [log] [blame]
commit-bot@chromium.org85facf72014-01-07 17:03:31 +00001/*
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
tfarinaf168b862014-06-19 12:32:29 -07008#include "Benchmark.h"
commit-bot@chromium.org85facf72014-01-07 17:03:31 +00009#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
31template <typename Impl>
tfarinaf168b862014-06-19 12:32:29 -070032struct StackBench : public Benchmark {
commit-bot@chromium.org85facf72014-01-07 17:03:31 +000033 virtual bool isSuitableFor(Backend b) SK_OVERRIDE { return b == kNonRendering_Backend; }
34 virtual const char* onGetName() SK_OVERRIDE { return Impl::kName; }
35 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
44static const int K = 2049;
45
46// Add K items, then iterate through them serially many times.
47
48BENCH(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
61BENCH(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
71BENCH(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
83BENCH(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
94BENCH(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
107BENCH(ChunkAlloc_Push) {
108 SkChunkAlloc s(4096);
109 for (int i = 0; i < K*loops; i++) s.allocThrow(sizeof(int));
110}
111
112BENCH(Deque_Push) {
113 SkDeque s(sizeof(int), 1024);
114 for (int i = 0; i < K*loops; i++) *(int*)s.push_back() = i;
115}
116
117BENCH(TArray_Push) {
118 SkTArray<int, true> s;
119 for (int i = 0; i < K*loops; i++) s.push_back(i);
120}
121
122BENCH(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
129BENCH(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
137BENCH(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
145BENCH(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
153BENCH(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
163BENCH(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
169BENCH(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
175BENCH(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}