diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index febb9a7..009e67c 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -305,6 +305,7 @@ deps = [ ":container_memory", ":flat_hash_set", + ":hash_container_defaults", ":hash_generator_testing", ":test_allocator", ":unordered_set_constructor_test", @@ -312,6 +313,7 @@ ":unordered_set_members_test", ":unordered_set_modifiers_test", "//absl/base:config", + "//absl/hash", "//absl/log:check", "//absl/memory", "//absl/strings",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 68a12eb..b9152d2 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -350,6 +350,8 @@ absl::config absl::container_memory absl::flat_hash_set + absl::hash + absl::hash_container_defaults absl::hash_generator_testing absl::memory absl::strings
diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc index 0dd4326..96d7744 100644 --- a/absl/container/flat_hash_set_test.cc +++ b/absl/container/flat_hash_set_test.cc
@@ -14,6 +14,7 @@ #include "absl/container/flat_hash_set.h" +#include <cstddef> #include <cstdint> #include <memory> #include <type_traits> @@ -23,6 +24,7 @@ #include "gmock/gmock.h" #include "gtest/gtest.h" #include "absl/base/config.h" +#include "absl/container/hash_container_defaults.h" #include "absl/container/internal/container_memory.h" #include "absl/container/internal/hash_generator_testing.h" #include "absl/container/internal/test_allocator.h" @@ -30,6 +32,7 @@ #include "absl/container/internal/unordered_set_lookup_test.h" #include "absl/container/internal/unordered_set_members_test.h" #include "absl/container/internal/unordered_set_modifiers_test.h" +#include "absl/hash/hash.h" #include "absl/log/check.h" #include "absl/memory/memory.h" #include "absl/strings/string_view.h" @@ -291,6 +294,49 @@ std::allocator<int>>(nullptr, nullptr))())); } +struct HashEqInvalidOnMove { + HashEqInvalidOnMove() = default; + HashEqInvalidOnMove(const HashEqInvalidOnMove& rhs) = default; + HashEqInvalidOnMove(HashEqInvalidOnMove&& rhs) { rhs.moved = true; } + HashEqInvalidOnMove& operator=(const HashEqInvalidOnMove& rhs) = default; + HashEqInvalidOnMove& operator=(HashEqInvalidOnMove&& rhs) { + rhs.moved = true; + return *this; + } + + size_t operator()(int x) const { + CHECK(!moved); + return absl::HashOf(x); + } + + bool operator()(int x, int y) const { + CHECK(!moved); + return x == y; + } + + bool moved = false; +}; + +TEST(FlatHashSet, MovedFromCleared_HashMustBeValid) { + flat_hash_set<int, HashEqInvalidOnMove> s1, s2; + // Moving the hashtable must not move the hasher because we need to support + // this behavior. + s2 = std::move(s1); + s1.clear(); + s1.insert(2); + EXPECT_THAT(s1, UnorderedElementsAre(2)); +} + +TEST(FlatHashSet, MovedFromCleared_EqMustBeValid) { + flat_hash_set<int, DefaultHashContainerHash<int>, HashEqInvalidOnMove> s1, s2; + // Moving the hashtable must not move the equality functor because we need to + // support this behavior. + s2 = std::move(s1); + s1.clear(); + s1.insert(2); + EXPECT_THAT(s1, UnorderedElementsAre(2)); +} + } // namespace } // namespace container_internal ABSL_NAMESPACE_END
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 3cb9422..2c44f60 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -2841,7 +2841,6 @@ : // Hash, equality and allocator are copied instead of moved because // `that` must be left valid. If Hash is std::function<Key>, moving it // would create a nullptr functor that cannot be called. - // TODO(b/296061262): move instead of copying hash/eq/alloc. // Note: we avoid using exchange for better generated code. settings_(PolicyTraits::transfer_uses_memcpy() || !that.is_full_soo() ? std::move(that.common()) @@ -3831,7 +3830,6 @@ destructor_impl(); move_common(that.is_full_soo(), that.alloc_ref(), common(), std::move(that.common())); - // TODO(b/296061262): move instead of copying hash/eq/alloc. hash_ref() = that.hash_ref(); eq_ref() = that.eq_ref(); CopyAlloc(alloc_ref(), that.alloc_ref(), @@ -3870,7 +3868,6 @@ // We can't take over that's memory so we need to move each element. // While moving elements, this should have that's hash/eq so copy hash/eq // before moving elements. - // TODO(b/296061262): move instead of copying hash/eq. hash_ref() = that.hash_ref(); eq_ref() = that.eq_ref(); return move_elements_allocs_unequal(std::move(that));
diff --git a/absl/crc/internal/non_temporal_memcpy.h b/absl/crc/internal/non_temporal_memcpy.h index 7ae83bd..5d3e4e3 100644 --- a/absl/crc/internal/non_temporal_memcpy.h +++ b/absl/crc/internal/non_temporal_memcpy.h
@@ -111,20 +111,31 @@ #endif // __SSE3__ || __aarch64__ || (_MSC_VER && __AVX__) } +// We try to force non_temporal_store_memcpy_avx to use AVX instructions +// so that we can select it at runtime when AVX is available. +// Clang on Windows has gnu::target but does not make AVX types like __m256i +// available when trying to force specific functions to use AVX compiles. +#if ABSL_HAVE_CPP_ATTRIBUTE(gnu::target) && !defined(_MSC_VER) && \ + (defined(__x86_64__) || defined(__i386__)) +#define ABSL_INTERNAL_CAN_FORCE_AVX 1 +#endif + // If the objects overlap, the behavior is undefined. Uses regular memcpy // instead of non-temporal memcpy if the required CPU intrinsics are unavailable // at compile time. -#if ABSL_HAVE_CPP_ATTRIBUTE(gnu::target) && \ - (defined(__x86_64__) || defined(__i386__)) +#ifdef ABSL_INTERNAL_CAN_FORCE_AVX [[gnu::target("avx")]] #endif inline void *non_temporal_store_memcpy_avx(void *__restrict dst, const void *__restrict src, size_t len) { - // This function requires AVX. For clang and gcc we compile it with AVX even - // if the translation unit isn't built with AVX support. This works because we - // only select this implementation at runtime if the CPU supports AVX. -#if defined(__SSE3__) || (defined(_MSC_VER) && defined(__AVX__)) + // This function requires AVX. If possible we compile it with AVX even if the + // translation unit isn't built with AVX support. This works because we only + // select this implementation at runtime if the CPU supports AVX. + // MSVC AVX support implies SSE3 support. +#if ((defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ + defined(__SSE3__)) || \ + (defined(_MSC_VER) && defined(__AVX__)) uint8_t *d = reinterpret_cast<uint8_t *>(dst); const uint8_t *s = reinterpret_cast<const uint8_t *>(src); @@ -170,10 +181,13 @@ } return dst; #else + // Fallback to regular memcpy so that this function compiles. return memcpy(dst, src, len); -#endif // __SSE3__ || (_MSC_VER && __AVX__) +#endif } +#undef ABSL_INTERNAL_CAN_FORCE_AVX + } // namespace crc_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/strings/escaping.cc b/absl/strings/escaping.cc index 4ffef94..8f5dbcf 100644 --- a/absl/strings/escaping.cc +++ b/absl/strings/escaping.cc
@@ -15,6 +15,7 @@ #include "absl/strings/escaping.h" #include <algorithm> +#include <array> #include <cassert> #include <cstddef> #include <cstdint> @@ -24,6 +25,7 @@ #include <utility> #include "absl/base/config.h" +#include "absl/base/internal/endian.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/internal/unaligned_access.h" #include "absl/base/nullability.h" @@ -388,6 +390,40 @@ }; /* clang-format on */ +constexpr uint32_t MakeCEscapedLittleEndianUint32(size_t c) { + size_t char_len = kCEscapedLen[c]; + if (char_len == 1) { + return static_cast<uint32_t>(c); + } + if (char_len == 2) { + switch (c) { + case '\n': + return '\\' | (static_cast<uint32_t>('n') << 8); + case '\r': + return '\\' | (static_cast<uint32_t>('r') << 8); + case '\t': + return '\\' | (static_cast<uint32_t>('t') << 8); + case '\"': + return '\\' | (static_cast<uint32_t>('\"') << 8); + case '\'': + return '\\' | (static_cast<uint32_t>('\'') << 8); + case '\\': + return '\\' | (static_cast<uint32_t>('\\') << 8); + } + } + return static_cast<uint32_t>('\\' | (('0' + (c / 64)) << 8) | + (('0' + ((c % 64) / 8)) << 16) | + (('0' + (c % 8)) << 24)); +} + +template <size_t... indexes> +inline constexpr std::array<uint32_t, sizeof...(indexes)> +MakeCEscapedLittleEndianUint32Array(std::index_sequence<indexes...>) { + return {MakeCEscapedLittleEndianUint32(indexes)...}; +} +constexpr std::array<uint32_t, 256> kCEscapedLittleEndianUint32Array = + MakeCEscapedLittleEndianUint32Array(std::make_index_sequence<256>()); + // Calculates the length of the C-style escaped version of 'src'. // Assumes that non-printable characters are escaped using octal sequences, and // that UTF-8 bytes are not handled specially. @@ -421,52 +457,24 @@ return; } + // We keep 3 slop bytes so that we can call `little_endian::Store32` + // invariably regardless of the length of the escaped character. + constexpr size_t slop_bytes = 3; size_t cur_dest_len = dest->size(); - ABSL_INTERNAL_CHECK( - cur_dest_len <= std::numeric_limits<size_t>::max() - escaped_len, - "std::string size overflow"); - strings_internal::STLStringResizeUninitialized(dest, - cur_dest_len + escaped_len); + size_t new_dest_len = cur_dest_len + escaped_len + slop_bytes; + ABSL_INTERNAL_CHECK(new_dest_len > cur_dest_len, "std::string size overflow"); + strings_internal::AppendUninitializedTraits<std::string>::Append( + dest, escaped_len + slop_bytes); char* append_ptr = &(*dest)[cur_dest_len]; for (char c : src) { - size_t char_len = kCEscapedLen[static_cast<unsigned char>(c)]; - if (char_len == 1) { - *append_ptr++ = c; - } else if (char_len == 2) { - switch (c) { - case '\n': - *append_ptr++ = '\\'; - *append_ptr++ = 'n'; - break; - case '\r': - *append_ptr++ = '\\'; - *append_ptr++ = 'r'; - break; - case '\t': - *append_ptr++ = '\\'; - *append_ptr++ = 't'; - break; - case '\"': - *append_ptr++ = '\\'; - *append_ptr++ = '\"'; - break; - case '\'': - *append_ptr++ = '\\'; - *append_ptr++ = '\''; - break; - case '\\': - *append_ptr++ = '\\'; - *append_ptr++ = '\\'; - break; - } - } else { - *append_ptr++ = '\\'; - *append_ptr++ = '0' + static_cast<unsigned char>(c) / 64; - *append_ptr++ = '0' + (static_cast<unsigned char>(c) % 64) / 8; - *append_ptr++ = '0' + static_cast<unsigned char>(c) % 8; - } + unsigned char uc = static_cast<unsigned char>(c); + size_t char_len = kCEscapedLen[uc]; + uint32_t little_endian_uint32 = kCEscapedLittleEndianUint32Array[uc]; + little_endian::Store32(append_ptr, little_endian_uint32); + append_ptr += char_len; } + dest->resize(new_dest_len - slop_bytes); } // Reverses the mapping in Base64EscapeInternal; see that method's
diff --git a/absl/strings/escaping_benchmark.cc b/absl/strings/escaping_benchmark.cc index f792226..ba8f09f 100644 --- a/absl/strings/escaping_benchmark.cc +++ b/absl/strings/escaping_benchmark.cc
@@ -15,8 +15,6 @@ #include "absl/strings/escaping.h" #include <cstdint> -#include <cstdio> -#include <cstring> #include <memory> #include <random> #include <string> @@ -25,6 +23,7 @@ #include "absl/base/internal/raw_logging.h" #include "absl/strings/internal/escaping_test_common.h" #include "absl/strings/str_cat.h" +#include "absl/strings/string_view.h" namespace { @@ -33,9 +32,12 @@ for (int i = 0; i < 50; i++) { src += "\\x55"; } - std::string dest; for (auto _ : state) { - absl::CUnescape(src, &dest); + std::string dest; + benchmark::DoNotOptimize(src); + bool result = absl::CUnescape(src, &dest); + benchmark::DoNotOptimize(result); + benchmark::DoNotOptimize(dest); } } BENCHMARK(BM_CUnescapeHexString); @@ -47,19 +49,12 @@ raw += std::string(test_set.plaintext); } } - - // The actual benchmark loop is tiny... - std::string escaped; for (auto _ : state) { + std::string escaped; + benchmark::DoNotOptimize(raw); absl::WebSafeBase64Escape(raw, &escaped); + benchmark::DoNotOptimize(escaped); } - - // We want to be sure the compiler doesn't throw away the loop above, - // and the easiest way to ensure that is to round-trip the results and verify - // them. - std::string round_trip; - absl::WebSafeBase64Unescape(escaped, &round_trip); - ABSL_RAW_CHECK(round_trip == raw, ""); } BENCHMARK(BM_WebSafeBase64Escape_string); @@ -76,7 +71,9 @@ } for (auto _ : state) { - absl::CEscape(src); + benchmark::DoNotOptimize(src); + std::string result = absl::CEscape(src); + benchmark::DoNotOptimize(result); } }
diff --git a/absl/synchronization/internal/waiter_test.cc b/absl/synchronization/internal/waiter_test.cc index 4dfb7a7..da13896 100644 --- a/absl/synchronization/internal/waiter_test.cc +++ b/absl/synchronization/internal/waiter_test.cc
@@ -32,10 +32,6 @@ #include "absl/time/time.h" #include "gtest/gtest.h" -#ifdef ABSL_INTERNAL_HAVE_WIN32_WAITER -#include <windows.h> -#endif - // Test go/btm support by randomizing the value of clock_gettime() for // CLOCK_MONOTONIC. This works by overriding a weak symbol in glibc. // We should be resistant to this randomization when !SupportsSteadyClock(). @@ -57,42 +53,6 @@ } #endif -#ifdef ABSL_INTERNAL_HAVE_WIN32_WAITER -// Returns the "interrupt time bias" from KUSER_SHARED_DATA, which is in units -// of 100ns. -static uint64_t GetSuspendTime() { - return *reinterpret_cast<uint64_t volatile*>( - 0x7FFE0000 /* KUSER_SHARED_DATA */ + 0x3B0); -} - -// Like GetTickCount(), but excludes suspend time. -static unsigned int GetTickCountExcludingSuspend() { - unsigned int result; - uint64_t prev_bias; - uint64_t bias = GetSuspendTime(); - do { - prev_bias = bias; - result = GetTickCount(); - bias = GetSuspendTime(); - } while (bias != prev_bias); - return result - bias / 10000; -} -#endif - -struct BenchmarkTime { - absl::Time time; - absl::Time vtime; -}; - -static BenchmarkTime BenchmarkNow() { - absl::Time now = absl::Now(); - absl::Time vnow = now; -#ifdef ABSL_INTERNAL_HAVE_WIN32_WAITER - vnow = absl::UnixEpoch() + absl::Milliseconds(GetTickCountExcludingSuspend()); -#endif - return {now, vnow}; -} - namespace { TEST(Waiter, PrintPlatformImplementation) { @@ -126,10 +86,10 @@ absl::SleepFor(absl::Seconds(1)); waiter.Post(); }); - BenchmarkTime start = BenchmarkNow(); + absl::Time start = absl::Now(); EXPECT_TRUE( waiter.Wait(absl::synchronization_internal::KernelTimeout::Never())); - absl::Duration waited = BenchmarkNow().vtime - start.vtime; + absl::Duration waited = absl::Now() - start; EXPECT_GE(waited, WithTolerance(absl::Seconds(2))); } @@ -143,10 +103,10 @@ absl::SleepFor(absl::Milliseconds(500)); waiter.Post(); }); - BenchmarkTime start = BenchmarkNow(); + absl::Time start = absl::Now(); EXPECT_TRUE(waiter.Wait( absl::synchronization_internal::KernelTimeout(absl::Seconds(10)))); - absl::Duration waited = BenchmarkNow().vtime - start.vtime; + absl::Duration waited = absl::Now() - start; EXPECT_GE(waited, WithTolerance(absl::Milliseconds(500))); EXPECT_LT(waited, absl::Seconds(2)); } @@ -161,30 +121,30 @@ absl::SleepFor(absl::Milliseconds(500)); waiter.Post(); }); - BenchmarkTime start = BenchmarkNow(); + absl::Time start = absl::Now(); EXPECT_TRUE(waiter.Wait(absl::synchronization_internal::KernelTimeout( - start.time + absl::Seconds(10)))); - absl::Duration waited = BenchmarkNow().vtime - start.vtime; + start + absl::Seconds(10)))); + absl::Duration waited = absl::Now() - start; EXPECT_GE(waited, WithTolerance(absl::Milliseconds(500))); EXPECT_LT(waited, absl::Seconds(2)); } TYPED_TEST_P(WaiterTest, WaitDurationReached) { TypeParam waiter; - BenchmarkTime start = BenchmarkNow(); + absl::Time start = absl::Now(); EXPECT_FALSE(waiter.Wait( absl::synchronization_internal::KernelTimeout(absl::Milliseconds(500)))); - absl::Duration waited = BenchmarkNow().vtime - start.vtime; + absl::Duration waited = absl::Now() - start; EXPECT_GE(waited, WithTolerance(absl::Milliseconds(500))); EXPECT_LT(waited, absl::Seconds(1)); } TYPED_TEST_P(WaiterTest, WaitTimeReached) { TypeParam waiter; - BenchmarkTime start = BenchmarkNow(); + absl::Time start = absl::Now(); EXPECT_FALSE(waiter.Wait(absl::synchronization_internal::KernelTimeout( - start.time + absl::Milliseconds(500)))); - absl::Duration waited = BenchmarkNow().vtime - start.vtime; + start + absl::Milliseconds(500)))); + absl::Duration waited = absl::Now() - start; EXPECT_GE(waited, WithTolerance(absl::Milliseconds(500))); EXPECT_LT(waited, absl::Seconds(1)); }