ceph/src/arrow/cpp/src/arrow/compute/kernels/vector_sort_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 "benchmark/benchmark.h"
  19
  20 #include "arrow/compute/api_vector.h"
  21 #include "arrow/compute/kernels/test_util.h"
  22 #include "arrow/table.h"
  23 #include "arrow/testing/gtest_util.h"
  24 #include "arrow/testing/random.h"
  25 #include "arrow/util/benchmark_util.h"
  26 #include "arrow/util/logging.h"
  27
  28 namespace arrow {
  29 namespace compute {
  30 constexpr auto kSeed = 0x0ff1ce;
  31
  32 static void ArraySortIndicesBenchmark(benchmark::State& state,
  33                                       const std::shared_ptr<Array>& values) {
  34   for (auto _ : state) {
  35     ABORT_NOT_OK(SortIndices(*values).status());
  36   }
  37   state.SetItemsProcessed(state.iterations() * values->length());
  38 }
  39
  40 static void ChunkedArraySortIndicesBenchmark(
  41     benchmark::State& state, const std::shared_ptr<ChunkedArray>& values) {
  42   for (auto _ : state) {
  43     ABORT_NOT_OK(SortIndices(*values).status());
  44   }
  45   state.SetItemsProcessed(state.iterations() * values->length());
  46 }
  47
  48 static void ArraySortIndicesInt64Benchmark(benchmark::State& state, int64_t min,
  49                                            int64_t max) {
  50   RegressionArgs args(state);
  51
  52   const int64_t array_size = args.size / sizeof(int64_t);
  53   auto rand = random::RandomArrayGenerator(kSeed);
  54   auto values = rand.Int64(array_size, min, max, args.null_proportion);
  55
  56   ArraySortIndicesBenchmark(state, values);
  57 }
  58
  59 static void ChunkedArraySortIndicesInt64Benchmark(benchmark::State& state, int64_t min,
  60                                                   int64_t max) {
  61   RegressionArgs args(state);
  62
  63   const int64_t n_chunks = 10;
  64   const int64_t array_size = args.size / n_chunks / sizeof(int64_t);
  65   auto rand = random::RandomArrayGenerator(kSeed);
  66   ArrayVector chunks;
  67   for (int64_t i = 0; i < n_chunks; ++i) {
  68     chunks.push_back(rand.Int64(array_size, min, max, args.null_proportion));
  69   }
  70
  71   ChunkedArraySortIndicesBenchmark(state, std::make_shared<ChunkedArray>(chunks));
  72 }
  73
  74 static void ArraySortIndicesInt64Narrow(benchmark::State& state) {
  75   ArraySortIndicesInt64Benchmark(state, -100, 100);
  76 }
  77
  78 static void ArraySortIndicesInt64Wide(benchmark::State& state) {
  79   const auto min = std::numeric_limits<int64_t>::min();
  80   const auto max = std::numeric_limits<int64_t>::max();
  81   ArraySortIndicesInt64Benchmark(state, min, max);
  82 }
  83
  84 static void ArraySortIndicesBool(benchmark::State& state) {
  85   RegressionArgs args(state);
  86
  87   const int64_t array_size = args.size * 8;
  88   auto rand = random::RandomArrayGenerator(kSeed);
  89   auto values = rand.Boolean(array_size, 0.5, args.null_proportion);
  90
  91   ArraySortIndicesBenchmark(state, values);
  92 }
  93
  94 static void ChunkedArraySortIndicesInt64Narrow(benchmark::State& state) {
  95   ChunkedArraySortIndicesInt64Benchmark(state, -100, 100);
  96 }
  97
  98 static void ChunkedArraySortIndicesInt64Wide(benchmark::State& state) {
  99   const auto min = std::numeric_limits<int64_t>::min();
 100   const auto max = std::numeric_limits<int64_t>::max();
 101   ChunkedArraySortIndicesInt64Benchmark(state, min, max);
 102 }
 103
 104 static void DatumSortIndicesBenchmark(benchmark::State& state, const Datum& datum,
 105                                       const SortOptions& options) {
 106   for (auto _ : state) {
 107     ABORT_NOT_OK(SortIndices(datum, options).status());
 108   }
 109 }
 110
 111 // Extract benchmark args from benchmark::State
 112 struct RecordBatchSortIndicesArgs {
 113   // the number of records
 114   const int64_t num_records;
 115
 116   // proportion of nulls in generated arrays
 117   const double null_proportion;
 118
 119   // the number of columns
 120   const int64_t num_columns;
 121
 122   // Extract args
 123   explicit RecordBatchSortIndicesArgs(benchmark::State& state)
 124       : num_records(state.range(0)),
 125         null_proportion(ComputeNullProportion(state.range(1))),
 126         num_columns(state.range(2)),
 127         state_(state) {}
 128
 129   ~RecordBatchSortIndicesArgs() {
 130     state_.counters["columns"] = static_cast<double>(num_columns);
 131     state_.counters["null_percent"] = null_proportion * 100;
 132     state_.SetItemsProcessed(state_.iterations() * num_records);
 133   }
 134
 135  protected:
 136   double ComputeNullProportion(int64_t inverse_null_proportion) {
 137     if (inverse_null_proportion == 0) {
 138       return 0.0;
 139     } else {
 140       return std::min(1., 1. / static_cast<double>(inverse_null_proportion));
 141     }
 142   }
 143
 144   benchmark::State& state_;
 145 };
 146
 147 struct TableSortIndicesArgs : public RecordBatchSortIndicesArgs {
 148   // the number of chunks in each generated column
 149   const int64_t num_chunks;
 150
 151   // Extract args
 152   explicit TableSortIndicesArgs(benchmark::State& state)
 153       : RecordBatchSortIndicesArgs(state), num_chunks(state.range(3)) {}
 154
 155   ~TableSortIndicesArgs() { state_.counters["chunks"] = static_cast<double>(num_chunks); }
 156 };
 157
 158 struct BatchOrTableBenchmarkData {
 159   std::shared_ptr<Schema> schema;
 160   std::vector<SortKey> sort_keys;
 161   ChunkedArrayVector columns;
 162 };
 163
 164 BatchOrTableBenchmarkData MakeBatchOrTableBenchmarkDataInt64(
 165     const RecordBatchSortIndicesArgs& args, int64_t num_chunks, int64_t min_value,
 166     int64_t max_value) {
 167   auto rand = random::RandomArrayGenerator(kSeed);
 168   FieldVector fields;
 169   BatchOrTableBenchmarkData data;
 170
 171   for (int64_t i = 0; i < args.num_columns; ++i) {
 172     auto name = std::to_string(i);
 173     fields.push_back(field(name, int64()));
 174     auto order = (i % 2) == 0 ? SortOrder::Ascending : SortOrder::Descending;
 175     data.sort_keys.emplace_back(name, order);
 176     ArrayVector chunks;
 177     if ((args.num_records % num_chunks) != 0) {
 178       Status::Invalid("The number of chunks (", num_chunks,
 179                       ") must be "
 180                       "a multiple of the number of records (",
 181                       args.num_records, ")")
 182           .Abort();
 183     }
 184     auto num_records_in_array = args.num_records / num_chunks;
 185     for (int64_t j = 0; j < num_chunks; ++j) {
 186       chunks.push_back(
 187           rand.Int64(num_records_in_array, min_value, max_value, args.null_proportion));
 188     }
 189     ASSIGN_OR_ABORT(auto chunked_array, ChunkedArray::Make(chunks, int64()));
 190     data.columns.push_back(chunked_array);
 191   }
 192
 193   data.schema = schema(fields);
 194   return data;
 195 }
 196
 197 static void RecordBatchSortIndicesInt64(benchmark::State& state, int64_t min,
 198                                         int64_t max) {
 199   RecordBatchSortIndicesArgs args(state);
 200
 201   auto data = MakeBatchOrTableBenchmarkDataInt64(args, /*num_chunks=*/1, min, max);
 202   ArrayVector columns;
 203   for (const auto& chunked : data.columns) {
 204     ARROW_CHECK_EQ(chunked->num_chunks(), 1);
 205     columns.push_back(chunked->chunk(0));
 206   }
 207
 208   auto batch = RecordBatch::Make(data.schema, args.num_records, columns);
 209   SortOptions options(data.sort_keys);
 210   DatumSortIndicesBenchmark(state, Datum(*batch), options);
 211 }
 212
 213 static void TableSortIndicesInt64(benchmark::State& state, int64_t min, int64_t max) {
 214   TableSortIndicesArgs args(state);
 215
 216   auto data = MakeBatchOrTableBenchmarkDataInt64(args, args.num_chunks, min, max);
 217   auto table = Table::Make(data.schema, data.columns, args.num_records);
 218   SortOptions options(data.sort_keys);
 219   DatumSortIndicesBenchmark(state, Datum(*table), options);
 220 }
 221
 222 static void RecordBatchSortIndicesInt64Narrow(benchmark::State& state) {
 223   RecordBatchSortIndicesInt64(state, -100, 100);
 224 }
 225
 226 static void RecordBatchSortIndicesInt64Wide(benchmark::State& state) {
 227   RecordBatchSortIndicesInt64(state, std::numeric_limits<int64_t>::min(),
 228                               std::numeric_limits<int64_t>::max());
 229 }
 230
 231 static void TableSortIndicesInt64Narrow(benchmark::State& state) {
 232   TableSortIndicesInt64(state, -100, 100);
 233 }
 234
 235 static void TableSortIndicesInt64Wide(benchmark::State& state) {
 236   TableSortIndicesInt64(state, std::numeric_limits<int64_t>::min(),
 237                         std::numeric_limits<int64_t>::max());
 238 }
 239
 240 BENCHMARK(ArraySortIndicesInt64Narrow)
 241     ->Apply(RegressionSetArgs)
 242     ->Args({1 << 20, 100})
 243     ->Args({1 << 23, 100})
 244     ->Unit(benchmark::TimeUnit::kNanosecond);
 245
 246 BENCHMARK(ArraySortIndicesInt64Wide)
 247     ->Apply(RegressionSetArgs)
 248     ->Args({1 << 20, 100})
 249     ->Args({1 << 23, 100})
 250     ->Unit(benchmark::TimeUnit::kNanosecond);
 251
 252 BENCHMARK(ArraySortIndicesBool)
 253     ->Apply(RegressionSetArgs)
 254     ->Args({1 << 20, 100})
 255     ->Args({1 << 23, 100})
 256     ->Unit(benchmark::TimeUnit::kNanosecond);
 257
 258 BENCHMARK(ChunkedArraySortIndicesInt64Narrow)
 259     ->Apply(RegressionSetArgs)
 260     ->Args({1 << 20, 100})
 261     ->Args({1 << 23, 100})
 262     ->Unit(benchmark::TimeUnit::kNanosecond);
 263
 264 BENCHMARK(ChunkedArraySortIndicesInt64Wide)
 265     ->Apply(RegressionSetArgs)
 266     ->Args({1 << 20, 100})
 267     ->Args({1 << 23, 100})
 268     ->Unit(benchmark::TimeUnit::kNanosecond);
 269
 270 BENCHMARK(RecordBatchSortIndicesInt64Narrow)
 271     ->ArgsProduct({
 272         {1 << 20},      // the number of records
 273         {100, 4, 0},    // inverse null proportion
 274         {16, 8, 2, 1},  // the number of columns
 275     })
 276     ->Unit(benchmark::TimeUnit::kNanosecond);
 277
 278 BENCHMARK(RecordBatchSortIndicesInt64Wide)
 279     ->ArgsProduct({
 280         {1 << 20},      // the number of records
 281         {100, 4, 0},    // inverse null proportion
 282         {16, 8, 2, 1},  // the number of columns
 283     })
 284     ->Unit(benchmark::TimeUnit::kNanosecond);
 285
 286 BENCHMARK(TableSortIndicesInt64Narrow)
 287     ->ArgsProduct({
 288         {1 << 20},      // the number of records
 289         {100, 4, 0},    // inverse null proportion
 290         {16, 8, 2, 1},  // the number of columns
 291         {32, 4, 1},     // the number of chunks
 292     })
 293     ->Unit(benchmark::TimeUnit::kNanosecond);
 294
 295 BENCHMARK(TableSortIndicesInt64Wide)
 296     ->ArgsProduct({
 297         {1 << 20},      // the number of records
 298         {100, 4, 0},    // inverse null proportion
 299         {16, 8, 2, 1},  // the number of columns
 300         {32, 4, 1},     // the number of chunks
 301     })
 302     ->Unit(benchmark::TimeUnit::kNanosecond);
 303
 304 }  // namespace compute
 305 }  // namespace arrow