tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

int128_benchmark.cc (9891B)

      1 // Copyright 2017 The Abseil Authors.
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      https://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 #include <algorithm>
     16 #include <cstdint>
     17 #include <limits>
     18 #include <random>
     19 #include <vector>
     20 
     21 #include "absl/base/config.h"
     22 #include "absl/numeric/int128.h"
     23 #include "benchmark/benchmark.h"
     24 
     25 namespace {
     26 
     27 constexpr size_t kSampleSize = 1000000;
     28 
     29 std::mt19937 MakeRandomEngine() {
     30  std::random_device r;
     31  std::seed_seq seed({r(), r(), r(), r(), r(), r(), r(), r()});
     32  return std::mt19937(seed);
     33 }
     34 
     35 template <typename T,
     36          typename H = typename std::conditional<
     37              std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type>
     38 std::vector<std::pair<T, T>> GetRandomClass128SampleUniformDivisor() {
     39  std::vector<std::pair<T, T>> values;
     40  std::mt19937 random = MakeRandomEngine();
     41  std::uniform_int_distribution<H> uniform_h;
     42  values.reserve(kSampleSize);
     43  for (size_t i = 0; i < kSampleSize; ++i) {
     44    T a{absl::MakeUint128(uniform_h(random), uniform_h(random))};
     45    T b{absl::MakeUint128(uniform_h(random), uniform_h(random))};
     46    values.emplace_back(std::max(a, b), std::max(T(2), std::min(a, b)));
     47  }
     48  return values;
     49 }
     50 
     51 template <typename T>
     52 void BM_DivideClass128UniformDivisor(benchmark::State& state) {
     53  auto values = GetRandomClass128SampleUniformDivisor<T>();
     54  while (state.KeepRunningBatch(values.size())) {
     55    for (const auto& pair : values) {
     56      benchmark::DoNotOptimize(pair.first / pair.second);
     57    }
     58  }
     59 }
     60 BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::uint128);
     61 BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::int128);
     62 
     63 template <typename T>
     64 void BM_RemainderClass128UniformDivisor(benchmark::State& state) {
     65  auto values = GetRandomClass128SampleUniformDivisor<T>();
     66  while (state.KeepRunningBatch(values.size())) {
     67    for (const auto& pair : values) {
     68      benchmark::DoNotOptimize(pair.first % pair.second);
     69    }
     70  }
     71 }
     72 BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::uint128);
     73 BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::int128);
     74 
     75 template <typename T,
     76          typename H = typename std::conditional<
     77              std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type>
     78 std::vector<std::pair<T, H>> GetRandomClass128SampleSmallDivisor() {
     79  std::vector<std::pair<T, H>> values;
     80  std::mt19937 random = MakeRandomEngine();
     81  std::uniform_int_distribution<H> uniform_h;
     82  values.reserve(kSampleSize);
     83  for (size_t i = 0; i < kSampleSize; ++i) {
     84    T a{absl::MakeUint128(uniform_h(random), uniform_h(random))};
     85    H b{std::max(H{2}, uniform_h(random))};
     86    values.emplace_back(std::max(a, T(b)), b);
     87  }
     88  return values;
     89 }
     90 
     91 template <typename T>
     92 void BM_DivideClass128SmallDivisor(benchmark::State& state) {
     93  auto values = GetRandomClass128SampleSmallDivisor<T>();
     94  while (state.KeepRunningBatch(values.size())) {
     95    for (const auto& pair : values) {
     96      benchmark::DoNotOptimize(pair.first / pair.second);
     97    }
     98  }
     99 }
    100 BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::uint128);
    101 BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::int128);
    102 
    103 template <typename T>
    104 void BM_RemainderClass128SmallDivisor(benchmark::State& state) {
    105  auto values = GetRandomClass128SampleSmallDivisor<T>();
    106  while (state.KeepRunningBatch(values.size())) {
    107    for (const auto& pair : values) {
    108      benchmark::DoNotOptimize(pair.first % pair.second);
    109    }
    110  }
    111 }
    112 BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::uint128);
    113 BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::int128);
    114 
    115 std::vector<std::pair<absl::uint128, absl::uint128>> GetRandomClass128Sample() {
    116  std::vector<std::pair<absl::uint128, absl::uint128>> values;
    117  std::mt19937 random = MakeRandomEngine();
    118  std::uniform_int_distribution<uint64_t> uniform_uint64;
    119  values.reserve(kSampleSize);
    120  for (size_t i = 0; i < kSampleSize; ++i) {
    121    values.emplace_back(
    122        absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)),
    123        absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)));
    124  }
    125  return values;
    126 }
    127 
    128 void BM_MultiplyClass128(benchmark::State& state) {
    129  auto values = GetRandomClass128Sample();
    130  while (state.KeepRunningBatch(values.size())) {
    131    for (const auto& pair : values) {
    132      benchmark::DoNotOptimize(pair.first * pair.second);
    133    }
    134  }
    135 }
    136 BENCHMARK(BM_MultiplyClass128);
    137 
    138 void BM_AddClass128(benchmark::State& state) {
    139  auto values = GetRandomClass128Sample();
    140  while (state.KeepRunningBatch(values.size())) {
    141    for (const auto& pair : values) {
    142      benchmark::DoNotOptimize(pair.first + pair.second);
    143    }
    144  }
    145 }
    146 BENCHMARK(BM_AddClass128);
    147 
    148 #ifdef ABSL_HAVE_INTRINSIC_INT128
    149 
    150 // Some implementations of <random> do not support __int128 when it is
    151 // available, so we make our own uniform_int_distribution-like type.
    152 template <typename T,
    153          typename H = typename std::conditional<
    154              std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
    155 class UniformIntDistribution128 {
    156 public:
    157  // NOLINTNEXTLINE: mimicking std::uniform_int_distribution API
    158  T operator()(std::mt19937& generator) {
    159    return (static_cast<T>(dist64_(generator)) << 64) | dist64_(generator);
    160  }
    161 
    162 private:
    163  std::uniform_int_distribution<H> dist64_;
    164 };
    165 
    166 template <typename T,
    167          typename H = typename std::conditional<
    168              std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
    169 std::vector<std::pair<T, T>> GetRandomIntrinsic128SampleUniformDivisor() {
    170  std::vector<std::pair<T, T>> values;
    171  std::mt19937 random = MakeRandomEngine();
    172  UniformIntDistribution128<T> uniform_128;
    173  values.reserve(kSampleSize);
    174  for (size_t i = 0; i < kSampleSize; ++i) {
    175    T a = uniform_128(random);
    176    T b = uniform_128(random);
    177    values.emplace_back(std::max(a, b),
    178                        std::max(static_cast<T>(2), std::min(a, b)));
    179  }
    180  return values;
    181 }
    182 
    183 template <typename T>
    184 void BM_DivideIntrinsic128UniformDivisor(benchmark::State& state) {
    185  auto values = GetRandomIntrinsic128SampleUniformDivisor<T>();
    186  while (state.KeepRunningBatch(values.size())) {
    187    for (const auto& pair : values) {
    188      benchmark::DoNotOptimize(pair.first / pair.second);
    189    }
    190  }
    191 }
    192 BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, unsigned __int128);
    193 BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, __int128);
    194 
    195 template <typename T>
    196 void BM_RemainderIntrinsic128UniformDivisor(benchmark::State& state) {
    197  auto values = GetRandomIntrinsic128SampleUniformDivisor<T>();
    198  while (state.KeepRunningBatch(values.size())) {
    199    for (const auto& pair : values) {
    200      benchmark::DoNotOptimize(pair.first % pair.second);
    201    }
    202  }
    203 }
    204 BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, unsigned __int128);
    205 BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, __int128);
    206 
    207 template <typename T,
    208          typename H = typename std::conditional<
    209              std::is_same<T, __int128>::value, int64_t, uint64_t>::type>
    210 std::vector<std::pair<T, H>> GetRandomIntrinsic128SampleSmallDivisor() {
    211  std::vector<std::pair<T, H>> values;
    212  std::mt19937 random = MakeRandomEngine();
    213  UniformIntDistribution128<T> uniform_int128;
    214  std::uniform_int_distribution<H> uniform_int64;
    215  values.reserve(kSampleSize);
    216  for (size_t i = 0; i < kSampleSize; ++i) {
    217    T a = uniform_int128(random);
    218    H b = std::max(H{2}, uniform_int64(random));
    219    values.emplace_back(std::max(a, static_cast<T>(b)), b);
    220  }
    221  return values;
    222 }
    223 
    224 template <typename T>
    225 void BM_DivideIntrinsic128SmallDivisor(benchmark::State& state) {
    226  auto values = GetRandomIntrinsic128SampleSmallDivisor<T>();
    227  while (state.KeepRunningBatch(values.size())) {
    228    for (const auto& pair : values) {
    229      benchmark::DoNotOptimize(pair.first / pair.second);
    230    }
    231  }
    232 }
    233 BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, unsigned __int128);
    234 BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, __int128);
    235 
    236 template <typename T>
    237 void BM_RemainderIntrinsic128SmallDivisor(benchmark::State& state) {
    238  auto values = GetRandomIntrinsic128SampleSmallDivisor<T>();
    239  while (state.KeepRunningBatch(values.size())) {
    240    for (const auto& pair : values) {
    241      benchmark::DoNotOptimize(pair.first % pair.second);
    242    }
    243  }
    244 }
    245 BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, unsigned __int128);
    246 BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, __int128);
    247 
    248 std::vector<std::pair<unsigned __int128, unsigned __int128>>
    249      GetRandomIntrinsic128Sample() {
    250  std::vector<std::pair<unsigned __int128, unsigned __int128>> values;
    251  std::mt19937 random = MakeRandomEngine();
    252  UniformIntDistribution128<unsigned __int128> uniform_uint128;
    253  values.reserve(kSampleSize);
    254  for (size_t i = 0; i < kSampleSize; ++i) {
    255    values.emplace_back(uniform_uint128(random), uniform_uint128(random));
    256  }
    257  return values;
    258 }
    259 
    260 void BM_MultiplyIntrinsic128(benchmark::State& state) {
    261  auto values = GetRandomIntrinsic128Sample();
    262  while (state.KeepRunningBatch(values.size())) {
    263    for (const auto& pair : values) {
    264      benchmark::DoNotOptimize(pair.first * pair.second);
    265    }
    266  }
    267 }
    268 BENCHMARK(BM_MultiplyIntrinsic128);
    269 
    270 void BM_AddIntrinsic128(benchmark::State& state) {
    271  auto values = GetRandomIntrinsic128Sample();
    272  while (state.KeepRunningBatch(values.size())) {
    273    for (const auto& pair : values) {
    274      benchmark::DoNotOptimize(pair.first + pair.second);
    275    }
    276  }
    277 }
    278 BENCHMARK(BM_AddIntrinsic128);
    279 
    280 #endif  // ABSL_HAVE_INTRINSIC_INT128
    281 
    282 }  // namespace