265 lines
8.7 KiB
C++
265 lines
8.7 KiB
C++
// Copyright 2010-2025 Google LLC
|
|
// 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 "ortools/base/constant_divisor.h"
|
|
|
|
#include <algorithm>
|
|
#include <cstdint>
|
|
#include <limits>
|
|
|
|
#include "absl/flags/flag.h"
|
|
#include "absl/random/bit_gen_ref.h"
|
|
#include "absl/random/distributions.h"
|
|
#include "absl/random/random.h"
|
|
#include "benchmark/benchmark.h"
|
|
#include "gtest/gtest.h"
|
|
|
|
ABSL_FLAG(int32_t, random_iterations, 100000,
|
|
"Number of iterations for ConstantDivisorTest::RandomCases.");
|
|
|
|
namespace util {
|
|
namespace math {
|
|
namespace {
|
|
|
|
template <typename T>
|
|
class NativeDivisor {
|
|
public:
|
|
typedef T value_type;
|
|
|
|
explicit NativeDivisor(T denominator) : denominator_(denominator) {}
|
|
|
|
T div(T value) const { return value / denominator_; }
|
|
|
|
T mod(T value) const { return value % denominator_; }
|
|
|
|
friend value_type operator/(value_type a, const NativeDivisor& b) {
|
|
return b.div(a);
|
|
}
|
|
|
|
friend value_type operator%(value_type a, const NativeDivisor& b) {
|
|
return b.mod(a);
|
|
}
|
|
|
|
private:
|
|
const T denominator_;
|
|
};
|
|
|
|
template <typename Divisor>
|
|
class ConstantDivisorTest : public ::testing::Test {};
|
|
|
|
// Currently there is no specialization for int, so it should default to the
|
|
// builtin version.
|
|
TEST(ConstantDivisorTemplateTest, Simple) {
|
|
ConstantDivisor<int> divisor(3);
|
|
EXPECT_EQ(4, divisor.div(12));
|
|
EXPECT_EQ(1, divisor.mod(13));
|
|
EXPECT_EQ(4, 12 / divisor);
|
|
EXPECT_EQ(1, 13 % divisor);
|
|
}
|
|
|
|
TEST(ConstantDivisorUint64Test, Bugs) {
|
|
// If formula (27) from p231 is ever implemented, these divisors will break
|
|
// if a >= is accidentally used instead of >.
|
|
EXPECT_EQ(uint64_t{828560257293048160},
|
|
ConstantDivisor<uint64_t>(21).div(uint64_t{17399765403154011380u}));
|
|
EXPECT_EQ(uint64_t{185733693349184273},
|
|
ConstantDivisor<uint64_t>(99).div(uint64_t{18387635641569243125u}));
|
|
}
|
|
|
|
TEST(ConstantDivisorUint16Test, Supports1) {
|
|
ConstantDivisor<uint16_t> divisor(1);
|
|
ASSERT_EQ(42, 42 / divisor);
|
|
ASSERT_EQ(0, 42 % divisor);
|
|
}
|
|
|
|
TEST(ConstantDivisorUint8Test, Exhaustive) {
|
|
// This is cheap, so test all values.
|
|
for (int denominator = 1; denominator < 256; ++denominator) {
|
|
ConstantDivisor<uint8_t> divisor(denominator);
|
|
for (int value = 0; value < 256; ++value) {
|
|
ASSERT_EQ(value / denominator, divisor.div(value))
|
|
<< "denominator: " << denominator << " value: " << value;
|
|
ASSERT_EQ(value % denominator, divisor.mod(value))
|
|
<< "denominator: " << denominator << " value: " << value;
|
|
}
|
|
}
|
|
}
|
|
|
|
typedef ::testing::Types<ConstantDivisor<uint16_t>, ConstantDivisor<uint32_t>,
|
|
ConstantDivisor<uint64_t>, NativeDivisor<uint16_t>,
|
|
NativeDivisor<uint32_t>, NativeDivisor<uint64_t> >
|
|
Divisors;
|
|
TYPED_TEST_SUITE(ConstantDivisorTest, Divisors);
|
|
|
|
TYPED_TEST(ConstantDivisorTest, Simple) {
|
|
TypeParam divisor(3);
|
|
EXPECT_EQ(4, divisor.div(12));
|
|
EXPECT_EQ(1, divisor.mod(13));
|
|
EXPECT_EQ(4, 12 / divisor);
|
|
EXPECT_EQ(1, 13 % divisor);
|
|
}
|
|
|
|
TYPED_TEST(ConstantDivisorTest, CornerCases) {
|
|
EXPECT_EQ(1, TypeParam(5).div(5));
|
|
EXPECT_EQ(2, TypeParam(2).div(4));
|
|
if constexpr (sizeof(typename TypeParam::value_type) >= sizeof(uint16_t)) {
|
|
EXPECT_EQ(100, TypeParam(5).div(500));
|
|
}
|
|
const auto kTypeMax =
|
|
std::numeric_limits<typename TypeParam::value_type>::max();
|
|
if constexpr (sizeof(typename TypeParam::value_type) >= sizeof(uint16_t)) {
|
|
EXPECT_EQ(kTypeMax / 345, TypeParam(345).div(kTypeMax));
|
|
}
|
|
EXPECT_EQ(1, TypeParam(kTypeMax).div(kTypeMax));
|
|
EXPECT_EQ(1, TypeParam(kTypeMax - 1).div(kTypeMax));
|
|
EXPECT_EQ(0, TypeParam(kTypeMax).div((kTypeMax - 1)));
|
|
}
|
|
|
|
TYPED_TEST(ConstantDivisorTest, Bugs) {
|
|
if constexpr (sizeof(typename TypeParam::value_type) < sizeof(uint32_t)) {
|
|
GTEST_SKIP() << "This test is only for 32-bit and above.";
|
|
} else {
|
|
// Cases that triggered bugs found during initial implementation.
|
|
EXPECT_EQ(0, TypeParam(2969932030).div(265448460));
|
|
EXPECT_EQ(2, TypeParam(978790915).div(2489284541));
|
|
EXPECT_EQ(1, TypeParam(4113163180).div(4220126436));
|
|
EXPECT_EQ(2072455839, TypeParam(2).div(4144911678));
|
|
}
|
|
}
|
|
|
|
// Choose a random value of type T, biased towards smaller values.
|
|
template <typename T>
|
|
T ChooseValue(absl::BitGenRef gen) {
|
|
return absl::Uniform<T>(gen, 0, std::numeric_limits<T>::max()) >>
|
|
absl::Uniform<unsigned>(gen, 0, 8 * sizeof(T));
|
|
}
|
|
|
|
TYPED_TEST(ConstantDivisorTest, RandomCases) {
|
|
typedef typename TypeParam::value_type T;
|
|
absl::BitGen gen;
|
|
for (int i = 0; i < absl::GetFlag(FLAGS_random_iterations); ++i) {
|
|
T denominator = std::max<T>(2, ChooseValue<T>(gen));
|
|
T value = ChooseValue<T>(gen);
|
|
TypeParam divisor(denominator);
|
|
ASSERT_EQ(value / denominator, divisor.div(value))
|
|
<< value << " / " << denominator;
|
|
ASSERT_EQ(value % denominator, divisor.mod(value));
|
|
}
|
|
}
|
|
|
|
// Gives a sense of benchmark overhead.
|
|
class NoopDivisor {
|
|
public:
|
|
typedef uint32_t value_type;
|
|
|
|
explicit NoopDivisor(uint32_t) {}
|
|
|
|
uint32_t div(uint32_t value) const { return value; }
|
|
|
|
uint32_t mod(uint32_t value) const { return value; }
|
|
};
|
|
|
|
// Choose a random denominator which is supported by all our implementations,
|
|
// biased towards smaller denominators for uint64_t/uint32_t/uint16_t.
|
|
template <typename T>
|
|
T ChooseDenominator(absl::BitGenRef random) {
|
|
return std::max(uint8_t{2}, ChooseValue<uint8_t>(random));
|
|
}
|
|
|
|
template <typename Divisor>
|
|
void BM_Divide(benchmark::State& state) {
|
|
typedef typename Divisor::value_type T;
|
|
absl::BitGen gen;
|
|
std::vector<T> values;
|
|
for (int i = 0; i < 100000; ++i) {
|
|
values.push_back(ChooseValue<T>(gen));
|
|
}
|
|
|
|
for (auto _ : state) {
|
|
state.PauseTiming();
|
|
Divisor divisor(ChooseDenominator<T>(gen));
|
|
state.ResumeTiming();
|
|
for (T value : values) {
|
|
benchmark::DoNotOptimize(divisor.div(value));
|
|
}
|
|
}
|
|
}
|
|
BENCHMARK_TEMPLATE(BM_Divide, NoopDivisor);
|
|
BENCHMARK_TEMPLATE(BM_Divide, NativeDivisor<uint8_t>);
|
|
BENCHMARK_TEMPLATE(BM_Divide, ConstantDivisor<uint8_t>);
|
|
BENCHMARK_TEMPLATE(BM_Divide, NativeDivisor<uint16_t>);
|
|
BENCHMARK_TEMPLATE(BM_Divide, ConstantDivisor<uint16_t>);
|
|
BENCHMARK_TEMPLATE(BM_Divide, NativeDivisor<uint32_t>);
|
|
BENCHMARK_TEMPLATE(BM_Divide, ConstantDivisor<uint32_t>);
|
|
BENCHMARK_TEMPLATE(BM_Divide, NativeDivisor<uint64_t>);
|
|
BENCHMARK_TEMPLATE(BM_Divide, ConstantDivisor<uint64_t>);
|
|
|
|
template <typename Divisor>
|
|
void BM_Modulo(benchmark::State& state) {
|
|
typedef typename Divisor::value_type T;
|
|
absl::BitGen gen;
|
|
std::vector<T> values;
|
|
for (int i = 0; i < 100000; ++i) {
|
|
values.push_back(ChooseValue<T>(gen));
|
|
}
|
|
|
|
for (auto _ : state) {
|
|
state.PauseTiming();
|
|
Divisor divisor(ChooseDenominator<T>(gen));
|
|
state.ResumeTiming();
|
|
for (T value : values) {
|
|
benchmark::DoNotOptimize(divisor.mod(value));
|
|
}
|
|
}
|
|
}
|
|
BENCHMARK_TEMPLATE(BM_Modulo, NoopDivisor);
|
|
BENCHMARK_TEMPLATE(BM_Modulo, NativeDivisor<uint8_t>);
|
|
BENCHMARK_TEMPLATE(BM_Modulo, ConstantDivisor<uint8_t>);
|
|
BENCHMARK_TEMPLATE(BM_Modulo, NativeDivisor<uint16_t>);
|
|
BENCHMARK_TEMPLATE(BM_Modulo, ConstantDivisor<uint16_t>);
|
|
BENCHMARK_TEMPLATE(BM_Modulo, NativeDivisor<uint32_t>);
|
|
BENCHMARK_TEMPLATE(BM_Modulo, ConstantDivisor<uint32_t>);
|
|
BENCHMARK_TEMPLATE(BM_Modulo, NativeDivisor<uint64_t>);
|
|
BENCHMARK_TEMPLATE(BM_Modulo, ConstantDivisor<uint64_t>);
|
|
|
|
template <typename Divisor>
|
|
void BM_ConstructDivisor(benchmark::State& state) {
|
|
typedef typename Divisor::value_type T;
|
|
absl::BitGen gen;
|
|
std::vector<T> values;
|
|
for (int i = 0; i < 2048; ++i) {
|
|
values.push_back(ChooseDenominator<T>(gen));
|
|
}
|
|
|
|
int mask = values.size() - 1;
|
|
int i = 0;
|
|
for (auto _ : state) {
|
|
Divisor divisor(values[i & mask]);
|
|
benchmark::DoNotOptimize(divisor.div(values[(i + 1) & mask]));
|
|
i++;
|
|
}
|
|
}
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, NoopDivisor);
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, NativeDivisor<uint8_t>);
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, ConstantDivisor<uint8_t>);
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, NativeDivisor<uint16_t>);
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, ConstantDivisor<uint16_t>);
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, NativeDivisor<uint32_t>);
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, ConstantDivisor<uint32_t>);
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, NativeDivisor<uint64_t>);
|
|
BENCHMARK_TEMPLATE(BM_ConstructDivisor, ConstantDivisor<uint64_t>);
|
|
|
|
} // namespace
|
|
} // namespace math
|
|
} // namespace util
|