Add StackBench to measure performance on stack-like (fixed element size) work loads.
BUG=303282
R=reed@google.com, caryclark@google.com, mtklein@chromium.org
Author: mtklein@google.com
Review URL: https://codereview.chromium.org/110893007
git-svn-id: http://skia.googlecode.com/svn/trunk@12940 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/bench/StackBench.cpp b/bench/StackBench.cpp
new file mode 100644
index 0000000..61af99f
--- /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();
+}