From 9a79278a9793574cad2773b3445a887f949bc705 Mon Sep 17 00:00:00 2001 From: Matt Kulukundis Date: Mon, 29 Jan 2024 12:14:16 -0800 Subject: Fix a corner case in SpyHashState for exact boundaries. AbslHash allows for piecewise chunks to be streamed incrementally into hash states and requires them to hash identically to one giant stream. The exact size window for this is an internal details `PiecewiseChunkSize`. There was an off by one error in this code. Add tests and fix it. PiperOrigin-RevId: 602463183 Change-Id: I159bbb5e7e745f55b2fe6eaf0d2735bd0a08aca9 --- absl/hash/internal/spy_hash_state.h | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) (limited to 'absl/hash') diff --git a/absl/hash/internal/spy_hash_state.h b/absl/hash/internal/spy_hash_state.h index 09728266..357c301c 100644 --- a/absl/hash/internal/spy_hash_state.h +++ b/absl/hash/internal/spy_hash_state.h @@ -149,20 +149,20 @@ class SpyHashStateImpl : public HashStateBase> { const unsigned char* begin, size_t size) { const size_t large_chunk_stride = PiecewiseChunkSize(); - if (size > large_chunk_stride) { - // Combining a large contiguous buffer must have the same effect as - // doing it piecewise by the stride length, followed by the (possibly - // empty) remainder. - while (size >= large_chunk_stride) { - hash_state = SpyHashStateImpl::combine_contiguous( - std::move(hash_state), begin, large_chunk_stride); - begin += large_chunk_stride; - size -= large_chunk_stride; - } + // Combining a large contiguous buffer must have the same effect as + // doing it piecewise by the stride length, followed by the (possibly + // empty) remainder. + while (size > large_chunk_stride) { + hash_state = SpyHashStateImpl::combine_contiguous( + std::move(hash_state), begin, large_chunk_stride); + begin += large_chunk_stride; + size -= large_chunk_stride; } - hash_state.hash_representation_.emplace_back( - reinterpret_cast(begin), size); + if (size > 0) { + hash_state.hash_representation_.emplace_back( + reinterpret_cast(begin), size); + } return hash_state; } -- cgit v1.2.3 From 780bfc194d807dbd56363635ca40bf96743aa00b Mon Sep 17 00:00:00 2001 From: Shahriar Rouf Date: Wed, 31 Jan 2024 10:07:48 -0800 Subject: Replace `testonly = 1` with `testonly = True` in abseil BUILD files. https://bazel.build/build/style-guide#other-conventions PiperOrigin-RevId: 603084345 Change-Id: Ibd7c9573d820f88059d12c46ff82d7d322d002ae --- absl/base/BUILD.bazel | 18 +++++++++--------- absl/container/BUILD.bazel | 40 ++++++++++++++++++++-------------------- absl/crc/BUILD.bazel | 2 +- absl/flags/BUILD.bazel | 2 +- absl/hash/BUILD.bazel | 6 +++--- absl/log/internal/BUILD.bazel | 2 +- absl/numeric/BUILD.bazel | 2 +- absl/profiling/BUILD.bazel | 2 +- absl/random/BUILD.bazel | 6 +++--- absl/random/internal/BUILD.bazel | 8 ++++---- absl/strings/BUILD.bazel | 8 ++++---- absl/synchronization/BUILD.bazel | 10 +++++----- absl/time/BUILD.bazel | 2 +- 13 files changed, 54 insertions(+), 54 deletions(-) (limited to 'absl/hash') diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel index 0eb735da..1eb8f098 100644 --- a/absl/base/BUILD.bazel +++ b/absl/base/BUILD.bazel @@ -294,7 +294,7 @@ cc_library( cc_library( name = "atomic_hook_test_helper", - testonly = 1, + testonly = True, srcs = ["internal/atomic_hook_test_helper.cc"], hdrs = ["internal/atomic_hook_test_helper.h"], copts = ABSL_DEFAULT_COPTS, @@ -380,7 +380,7 @@ cc_test( cc_library( name = "exception_testing", - testonly = 1, + testonly = True, hdrs = ["internal/exception_testing.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -404,7 +404,7 @@ cc_library( cc_library( name = "exception_safety_testing", - testonly = 1, + testonly = True, srcs = ["internal/exception_safety_testing.cc"], hdrs = ["internal/exception_safety_testing.h"], copts = ABSL_TEST_COPTS, @@ -470,7 +470,7 @@ cc_test( # AbslInternalSpinLockDelay and AbslInternalSpinLockWake. cc_library( name = "spinlock_test_common", - testonly = 1, + testonly = True, srcs = ["spinlock_test_common.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -507,7 +507,7 @@ cc_test( cc_library( name = "spinlock_benchmark_common", - testonly = 1, + testonly = True, srcs = ["internal/spinlock_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -527,7 +527,7 @@ cc_library( cc_binary( name = "spinlock_benchmark", - testonly = 1, + testonly = True, copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, tags = ["benchmark"], @@ -608,7 +608,7 @@ cc_test( cc_binary( name = "no_destructor_benchmark", - testonly = 1, + testonly = True, srcs = ["no_destructor_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -710,7 +710,7 @@ cc_test( cc_library( name = "scoped_set_env", - testonly = 1, + testonly = True, srcs = ["internal/scoped_set_env.cc"], hdrs = ["internal/scoped_set_env.h"], linkopts = ABSL_DEFAULT_LINKOPTS, @@ -784,7 +784,7 @@ cc_test( cc_binary( name = "strerror_benchmark", - testonly = 1, + testonly = True, srcs = ["internal/strerror_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index bc5b2201..91633948 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -108,7 +108,7 @@ cc_test( cc_binary( name = "fixed_array_benchmark", - testonly = 1, + testonly = True, srcs = ["fixed_array_benchmark.cc"], copts = ABSL_TEST_COPTS + ["$(STACK_FRAME_UNLIMITED)"], linkopts = ABSL_DEFAULT_LINKOPTS, @@ -151,7 +151,7 @@ cc_library( cc_library( name = "test_allocator", - testonly = 1, + testonly = True, copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, textual_hdrs = ["internal/test_allocator.h"], @@ -181,7 +181,7 @@ cc_test( cc_binary( name = "inlined_vector_benchmark", - testonly = 1, + testonly = True, srcs = ["inlined_vector_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -210,7 +210,7 @@ cc_test( cc_library( name = "test_instance_tracker", - testonly = 1, + testonly = True, srcs = ["internal/test_instance_tracker.cc"], hdrs = ["internal/test_instance_tracker.h"], copts = ABSL_DEFAULT_COPTS, @@ -449,7 +449,7 @@ cc_test( cc_library( name = "hash_generator_testing", - testonly = 1, + testonly = True, srcs = ["internal/hash_generator_testing.cc"], hdrs = ["internal/hash_generator_testing.h"], copts = ABSL_TEST_COPTS, @@ -465,7 +465,7 @@ cc_library( cc_library( name = "hash_policy_testing", - testonly = 1, + testonly = True, hdrs = ["internal/hash_policy_testing.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -707,7 +707,7 @@ cc_test( cc_binary( name = "raw_hash_set_benchmark", - testonly = 1, + testonly = True, srcs = ["internal/raw_hash_set_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -724,7 +724,7 @@ cc_binary( cc_binary( name = "raw_hash_set_probe_benchmark", - testonly = 1, + testonly = True, srcs = ["internal/raw_hash_set_probe_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = select({ @@ -798,7 +798,7 @@ cc_test( cc_binary( name = "layout_benchmark", - testonly = 1, + testonly = True, srcs = ["internal/layout_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -814,7 +814,7 @@ cc_binary( cc_library( name = "tracked", - testonly = 1, + testonly = True, hdrs = ["internal/tracked.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -825,7 +825,7 @@ cc_library( cc_library( name = "unordered_map_constructor_test", - testonly = 1, + testonly = True, hdrs = ["internal/unordered_map_constructor_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -838,7 +838,7 @@ cc_library( cc_library( name = "unordered_map_lookup_test", - testonly = 1, + testonly = True, hdrs = ["internal/unordered_map_lookup_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -851,7 +851,7 @@ cc_library( cc_library( name = "unordered_map_modifiers_test", - testonly = 1, + testonly = True, hdrs = ["internal/unordered_map_modifiers_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -864,7 +864,7 @@ cc_library( cc_library( name = "unordered_set_constructor_test", - testonly = 1, + testonly = True, hdrs = ["internal/unordered_set_constructor_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -878,7 +878,7 @@ cc_library( cc_library( name = "unordered_set_members_test", - testonly = 1, + testonly = True, hdrs = ["internal/unordered_set_members_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -890,7 +890,7 @@ cc_library( cc_library( name = "unordered_map_members_test", - testonly = 1, + testonly = True, hdrs = ["internal/unordered_map_members_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -902,7 +902,7 @@ cc_library( cc_library( name = "unordered_set_lookup_test", - testonly = 1, + testonly = True, hdrs = ["internal/unordered_set_lookup_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -915,7 +915,7 @@ cc_library( cc_library( name = "unordered_set_modifiers_test", - testonly = 1, + testonly = True, hdrs = ["internal/unordered_set_modifiers_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -1008,7 +1008,7 @@ cc_library( cc_library( name = "btree_test_common", - testonly = 1, + testonly = True, hdrs = ["btree_test.h"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -1059,7 +1059,7 @@ cc_test( cc_binary( name = "btree_benchmark", - testonly = 1, + testonly = True, srcs = [ "btree_benchmark.cc", ], diff --git a/absl/crc/BUILD.bazel b/absl/crc/BUILD.bazel index d923aec4..9dc81819 100644 --- a/absl/crc/BUILD.bazel +++ b/absl/crc/BUILD.bazel @@ -203,7 +203,7 @@ cc_test( cc_binary( name = "crc32c_benchmark", - testonly = 1, + testonly = True, srcs = ["crc32c_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/flags/BUILD.bazel b/absl/flags/BUILD.bazel index d3b06227..657f8d2c 100644 --- a/absl/flags/BUILD.bazel +++ b/absl/flags/BUILD.bazel @@ -404,7 +404,7 @@ cc_test( cc_binary( name = "flag_benchmark", - testonly = 1, + testonly = True, srcs = [ "flag_benchmark.cc", ], diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel index 1e8ad451..fe567e91 100644 --- a/absl/hash/BUILD.bazel +++ b/absl/hash/BUILD.bazel @@ -61,7 +61,7 @@ cc_library( cc_library( name = "hash_testing", - testonly = 1, + testonly = True, hdrs = ["hash_testing.h"], linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ @@ -128,7 +128,7 @@ cc_test( cc_binary( name = "hash_benchmark", - testonly = 1, + testonly = True, srcs = ["hash_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -148,7 +148,7 @@ cc_binary( cc_library( name = "spy_hash_state", - testonly = 1, + testonly = True, hdrs = ["internal/spy_hash_state.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/log/internal/BUILD.bazel b/absl/log/internal/BUILD.bazel index 1be13499..2a8c1a47 100644 --- a/absl/log/internal/BUILD.bazel +++ b/absl/log/internal/BUILD.bazel @@ -400,7 +400,7 @@ cc_library( cc_binary( name = "vlog_config_benchmark", - testonly = 1, + testonly = True, srcs = ["vlog_config_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/numeric/BUILD.bazel b/absl/numeric/BUILD.bazel index db02b9c0..41c015db 100644 --- a/absl/numeric/BUILD.bazel +++ b/absl/numeric/BUILD.bazel @@ -46,7 +46,7 @@ cc_library( cc_binary( name = "bits_benchmark", - testonly = 1, + testonly = True, srcs = ["bits_benchmark.cc"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/profiling/BUILD.bazel b/absl/profiling/BUILD.bazel index 86f205f9..abe127ec 100644 --- a/absl/profiling/BUILD.bazel +++ b/absl/profiling/BUILD.bazel @@ -126,7 +126,7 @@ cc_test( cc_binary( name = "periodic_sampler_benchmark", - testonly = 1, + testonly = True, srcs = ["internal/periodic_sampler_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/random/BUILD.bazel b/absl/random/BUILD.bazel index 80c4f055..bec979d6 100644 --- a/absl/random/BUILD.bazel +++ b/absl/random/BUILD.bazel @@ -132,7 +132,7 @@ cc_library( cc_library( name = "mock_distributions", - testonly = 1, + testonly = True, hdrs = ["mock_distributions.h"], linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ @@ -146,7 +146,7 @@ cc_library( cc_library( name = "mocking_bit_gen", - testonly = 1, + testonly = True, hdrs = [ "mocking_bit_gen.h", ], @@ -521,7 +521,7 @@ cc_test( # Benchmarks for various methods / test utilities cc_binary( name = "benchmarks", - testonly = 1, + testonly = True, srcs = [ "benchmarks.cc", ], diff --git a/absl/random/internal/BUILD.bazel b/absl/random/internal/BUILD.bazel index 71a742ee..69fb5f2b 100644 --- a/absl/random/internal/BUILD.bazel +++ b/absl/random/internal/BUILD.bazel @@ -137,7 +137,7 @@ cc_library( cc_library( name = "explicit_seed_seq", - testonly = 1, + testonly = True, hdrs = [ "explicit_seed_seq.h", ], @@ -151,7 +151,7 @@ cc_library( cc_library( name = "sequence_urbg", - testonly = 1, + testonly = True, hdrs = [ "sequence_urbg.h", ], @@ -375,7 +375,7 @@ cc_binary( cc_library( name = "distribution_test_util", - testonly = 1, + testonly = True, srcs = [ "chi_square.cc", "distribution_test_util.cc", @@ -534,7 +534,7 @@ cc_library( cc_library( name = "mock_overload_set", - testonly = 1, + testonly = True, hdrs = ["mock_overload_set.h"], linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 1b6c7e4b..942c5324 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel @@ -829,7 +829,7 @@ cc_test( cc_library( name = "cord_test_helpers", - testonly = 1, + testonly = True, hdrs = [ "cord_test_helpers.h", ], @@ -845,7 +845,7 @@ cc_library( cc_library( name = "cord_rep_test_util", - testonly = 1, + testonly = True, hdrs = ["internal/cord_rep_test_util.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -859,7 +859,7 @@ cc_library( cc_library( name = "cordz_test_helpers", - testonly = 1, + testonly = True, hdrs = ["cordz_test_helpers.h"], copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -1449,7 +1449,7 @@ cc_test( cc_binary( name = "atod_manual_test", - testonly = 1, + testonly = True, srcs = ["atod_manual_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/synchronization/BUILD.bazel b/absl/synchronization/BUILD.bazel index de06ebdd..f747d14a 100644 --- a/absl/synchronization/BUILD.bazel +++ b/absl/synchronization/BUILD.bazel @@ -183,7 +183,7 @@ cc_test( cc_binary( name = "blocking_counter_benchmark", - testonly = 1, + testonly = True, srcs = ["blocking_counter_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -230,7 +230,7 @@ cc_test( cc_library( name = "thread_pool", - testonly = 1, + testonly = True, hdrs = ["internal/thread_pool.h"], linkopts = ABSL_DEFAULT_LINKOPTS, visibility = [ @@ -281,7 +281,7 @@ cc_test( cc_library( name = "mutex_benchmark_common", - testonly = 1, + testonly = True, srcs = ["mutex_benchmark.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, @@ -300,7 +300,7 @@ cc_library( cc_binary( name = "mutex_benchmark", - testonly = 1, + testonly = True, copts = ABSL_DEFAULT_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, deps = [ @@ -326,7 +326,7 @@ cc_test( cc_library( name = "per_thread_sem_test_common", - testonly = 1, + testonly = True, srcs = ["internal/per_thread_sem_test.cc"], copts = ABSL_TEST_COPTS, linkopts = ABSL_DEFAULT_LINKOPTS, diff --git a/absl/time/BUILD.bazel b/absl/time/BUILD.bazel index e3fe705b..05f1f2f2 100644 --- a/absl/time/BUILD.bazel +++ b/absl/time/BUILD.bazel @@ -65,7 +65,7 @@ cc_library( cc_library( name = "test_util", - testonly = 1, + testonly = True, srcs = ["internal/test_util.cc"], hdrs = ["internal/test_util.h"], copts = ABSL_DEFAULT_COPTS, -- cgit v1.2.3 From 3e59efa2ad1d1777257bd3b1845d5acc4a931687 Mon Sep 17 00:00:00 2001 From: Shahriar Rouf Date: Wed, 7 Feb 2024 13:58:56 -0800 Subject: Optimize `absl::Hash` by making `LowLevelHash` faster. Throughput of the 64 byte chunk loop inside `LowLevelHash` (or now in `LowLevelHashLenGt16`) gets limited by the loop carried dependency on `current_state`. By using 4 states instead of 2, we can reduce this duration by 1 cycle. On Skylake, it is reduced from 9 cycles to 8 cycles (12.5% faster asymptotically). To see the reduction in a simplified version of `LowLevelHash` implementation on Skylake: * Before: https://godbolt.org/z/Tcj9vsGax, llvm-mca (https://godbolt.org/z/3o78Msr63) shows 9 cycles / iteration. * After: https://godbolt.org/z/q4GM4EjPr, llvm-mca (https://godbolt.org/z/W5d1KEMzq) shows 8 cycles / iteration. * This CL is removing 1 xor (1 cycle) per iteration from the critical path. A block for 32 byte chunk is also added. Finally, just before returning, `Mix` is called 1 time instead of twice. PiperOrigin-RevId: 605090653 Change-Id: Ib7517ebb8bef7484066cd14cf41a943953e93377 --- absl/hash/internal/hash.cc | 2 +- absl/hash/internal/low_level_hash.cc | 84 +++++++++----- absl/hash/internal/low_level_hash.h | 4 + absl/hash/internal/low_level_hash_test.cc | 180 +++++++++++++++--------------- 4 files changed, 154 insertions(+), 116 deletions(-) (limited to 'absl/hash') diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc index 11451e57..93906ef8 100644 --- a/absl/hash/internal/hash.cc +++ b/absl/hash/internal/hash.cc @@ -61,7 +61,7 @@ constexpr uint64_t kHashSalt[5] = { uint64_t MixingHashState::LowLevelHashImpl(const unsigned char* data, size_t len) { - return LowLevelHash(data, len, Seed(), kHashSalt); + return LowLevelHashLenGt16(data, len, Seed(), kHashSalt); } } // namespace hash_internal diff --git a/absl/hash/internal/low_level_hash.cc b/absl/hash/internal/low_level_hash.cc index b5db0b89..43de6729 100644 --- a/absl/hash/internal/low_level_hash.cc +++ b/absl/hash/internal/low_level_hash.cc @@ -14,6 +14,9 @@ #include "absl/hash/internal/low_level_hash.h" +#include +#include + #include "absl/base/internal/unaligned_access.h" #include "absl/base/prefetch.h" #include "absl/numeric/int128.h" @@ -28,8 +31,8 @@ static uint64_t Mix(uint64_t v0, uint64_t v1) { return absl::Uint128Low64(p) ^ absl::Uint128High64(p); } -uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, - const uint64_t salt[5]) { +uint64_t LowLevelHashLenGt16(const void* data, size_t len, uint64_t seed, + const uint64_t salt[5]) { // Prefetch the cacheline that data resides in. PrefetchToLocalCache(data); const uint8_t* ptr = static_cast(data); @@ -40,7 +43,9 @@ uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, // If we have more than 64 bytes, we're going to handle chunks of 64 // bytes at a time. We're going to build up two separate hash states // which we will then hash together. - uint64_t duplicated_state = current_state; + uint64_t duplicated_state0 = current_state; + uint64_t duplicated_state1 = current_state; + uint64_t duplicated_state2 = current_state; do { // Always prefetch the next cacheline. @@ -55,24 +60,39 @@ uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48); uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56); - uint64_t cs0 = Mix(a ^ salt[1], b ^ current_state); - uint64_t cs1 = Mix(c ^ salt[2], d ^ current_state); - current_state = (cs0 ^ cs1); + current_state = Mix(a ^ salt[1], b ^ current_state); + duplicated_state0 = Mix(c ^ salt[2], d ^ duplicated_state0); - uint64_t ds0 = Mix(e ^ salt[3], f ^ duplicated_state); - uint64_t ds1 = Mix(g ^ salt[4], h ^ duplicated_state); - duplicated_state = (ds0 ^ ds1); + duplicated_state1 = Mix(e ^ salt[3], f ^ duplicated_state1); + duplicated_state2 = Mix(g ^ salt[4], h ^ duplicated_state2); ptr += 64; len -= 64; } while (len > 64); - current_state = current_state ^ duplicated_state; + current_state = (current_state ^ duplicated_state0) ^ + (duplicated_state1 + duplicated_state2); } // We now have a data `ptr` with at most 64 bytes and the current state // of the hashing state machine stored in current_state. - while (len > 16) { + if (len > 32) { + uint64_t a = absl::base_internal::UnalignedLoad64(ptr); + uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); + uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); + uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); + + uint64_t cs0 = Mix(a ^ salt[1], b ^ current_state); + uint64_t cs1 = Mix(c ^ salt[2], d ^ current_state); + current_state = cs0 ^ cs1; + + ptr += 32; + len -= 32; + } + + // We now have a data `ptr` with at most 32 bytes and the current state + // of the hashing state machine stored in current_state. + if (len > 16) { uint64_t a = absl::base_internal::UnalignedLoad64(ptr); uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); @@ -82,13 +102,33 @@ uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, len -= 16; } - // We now have a data `ptr` with at most 16 bytes. + // We now have a data `ptr` with at least 1 and at most 16 bytes. But we can + // safely read from `ptr + len - 16`. + uint64_t a = absl::base_internal::UnalignedLoad64(ptr + len - 16); + uint64_t b = absl::base_internal::UnalignedLoad64(ptr + len - 8); + + return Mix(a ^ salt[1] ^ starting_length, b ^ current_state); +} + +uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, + const uint64_t salt[5]) { + if (len > 16) return LowLevelHashLenGt16(data, len, seed, salt); + + // Prefetch the cacheline that data resides in. + PrefetchToLocalCache(data); + const uint8_t* ptr = static_cast(data); + uint64_t starting_length = static_cast(len); + uint64_t current_state = seed ^ salt[0]; + if (len == 0) return current_state; + uint64_t a = 0; uint64_t b = 0; + + // We now have a data `ptr` with at least 1 and at most 16 bytes. if (len > 8) { // When we have at least 9 and at most 16 bytes, set A to the first 64 - // bits of the input and B to the last 64 bits of the input. Yes, they will - // overlap in the middle if we are working with less than the full 16 + // bits of the input and B to the last 64 bits of the input. Yes, they + // will overlap in the middle if we are working with less than the full 16 // bytes. a = absl::base_internal::UnalignedLoad64(ptr); b = absl::base_internal::UnalignedLoad64(ptr + len - 8); @@ -97,20 +137,14 @@ uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, // bits and B to the last 32 bits. a = absl::base_internal::UnalignedLoad32(ptr); b = absl::base_internal::UnalignedLoad32(ptr + len - 4); - } else if (len > 0) { - // If we have at least 1 and at most 3 bytes, read all of the provided - // bits into A, with some adjustments. - a = static_cast((ptr[0] << 16) | (ptr[len >> 1] << 8) | - ptr[len - 1]); - b = 0; } else { - a = 0; - b = 0; + // If we have at least 1 and at most 3 bytes, read 2 bytes into A and the + // other byte into B, with some adjustments. + a = static_cast((ptr[0] << 8) | ptr[len - 1]); + b = static_cast(ptr[len >> 1]); } - uint64_t w = Mix(a ^ salt[1], b ^ current_state); - uint64_t z = salt[1] ^ starting_length; - return Mix(w, z); + return Mix(a ^ salt[1] ^ starting_length, b ^ current_state); } } // namespace hash_internal diff --git a/absl/hash/internal/low_level_hash.h b/absl/hash/internal/low_level_hash.h index 439968aa..d460e351 100644 --- a/absl/hash/internal/low_level_hash.h +++ b/absl/hash/internal/low_level_hash.h @@ -43,6 +43,10 @@ namespace hash_internal { uint64_t LowLevelHash(const void* data, size_t len, uint64_t seed, const uint64_t salt[5]); +// Same as above except the length must be greater than 16. +uint64_t LowLevelHashLenGt16(const void* data, size_t len, uint64_t seed, + const uint64_t salt[5]); + } // namespace hash_internal ABSL_NAMESPACE_END } // namespace absl diff --git a/absl/hash/internal/low_level_hash_test.cc b/absl/hash/internal/low_level_hash_test.cc index 589a3d8f..ea781dd9 100644 --- a/absl/hash/internal/low_level_hash_test.cc +++ b/absl/hash/internal/low_level_hash_test.cc @@ -406,99 +406,99 @@ TEST(LowLevelHashTest, VerifyGolden) { #if defined(ABSL_IS_BIG_ENDIAN) constexpr uint64_t kGolden[kNumGoldenOutputs] = { - 0xe5a40d39ab796423, 0x1766974bf7527d81, 0x5c3bbbe230db17a8, - 0xa6630143a7e6aa6f, 0x17645cb7318b86b, 0x218b175f30ba61f8, - 0xa6564b468248c683, 0xef192f401b116e1c, 0xbe8dc0c54617639d, - 0xe7b01610fc22dbb8, 0x99d9f694404af913, 0xf4eecd37464b45c5, - 0x7d2c653d63596d9b, 0x3f15c8544ec5393a, 0x6b9dc0c1704f796c, - 0xf1ded7a7eae5ed5a, 0x2db2fd7c6dd4641b, 0x151ca2d3d4cd33ab, - 0xa5af5994ac2ccd64, 0x2b2a4ca3191d2fce, 0xf89e68c9364e7c05, - 0x71724c70b799c21, 0x70536fabfd157369, 0xdee92794c3c3082b, - 0xac033a6743d3b3eb, 0xed2956b506cd5151, 0xbd669644755264b6, - 0x6ab1ff5d5f549a63, 0xf6bd551a2e3e04e, 0x7b5a8cef6875ea73, - 0x22bccf4d4db0a91c, 0x4f2bc07754c7c7eb, 0xfb6b8342a86725db, - 0x13a1a0d4c5854da, 0x5f6e44655f7dedac, 0x54a9198dff2bdf85, - 0xdb17e6915d4e4042, 0xa69926cf5c3b89f, 0xf77f031bfd74c096, - 0x1d6f916fdd50ec3c, 0x334ac76013ade393, 0x99370f899111de15, - 0x352457a03ada6de, 0x341974d4f42d854d, 0xda89ab02872aeb5, - 0x6ec2b74e143b10d9, 0x6f284c0b5cd60522, 0xf9670de353438f88, - 0xde920913adf0a2b4, 0xb7a07d7c0c17a8ec, 0x879a69f558ba3a98, - 0x360cf6d802df20f9, 0x53530f8046673738, 0xbd8f5f2bcf35e483, - 0x3f171f047144b983, 0x644d04e820823465, 0x50e44773a20b2702, - 0xe584ed4c05c745dd, 0x9a825c85b95ab6c0, 0xbce2931deb74e775, - 0x10468e9e705c7cfe, 0x12e01de3104141e2, 0x5c11ae2ee3713abd, - 0x6ac5ffb0860319e6, 0xc1e6da1849d30fc9, 0xa0e4d247a458b447, - 0x4530d4615c32b89b, 0x116aa09107a76505, 0xf941339d00d9bb73, - 0x573a0fc1615afb33, 0xa975c81dc868b258, 0x3ab2c5250ab54bda, - 0x37f99f208a3e3b11, 0x4b49b0ff706689d, 0x30bafa0b8f0a87fe, - 0xea6787a65cc20cdd, 0x55861729f1fc3ab8, 0xea38e009c5be9b72, - 0xcb8522cba33c3c66, 0x352e77653fe306f3, 0xe0bb760793bac064, - 0xf66ec59322662956, 0x637aa320455d56f8, 0x46ee546be5824a89, - 0x9e6842421e83d8a4, 0xf98ac2bc96b9fb8c, 0xf2c1002fd9a70b99, - 0x4c2b62b1e39e9405, 0x3248555fa3ade9c4, 0xd4d04c37f6417c21, - 0xf40cd506b1bf5653, 0x6c45d6005c760d2f, 0x61d88a7e61ff0d7e, - 0x131591e8a53cc967, 0xdae85cb9bc29bab6, 0xe98835334905e626, - 0x7cce50a2b66b8754, 0x5b0b3d0c5ac498ae, 0xd35a218c974d1756, - 0xfce436ddc1d003c, 0xd183901de90bb741, 0x9378f8f34974a66, - 0x21f11ae0a0402368, 0xf2fbd7c94ef89cb6, 0xc329c69d0f0d080b, - 0xf2841cba16216a61, 0x47aba97b44916df1, 0x724d4e00a8019fcf, - 0x2df9005c2a728d63, 0xc788892a1a5d7515, 0x9e993a65f9df0480, - 0x76876721ff49f969, 0xbe7a796cfba15bf5, 0xa4c8bd54586f5488, - 0xb390a325275501ab, 0x893f11317427ccf1, 0x92f2bb57da5695b9, - 0x30985b90da88269f, 0x2c690e268e086de8, 0x1c02df6097997196, - 0x1f9778f8bbdf6455, 0x7d57378c7bf8416d, 0xba8582a5f8d84d38, - 0xe8ca43b85050be4e, 0x5048cf6bed8a5d9f, 0xfbc5ba80917d0ea4, - 0x8011026525bf1691, 0x26b8dc6aed9fb50d, 0x191f5bfee77c1fe3, - 0xdd497891465a2cc1, 0x6f1fe8c57a33072e, 0x2c9f4ec078c460c0, - 0x9a725bde8f6a1437, 0x6ce545fa3ef61e4d, + 0x4c34aacf38f6eee4, 0x88b1366815e50b88, 0x1a36bd0c6150fb9c, + 0xa783aba8a67366c7, 0x5e4a92123ae874f2, 0x0cc9ecf27067ee9a, + 0xbe77aa94940527f9, 0x7ea5c12f2669fe31, 0xa33eed8737d946b9, + 0x310aec5b1340bb36, 0x354e400861c5d8ff, 0x15be98166adcf42f, + 0xc51910b62a90ae51, 0x539d47fc7fdf6a1f, 0x3ebba9daa46eef93, + 0xd96bcd3a9113c17f, 0xc78eaf6256ded15a, 0x98902ed321c2f0d9, + 0x75a4ac96414b954a, 0x2cb90e00a39e307b, 0x46539574626c3637, + 0x186ec89a2be3ff45, 0x972a3bf7531519d2, 0xa14df0d25922364b, + 0xa351e19d22752109, 0x08bd311d8fed4f82, 0xea2b52ddc6af54f9, + 0x5f20549941338336, 0xd43b07422dc2782e, 0x377c68e2acda4835, + 0x1b31a0a663b1d7b3, 0x7388ba5d68058a1a, 0xe382794ea816f032, + 0xd4c3fe7889276ee0, 0x2833030545582ea9, 0x554d32a55e55df32, + 0x8d6d33d7e17b424d, 0xe51a193d03ae1e34, 0xabb6a80835bd66b3, + 0x0e4ba5293f9ce9b7, 0x1ebd8642cb762cdf, 0xcb54b555850888ee, + 0x1e4195e4717c701f, 0x6235a13937f6532a, 0xd460960741e845c0, + 0x2a72168a2d6af7b1, 0x6be38fbbfc5b17de, 0x4ee97cffa0d0fb39, + 0xfdf1119ad5e71a55, 0x0dff7f66b3070727, 0x812d791d6ed62744, + 0x60962919074b70b8, 0x956fa5c7d6872547, 0xee892daa58aae597, + 0xeeda546e998ee369, 0x454481f5eb9b1fa8, 0x1054394634c98b1b, + 0x55bb425415f591fb, 0x9601fa97416232c4, 0xd7a18506519daad7, + 0x90935cb5de039acf, 0xe64054c5146ed359, 0xe5b323fb1e866c09, + 0x10a472555f5ba1bc, 0xe3c0cd57d26e0972, 0x7ca3db7c121da3e8, + 0x7004a89c800bb466, 0x865f69c1a1ff7f39, 0xbe0edd48f0cf2b99, + 0x10e5e4ba3cc400f5, 0xafc2b91a220eef50, 0x6f04a259289b24f1, + 0x2179a8070e880ef0, 0xd6a9a3d023a740c2, 0x96e6d7954755d9b8, + 0xc8e4bddecce5af9f, 0x93941f0fbc724c92, 0xbef5fb15bf76a479, + 0x534dca8f5da86529, 0x70789790feec116b, 0x2a296e167eea1fe9, + 0x54cb1efd2a3ec7ea, 0x357b43897dfeb9f7, 0xd1eda89bc7ff89d3, + 0x434f2e10cbb83c98, 0xeec4cdac46ca69ce, 0xd46aafd52a303206, + 0x4bf05968ff50a5c9, 0x71c533747a6292df, 0xa40bd0d16a36118c, + 0x597b4ee310c395ab, 0xc5b3e3e386172583, 0x12ca0b32284e6c70, + 0xb48995fadcf35630, 0x0646368454cd217d, 0xa21c168e40d765b5, + 0x4260d3811337da30, 0xb72728a01cff78e4, 0x8586920947f4756f, + 0xc21e5f853cae7dc1, 0xf08c9533be9de285, 0x72df06653b4256d6, + 0xf7b7f937f8db1779, 0x976db27dd0418127, 0x9ce863b7bc3f9e00, + 0xebb679854fcf3a0a, 0x2ccebabbcf1afa99, 0x44201d6be451dac5, + 0xb4af71c0e9a537d1, 0xad8fe9bb33ed2681, 0xcb30128bb68df43b, + 0x154d8328903e8d07, 0x5844276dabeabdff, 0xd99017d7d36d930b, + 0xabb0b4774fb261ca, 0x0a43f075d62e67e0, 0x8df7b371355ada6b, + 0xf4c7a40d06513dcf, 0x257a3615955a0372, 0x987ac410bba74c06, + 0xa011a46f25a632a2, 0xa14384b963ddd995, 0xf51b6b8cf9d50ba7, + 0x3acdb91ee3abf18d, 0x34e799be08920e8c, 0x8766748a31304b36, + 0x0aa239d5d0092f2e, 0xadf473ed26628594, 0xc4094b798eb4b79b, + 0xe04ee5f33cd130f4, 0x85045d098c341d46, 0xf936cdf115a890ec, + 0x51d137b6d8d2eb4f, 0xd10738bb2fccc1ef, }; #else constexpr uint64_t kGolden[kNumGoldenOutputs] = { - 0xe5a40d39ab796423, 0x1766974bf7527d81, 0x5c3bbbe230db17a8, - 0xa6630143a7e6aa6f, 0x8787cb2d04b0c984, 0x33603654ff574ac2, - 0xa6564b468248c683, 0xef192f401b116e1c, 0xbe8dc0c54617639d, - 0x93d7f665b5521c8e, 0x646d70bb42445f28, 0x96a7b1e3cc9bd426, - 0x76020289ab0790c4, 0x39f842e4133b9b44, 0x2b8d7047be4bcaab, - 0x99628abef6716a97, 0x4432e02ba42b2740, 0x74d810efcad7918a, - 0x88c84e986002507f, 0x4f99acf193cf39b9, 0xd90e7a3655891e37, - 0x3bb378b1d4df8fcf, 0xf78e94045c052d47, 0x26da0b2130da6b40, - 0x30b4d426af8c6986, 0x5413b4aaf3baaeae, 0x756ab265370a1597, - 0xdaf5f4b7d09814fb, 0x8f874ae37742b75e, 0x8fecd03956121ce8, - 0x229c292ea7a08285, 0x0bb4bf0692d14bae, 0x207b24ca3bdac1db, - 0x64f6cd6745d3825b, 0xa2b2e1656b58df1e, 0x0d01d30d9ee7a148, - 0x1cb4cd00ab804e3b, 0x4697f2637fd90999, 0x8383a756b5688c07, - 0x695c29cb3696a975, 0xda2e5a5a5e971521, 0x7935d4befa056b2b, - 0x38dd541ca95420fe, 0xcc06c7a4963f967f, 0xbf0f6f66e232fb20, - 0xf7efb32d373fe71a, 0xe2e64634b1c12660, 0x285b8fd1638e306d, - 0x658e8a4e3b714d6c, 0xf391fb968e0eb398, 0x744a9ea0cc144bf2, - 0x12636f2be11012f1, 0x29c57de825948f80, 0x58c6f99ab0d1c021, - 0x13e7b5a7b82fe3bb, 0x10fbc87901e02b63, 0xa24c9184901b748b, - 0xcac4fd4c5080e581, 0xc38bdb7483ba68e1, 0xdb2a8069b2ceaffa, - 0xdf9fe91d0d1c7887, 0xe83f49e96e2e6a08, 0x0c69e61b62ca2b62, - 0xb4a4f3f85f8298fe, 0x167a1b39e1e95f41, 0xf8a2a5649855ee41, - 0x27992565b595c498, 0x3e08cca5b71f9346, 0xad406b10c770a6d2, - 0xd1713ce6e552bcf2, 0x753b287194c73ad3, 0x5ae41a95f600af1c, - 0x4a61163b86a8bb4c, 0x42eeaa79e760c7e4, 0x698df622ef465b0a, - 0x157583111e1a6026, 0xaa1388f078e793e0, 0xf10d68d0f3309360, - 0x2af056184457a3de, 0x6d0058e1590b2489, 0x638f287f68817f12, - 0xc46b71fecefd5467, 0x2c8e94679d964e0a, 0x8612b797ce22503a, - 0x59f929babfba7170, 0x9527556923fb49a0, 0x1039ab644f5e150b, - 0x7816c83f3aa05e6d, 0xf51d2f564518c619, 0x67d494cff03ac004, - 0x2802d636ced1cfbb, 0xf64e20bad771cb12, 0x0b9a6cf84a83e15e, - 0x8da6630319609301, 0x40946a86e2a996f3, 0xcab7f5997953fa76, - 0x39129ca0e04fc465, 0x5238221fd685e1b8, 0x175130c407dbcaab, - 0x02f20e7536c0b0df, 0x2742cb488a04ad56, 0xd6afb593879ff93b, - 0xf50ad64caac0ca7f, 0x2ade95c4261364ae, 0x5c4f3299faacd07a, - 0xfffe3bff0ae5e9bc, 0x1db785c0005166e4, 0xea000d962ad18418, - 0xe42aef38359362d9, 0xc8e95657348a3891, 0xc162eca864f238c6, - 0xbe1fb373e20579ad, 0x628a1d4f40aa6ffd, 0xa87bdb7456340f90, - 0x5960ef3ba982c801, 0x5026586df9a431ec, 0xfe4b8a20fdf0840b, - 0xdcb761867da7072f, 0xc10d4653667275b7, 0x727720deec13110b, - 0x710b009662858dc9, 0xfbf8f7a3ecac1eb7, 0xb6fc4fcd0722e3df, - 0x7cb86dcc55104aac, 0x19e71e9b45c3a51e, 0x51de38573c2bea48, - 0xa73ab6996d6df158, 0x55ef2b8c930817b2, 0xb2850bf5fae87157, - 0xecf3de1acd04651f, 0xcc0a40552559ff32, 0xc385c374f20315b1, - 0xb90208a4c7234183, 0x58aa1ca7a4c075d9, + 0x4c34aacf38f6eee4, 0x88b1366815e50b88, 0x1a36bd0c6150fb9c, + 0xa783aba8a67366c7, 0xbc89ebdc622314e4, 0x632bc3cfcc7544d8, + 0xbe77aa94940527f9, 0x7ea5c12f2669fe31, 0xa33eed8737d946b9, + 0x74d832ea11fd18ab, 0x49c0487486246cdc, 0x3fdd986c87ddb0a0, + 0xac3fa52a64d7c09a, 0xbff0e330196e7ed2, 0x8c8138d3ad7d3cce, + 0x968c7d4b48e93778, 0xa04c78d3a421f529, 0x8854bc9c3c3c0241, + 0xcccfcdf5a41113fe, 0xe6fc63dc543d984d, 0x00a39ff89e903c05, + 0xaf7e9da25f9a26f9, 0x6e269a13d01a43df, 0x846d2300ce2ecdf8, + 0xe7ea8c8f08478260, 0x9a2db0d62f6232f3, 0x6f66c761d168c59f, + 0x55f9feacaae82043, 0x518084043700f614, 0xb0c8cfc11bead99f, + 0xe4a68fdab6359d80, 0x97b17caa8f92236e, 0x96edf5e8363643dc, + 0x9b3fbcd8d5b254cd, 0x22a263621d9b3a8b, 0xde90bf6f81800a6d, + 0x1b51cae38c2e9513, 0x689215b3c414ef21, 0x064dc85afae8f557, + 0xa2f3a8b51f408378, 0x6907c197ec1f6a3b, 0xfe83a42ef5c1cf13, + 0x9b8b1d8f7a20cc13, 0x1f1681d52ca895d0, 0xd7b1670bf28e0f96, + 0xb32f20f82d8b038a, 0x6a61d030fb2f5253, 0x8eb2bb0bc29ebb39, + 0x144f36f7a9eef95c, 0xe77aa47d29808d8c, 0xf14d34c1fc568bad, + 0x9796dcd4383f3c73, 0xa2f685fc1be7225b, 0xf3791295b16068b1, + 0xb6b8f63424618948, 0x8ac4fd587045db19, 0x7e2aec2c34feb72e, + 0x72e135a6910ccbb1, 0x661ff16f3c904e6f, 0xdf92cf9d67ca092d, + 0x98a9953d79722eef, 0xe0649ed2181d1707, 0xcd8b8478636a297b, + 0x9516258709c8471b, 0xc703b675b51f4394, 0xdb740eae020139f3, + 0x57d1499ac4212ff2, 0x355cc03713d43825, 0x0e71ac9b8b1e101e, + 0x8029fa72258ff559, 0xa2159726b4c16a50, 0x04e61582fba43007, + 0xdab25af835be8cce, 0x13510b1b184705ee, 0xabdbc9e53666fdeb, + 0x94a788fcb8173cef, 0x750d5e031286e722, 0x02559e72f4f5b497, + 0x7d6e0e5996a646fa, 0x66e871b73b014132, 0x2ec170083f8b784f, + 0x34ac9540cfce3fd9, 0x75c5622c6aad1295, 0xf799a6bb2651acc1, + 0x8f6bcd3145bdc452, 0xddd9d326eb584a04, 0x5411af1e3532f8dc, + 0xeb34722f2ad0f509, 0x835bc952a82298cc, 0xeb3839ff60ea92ad, + 0x70bddf1bcdc8a4bc, 0x4bfb3ee86fcde525, 0xc7b3b93b81dfa386, + 0xe66db544d57997e8, 0xf68a1b83fd363187, 0xe9b99bec615b171b, + 0x093fba04d04ad28a, 0xba6117ed4231a303, 0x594bef25f9d4e206, + 0x0a8cba60578b8f67, 0x88f6c7ca10b06019, 0x32a74082aef17b08, + 0xe758222f971e22df, 0x4af14ff4a593e51e, 0xdba651e16cb09044, + 0x3f3ac837d181eaac, 0xa5589a3f89610c01, 0xd409a7c3a18d5643, + 0x8a89444f82962f26, 0x22eb62a13b9771b9, 0xd3a617615256ddd8, + 0x7089b990c4bba297, 0x7d752893783eac4f, 0x1f2fcbb79372c915, + 0x67a4446b17eb9839, 0x70d11df5cae46788, 0x52621e1780b47d0f, + 0xcf63b93a6e590ee6, 0xb6bc96b58ee064b8, 0x2587f8d635ca9c75, + 0xc6bddd62ec5e5d01, 0x957398ad3009cdb7, 0x05b6890b20bcd0d3, + 0xbe6e965ff837222e, 0x47383a87d2b04b1a, 0x7d42207e6d8d7950, + 0x7e981ed12a7f4aa3, 0xdebb05b30769441a, 0xaac5d86f4ff76c49, + 0x384f195ca3248331, 0xec4c4b855e909ca1, 0x6a7eeb5a657d73d5, + 0x9efbebe2fa9c2791, 0x19e7fa0546900c4d, }; #endif -- cgit v1.2.3 From bb83aceacb554e79e7cd2404856f0be30bd00303 Mon Sep 17 00:00:00 2001 From: Derek Mauro Date: Tue, 12 Mar 2024 08:33:40 -0700 Subject: Fix GCC7 C++17 build GCC did not support until GCC8. Fixes #1635 PiperOrigin-RevId: 615051227 Change-Id: If7cd5802ead40805b1ff1c3bdfc10ba6d2858ef0 --- absl/hash/hash_test.cc | 2 +- absl/hash/internal/hash.h | 12 ++++++++++-- 2 files changed, 11 insertions(+), 3 deletions(-) (limited to 'absl/hash') diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index 59fe8dea..7fecf534 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc @@ -48,7 +48,7 @@ #include "absl/types/optional.h" #include "absl/types/variant.h" -#if ABSL_INTERNAL_CPLUSPLUS_LANG >= 201703L +#ifdef ABSL_INTERNAL_STD_FILESYSTEM_PATH_HASH_AVAILABLE #include // NOLINT #endif diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index f4a94f91..b7d89b01 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -24,6 +24,15 @@ #include #endif +#include "absl/base/config.h" + +// For feature testing and determining which headers can be included. +#if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L +#include +#else +#include +#endif + #include #include #include @@ -47,7 +56,6 @@ #include #include -#include "absl/base/config.h" #include "absl/base/internal/unaligned_access.h" #include "absl/base/port.h" #include "absl/container/fixed_array.h" @@ -61,7 +69,7 @@ #include "absl/types/variant.h" #include "absl/utility/utility.h" -#if ABSL_INTERNAL_CPLUSPLUS_LANG >= 201703L && \ +#if defined(__cpp_lib_filesystem) && __cpp_lib_filesystem >= 201703L && \ !defined(_LIBCPP_HAS_NO_FILESYSTEM_LIBRARY) #include // NOLINT #endif -- cgit v1.2.3 From 16e21953352993faeb83d16d4bce99718e6e9d9c Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Fri, 15 Mar 2024 04:17:31 -0700 Subject: Remove redundant semicolons introduced by macros PiperOrigin-RevId: 616083064 Change-Id: I3d69303d32431227c197247682f8dcb70f9a239d --- absl/copts/GENERATED_AbseilCopts.cmake | 2 ++ absl/copts/GENERATED_copts.bzl | 2 ++ absl/copts/copts.py | 1 + absl/flags/flag_benchmark.cc | 2 +- absl/flags/parse_test.cc | 10 +++++----- absl/hash/hash_benchmark.cc | 14 +++++++------- absl/random/benchmarks.cc | 4 ++-- 7 files changed, 20 insertions(+), 15 deletions(-) (limited to 'absl/hash') diff --git a/absl/copts/GENERATED_AbseilCopts.cmake b/absl/copts/GENERATED_AbseilCopts.cmake index 0079a719..24b6175a 100644 --- a/absl/copts/GENERATED_AbseilCopts.cmake +++ b/absl/copts/GENERATED_AbseilCopts.cmake @@ -84,6 +84,7 @@ list(APPEND ABSL_GCC_TEST_FLAGS list(APPEND ABSL_LLVM_FLAGS "-Wall" "-Wextra" + "-Wc++98-compat-extra-semi" "-Wcast-qual" "-Wconversion" "-Wdead-code-aggressive" @@ -123,6 +124,7 @@ list(APPEND ABSL_LLVM_FLAGS list(APPEND ABSL_LLVM_TEST_FLAGS "-Wall" "-Wextra" + "-Wc++98-compat-extra-semi" "-Wcast-qual" "-Wconversion" "-Wdead-code-aggressive" diff --git a/absl/copts/GENERATED_copts.bzl b/absl/copts/GENERATED_copts.bzl index d9a9b375..9f59be4f 100644 --- a/absl/copts/GENERATED_copts.bzl +++ b/absl/copts/GENERATED_copts.bzl @@ -85,6 +85,7 @@ ABSL_GCC_TEST_FLAGS = [ ABSL_LLVM_FLAGS = [ "-Wall", "-Wextra", + "-Wc++98-compat-extra-semi", "-Wcast-qual", "-Wconversion", "-Wdead-code-aggressive", @@ -124,6 +125,7 @@ ABSL_LLVM_FLAGS = [ ABSL_LLVM_TEST_FLAGS = [ "-Wall", "-Wextra", + "-Wc++98-compat-extra-semi", "-Wcast-qual", "-Wconversion", "-Wdead-code-aggressive", diff --git a/absl/copts/copts.py b/absl/copts/copts.py index 1170d005..64e6f8a5 100644 --- a/absl/copts/copts.py +++ b/absl/copts/copts.py @@ -44,6 +44,7 @@ ABSL_GCC_TEST_ADDITIONAL_FLAGS = [ ABSL_LLVM_FLAGS = [ "-Wall", "-Wextra", + "-Wc++98-compat-extra-semi", "-Wcast-qual", "-Wconversion", "-Wdead-code-aggressive", diff --git a/absl/flags/flag_benchmark.cc b/absl/flags/flag_benchmark.cc index 758a6a55..88cc0c56 100644 --- a/absl/flags/flag_benchmark.cc +++ b/absl/flags/flag_benchmark.cc @@ -143,7 +143,7 @@ constexpr size_t kNumFlags = 0 REPLICATE(COUNT, _, _); #pragma clang section data = ".benchmark_flags" #endif #define DEFINE_FLAG(T, name, index) ABSL_FLAG(T, name##_##index, {}, ""); -#define FLAG_DEF(T) REPLICATE(DEFINE_FLAG, T, T##_flag); +#define FLAG_DEF(T) REPLICATE(DEFINE_FLAG, T, T##_flag) BENCHMARKED_TYPES(FLAG_DEF) #if defined(__clang__) && defined(__linux__) #pragma clang section data = "" diff --git a/absl/flags/parse_test.cc b/absl/flags/parse_test.cc index b3d4ce4e..99970692 100644 --- a/absl/flags/parse_test.cc +++ b/absl/flags/parse_test.cc @@ -44,31 +44,31 @@ #define FLAG_MULT(x) F3(x) #define TEST_FLAG_HEADER FLAG_HEADER_ -#define F(name) ABSL_FLAG(int, name, 0, ""); +#define F(name) ABSL_FLAG(int, name, 0, "") #define F1(name) \ F(name##1); \ F(name##2); \ F(name##3); \ F(name##4); \ - F(name##5); + F(name##5) /**/ #define F2(name) \ F1(name##1); \ F1(name##2); \ F1(name##3); \ F1(name##4); \ - F1(name##5); + F1(name##5) /**/ #define F3(name) \ F2(name##1); \ F2(name##2); \ F2(name##3); \ F2(name##4); \ - F2(name##5); + F2(name##5) /**/ -FLAG_MULT(TEST_FLAG_HEADER) +FLAG_MULT(TEST_FLAG_HEADER); namespace { diff --git a/absl/hash/hash_benchmark.cc b/absl/hash/hash_benchmark.cc index d18ea694..9b73f461 100644 --- a/absl/hash/hash_benchmark.cc +++ b/absl/hash/hash_benchmark.cc @@ -160,7 +160,7 @@ absl::flat_hash_set FlatHashSet(size_t count) { return hash{}(arg); \ } \ bool absl_hash_test_odr_use##hash##name = \ - (benchmark::DoNotOptimize(&Codegen##hash##name), false); + (benchmark::DoNotOptimize(&Codegen##hash##name), false) MAKE_BENCHMARK(AbslHash, Int32, int32_t{}); MAKE_BENCHMARK(AbslHash, Int64, int64_t{}); @@ -315,9 +315,9 @@ struct StringRand { BENCHMARK(BM_latency_##hash##_##name); \ } // namespace -MAKE_LATENCY_BENCHMARK(AbslHash, Int32, PodRand); -MAKE_LATENCY_BENCHMARK(AbslHash, Int64, PodRand); -MAKE_LATENCY_BENCHMARK(AbslHash, String9, StringRand<9>); -MAKE_LATENCY_BENCHMARK(AbslHash, String33, StringRand<33>); -MAKE_LATENCY_BENCHMARK(AbslHash, String65, StringRand<65>); -MAKE_LATENCY_BENCHMARK(AbslHash, String257, StringRand<257>); +MAKE_LATENCY_BENCHMARK(AbslHash, Int32, PodRand) +MAKE_LATENCY_BENCHMARK(AbslHash, Int64, PodRand) +MAKE_LATENCY_BENCHMARK(AbslHash, String9, StringRand<9>) +MAKE_LATENCY_BENCHMARK(AbslHash, String33, StringRand<33>) +MAKE_LATENCY_BENCHMARK(AbslHash, String65, StringRand<65>) +MAKE_LATENCY_BENCHMARK(AbslHash, String257, StringRand<257>) diff --git a/absl/random/benchmarks.cc b/absl/random/benchmarks.cc index 0900e818..26bc95e8 100644 --- a/absl/random/benchmarks.cc +++ b/absl/random/benchmarks.cc @@ -291,7 +291,7 @@ void BM_Thread(benchmark::State& state) { BENCHMARK_TEMPLATE(BM_Shuffle, Engine, 100)->ThreadPerCpu(); \ BENCHMARK_TEMPLATE(BM_Shuffle, Engine, 1000)->ThreadPerCpu(); \ BENCHMARK_TEMPLATE(BM_ShuffleReuse, Engine, 100)->ThreadPerCpu(); \ - BENCHMARK_TEMPLATE(BM_ShuffleReuse, Engine, 1000)->ThreadPerCpu(); + BENCHMARK_TEMPLATE(BM_ShuffleReuse, Engine, 1000)->ThreadPerCpu() #define BM_EXTENDED(Engine) \ /* -------------- Extended Uniform -----------------------*/ \ @@ -355,7 +355,7 @@ void BM_Thread(benchmark::State& state) { BENCHMARK_TEMPLATE(BM_Beta, Engine, absl::beta_distribution, 410, \ 580); \ BENCHMARK_TEMPLATE(BM_Gamma, Engine, std::gamma_distribution, 199); \ - BENCHMARK_TEMPLATE(BM_Gamma, Engine, std::gamma_distribution, 199); + BENCHMARK_TEMPLATE(BM_Gamma, Engine, std::gamma_distribution, 199) // ABSL Recommended interfaces. BM_BASIC(absl::InsecureBitGen); // === pcg64_2018_engine -- cgit v1.2.3 From c0f104bf3aca7001d8a549f5efe15f89ee99d050 Mon Sep 17 00:00:00 2001 From: Connal de Souza Date: Thu, 28 Mar 2024 10:21:43 -0700 Subject: Optimize LowLevelHash by breaking dependency between final loads and previous len/ptr updates. No functional change. PiperOrigin-RevId: 619979819 Change-Id: I71a4ae14272bcdf1da2e201ed286f95213ecb5e2 --- absl/hash/internal/low_level_hash.cc | 8 +++----- 1 file changed, 3 insertions(+), 5 deletions(-) (limited to 'absl/hash') diff --git a/absl/hash/internal/low_level_hash.cc b/absl/hash/internal/low_level_hash.cc index 43de6729..6dc71cf7 100644 --- a/absl/hash/internal/low_level_hash.cc +++ b/absl/hash/internal/low_level_hash.cc @@ -37,6 +37,7 @@ uint64_t LowLevelHashLenGt16(const void* data, size_t len, uint64_t seed, PrefetchToLocalCache(data); const uint8_t* ptr = static_cast(data); uint64_t starting_length = static_cast(len); + const uint8_t* last_16_ptr = ptr + starting_length - 16; uint64_t current_state = seed ^ salt[0]; if (len > 64) { @@ -97,15 +98,12 @@ uint64_t LowLevelHashLenGt16(const void* data, size_t len, uint64_t seed, uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); current_state = Mix(a ^ salt[1], b ^ current_state); - - ptr += 16; - len -= 16; } // We now have a data `ptr` with at least 1 and at most 16 bytes. But we can // safely read from `ptr + len - 16`. - uint64_t a = absl::base_internal::UnalignedLoad64(ptr + len - 16); - uint64_t b = absl::base_internal::UnalignedLoad64(ptr + len - 8); + uint64_t a = absl::base_internal::UnalignedLoad64(last_16_ptr); + uint64_t b = absl::base_internal::UnalignedLoad64(last_16_ptr + 8); return Mix(a ^ salt[1] ^ starting_length, b ^ current_state); } -- cgit v1.2.3 From 65a55c2ba891f6d2492477707f4a2e327a0b40dc Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 29 May 2024 11:12:50 -0700 Subject: Do not make std::filesystem::path hash available for macOS <10.15 C++17 is only available on macOS 10.15 and newer, so do not enable this feature on older versions. PiperOrigin-RevId: 638348906 Change-Id: I5e12db47513f7f8aeb9e55a3e253c866ec046d47 --- absl/hash/internal/hash.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) (limited to 'absl/hash') diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index b7d89b01..03bf1839 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -599,7 +599,9 @@ H AbslHashValue(H hash_state, std::basic_string_view str) { #if defined(__cpp_lib_filesystem) && __cpp_lib_filesystem >= 201703L && \ !defined(_LIBCPP_HAS_NO_FILESYSTEM_LIBRARY) && \ (!defined(__ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__) || \ - __ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__ >= 130000) + __ENVIRONMENT_IPHONE_OS_VERSION_MIN_REQUIRED__ >= 130000) && \ + (!defined(__ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__) || \ + __ENVIRONMENT_MAC_OS_X_VERSION_MIN_REQUIRED__ >= 101500) #define ABSL_INTERNAL_STD_FILESYSTEM_PATH_HASH_AVAILABLE 1 -- cgit v1.2.3