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/internal') 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 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/internal') 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/internal') 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 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/internal') 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/internal') 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