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
31template <typename Impl>
32struct StackBench : public Benchmark {
33    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}
180