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 31 template <typename Impl> 32 struct 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 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 } 180
