Index: bench/StackBench.cpp |
diff --git a/bench/StackBench.cpp b/bench/StackBench.cpp |
new file mode 100644 |
index 0000000000000000000000000000000000000000..61af99fb1a22c964bd84c1e609bfbeb80e2f4b3d |
--- /dev/null |
+++ b/bench/StackBench.cpp |
@@ -0,0 +1,179 @@ |
+/* |
+ * Copyright 2014 Google Inc. |
+ * |
+ * Use of this source code is governed by a BSD-style license that can be |
+ * found in the LICENSE file. |
+ */ |
+ |
+#include "SkBenchmark.h" |
+#include "SkRandom.h" |
+ |
+#include "SkChunkAlloc.h" |
+#include "SkDeque.h" |
+#include "SkTArray.h" |
+#include "SkTDArray.h" |
+ |
+// This file has several benchmarks using various data structures to do stack-like things: |
+// - push |
+// - push, immediately pop |
+// - push many, pop all of them |
+// - serial access |
+// - random access |
+// When a data structure doesn't suppport an operation efficiently, we leave that combination out. |
+// Where possible we hint to the data structure to allocate in 4K pages. |
+// |
+// These benchmarks may help you decide which data structure to use for a dynamically allocated |
+// ordered list of allocations that grows on one end. |
+// |
+// Current overall winner (01/2014): SkTDArray. |
+// It wins every benchmark on every machine I tried (Desktop, Nexus S, Laptop). |
+ |
+template <typename Impl> |
+struct StackBench : public SkBenchmark { |
+ virtual bool isSuitableFor(Backend b) SK_OVERRIDE { return b == kNonRendering_Backend; } |
+ virtual const char* onGetName() SK_OVERRIDE { return Impl::kName; } |
+ virtual void onDraw(const int loops, SkCanvas*) SK_OVERRIDE { Impl::bench(loops); } |
+}; |
+ |
+#define BENCH(name) \ |
+ struct name { static const char* const kName; static void bench(int); }; \ |
+ const char* const name::kName = #name; \ |
+ DEF_BENCH(return new StackBench<name>();) \ |
+ void name::bench(int loops) |
+ |
+static const int K = 2049; |
+ |
+// Add K items, then iterate through them serially many times. |
+ |
+BENCH(Deque_Serial) { |
+ SkDeque s(sizeof(int), 1024); |
+ for (int i = 0; i < K; i++) *(int*)s.push_back() = i; |
+ |
+ volatile int junk = 0; |
+ for (int j = 0; j < loops; j++) { |
+ SkDeque::Iter it(s, SkDeque::Iter::kFront_IterStart); |
+ while(void* p = it.next()) { |
+ junk += *(int*)p; |
+ } |
+ } |
+} |
+ |
+BENCH(TArray_Serial) { |
+ SkTArray<int, true> s; |
+ for (int i = 0; i < K; i++) s.push_back(i); |
+ |
+ volatile int junk = 0; |
+ for (int j = 0; j < loops; j++) { |
+ for (int i = 0; i < s.count(); i++) junk += s[i]; |
+ } |
+} |
+ |
+BENCH(TDArray_Serial) { |
+ SkTDArray<int> s; |
+ for (int i = 0; i < K; i++) s.push(i); |
+ |
+ volatile int junk = 0; |
+ for (int j = 0; j < loops; j++) { |
+ for (int i = 0; i < s.count(); i++) junk += s[i]; |
+ } |
+} |
+ |
+// Add K items, then randomly access them many times. |
+ |
+BENCH(TArray_RandomAccess) { |
+ SkTArray<int, true> s; |
+ for (int i = 0; i < K; i++) s.push_back(i); |
+ |
+ SkRandom rand; |
+ volatile int junk = 0; |
+ for (int i = 0; i < K*loops; i++) { |
+ junk += s[rand.nextULessThan(K)]; |
+ } |
+} |
+ |
+BENCH(TDArray_RandomAccess) { |
+ SkTDArray<int> s; |
+ for (int i = 0; i < K; i++) s.push(i); |
+ |
+ SkRandom rand; |
+ volatile int junk = 0; |
+ for (int i = 0; i < K*loops; i++) { |
+ junk += s[rand.nextULessThan(K)]; |
+ } |
+} |
+ |
+// Push many times. |
+ |
+BENCH(ChunkAlloc_Push) { |
+ SkChunkAlloc s(4096); |
+ for (int i = 0; i < K*loops; i++) s.allocThrow(sizeof(int)); |
+} |
+ |
+BENCH(Deque_Push) { |
+ SkDeque s(sizeof(int), 1024); |
+ for (int i = 0; i < K*loops; i++) *(int*)s.push_back() = i; |
+} |
+ |
+BENCH(TArray_Push) { |
+ SkTArray<int, true> s; |
+ for (int i = 0; i < K*loops; i++) s.push_back(i); |
+} |
+ |
+BENCH(TDArray_Push) { |
+ SkTDArray<int> s; |
+ for (int i = 0; i < K*loops; i++) s.push(i); |
+} |
+ |
+// Push then immediately pop many times. |
+ |
+BENCH(ChunkAlloc_PushPop) { |
+ SkChunkAlloc s(4096); |
+ for (int i = 0; i < K*loops; i++) { |
+ void* p = s.allocThrow(sizeof(int)); |
+ s.unalloc(p); |
+ } |
+} |
+ |
+BENCH(Deque_PushPop) { |
+ SkDeque s(sizeof(int), 1024); |
+ for (int i = 0; i < K*loops; i++) { |
+ *(int*)s.push_back() = i; |
+ s.pop_back(); |
+ } |
+} |
+ |
+BENCH(TArray_PushPop) { |
+ SkTArray<int, true> s; |
+ for (int i = 0; i < K*loops; i++) { |
+ s.push_back(i); |
+ s.pop_back(); |
+ } |
+} |
+ |
+BENCH(TDArray_PushPop) { |
+ SkTDArray<int> s; |
+ for (int i = 0; i < K*loops; i++) { |
+ s.push(i); |
+ s.pop(); |
+ } |
+} |
+ |
+// Push many items, then pop them all. |
+ |
+BENCH(Deque_PushAllPopAll) { |
+ SkDeque s(sizeof(int), 1024); |
+ for (int i = 0; i < K*loops; i++) *(int*)s.push_back() = i; |
+ for (int i = 0; i < K*loops; i++) s.pop_back(); |
+} |
+ |
+BENCH(TArray_PushAllPopAll) { |
+ SkTArray<int, true> s; |
+ for (int i = 0; i < K*loops; i++) s.push_back(i); |
+ for (int i = 0; i < K*loops; i++) s.pop_back(); |
+} |
+ |
+BENCH(TDArray_PushAllPopAll) { |
+ SkTDArray<int> s; |
+ for (int i = 0; i < K*loops; i++) s.push(i); |
+ for (int i = 0; i < K*loops; i++) s.pop(); |
+} |