From 078b89b3c046d230ef3ad39494e5852184eb528b Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 23 Oct 2019 19:35:39 -0700 Subject: Export of internal Abseil changes -- e54b9c7bbb0c58475676c268e2e19c69f4bce48a by Jorg Brown : Tweak ABSL_PREDICT_TRUE slightly, for better code on some platforms and/or optimization levels. "false || (x)" is more verbose than "!!(x)", but ultimately more efficient. For example, given this code: void InitIfNecessary() { if (ABSL_PREDICT_TRUE(NeedsInit())) { SlowInitIfNecessary(); } } Clang with default optimization level will produce: Before this CL After this CL InitIfNecessary: InitIfNecessary: push rbp push rbp mov rbp, rsp mov rbp, rsp call NeedsInit call NeedsInit xor al, -1 xor al, -1 test al, 1 test al, 1 jne .LBB2_1 jne .LBB3_1 jmp .LBB2_2 jmp .LBB3_2 .LBB2_1: .LBB3_1: call SlowInitIfNecessary call SlowInitIfNecessary .LBB2_2: .LBB3_2: pop rbp pop rbp ret ret PiperOrigin-RevId: 276401386 -- 0a3c4dfd8342bf2b1b11a87f1c662c883f73cab7 by Abseil Team : Fix comment nit: sem_open => sem_init. The code calls sem_init, not sem_open, to initialize an unnamed semaphore. (sem_open creates or opens a named semaphore.) PiperOrigin-RevId: 276344072 -- b36a664e9459057509a90e83d3482e1d3a4c44c7 by Abseil Team : Fix typo in flat_hash_map.h: exchaged -> exchanged PiperOrigin-RevId: 276295792 -- 7bbd8d18276eb110c8335743e35fceb662ddf3d6 by Samuel Benzaquen : Add assertions to verify use of iterators. PiperOrigin-RevId: 276283300 -- 677398a8ffcb1f59182cffe57a4fe7ff147a0404 by Laramie Leavitt : Migrate distribution_impl.h/cc to generate_real.h/cc. Combine the methods RandU64To into a single method: GenerateRealFromBits(). Remove rejection sampling from absl::uniform_real_distribution. PiperOrigin-RevId: 276158675 -- c60c9d11d24b0c546329d998e78e15a84b3153f5 by Abseil Team : Internal change PiperOrigin-RevId: 276126962 -- 4c840cab6a8d86efa29b397cafaf7520eece68cc by Andy Soffer : Update CMakeLists.txt to address https://github.com/abseil/abseil-cpp/issues/365. This does not cover every platform, but it does at least address the first-order issue of assuming gcc implies x86. PiperOrigin-RevId: 276116253 -- 98da366e6b5d51afe5d7ac6722126aca23d85ee6 by Abseil Team : Internal change PiperOrigin-RevId: 276097452 GitOrigin-RevId: e54b9c7bbb0c58475676c268e2e19c69f4bce48a Change-Id: I02d84454bb71ab21ad3d39650acf6cc6e36f58d7 --- absl/container/BUILD.bazel | 1 + absl/container/CMakeLists.txt | 1 + absl/container/flat_hash_map.h | 2 +- absl/container/internal/hashtablez_sampler.cc | 83 ++++----------------------- absl/container/internal/raw_hash_set.h | 20 ++++++- absl/container/internal/raw_hash_set_test.cc | 2 +- 6 files changed, 33 insertions(+), 76 deletions(-) (limited to 'absl/container') diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 0894bb2..e60979b 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel @@ -493,6 +493,7 @@ cc_library( ":have_sse", "//absl/base", "//absl/base:core_headers", + "//absl/base:exponential_biased", "//absl/debugging:stacktrace", "//absl/memory", "//absl/synchronization", diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 933c7a8..aa33659 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt @@ -538,6 +538,7 @@ absl_cc_library( ${ABSL_DEFAULT_COPTS} DEPS absl::base + absl::exponential_biased absl::have_sse absl::synchronization ) diff --git a/absl/container/flat_hash_map.h b/absl/container/flat_hash_map.h index 5c16ac8..283f243 100644 --- a/absl/container/flat_hash_map.h +++ b/absl/container/flat_hash_map.h @@ -401,7 +401,7 @@ class flat_hash_map : public absl::container_internal::raw_hash_map< // for the past-the-end iterator, which is invalidated. // // `swap()` requires that the flat hash map's hashing and key equivalence - // functions be Swappable, and are exchaged using unqualified calls to + // functions be Swappable, and are exchanged using unqualified calls to // non-member `swap()`. If the map's allocator has // `std::allocator_traits::propagate_on_container_swap::value` // set to `true`, the allocators are also exchanged using an unqualified call diff --git a/absl/container/internal/hashtablez_sampler.cc b/absl/container/internal/hashtablez_sampler.cc index 054e898..0a7ef61 100644 --- a/absl/container/internal/hashtablez_sampler.cc +++ b/absl/container/internal/hashtablez_sampler.cc @@ -21,6 +21,7 @@ #include #include "absl/base/attributes.h" +#include "absl/base/internal/exponential_biased.h" #include "absl/container/internal/have_sse.h" #include "absl/debugging/stacktrace.h" #include "absl/memory/memory.h" @@ -37,77 +38,13 @@ ABSL_CONST_INIT std::atomic g_hashtablez_enabled{ ABSL_CONST_INIT std::atomic g_hashtablez_sample_parameter{1 << 10}; ABSL_CONST_INIT std::atomic g_hashtablez_max_samples{1 << 20}; -// Returns the next pseudo-random value. -// pRNG is: aX+b mod c with a = 0x5DEECE66D, b = 0xB, c = 1<<48 -// This is the lrand64 generator. -uint64_t NextRandom(uint64_t rnd) { - const uint64_t prng_mult = uint64_t{0x5DEECE66D}; - const uint64_t prng_add = 0xB; - const uint64_t prng_mod_power = 48; - const uint64_t prng_mod_mask = ~(~uint64_t{0} << prng_mod_power); - return (prng_mult * rnd + prng_add) & prng_mod_mask; -} - -// Generates a geometric variable with the specified mean. -// This is done by generating a random number between 0 and 1 and applying -// the inverse cumulative distribution function for an exponential. -// Specifically: Let m be the inverse of the sample period, then -// the probability distribution function is m*exp(-mx) so the CDF is -// p = 1 - exp(-mx), so -// q = 1 - p = exp(-mx) -// log_e(q) = -mx -// -log_e(q)/m = x -// log_2(q) * (-log_e(2) * 1/m) = x -// In the code, q is actually in the range 1 to 2**26, hence the -26 below -// -int64_t GetGeometricVariable(int64_t mean) { #if ABSL_HAVE_THREAD_LOCAL - thread_local -#else // ABSL_HAVE_THREAD_LOCAL - // SampleSlow and hence GetGeometricVariable is guarded by a single mutex when - // there are not thread locals. Thus, a single global rng is acceptable for - // that case. - static -#endif // ABSL_HAVE_THREAD_LOCAL - uint64_t rng = []() { - // We don't get well distributed numbers from this so we call - // NextRandom() a bunch to mush the bits around. We use a global_rand - // to handle the case where the same thread (by memory address) gets - // created and destroyed repeatedly. - ABSL_CONST_INIT static std::atomic global_rand(0); - uint64_t r = reinterpret_cast(&rng) + - global_rand.fetch_add(1, std::memory_order_relaxed); - for (int i = 0; i < 20; ++i) { - r = NextRandom(r); - } - return r; - }(); - - rng = NextRandom(rng); - - // Take the top 26 bits as the random number - // (This plus the 1<<58 sampling bound give a max possible step of - // 5194297183973780480 bytes.) - const uint64_t prng_mod_power = 48; // Number of bits in prng - // The uint32_t cast is to prevent a (hard-to-reproduce) NAN - // under piii debug for some binaries. - double q = static_cast(rng >> (prng_mod_power - 26)) + 1.0; - // Put the computed p-value through the CDF of a geometric. - double interval = (log2(q) - 26) * (-std::log(2.0) * mean); - - // Very large values of interval overflow int64_t. If we happen to - // hit such improbable condition, we simply cheat and clamp interval - // to largest supported value. - if (interval > static_cast(std::numeric_limits::max() / 2)) { - return std::numeric_limits::max() / 2; - } - - // Small values of interval are equivalent to just sampling next time. - if (interval < 1) { - return 1; - } - return static_cast(interval); -} +thread_local absl::base_internal::ExponentialBiased + g_exponential_biased_generator; +#else +ABSL_CONST_INIT static absl::base_internal::ExponentialBiased + g_exponential_biased_generator; +#endif } // namespace @@ -253,8 +190,12 @@ HashtablezInfo* SampleSlow(int64_t* next_sample) { } bool first = *next_sample < 0; - *next_sample = GetGeometricVariable( + *next_sample = g_exponential_biased_generator.Get( g_hashtablez_sample_parameter.load(std::memory_order_relaxed)); + // Small values of interval are equivalent to just sampling next time. + if (*next_sample < 1) { + *next_sample = 1; + } // g_hashtablez_enabled can be dynamically flipped, we need to set a threshold // low enough that we will start sampling in a reasonable time, so we just use diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 42b3c46..9992ba4 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -614,13 +614,17 @@ class raw_hash_set { iterator() {} // PRECONDITION: not an end() iterator. - reference operator*() const { return PolicyTraits::element(slot_); } + reference operator*() const { + /* To be enabled: assert_is_full(); */ + return PolicyTraits::element(slot_); + } // PRECONDITION: not an end() iterator. pointer operator->() const { return &operator*(); } // PRECONDITION: not an end() iterator. iterator& operator++() { + /* To be enabled: assert_is_full(); */ ++ctrl_; ++slot_; skip_empty_or_deleted(); @@ -634,6 +638,8 @@ class raw_hash_set { } friend bool operator==(const iterator& a, const iterator& b) { + /* To be enabled: a.assert_is_valid(); */ + /* To be enabled: b.assert_is_valid(); */ return a.ctrl_ == b.ctrl_; } friend bool operator!=(const iterator& a, const iterator& b) { @@ -644,6 +650,11 @@ class raw_hash_set { iterator(ctrl_t* ctrl) : ctrl_(ctrl) {} // for end() iterator(ctrl_t* ctrl, slot_type* slot) : ctrl_(ctrl), slot_(slot) {} + void assert_is_full() const { assert(IsFull(*ctrl_)); } + void assert_is_valid() const { + assert(!ctrl_ || IsFull(*ctrl_) || *ctrl_ == kSentinel); + } + void skip_empty_or_deleted() { while (IsEmptyOrDeleted(*ctrl_)) { // ctrl is not necessarily aligned to Group::kWidth. It is also likely @@ -1155,7 +1166,7 @@ class raw_hash_set { // This overload is necessary because otherwise erase(const K&) would be // a better match if non-const iterator is passed as an argument. void erase(iterator it) { - assert(it != end()); + it.assert_is_full(); PolicyTraits::destroy(&alloc_ref(), it.slot_); erase_meta_only(it); } @@ -1172,12 +1183,14 @@ class raw_hash_set { template void merge(raw_hash_set& src) { // NOLINT assert(this != &src); - for (auto it = src.begin(), e = src.end(); it != e; ++it) { + for (auto it = src.begin(), e = src.end(); it != e;) { + auto next = std::next(it); if (PolicyTraits::apply(InsertSlot{*this, std::move(*it.slot_)}, PolicyTraits::element(it.slot_)) .second) { src.erase_meta_only(it); } + it = next; } } @@ -1187,6 +1200,7 @@ class raw_hash_set { } node_type extract(const_iterator position) { + position.inner_.assert_is_full(); auto node = CommonAccess::Transfer(alloc_ref(), position.inner_.slot_); erase_meta_only(position); diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index ed4ca8c..33cfa72 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -1837,7 +1837,7 @@ TEST(TableDeathTest, EraseOfEndAsserts) { IntTable t; // Extra simple "regexp" as regexp support is highly varied across platforms. - constexpr char kDeathMsg[] = "it != end"; + constexpr char kDeathMsg[] = "IsFull"; EXPECT_DEATH_IF_SUPPORTED(t.erase(t.end()), kDeathMsg); } -- cgit v1.2.3