From 93d155bc4414f6c121bb1f19dba9fdb27c8943bc Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Tue, 19 Feb 2019 14:29:09 -0800 Subject: Export of internal Abseil changes. -- 3d20ce6cd6541579abecaba169d4b8716d511272 by Jon Cohen : Only use LSAN for clang version >= 3.5. This should fix https://github.com/abseil/abseil-cpp/issues/244 PiperOrigin-RevId: 234675129 -- e15bd4ec7a81aa95cc3d09fa1e0e81d58ae478fb by Conrad Parker : Fix errors in apply() sample code The following changes are made: * Make the example method public. * Give the two user functions different names to avoid confusion about whether apply() can select the correct overload of a function based on its tuple argument (it can't). * Pass tuple2 to the second example apply() invocation, instead of passing its contents individually. * Fix a s/tuple/tuple3/ typo in the third example apply() invocation. PiperOrigin-RevId: 234223407 -- de0ed71e21bc76ddf9fe715fdbaef74cd0df95c7 by Abseil Team : First test if a macro is defined to avoid -Wundef. ABSL clients may need to compile their code with the -Wundef warning flag. It will be helpful if ABSL header files can be compiled without the -Wundef warning. How to avoid the -Wundef warning: If a macro may be undefined, we need to first test whether the macro is defined before testing its value. We can't rely on the C preprocessor rule that an undefined macro has the value 0L. PiperOrigin-RevId: 234201123 -- fa484ad7dae0cac21140a96662809ecb0ec8eb5d by Abseil Team : Internal change. PiperOrigin-RevId: 234185697 -- d69b1baef681e27954b065375ecf9c2320463b2b by Samuel Benzaquen : Mix pointers more thoroughly. Some pointer alignments interact badly with the mixing constant. By mixing twice we reduce this problem. PiperOrigin-RevId: 234178401 -- 1041d0e474610f3a8fea0db90958857327d6da1c by Samuel Benzaquen : Record rehashes in the hashtablez struct. Only recording the probe length on insertion causes a huge overestimation of the total probe length at any given time. With natural growth, elements are inserted when the load factor is between (max load/2, max load). However, after a rehash the majority of elements are actually inserted when the load factor is less than max/2 and have a much lower average probe length. Also reset some values when the table is cleared. PiperOrigin-RevId: 234013580 -- 299205caf3c89c47339f7409bc831746602cea84 by Mark Barolak : Fix a sample code snippet that assumes `absl::string_view::const_iterator` is `const char*`. This is generally true, however in C++17 builds, absl::string_view is an alias for std::string_view and on MSVC, the std::string_view::const_iterator is an object instead of just a pointer. PiperOrigin-RevId: 233844595 -- af6c6370cf51a1e6c1469c79dfb2a486a4009136 by Abseil Team : Internal change. PiperOrigin-RevId: 233773470 -- 6e59e4b8e2bb6101b448f0f32b0bea81fe399ccf by Abseil Team : fix typo in {Starts|Ends}WithIgnoreCase comment in match.h PiperOrigin-RevId: 233662951 GitOrigin-RevId: 3d20ce6cd6541579abecaba169d4b8716d511272 Change-Id: Ib9a29b1c38c6aedf5d9f3f7f00596e8d30e864dd --- absl/hash/hash_test.cc | 30 ++++++++++++++++++++++++++++++ absl/hash/internal/hash.h | 7 ++++++- 2 files changed, 36 insertions(+), 1 deletion(-) (limited to 'absl/hash') diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index a5af93a..2c9e46b 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc @@ -135,6 +135,36 @@ TEST(HashValueTest, Pointer) { std::make_tuple(&i, ptr, nullptr, ptr + 1, n))); } +TEST(HashValueTest, PointerAlignment) { + // We want to make sure that pointer alignment will not cause bits to be + // stuck. + + constexpr size_t kTotalSize = 1 << 20; + std::unique_ptr data(new char[kTotalSize]); + constexpr size_t kLog2NumValues = 5; + constexpr size_t kNumValues = 1 << kLog2NumValues; + + for (size_t align = 1; align < kTotalSize / kNumValues; + align < 8 ? align += 1 : align < 1024 ? align += 8 : align += 32) { + SCOPED_TRACE(align); + ASSERT_LE(align * kNumValues, kTotalSize); + + size_t bits_or = 0; + size_t bits_and = ~size_t{}; + + for (size_t i = 0; i < kNumValues; ++i) { + size_t hash = absl::Hash()(data.get() + i * align); + bits_or |= hash; + bits_and &= hash; + } + + // Limit the scope to the bits we would be using for Swisstable. + constexpr size_t kMask = (1 << (kLog2NumValues + 7)) - 1; + size_t stuck_bits = (~bits_or | bits_and) & kMask; + EXPECT_EQ(stuck_bits, 0) << "0x" << std::hex << stuck_bits; + } +} + // TODO(EricWF): MSVC 15 has a bug that causes it to incorrectly evaluate the // SFINAE in internal/hash.h, causing this test to fail. #if !defined(_MSC_VER) diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index ba6d746..bd07677 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h @@ -264,7 +264,12 @@ H AbslHashValue(H hash_state, long double value) { // AbslHashValue() for hashing pointers template H AbslHashValue(H hash_state, T* ptr) { - return hash_internal::hash_bytes(std::move(hash_state), ptr); + auto v = reinterpret_cast(ptr); + // Due to alignment, pointers tend to have low bits as zero, and the next few + // bits follow a pattern since they are also multiples of some base value. + // Mixing the pointer twice helps prevent stuck low bits for certain alignment + // values. + return H::combine(std::move(hash_state), v, v); } // AbslHashValue() for hashing nullptr_t -- cgit v1.2.3