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