about summary refs log tree commit diff
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 8bdf63122aba..69cd5195dc7d 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 000000000000..2d39898d8a5f
--- /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 000000000000..a2035e35ca83
--- /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-pink 1.4.1 (git 2.44.2) at 2024-11-28T02ยท28+0000