diff options
Diffstat (limited to 'third_party/abseil_cpp/absl/numeric')
| -rw-r--r-- | third_party/abseil_cpp/absl/numeric/BUILD.bazel | 1 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/numeric/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/numeric/int128.cc | 40 | ||||
| -rw-r--r-- | third_party/abseil_cpp/absl/numeric/int128_benchmark.cc | 161 |
4 files changed, 126 insertions, 77 deletions
diff --git a/third_party/abseil_cpp/absl/numeric/BUILD.bazel b/third_party/abseil_cpp/absl/numeric/BUILD.bazel index e09e52d21fe6..da3af4d0cec7 100644 --- a/third_party/abseil_cpp/absl/numeric/BUILD.bazel +++ b/third_party/abseil_cpp/absl/numeric/BUILD.bazel @@ -35,6 +35,7 @@ cc_library( copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ + "//absl/base:bits", "//absl/base:config", "//absl/base:core_headers", ], diff --git a/third_party/abseil_cpp/absl/numeric/CMakeLists.txt b/third_party/abseil_cpp/absl/numeric/CMakeLists.txt index 242889f088ad..1e12d80f7ce9 100644 --- a/third_party/abseil_cpp/absl/numeric/CMakeLists.txt +++ b/third_party/abseil_cpp/absl/numeric/CMakeLists.txt @@ -26,6 +26,7 @@ absl_cc_library( COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::bits absl::config absl::core_headers PUBLIC diff --git a/third_party/abseil_cpp/absl/numeric/int128.cc b/third_party/abseil_cpp/absl/numeric/int128.cc index b605a87042c1..e21e5e9a4ad4 100644 --- a/third_party/abseil_cpp/absl/numeric/int128.cc +++ b/third_party/abseil_cpp/absl/numeric/int128.cc @@ -15,6 +15,7 @@ #include "absl/numeric/int128.h" #include <stddef.h> + #include <cassert> #include <iomanip> #include <ostream> // NOLINT(readability/streams) @@ -22,6 +23,9 @@ #include <string> #include <type_traits> +#include "absl/base/internal/bits.h" +#include "absl/base/optimization.h" + namespace absl { ABSL_NAMESPACE_BEGIN @@ -31,44 +35,26 @@ ABSL_DLL const uint128 kuint128max = MakeUint128( namespace { // Returns the 0-based position of the last set bit (i.e., most significant bit) -// in the given uint64_t. The argument may not be 0. +// in the given uint128. The argument is not 0. // // For example: // Given: 5 (decimal) == 101 (binary) // Returns: 2 -#define STEP(T, n, pos, sh) \ - do { \ - if ((n) >= (static_cast<T>(1) << (sh))) { \ - (n) = (n) >> (sh); \ - (pos) |= (sh); \ - } \ - } while (0) -static inline int Fls64(uint64_t n) { - assert(n != 0); - int pos = 0; - STEP(uint64_t, n, pos, 0x20); - uint32_t n32 = static_cast<uint32_t>(n); - STEP(uint32_t, n32, pos, 0x10); - STEP(uint32_t, n32, pos, 0x08); - STEP(uint32_t, n32, pos, 0x04); - return pos + ((uint64_t{0x3333333322221100} >> (n32 << 2)) & 0x3); -} -#undef STEP - -// Like Fls64() above, but returns the 0-based position of the last set bit -// (i.e., most significant bit) in the given uint128. The argument may not be 0. -static inline int Fls128(uint128 n) { +inline ABSL_ATTRIBUTE_ALWAYS_INLINE int Fls128(uint128 n) { if (uint64_t hi = Uint128High64(n)) { - return Fls64(hi) + 64; + ABSL_INTERNAL_ASSUME(hi != 0); + return 127 - base_internal::CountLeadingZeros64(hi); } - return Fls64(Uint128Low64(n)); + const uint64_t low = Uint128Low64(n); + ABSL_INTERNAL_ASSUME(low != 0); + return 63 - base_internal::CountLeadingZeros64(low); } // Long division/modulo for uint128 implemented using the shift-subtract // division algorithm adapted from: // https://stackoverflow.com/questions/5386377/division-without-using -void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret, - uint128* remainder_ret) { +inline void DivModImpl(uint128 dividend, uint128 divisor, uint128* quotient_ret, + uint128* remainder_ret) { assert(divisor != 0); if (divisor > dividend) { diff --git a/third_party/abseil_cpp/absl/numeric/int128_benchmark.cc b/third_party/abseil_cpp/absl/numeric/int128_benchmark.cc index a5502d927c08..eab1515c0ad8 100644 --- a/third_party/abseil_cpp/absl/numeric/int128_benchmark.cc +++ b/third_party/abseil_cpp/absl/numeric/int128_benchmark.cc @@ -12,15 +12,15 @@ // See the License for the specific language governing permissions and // limitations under the License. -#include "absl/numeric/int128.h" - #include <algorithm> #include <cstdint> +#include <limits> #include <random> #include <vector> #include "benchmark/benchmark.h" #include "absl/base/config.h" +#include "absl/numeric/int128.h" namespace { @@ -32,57 +32,85 @@ std::mt19937 MakeRandomEngine() { return std::mt19937(seed); } -std::vector<std::pair<absl::uint128, absl::uint128>> -GetRandomClass128SampleUniformDivisor() { - std::vector<std::pair<absl::uint128, absl::uint128>> values; +template <typename T, + typename H = typename std::conditional< + std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type> +std::vector<std::pair<T, T>> GetRandomClass128SampleUniformDivisor() { + std::vector<std::pair<T, T>> values; std::mt19937 random = MakeRandomEngine(); - std::uniform_int_distribution<uint64_t> uniform_uint64; + std::uniform_int_distribution<H> uniform_h; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { - absl::uint128 a = - absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)); - absl::uint128 b = - absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)); - values.emplace_back(std::max(a, b), - std::max(absl::uint128(2), std::min(a, b))); + T a{absl::MakeUint128(uniform_h(random), uniform_h(random))}; + T b{absl::MakeUint128(uniform_h(random), uniform_h(random))}; + values.emplace_back(std::max(a, b), std::max(T(2), std::min(a, b))); } return values; } +template <typename T> void BM_DivideClass128UniformDivisor(benchmark::State& state) { - auto values = GetRandomClass128SampleUniformDivisor(); + auto values = GetRandomClass128SampleUniformDivisor<T>(); while (state.KeepRunningBatch(values.size())) { for (const auto& pair : values) { benchmark::DoNotOptimize(pair.first / pair.second); } } } -BENCHMARK(BM_DivideClass128UniformDivisor); +BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::uint128); +BENCHMARK_TEMPLATE(BM_DivideClass128UniformDivisor, absl::int128); + +template <typename T> +void BM_RemainderClass128UniformDivisor(benchmark::State& state) { + auto values = GetRandomClass128SampleUniformDivisor<T>(); + while (state.KeepRunningBatch(values.size())) { + for (const auto& pair : values) { + benchmark::DoNotOptimize(pair.first % pair.second); + } + } +} +BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::uint128); +BENCHMARK_TEMPLATE(BM_RemainderClass128UniformDivisor, absl::int128); -std::vector<std::pair<absl::uint128, uint64_t>> -GetRandomClass128SampleSmallDivisor() { - std::vector<std::pair<absl::uint128, uint64_t>> values; +template <typename T, + typename H = typename std::conditional< + std::numeric_limits<T>::is_signed, int64_t, uint64_t>::type> +std::vector<std::pair<T, H>> GetRandomClass128SampleSmallDivisor() { + std::vector<std::pair<T, H>> values; std::mt19937 random = MakeRandomEngine(); - std::uniform_int_distribution<uint64_t> uniform_uint64; + std::uniform_int_distribution<H> uniform_h; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { - absl::uint128 a = - absl::MakeUint128(uniform_uint64(random), uniform_uint64(random)); - uint64_t b = std::max(uint64_t{2}, uniform_uint64(random)); - values.emplace_back(std::max(a, absl::uint128(b)), b); + T a{absl::MakeUint128(uniform_h(random), uniform_h(random))}; + H b{std::max(H{2}, uniform_h(random))}; + values.emplace_back(std::max(a, T(b)), b); } return values; } +template <typename T> void BM_DivideClass128SmallDivisor(benchmark::State& state) { - auto values = GetRandomClass128SampleSmallDivisor(); + auto values = GetRandomClass128SampleSmallDivisor<T>(); while (state.KeepRunningBatch(values.size())) { for (const auto& pair : values) { benchmark::DoNotOptimize(pair.first / pair.second); } } } -BENCHMARK(BM_DivideClass128SmallDivisor); +BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::uint128); +BENCHMARK_TEMPLATE(BM_DivideClass128SmallDivisor, absl::int128); + +template <typename T> +void BM_RemainderClass128SmallDivisor(benchmark::State& state) { + auto values = GetRandomClass128SampleSmallDivisor<T>(); + while (state.KeepRunningBatch(values.size())) { + for (const auto& pair : values) { + benchmark::DoNotOptimize(pair.first % pair.second); + } + } +} +BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::uint128); +BENCHMARK_TEMPLATE(BM_RemainderClass128SmallDivisor, absl::int128); std::vector<std::pair<absl::uint128, absl::uint128>> GetRandomClass128Sample() { std::vector<std::pair<absl::uint128, absl::uint128>> values; @@ -121,74 +149,107 @@ BENCHMARK(BM_AddClass128); // Some implementations of <random> do not support __int128 when it is // available, so we make our own uniform_int_distribution-like type. +template <typename T, + typename H = typename std::conditional< + std::is_same<T, __int128>::value, int64_t, uint64_t>::type> class UniformIntDistribution128 { public: // NOLINTNEXTLINE: mimicking std::uniform_int_distribution API - unsigned __int128 operator()(std::mt19937& generator) { - return (static_cast<unsigned __int128>(dist64_(generator)) << 64) | - dist64_(generator); + T operator()(std::mt19937& generator) { + return (static_cast<T>(dist64_(generator)) << 64) | dist64_(generator); } private: - std::uniform_int_distribution<uint64_t> dist64_; + std::uniform_int_distribution<H> dist64_; }; -std::vector<std::pair<unsigned __int128, unsigned __int128>> -GetRandomIntrinsic128SampleUniformDivisor() { - std::vector<std::pair<unsigned __int128, unsigned __int128>> values; +template <typename T, + typename H = typename std::conditional< + std::is_same<T, __int128>::value, int64_t, uint64_t>::type> +std::vector<std::pair<T, T>> GetRandomIntrinsic128SampleUniformDivisor() { + std::vector<std::pair<T, T>> values; std::mt19937 random = MakeRandomEngine(); - UniformIntDistribution128 uniform_uint128; + UniformIntDistribution128<T> uniform_128; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { - unsigned __int128 a = uniform_uint128(random); - unsigned __int128 b = uniform_uint128(random); - values.emplace_back( - std::max(a, b), - std::max(static_cast<unsigned __int128>(2), std::min(a, b))); + T a = uniform_128(random); + T b = uniform_128(random); + values.emplace_back(std::max(a, b), + std::max(static_cast<T>(2), std::min(a, b))); } return values; } +template <typename T> void BM_DivideIntrinsic128UniformDivisor(benchmark::State& state) { - auto values = GetRandomIntrinsic128SampleUniformDivisor(); + auto values = GetRandomIntrinsic128SampleUniformDivisor<T>(); while (state.KeepRunningBatch(values.size())) { for (const auto& pair : values) { benchmark::DoNotOptimize(pair.first / pair.second); } } } -BENCHMARK(BM_DivideIntrinsic128UniformDivisor); +BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, unsigned __int128); +BENCHMARK_TEMPLATE(BM_DivideIntrinsic128UniformDivisor, __int128); + +template <typename T> +void BM_RemainderIntrinsic128UniformDivisor(benchmark::State& state) { + auto values = GetRandomIntrinsic128SampleUniformDivisor<T>(); + while (state.KeepRunningBatch(values.size())) { + for (const auto& pair : values) { + benchmark::DoNotOptimize(pair.first % pair.second); + } + } +} +BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, unsigned __int128); +BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128UniformDivisor, __int128); -std::vector<std::pair<unsigned __int128, uint64_t>> -GetRandomIntrinsic128SampleSmallDivisor() { - std::vector<std::pair<unsigned __int128, uint64_t>> values; +template <typename T, + typename H = typename std::conditional< + std::is_same<T, __int128>::value, int64_t, uint64_t>::type> +std::vector<std::pair<T, H>> GetRandomIntrinsic128SampleSmallDivisor() { + std::vector<std::pair<T, H>> values; std::mt19937 random = MakeRandomEngine(); - UniformIntDistribution128 uniform_uint128; - std::uniform_int_distribution<uint64_t> uniform_uint64; + UniformIntDistribution128<T> uniform_int128; + std::uniform_int_distribution<H> uniform_int64; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { - unsigned __int128 a = uniform_uint128(random); - uint64_t b = std::max(uint64_t{2}, uniform_uint64(random)); - values.emplace_back(std::max(a, static_cast<unsigned __int128>(b)), b); + T a = uniform_int128(random); + H b = std::max(H{2}, uniform_int64(random)); + values.emplace_back(std::max(a, static_cast<T>(b)), b); } return values; } +template <typename T> void BM_DivideIntrinsic128SmallDivisor(benchmark::State& state) { - auto values = GetRandomIntrinsic128SampleSmallDivisor(); + auto values = GetRandomIntrinsic128SampleSmallDivisor<T>(); while (state.KeepRunningBatch(values.size())) { for (const auto& pair : values) { benchmark::DoNotOptimize(pair.first / pair.second); } } } -BENCHMARK(BM_DivideIntrinsic128SmallDivisor); +BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, unsigned __int128); +BENCHMARK_TEMPLATE(BM_DivideIntrinsic128SmallDivisor, __int128); + +template <typename T> +void BM_RemainderIntrinsic128SmallDivisor(benchmark::State& state) { + auto values = GetRandomIntrinsic128SampleSmallDivisor<T>(); + while (state.KeepRunningBatch(values.size())) { + for (const auto& pair : values) { + benchmark::DoNotOptimize(pair.first % pair.second); + } + } +} +BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, unsigned __int128); +BENCHMARK_TEMPLATE(BM_RemainderIntrinsic128SmallDivisor, __int128); std::vector<std::pair<unsigned __int128, unsigned __int128>> GetRandomIntrinsic128Sample() { std::vector<std::pair<unsigned __int128, unsigned __int128>> values; std::mt19937 random = MakeRandomEngine(); - UniformIntDistribution128 uniform_uint128; + UniformIntDistribution128<unsigned __int128> uniform_uint128; values.reserve(kSampleSize); for (size_t i = 0; i < kSampleSize; ++i) { values.emplace_back(uniform_uint128(random), uniform_uint128(random)); |