From ab21820d47e4f83875dda008b600514d3520fd35 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Thu, 4 Mar 2021 09:10:07 -0800 Subject: Export of internal Abseil changes MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit -- e2de21d54c02b6419c57c0f4e2a16b608deca260 by Evan Brown : Remove the InsertEnd benchmark. This benchmark has significantly different possible behaviors that can result in misleading metrics. Specifically, we can have a case where we are deallocating the last node in the b-tree in the erase and then allocating a new node in the insert call repeatedly, whereas normally, we end up just inserting/erasing a value from the last node. Also, the name of the benchmark is misleading because it involves an erase and an insert, but the name only mentions the insert. PiperOrigin-RevId: 360930639 -- 51f6bb97b9cbdb809c31b77e93ce080ca3cba9ea by Benjamin Barenblat : Stop testing with double-double random variables On POWER, long double is often represented as a pair of doubles added together (double-double arithmetic). We’ve already special-cased double-double arithmetic in a number of tests, but compiler bugs [1, 2, 3] have now triggered both false positives and false negatives, which suggests testing with double doubles is unlikely to yield useful signal. Remove the special casing and detect if we’re on a double-double system; if so, just don’t test long doubles. [1] https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048 [2] https://bugs.llvm.org/show_bug.cgi?id=49131 [3] https://bugs.llvm.org/show_bug.cgi?id=49132 PiperOrigin-RevId: 360793161 -- 07fb4d7932c2f5d711c480f759dacb0be60f975e by Abseil Team : internal change PiperOrigin-RevId: 360712825 GitOrigin-RevId: e2de21d54c02b6419c57c0f4e2a16b608deca260 Change-Id: I98389b5a8789dcc8f35abc00c767e909181665f0 --- CMake/AbseilDll.cmake | 1 + absl/container/btree_benchmark.cc | 34 ------------- absl/numeric/BUILD.bazel | 12 +++++ absl/numeric/CMakeLists.txt | 12 +++++ absl/numeric/internal/representation.h | 55 ++++++++++++++++++++++ absl/random/BUILD.bazel | 4 ++ absl/random/CMakeLists.txt | 4 ++ absl/random/beta_distribution_test.cc | 40 +++++----------- absl/random/exponential_distribution_test.cc | 28 ++++------- absl/random/gaussian_distribution_test.cc | 35 +++++--------- absl/random/uniform_real_distribution_test.cc | 12 ++++- absl/strings/BUILD.bazel | 1 + absl/strings/CMakeLists.txt | 1 + .../internal/str_format/float_conversion.cc | 12 ++--- 14 files changed, 138 insertions(+), 113 deletions(-) create mode 100644 absl/numeric/internal/representation.h diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 47707dfd..39f85f2f 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake @@ -131,6 +131,7 @@ set(ABSL_INTERNAL_DLL_FILES "numeric/int128.cc" "numeric/int128.h" "numeric/internal/bits.h" + "numeric/internal/representation.h" "random/bernoulli_distribution.h" "random/beta_distribution.h" "random/bit_gen_ref.h" diff --git a/absl/container/btree_benchmark.cc b/absl/container/btree_benchmark.cc index 46798676..41f13f52 100644 --- a/absl/container/btree_benchmark.cc +++ b/absl/container/btree_benchmark.cc @@ -101,39 +101,6 @@ void BM_InsertSorted(benchmark::State& state) { BM_InsertImpl(state, true); } -// container::insert sometimes returns a pair and sometimes -// returns an iterator (for multi- containers). -template -Iter GetIterFromInsert(const std::pair& pair) { - return pair.first; -} -template -Iter GetIterFromInsert(const Iter iter) { - return iter; -} - -// Benchmark insertion of values into a container at the end. -template -void BM_InsertEnd(benchmark::State& state) { - using V = typename remove_pair_const::type; - typename KeyOfValue::type key_of_value; - - T container; - const int kSize = 10000; - for (int i = 0; i < kSize; ++i) { - container.insert(Generator(kSize)(i)); - } - V v = Generator(kSize)(kSize - 1); - typename T::key_type k = key_of_value(v); - - auto it = container.find(k); - while (state.KeepRunning()) { - // Repeatedly removing then adding v. - container.erase(it); - it = GetIterFromInsert(container.insert(v)); - } -} - // Benchmark inserting the first few elements in a container. In b-tree, this is // when the root node grows. template @@ -513,7 +480,6 @@ BTREE_TYPES(Time); #define MY_BENCHMARK3(type) \ MY_BENCHMARK4(type, Insert); \ MY_BENCHMARK4(type, InsertSorted); \ - MY_BENCHMARK4(type, InsertEnd); \ MY_BENCHMARK4(type, InsertSmall); \ MY_BENCHMARK4(type, Lookup); \ MY_BENCHMARK4(type, FullLookup); \ diff --git a/absl/numeric/BUILD.bazel b/absl/numeric/BUILD.bazel index 5d7b1857..ea587bfa 100644 --- a/absl/numeric/BUILD.bazel +++ b/absl/numeric/BUILD.bazel @@ -101,3 +101,15 @@ cc_test( "@com_github_google_benchmark//:benchmark_main", ], ) + +cc_library( + name = "representation", + hdrs = [ + "internal/representation.h", + ], + copts = ABSL_DEFAULT_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + deps = [ + "//absl/base:config", + ], +) diff --git a/absl/numeric/CMakeLists.txt b/absl/numeric/CMakeLists.txt index be94352a..781987dc 100644 --- a/absl/numeric/CMakeLists.txt +++ b/absl/numeric/CMakeLists.txt @@ -86,3 +86,15 @@ absl_cc_library( absl::int128 PUBLIC ) + +absl_cc_library( + NAME + numeric_representation + HDRS + "internal/representation.h" + COPTS + ${ABSL_DEFAULT_COPTS} + DEPS + absl::config + PUBLIC +) diff --git a/absl/numeric/internal/representation.h b/absl/numeric/internal/representation.h new file mode 100644 index 00000000..82d332fd --- /dev/null +++ b/absl/numeric/internal/representation.h @@ -0,0 +1,55 @@ +// Copyright 2021 The Abseil Authors +// +// 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 +// +// https://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. + +#ifndef ABSL_NUMERIC_INTERNAL_REPRESENTATION_H_ +#define ABSL_NUMERIC_INTERNAL_REPRESENTATION_H_ + +#include + +#include "absl/base/config.h" + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace numeric_internal { + +// Returns true iff long double is represented as a pair of doubles added +// together. +inline constexpr bool IsDoubleDouble() { + // A double-double value always has exactly twice the precision of a double + // value--one double carries the high digits and one double carries the low + // digits. This property is not shared with any other common floating-point + // representation, so this test won't trigger false positives. For reference, + // this table gives the number of bits of precision of each common + // floating-point representation: + // + // type precision + // IEEE single 24 b + // IEEE double 53 + // x86 long double 64 + // double-double 106 + // IEEE quadruple 113 + // + // Note in particular that a quadruple-precision float has greater precision + // than a double-double float despite taking up the same amount of memory; the + // quad has more of its bits allocated to the mantissa than the double-double + // has. + return std::numeric_limits::digits == + 2 * std::numeric_limits::digits; +} + +} // namespace numeric_internal +ABSL_NAMESPACE_END +} // namespace absl + +#endif // ABSL_NUMERIC_INTERNAL_REPRESENTATION_H_ diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index d97b2c4e..66ffcbc7 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel @@ -188,6 +188,7 @@ cc_test( ":distributions", ":random", "//absl/base:raw_logging_internal", + "//absl/numeric:representation", "//absl/random/internal:distribution_test_util", "//absl/random/internal:pcg_engine", "//absl/random/internal:sequence_urbg", @@ -308,6 +309,7 @@ cc_test( ":random", "//absl/base:core_headers", "//absl/base:raw_logging_internal", + "//absl/numeric:representation", "//absl/random/internal:distribution_test_util", "//absl/random/internal:pcg_engine", "//absl/random/internal:sequence_urbg", @@ -331,6 +333,7 @@ cc_test( ":random", "//absl/base:core_headers", "//absl/base:raw_logging_internal", + "//absl/numeric:representation", "//absl/random/internal:distribution_test_util", "//absl/random/internal:sequence_urbg", "//absl/strings", @@ -377,6 +380,7 @@ cc_test( ":distributions", ":random", "//absl/base:raw_logging_internal", + "//absl/numeric:representation", "//absl/random/internal:distribution_test_util", "//absl/random/internal:pcg_engine", "//absl/random/internal:sequence_urbg", diff --git a/absl/random/CMakeLists.txt b/absl/random/CMakeLists.txt index 13093d6d..3009a034 100644 --- a/absl/random/CMakeLists.txt +++ b/absl/random/CMakeLists.txt @@ -259,6 +259,7 @@ absl_cc_test( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS + absl::numeric_representation absl::random_distributions absl::random_random absl::random_internal_distribution_test_util @@ -381,6 +382,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::core_headers + absl::numeric_representation absl::random_distributions absl::random_internal_distribution_test_util absl::random_internal_pcg_engine @@ -404,6 +406,7 @@ absl_cc_test( ${ABSL_DEFAULT_LINKOPTS} DEPS absl::core_headers + absl::numeric_representation absl::random_distributions absl::random_internal_distribution_test_util absl::random_internal_sequence_urbg @@ -446,6 +449,7 @@ absl_cc_test( LINKOPTS ${ABSL_DEFAULT_LINKOPTS} DEPS + absl::numeric_representation absl::random_distributions absl::random_internal_distribution_test_util absl::random_internal_pcg_engine diff --git a/absl/random/beta_distribution_test.cc b/absl/random/beta_distribution_test.cc index 277e4dc6..44cdfdd0 100644 --- a/absl/random/beta_distribution_test.cc +++ b/absl/random/beta_distribution_test.cc @@ -21,12 +21,14 @@ #include #include #include +#include #include #include #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/internal/raw_logging.h" +#include "absl/numeric/internal/representation.h" #include "absl/random/internal/chi_square.h" #include "absl/random/internal/distribution_test_util.h" #include "absl/random/internal/pcg_engine.h" @@ -42,7 +44,15 @@ namespace { template class BetaDistributionInterfaceTest : public ::testing::Test {}; -using RealTypes = ::testing::Types; +// double-double arithmetic is not supported well by either GCC or Clang; see +// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048, +// https://bugs.llvm.org/show_bug.cgi?id=49131, and +// https://bugs.llvm.org/show_bug.cgi?id=49132. Don't bother running these tests +// with double doubles until compiler support is better. +using RealTypes = + std::conditional, + ::testing::Types>::type; TYPED_TEST_CASE(BetaDistributionInterfaceTest, RealTypes); TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { @@ -53,9 +63,6 @@ TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { const TypeParam kLargeA = std::exp(std::log((std::numeric_limits::max)()) - std::log(std::log((std::numeric_limits::max)()))); - const TypeParam kLargeAPPC = std::exp( - std::log((std::numeric_limits::max)()) - - std::log(std::log((std::numeric_limits::max)())) - 10.0f); using param_type = typename absl::beta_distribution::param_type; constexpr int kCount = 1000; @@ -76,9 +83,6 @@ TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { kLargeA, // std::nextafter(kLargeA, TypeParam(0)), // std::nextafter(kLargeA, std::numeric_limits::max()), - kLargeAPPC, // - std::nextafter(kLargeAPPC, TypeParam(0)), - std::nextafter(kLargeAPPC, std::numeric_limits::max()), // Boundary cases. std::numeric_limits::max(), std::numeric_limits::epsilon(), @@ -125,28 +129,6 @@ TYPED_TEST(BetaDistributionInterfaceTest, SerializeTest) { ss >> after; -#if defined(__powerpc64__) || defined(__PPC64__) || defined(__powerpc__) || \ - defined(__ppc__) || defined(__PPC__) - if (std::is_same::value) { - // Roundtripping floating point values requires sufficient precision - // to reconstruct the exact value. It turns out that long double - // has some errors doing this on ppc. - if (alpha <= std::numeric_limits::max() && - alpha >= std::numeric_limits::lowest()) { - EXPECT_EQ(static_cast(before.alpha()), - static_cast(after.alpha())) - << ss.str(); - } - if (beta <= std::numeric_limits::max() && - beta >= std::numeric_limits::lowest()) { - EXPECT_EQ(static_cast(before.beta()), - static_cast(after.beta())) - << ss.str(); - } - continue; - } -#endif - EXPECT_EQ(before.alpha(), after.alpha()); EXPECT_EQ(before.beta(), after.beta()); EXPECT_EQ(before, after) // diff --git a/absl/random/exponential_distribution_test.cc b/absl/random/exponential_distribution_test.cc index 5a8afde5..af11d61c 100644 --- a/absl/random/exponential_distribution_test.cc +++ b/absl/random/exponential_distribution_test.cc @@ -30,6 +30,7 @@ #include "gtest/gtest.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/macros.h" +#include "absl/numeric/internal/representation.h" #include "absl/random/internal/chi_square.h" #include "absl/random/internal/distribution_test_util.h" #include "absl/random/internal/pcg_engine.h" @@ -47,7 +48,15 @@ using absl::random_internal::kChiSquared; template class ExponentialDistributionTypedTest : public ::testing::Test {}; -using RealTypes = ::testing::Types; +// double-double arithmetic is not supported well by either GCC or Clang; see +// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048, +// https://bugs.llvm.org/show_bug.cgi?id=49131, and +// https://bugs.llvm.org/show_bug.cgi?id=49132. Don't bother running these tests +// with double doubles until compiler support is better. +using RealTypes = + std::conditional, + ::testing::Types>::type; TYPED_TEST_CASE(ExponentialDistributionTypedTest, RealTypes); TYPED_TEST(ExponentialDistributionTypedTest, SerializeTest) { @@ -126,23 +135,6 @@ TYPED_TEST(ExponentialDistributionTypedTest, SerializeTest) { ss >> after; -#if defined(__powerpc64__) || defined(__PPC64__) || defined(__powerpc__) || \ - defined(__ppc__) || defined(__PPC__) - if (std::is_same::value) { - // Roundtripping floating point values requires sufficient precision to - // reconstruct the exact value. It turns out that long double has some - // errors doing this on ppc, particularly for values - // near {1.0 +/- epsilon}. - if (lambda <= std::numeric_limits::max() && - lambda >= std::numeric_limits::lowest()) { - EXPECT_EQ(static_cast(before.lambda()), - static_cast(after.lambda())) - << ss.str(); - } - continue; - } -#endif - EXPECT_EQ(before.lambda(), after.lambda()) // << ss.str() << " " // << (ss.good() ? "good " : "") // diff --git a/absl/random/gaussian_distribution_test.cc b/absl/random/gaussian_distribution_test.cc index 2aa7caf4..c0bac2b0 100644 --- a/absl/random/gaussian_distribution_test.cc +++ b/absl/random/gaussian_distribution_test.cc @@ -21,12 +21,14 @@ #include #include #include +#include #include #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/macros.h" +#include "absl/numeric/internal/representation.h" #include "absl/random/internal/chi_square.h" #include "absl/random/internal/distribution_test_util.h" #include "absl/random/internal/sequence_urbg.h" @@ -43,7 +45,15 @@ using absl::random_internal::kChiSquared; template class GaussianDistributionInterfaceTest : public ::testing::Test {}; -using RealTypes = ::testing::Types; +// double-double arithmetic is not supported well by either GCC or Clang; see +// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048, +// https://bugs.llvm.org/show_bug.cgi?id=49131, and +// https://bugs.llvm.org/show_bug.cgi?id=49132. Don't bother running these tests +// with double doubles until compiler support is better. +using RealTypes = + std::conditional, + ::testing::Types>::type; TYPED_TEST_CASE(GaussianDistributionInterfaceTest, RealTypes); TYPED_TEST(GaussianDistributionInterfaceTest, SerializeTest) { @@ -129,29 +139,6 @@ TYPED_TEST(GaussianDistributionInterfaceTest, SerializeTest) { ss >> after; -#if defined(__powerpc64__) || defined(__PPC64__) || defined(__powerpc__) || \ - defined(__ppc__) || defined(__PPC__) - if (std::is_same::value) { - // Roundtripping floating point values requires sufficient precision - // to reconstruct the exact value. It turns out that long double - // has some errors doing this on ppc, particularly for values - // near {1.0 +/- epsilon}. - if (mean <= std::numeric_limits::max() && - mean >= std::numeric_limits::lowest()) { - EXPECT_EQ(static_cast(before.mean()), - static_cast(after.mean())) - << ss.str(); - } - if (stddev <= std::numeric_limits::max() && - stddev >= std::numeric_limits::lowest()) { - EXPECT_EQ(static_cast(before.stddev()), - static_cast(after.stddev())) - << ss.str(); - } - continue; - } -#endif - EXPECT_EQ(before.mean(), after.mean()); EXPECT_EQ(before.stddev(), after.stddev()) // << ss.str() << " " // diff --git a/absl/random/uniform_real_distribution_test.cc b/absl/random/uniform_real_distribution_test.cc index 8cf874d6..18bcd3bc 100644 --- a/absl/random/uniform_real_distribution_test.cc +++ b/absl/random/uniform_real_distribution_test.cc @@ -20,11 +20,13 @@ #include #include #include +#include #include #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/internal/raw_logging.h" +#include "absl/numeric/internal/representation.h" #include "absl/random/internal/chi_square.h" #include "absl/random/internal/distribution_test_util.h" #include "absl/random/internal/pcg_engine.h" @@ -55,7 +57,15 @@ namespace { template class UniformRealDistributionTest : public ::testing::Test {}; -using RealTypes = ::testing::Types; +// double-double arithmetic is not supported well by either GCC or Clang; see +// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=99048, +// https://bugs.llvm.org/show_bug.cgi?id=49131, and +// https://bugs.llvm.org/show_bug.cgi?id=49132. Don't bother running these tests +// with double doubles until compiler support is better. +using RealTypes = + std::conditional, + ::testing::Types>::type; TYPED_TEST_SUITE(UniformRealDistributionTest, RealTypes); diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 5efaf896..123b5efb 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -709,6 +709,7 @@ cc_library( "//absl/meta:type_traits", "//absl/numeric:bits", "//absl/numeric:int128", + "//absl/numeric:representation", "//absl/types:optional", "//absl/types:span", ], diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 12f322a9..3b7ae639 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt @@ -410,6 +410,7 @@ absl_cc_library( absl::strings absl::config absl::core_headers + absl::numeric_representation absl::type_traits absl::int128 absl::span diff --git a/absl/strings/internal/str_format/float_conversion.cc b/absl/strings/internal/str_format/float_conversion.cc index 2b1fd8cb..b1c40684 100644 --- a/absl/strings/internal/str_format/float_conversion.cc +++ b/absl/strings/internal/str_format/float_conversion.cc @@ -29,6 +29,7 @@ #include "absl/meta/type_traits.h" #include "absl/numeric/bits.h" #include "absl/numeric/int128.h" +#include "absl/numeric/internal/representation.h" #include "absl/strings/numbers.h" #include "absl/types/optional.h" #include "absl/types/span.h" @@ -39,6 +40,8 @@ namespace str_format_internal { namespace { +using ::absl::numeric_internal::IsDoubleDouble; + // The code below wants to avoid heap allocations. // To do so it needs to allocate memory on the stack. // `StackArray` will allocate memory on the stack in the form of a uint32_t @@ -112,13 +115,6 @@ inline uint64_t DivideBy10WithCarry(uint64_t *v, uint64_t carry) { return next_carry % divisor; } -constexpr bool IsDoubleDouble() { - // This is the `double-double` representation of `long double`. - // We do not handle it natively. Fallback to snprintf. - return std::numeric_limits::digits == - 2 * std::numeric_limits::digits; -} - using MaxFloatType = typename std::conditional::type; @@ -1404,6 +1400,8 @@ bool FloatToSink(const Float v, const FormatConversionSpecImpl &conv, bool ConvertFloatImpl(long double v, const FormatConversionSpecImpl &conv, FormatSinkImpl *sink) { if (IsDoubleDouble()) { + // This is the `double-double` representation of `long double`. We do not + // handle it natively. Fallback to snprintf. return FallbackToSnprintf(v, conv, sink); } -- cgit v1.2.3