summaryrefslogtreecommitdiff
path: root/absl/container
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container')
-rw-r--r--absl/container/BUILD.bazel24
-rw-r--r--absl/container/fixed_array_benchmark.cc68
-rw-r--r--absl/container/inlined_vector_benchmark.cc376
3 files changed, 468 insertions, 0 deletions
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 8bdf6312..69cd5195 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -62,6 +62,17 @@ cc_test(
],
)
+cc_binary(
+ name = "fixed_array_benchmark",
+ testonly = 1,
+ srcs = ["fixed_array_benchmark.cc"],
+ copts = ABSL_TEST_COPTS + ["$(STACK_FRAME_UNLIMITED)"],
+ deps = [
+ ":fixed_array",
+ "@com_github_google_benchmark//:benchmark",
+ ],
+)
+
cc_library(
name = "inlined_vector",
hdrs = ["inlined_vector.h"],
@@ -106,6 +117,19 @@ cc_test(
],
)
+cc_binary(
+ name = "inlined_vector_benchmark",
+ testonly = 1,
+ srcs = ["inlined_vector_benchmark.cc"],
+ copts = ABSL_TEST_COPTS,
+ deps = [
+ ":inlined_vector",
+ "//absl/base",
+ "//absl/strings",
+ "@com_github_google_benchmark//:benchmark",
+ ],
+)
+
cc_library(
name = "test_instance_tracker",
testonly = 1,
diff --git a/absl/container/fixed_array_benchmark.cc b/absl/container/fixed_array_benchmark.cc
new file mode 100644
index 00000000..2d39898d
--- /dev/null
+++ b/absl/container/fixed_array_benchmark.cc
@@ -0,0 +1,68 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/container/fixed_array.h"
+
+#include <stddef.h>
+#include <string>
+
+#include "benchmark/benchmark.h"
+
+namespace {
+
+// For benchmarking -- simple class with constructor and destructor that
+// set an int to a constant..
+class SimpleClass {
+ public:
+ SimpleClass() : i(3) { }
+ ~SimpleClass() { i = 0; }
+ private:
+ int i;
+};
+
+template <typename C, size_t stack_size>
+void BM_FixedArray(benchmark::State& state) {
+ const int size = state.range(0);
+ for (auto _ : state) {
+ absl::FixedArray<C, stack_size> fa(size);
+ benchmark::DoNotOptimize(fa.data());
+ }
+}
+BENCHMARK_TEMPLATE(BM_FixedArray, char, absl::kFixedArrayUseDefault)
+ ->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, char, 0)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, char, 1)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, char, 16)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, char, 256)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, char, 65536)->Range(0, 1 << 16);
+
+BENCHMARK_TEMPLATE(BM_FixedArray, SimpleClass, absl::kFixedArrayUseDefault)
+ ->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, SimpleClass, 0)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, SimpleClass, 1)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, SimpleClass, 16)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, SimpleClass, 256)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, SimpleClass, 65536)->Range(0, 1 << 16);
+
+BENCHMARK_TEMPLATE(BM_FixedArray, std::string, absl::kFixedArrayUseDefault)
+ ->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, std::string, 0)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, std::string, 1)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, std::string, 16)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, std::string, 256)->Range(0, 1 << 16);
+BENCHMARK_TEMPLATE(BM_FixedArray, std::string, 65536)->Range(0, 1 << 16);
+
+} // namespace
+
+BENCHMARK_MAIN();
diff --git a/absl/container/inlined_vector_benchmark.cc b/absl/container/inlined_vector_benchmark.cc
new file mode 100644
index 00000000..a2035e35
--- /dev/null
+++ b/absl/container/inlined_vector_benchmark.cc
@@ -0,0 +1,376 @@
+// Copyright 2017 The Abseil Authors.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+#include "absl/container/inlined_vector.h"
+
+#include <string>
+#include <vector>
+
+#include "absl/base/internal/raw_logging.h"
+#include "absl/strings/str_cat.h"
+#include "benchmark/benchmark.h"
+
+namespace {
+
+using IntVec = absl::InlinedVector<int, 8>;
+
+void BM_InlinedVectorFill(benchmark::State& state) {
+ const int len = state.range(0);
+ for (auto _ : state) {
+ IntVec v;
+ for (int i = 0; i < len; i++) {
+ v.push_back(i);
+ }
+ }
+ state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
+}
+BENCHMARK(BM_InlinedVectorFill)->Range(0, 1024);
+
+void BM_InlinedVectorFillRange(benchmark::State& state) {
+ const int len = state.range(0);
+ std::unique_ptr<int[]> ia(new int[len]);
+ for (int i = 0; i < len; i++) {
+ ia[i] = i;
+ }
+ for (auto _ : state) {
+ IntVec v(ia.get(), ia.get() + len);
+ benchmark::DoNotOptimize(v);
+ }
+ state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
+}
+BENCHMARK(BM_InlinedVectorFillRange)->Range(0, 1024);
+
+void BM_StdVectorFill(benchmark::State& state) {
+ const int len = state.range(0);
+ for (auto _ : state) {
+ std::vector<int> v;
+ for (int i = 0; i < len; i++) {
+ v.push_back(i);
+ }
+ }
+ state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
+}
+BENCHMARK(BM_StdVectorFill)->Range(0, 1024);
+
+bool StringRepresentedInline(std::string s) {
+ const char* chars = s.data();
+ std::string s1 = std::move(s);
+ return s1.data() != chars;
+}
+
+void BM_InlinedVectorFillString(benchmark::State& state) {
+ const int len = state.range(0);
+ std::string strings[4] = {"a quite long string",
+ "another long string",
+ "012345678901234567",
+ "to cause allocation"};
+ for (auto _ : state) {
+ absl::InlinedVector<std::string, 8> v;
+ for (int i = 0; i < len; i++) {
+ v.push_back(strings[i & 3]);
+ }
+ }
+ state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
+}
+BENCHMARK(BM_InlinedVectorFillString)->Range(0, 1024);
+
+void BM_StdVectorFillString(benchmark::State& state) {
+ const int len = state.range(0);
+ std::string strings[4] = {"a quite long string",
+ "another long string",
+ "012345678901234567",
+ "to cause allocation"};
+ for (auto _ : state) {
+ std::vector<std::string> v;
+ for (int i = 0; i < len; i++) {
+ v.push_back(strings[i & 3]);
+ }
+ }
+ state.SetItemsProcessed(static_cast<int64_t>(state.iterations()) * len);
+ // The purpose of the benchmark is to verify that inlined vector is
+ // efficient when moving is more efficent than copying. To do so, we
+ // use strings that are larger than the small std::string optimization.
+ ABSL_RAW_CHECK(!StringRepresentedInline(strings[0]),
+ "benchmarked with strings that are too small");
+}
+BENCHMARK(BM_StdVectorFillString)->Range(0, 1024);
+
+struct Buffer { // some arbitrary structure for benchmarking.
+ char* base;
+ int length;
+ int capacity;
+ void* user_data;
+};
+
+void BM_InlinedVectorTenAssignments(benchmark::State& state) {
+ const int len = state.range(0);
+ using BufferVec = absl::InlinedVector<Buffer, 2>;
+
+ BufferVec src;
+ src.resize(len);
+
+ BufferVec dst;
+ for (auto _ : state) {
+ for (int i = 0; i < 10; ++i) {
+ dst = src;
+ }
+ }
+}
+BENCHMARK(BM_InlinedVectorTenAssignments)
+ ->Arg(0)->Arg(1)->Arg(2)->Arg(3)->Arg(4)->Arg(20);
+
+void BM_CreateFromContainer(benchmark::State& state) {
+ for (auto _ : state) {
+ absl::InlinedVector<int, 4> x(absl::InlinedVector<int, 4>{1, 2, 3});
+ benchmark::DoNotOptimize(x);
+ }
+}
+BENCHMARK(BM_CreateFromContainer);
+
+struct LargeCopyableOnly {
+ LargeCopyableOnly() : d(1024, 17) {}
+ LargeCopyableOnly(const LargeCopyableOnly& o) = default;
+ LargeCopyableOnly& operator=(const LargeCopyableOnly& o) = default;
+
+ std::vector<int> d;
+};
+
+struct LargeCopyableSwappable {
+ LargeCopyableSwappable() : d(1024, 17) {}
+ LargeCopyableSwappable(const LargeCopyableSwappable& o) = default;
+ LargeCopyableSwappable(LargeCopyableSwappable&& o) = delete;
+
+ LargeCopyableSwappable& operator=(LargeCopyableSwappable o) {
+ using std::swap;
+ swap(*this, o);
+ return *this;
+ }
+ LargeCopyableSwappable& operator=(LargeCopyableSwappable&& o) = delete;
+
+ friend void swap(LargeCopyableSwappable& a, LargeCopyableSwappable& b) {
+ using std::swap;
+ swap(a.d, b.d);
+ }
+
+ std::vector<int> d;
+};
+
+struct LargeCopyableMovable {
+ LargeCopyableMovable() : d(1024, 17) {}
+ // Use implicitly defined copy and move.
+
+ std::vector<int> d;
+};
+
+struct LargeCopyableMovableSwappable {
+ LargeCopyableMovableSwappable() : d(1024, 17) {}
+ LargeCopyableMovableSwappable(const LargeCopyableMovableSwappable& o) =
+ default;
+ LargeCopyableMovableSwappable(LargeCopyableMovableSwappable&& o) = default;
+
+ LargeCopyableMovableSwappable& operator=(LargeCopyableMovableSwappable o) {
+ using std::swap;
+ swap(*this, o);
+ return *this;
+ }
+ LargeCopyableMovableSwappable& operator=(LargeCopyableMovableSwappable&& o) =
+ default;
+
+ friend void swap(LargeCopyableMovableSwappable& a,
+ LargeCopyableMovableSwappable& b) {
+ using std::swap;
+ swap(a.d, b.d);
+ }
+
+ std::vector<int> d;
+};
+
+template <typename ElementType>
+void BM_SwapElements(benchmark::State& state) {
+ const int len = state.range(0);
+ using Vec = absl::InlinedVector<ElementType, 32>;
+ Vec a(len);
+ Vec b;
+ for (auto _ : state) {
+ using std::swap;
+ swap(a, b);
+ }
+}
+BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableOnly)->Range(0, 1024);
+BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableSwappable)->Range(0, 1024);
+BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableMovable)->Range(0, 1024);
+BENCHMARK_TEMPLATE(BM_SwapElements, LargeCopyableMovableSwappable)
+ ->Range(0, 1024);
+
+// The following benchmark is meant to track the efficiency of the vector size
+// as a function of stored type via the benchmark label. It is not meant to
+// output useful sizeof operator performance. The loop is a dummy operation
+// to fulfill the requirement of running the benchmark.
+template <typename VecType>
+void BM_Sizeof(benchmark::State& state) {
+ int size = 0;
+ for (auto _ : state) {
+ VecType vec;
+ size = sizeof(vec);
+ }
+ state.SetLabel(absl::StrCat("sz=", size));
+}
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 1>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 4>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 7>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<char, 8>);
+
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 1>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 4>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 7>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<int, 8>);
+
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 1>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 4>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 7>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<void*, 8>);
+
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 1>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 4>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 7>);
+BENCHMARK_TEMPLATE(BM_Sizeof, absl::InlinedVector<std::string, 8>);
+
+void BM_InlinedVectorIndexInlined(benchmark::State& state) {
+ absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
+ for (auto _ : state) {
+ for (int i = 0; i < 1000; ++i) {
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v[4]);
+ }
+ }
+ state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_InlinedVectorIndexInlined);
+
+void BM_InlinedVectorIndexExternal(benchmark::State& state) {
+ absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (auto _ : state) {
+ for (int i = 0; i < 1000; ++i) {
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v[4]);
+ }
+ }
+ state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_InlinedVectorIndexExternal);
+
+void BM_StdVectorIndex(benchmark::State& state) {
+ std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (auto _ : state) {
+ for (int i = 0; i < 1000; ++i) {
+ benchmark::DoNotOptimize(v);
+ benchmark::DoNotOptimize(v[4]);
+ }
+ }
+ state.SetItemsProcessed(1000 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_StdVectorIndex);
+
+#define UNROLL_2(x) \
+ benchmark::DoNotOptimize(x); \
+ benchmark::DoNotOptimize(x);
+
+#define UNROLL_4(x) UNROLL_2(x) UNROLL_2(x)
+#define UNROLL_8(x) UNROLL_4(x) UNROLL_4(x)
+#define UNROLL_16(x) UNROLL_8(x) UNROLL_8(x);
+
+void BM_InlinedVectorDataInlined(benchmark::State& state) {
+ absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
+ for (auto _ : state) {
+ UNROLL_16(v.data());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_InlinedVectorDataInlined);
+
+void BM_InlinedVectorDataExternal(benchmark::State& state) {
+ absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (auto _ : state) {
+ UNROLL_16(v.data());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_InlinedVectorDataExternal);
+
+void BM_StdVectorData(benchmark::State& state) {
+ std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (auto _ : state) {
+ UNROLL_16(v.data());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_StdVectorData);
+
+void BM_InlinedVectorSizeInlined(benchmark::State& state) {
+ absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
+ for (auto _ : state) {
+ UNROLL_16(v.size());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_InlinedVectorSizeInlined);
+
+void BM_InlinedVectorSizeExternal(benchmark::State& state) {
+ absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (auto _ : state) {
+ UNROLL_16(v.size());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_InlinedVectorSizeExternal);
+
+void BM_StdVectorSize(benchmark::State& state) {
+ std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (auto _ : state) {
+ UNROLL_16(v.size());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_StdVectorSize);
+
+void BM_InlinedVectorEmptyInlined(benchmark::State& state) {
+ absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7};
+ for (auto _ : state) {
+ UNROLL_16(v.empty());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_InlinedVectorEmptyInlined);
+
+void BM_InlinedVectorEmptyExternal(benchmark::State& state) {
+ absl::InlinedVector<int, 8> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (auto _ : state) {
+ UNROLL_16(v.empty());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_InlinedVectorEmptyExternal);
+
+void BM_StdVectorEmpty(benchmark::State& state) {
+ std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
+ for (auto _ : state) {
+ UNROLL_16(v.empty());
+ }
+ state.SetItemsProcessed(16 * static_cast<int64_t>(state.iterations()));
+}
+BENCHMARK(BM_StdVectorEmpty);
+
+} // namespace
+
+BENCHMARK_MAIN();
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-30 14:44:24 +0000