ceph/src/arrow/cpp/src/arrow/util/small_vector_benchmark.cc

   1 // Licensed to the Apache Software Foundation (ASF) under one
   2 // or more contributor license agreements.  See the NOTICE file
   3 // distributed with this work for additional information
   4 // regarding copyright ownership.  The ASF licenses this file
   5 // to you under the Apache License, Version 2.0 (the
   6 // "License"); you may not use this file except in compliance
   7 // with the License.  You may obtain a copy of the License at
   8 //
   9 //   http://www.apache.org/licenses/LICENSE-2.0
  10 //
  11 // Unless required by applicable law or agreed to in writing,
  12 // software distributed under the License is distributed on an
  13 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  14 // KIND, either express or implied.  See the License for the
  15 // specific language governing permissions and limitations
  16 // under the License.
  17
  18 #include <algorithm>
  19 #include <cstdint>
  20 #include <iterator>
  21 #include <memory>
  22 #include <numeric>
  23 #include <string>
  24 #include <vector>
  25
  26 #include <benchmark/benchmark.h>
  27
  28 #include "arrow/testing/util.h"
  29 #include "arrow/util/logging.h"
  30 #include "arrow/util/macros.h"
  31 #include "arrow/util/small_vector.h"
  32
  33 namespace arrow {
  34 namespace internal {
  35
  36 template <typename T>
  37 T ValueInitializer();
  38 template <typename T>
  39 T ValueInitializer(int seed);
  40
  41 template <>
  42 int ValueInitializer<int>() {
  43   return 42;
  44 }
  45 template <>
  46 int ValueInitializer<int>(int seed) {
  47   return 42;
  48 }
  49
  50 template <>
  51 std::string ValueInitializer<std::string>() {
  52   return "42";
  53 }
  54 template <>
  55 std::string ValueInitializer<std::string>(int seed) {
  56   return std::string("x", seed & 0x3f);  // avoid making string too long
  57 }
  58
  59 template <>
  60 std::shared_ptr<int> ValueInitializer<std::shared_ptr<int>>() {
  61   return std::make_shared<int>(42);
  62 }
  63 template <>
  64 std::shared_ptr<int> ValueInitializer<std::shared_ptr<int>>(int seed) {
  65   return std::make_shared<int>(seed);
  66 }
  67
  68 template <typename Vector>
  69 ARROW_NOINLINE int64_t ConsumeVector(Vector v) {
  70   return reinterpret_cast<intptr_t>(v.data());
  71 }
  72
  73 template <typename Vector>
  74 ARROW_NOINLINE int64_t IngestVector(const Vector& v) {
  75   return reinterpret_cast<intptr_t>(v.data());
  76 }
  77
  78 // With ARROW_NOINLINE, try to make sure the number of items is not constant-propagated
  79 template <typename Vector>
  80 ARROW_NOINLINE void BenchmarkMoveVector(benchmark::State& state, Vector vec) {
  81   constexpr int kNumIters = 1000;
  82
  83   for (auto _ : state) {
  84     int64_t dummy = 0;
  85     for (int i = 0; i < kNumIters; ++i) {
  86       Vector tmp(std::move(vec));
  87       dummy += IngestVector(tmp);
  88       vec = std::move(tmp);
  89     }
  90     benchmark::DoNotOptimize(dummy);
  91   }
  92
  93   state.SetItemsProcessed(state.iterations() * kNumIters * 2);
  94 }
  95
  96 template <typename Vector>
  97 void MoveEmptyVector(benchmark::State& state) {
  98   BenchmarkMoveVector(state, Vector{});
  99 }
 100
 101 template <typename Vector>
 102 void MoveShortVector(benchmark::State& state) {
 103   using T = typename Vector::value_type;
 104   constexpr int kSize = 3;
 105   const auto initializer = ValueInitializer<T>();
 106
 107   BenchmarkMoveVector(state, Vector(kSize, initializer));
 108 }
 109
 110 template <typename Vector>
 111 void CopyEmptyVector(benchmark::State& state) {
 112   constexpr int kNumIters = 1000;
 113
 114   const Vector vec{};
 115
 116   for (auto _ : state) {
 117     int64_t dummy = 0;
 118     for (int i = 0; i < kNumIters; ++i) {
 119       dummy += ConsumeVector(vec);
 120     }
 121     benchmark::DoNotOptimize(dummy);
 122   }
 123
 124   state.SetItemsProcessed(state.iterations() * kNumIters);
 125 }
 126
 127 template <typename Vector>
 128 void CopyShortVector(benchmark::State& state) {
 129   constexpr int kSize = 3;
 130   constexpr int kNumIters = 1000;
 131
 132   const Vector vec(kSize);
 133
 134   for (auto _ : state) {
 135     int64_t dummy = 0;
 136     for (int i = 0; i < kNumIters; ++i) {
 137       dummy += ConsumeVector(vec);
 138     }
 139     benchmark::DoNotOptimize(dummy);
 140   }
 141
 142   state.SetItemsProcessed(state.iterations() * kNumIters);
 143 }
 144
 145 // With ARROW_NOINLINE, try to make sure the number of items is not constant-propagated
 146 template <typename Vector>
 147 ARROW_NOINLINE void BenchmarkConstructFromStdVector(benchmark::State& state,
 148                                                     const int nitems) {
 149   using T = typename Vector::value_type;
 150   constexpr int kNumIters = 1000;
 151   const std::vector<T> src(nitems, ValueInitializer<T>());
 152
 153   for (auto _ : state) {
 154     int64_t dummy = 0;
 155     for (int i = 0; i < kNumIters; ++i) {
 156       Vector vec(src);
 157       dummy += IngestVector(vec);
 158     }
 159     benchmark::DoNotOptimize(dummy);
 160   }
 161
 162   state.SetItemsProcessed(state.iterations() * kNumIters);
 163 }
 164
 165 template <typename Vector>
 166 void ConstructFromEmptyStdVector(benchmark::State& state) {
 167   BenchmarkConstructFromStdVector<Vector>(state, 0);
 168 }
 169
 170 template <typename Vector>
 171 void ConstructFromShortStdVector(benchmark::State& state) {
 172   BenchmarkConstructFromStdVector<Vector>(state, 3);
 173 }
 174
 175 // With ARROW_NOINLINE, try to make sure the number of items is not constant-propagated
 176 template <typename Vector>
 177 ARROW_NOINLINE void BenchmarkVectorPushBack(benchmark::State& state, const int nitems) {
 178   using T = typename Vector::value_type;
 179   constexpr int kNumIters = 1000;
 180
 181   ARROW_CHECK_LE(static_cast<size_t>(nitems), Vector{}.max_size());
 182
 183   for (auto _ : state) {
 184     int64_t dummy = 0;
 185     for (int i = 0; i < kNumIters; ++i) {
 186       Vector vec;
 187       vec.reserve(nitems);
 188       for (int j = 0; j < nitems; ++j) {
 189         vec.push_back(ValueInitializer<T>(j));
 190       }
 191       dummy += reinterpret_cast<intptr_t>(vec.data());
 192       benchmark::ClobberMemory();
 193     }
 194     benchmark::DoNotOptimize(dummy);
 195   }
 196
 197   state.SetItemsProcessed(state.iterations() * kNumIters * nitems);
 198 }
 199
 200 template <typename Vector>
 201 void ShortVectorPushBack(benchmark::State& state) {
 202   BenchmarkVectorPushBack<Vector>(state, 3);
 203 }
 204
 205 template <typename Vector>
 206 void LongVectorPushBack(benchmark::State& state) {
 207   BenchmarkVectorPushBack<Vector>(state, 100);
 208 }
 209
 210 // With ARROW_NOINLINE, try to make sure the source data is not constant-propagated
 211 // (we could also use random data)
 212 template <typename Vector, typename T = typename Vector::value_type>
 213 ARROW_NOINLINE void BenchmarkShortVectorInsert(benchmark::State& state,
 214                                                const std::vector<T>& src) {
 215   constexpr int kNumIters = 1000;
 216
 217   for (auto _ : state) {
 218     int64_t dummy = 0;
 219     for (int i = 0; i < kNumIters; ++i) {
 220       Vector vec;
 221       vec.reserve(4);
 222       vec.insert(vec.begin(), src.begin(), src.begin() + 2);
 223       vec.insert(vec.begin(), src.begin() + 2, src.end());
 224       dummy += reinterpret_cast<intptr_t>(vec.data());
 225       benchmark::ClobberMemory();
 226     }
 227     benchmark::DoNotOptimize(dummy);
 228   }
 229
 230   state.SetItemsProcessed(state.iterations() * kNumIters * 4);
 231 }
 232
 233 template <typename Vector>
 234 void ShortVectorInsert(benchmark::State& state) {
 235   using T = typename Vector::value_type;
 236   const std::vector<T> src(4, ValueInitializer<T>());
 237   BenchmarkShortVectorInsert<Vector>(state, src);
 238 }
 239
 240 template <typename Vector>
 241 ARROW_NOINLINE void BenchmarkVectorInsertAtEnd(benchmark::State& state,
 242                                                const int nitems) {
 243   using T = typename Vector::value_type;
 244   constexpr int kNumIters = 1000;
 245
 246   ARROW_CHECK_LE(static_cast<size_t>(nitems), Vector{}.max_size());
 247   ARROW_CHECK_EQ(nitems % 2, 0);
 248
 249   std::vector<T> src;
 250   for (int j = 0; j < nitems / 2; ++j) {
 251     src.push_back(ValueInitializer<T>(j));
 252   }
 253
 254   for (auto _ : state) {
 255     int64_t dummy = 0;
 256     for (int i = 0; i < kNumIters; ++i) {
 257       Vector vec;
 258       vec.reserve(nitems);
 259       vec.insert(vec.end(), src.begin(), src.end());
 260       vec.insert(vec.end(), src.begin(), src.end());
 261       dummy += reinterpret_cast<intptr_t>(vec.data());
 262       benchmark::ClobberMemory();
 263     }
 264     benchmark::DoNotOptimize(dummy);
 265   }
 266
 267   state.SetItemsProcessed(state.iterations() * kNumIters * nitems);
 268 }
 269
 270 template <typename Vector>
 271 void ShortVectorInsertAtEnd(benchmark::State& state) {
 272   BenchmarkVectorInsertAtEnd<Vector>(state, 4);
 273 }
 274
 275 template <typename Vector>
 276 void LongVectorInsertAtEnd(benchmark::State& state) {
 277   BenchmarkVectorInsertAtEnd<Vector>(state, 100);
 278 }
 279
 280 #define SHORT_VECTOR_BENCHMARKS(VEC_TYPE_FACTORY)                                  \
 281   BENCHMARK_TEMPLATE(MoveEmptyVector, VEC_TYPE_FACTORY(int));                      \
 282   BENCHMARK_TEMPLATE(MoveEmptyVector, VEC_TYPE_FACTORY(std::string));              \
 283   BENCHMARK_TEMPLATE(MoveEmptyVector, VEC_TYPE_FACTORY(std::shared_ptr<int>));     \
 284   BENCHMARK_TEMPLATE(MoveShortVector, VEC_TYPE_FACTORY(int));                      \
 285   BENCHMARK_TEMPLATE(MoveShortVector, VEC_TYPE_FACTORY(std::string));              \
 286   BENCHMARK_TEMPLATE(MoveShortVector, VEC_TYPE_FACTORY(std::shared_ptr<int>));     \
 287   BENCHMARK_TEMPLATE(CopyEmptyVector, VEC_TYPE_FACTORY(int));                      \
 288   BENCHMARK_TEMPLATE(CopyEmptyVector, VEC_TYPE_FACTORY(std::string));              \
 289   BENCHMARK_TEMPLATE(CopyEmptyVector, VEC_TYPE_FACTORY(std::shared_ptr<int>));     \
 290   BENCHMARK_TEMPLATE(CopyShortVector, VEC_TYPE_FACTORY(int));                      \
 291   BENCHMARK_TEMPLATE(CopyShortVector, VEC_TYPE_FACTORY(std::string));              \
 292   BENCHMARK_TEMPLATE(CopyShortVector, VEC_TYPE_FACTORY(std::shared_ptr<int>));     \
 293   BENCHMARK_TEMPLATE(ConstructFromEmptyStdVector, VEC_TYPE_FACTORY(int));          \
 294   BENCHMARK_TEMPLATE(ConstructFromEmptyStdVector, VEC_TYPE_FACTORY(std::string));  \
 295   BENCHMARK_TEMPLATE(ConstructFromEmptyStdVector,                                  \
 296                      VEC_TYPE_FACTORY(std::shared_ptr<int>));                      \
 297   BENCHMARK_TEMPLATE(ConstructFromShortStdVector, VEC_TYPE_FACTORY(int));          \
 298   BENCHMARK_TEMPLATE(ConstructFromShortStdVector, VEC_TYPE_FACTORY(std::string));  \
 299   BENCHMARK_TEMPLATE(ConstructFromShortStdVector,                                  \
 300                      VEC_TYPE_FACTORY(std::shared_ptr<int>));                      \
 301   BENCHMARK_TEMPLATE(ShortVectorPushBack, VEC_TYPE_FACTORY(int));                  \
 302   BENCHMARK_TEMPLATE(ShortVectorPushBack, VEC_TYPE_FACTORY(std::string));          \
 303   BENCHMARK_TEMPLATE(ShortVectorPushBack, VEC_TYPE_FACTORY(std::shared_ptr<int>)); \
 304   BENCHMARK_TEMPLATE(ShortVectorInsert, VEC_TYPE_FACTORY(int));                    \
 305   BENCHMARK_TEMPLATE(ShortVectorInsert, VEC_TYPE_FACTORY(std::string));            \
 306   BENCHMARK_TEMPLATE(ShortVectorInsert, VEC_TYPE_FACTORY(std::shared_ptr<int>));   \
 307   BENCHMARK_TEMPLATE(ShortVectorInsertAtEnd, VEC_TYPE_FACTORY(int));               \
 308   BENCHMARK_TEMPLATE(ShortVectorInsertAtEnd, VEC_TYPE_FACTORY(std::string));       \
 309   BENCHMARK_TEMPLATE(ShortVectorInsertAtEnd, VEC_TYPE_FACTORY(std::shared_ptr<int>));
 310
 311 #define LONG_VECTOR_BENCHMARKS(VEC_TYPE_FACTORY)                                  \
 312   BENCHMARK_TEMPLATE(LongVectorPushBack, VEC_TYPE_FACTORY(int));                  \
 313   BENCHMARK_TEMPLATE(LongVectorPushBack, VEC_TYPE_FACTORY(std::string));          \
 314   BENCHMARK_TEMPLATE(LongVectorPushBack, VEC_TYPE_FACTORY(std::shared_ptr<int>)); \
 315   BENCHMARK_TEMPLATE(LongVectorInsertAtEnd, VEC_TYPE_FACTORY(int));               \
 316   BENCHMARK_TEMPLATE(LongVectorInsertAtEnd, VEC_TYPE_FACTORY(std::string));       \
 317   BENCHMARK_TEMPLATE(LongVectorInsertAtEnd, VEC_TYPE_FACTORY(std::shared_ptr<int>));
 318
 319 // NOTE: the macro name below (STD_VECTOR etc.) is reflected in the
 320 // benchmark name, so use descriptive names.
 321
 322 #ifdef ARROW_WITH_BENCHMARKS_REFERENCE
 323
 324 #define STD_VECTOR(T) std::vector<T>
 325 SHORT_VECTOR_BENCHMARKS(STD_VECTOR);
 326 LONG_VECTOR_BENCHMARKS(STD_VECTOR);
 327 #undef STD_VECTOR
 328
 329 #endif
 330
 331 #define STATIC_VECTOR(T) StaticVector<T, 4>
 332 SHORT_VECTOR_BENCHMARKS(STATIC_VECTOR);
 333 #undef STATIC_VECTOR
 334
 335 #define SMALL_VECTOR(T) SmallVector<T, 4>
 336 SHORT_VECTOR_BENCHMARKS(SMALL_VECTOR);
 337 LONG_VECTOR_BENCHMARKS(SMALL_VECTOR);
 338 #undef SMALL_VECTOR
 339
 340 #undef SHORT_VECTOR_BENCHMARKS
 341 #undef LONG_VECTOR_BENCHMARKS
 342
 343 }  // namespace internal
 344 }  // namespace arrow