diff options
author | 2021-02-10 08:52:54 -0800 | |
---|---|---|
committer | 2021-02-10 17:01:18 -0500 | |
commit | 1d1ad2292bb5c7be26074e516b4cc70d9cc469f9 (patch) | |
tree | 698d051a6c78c3b64e71b245d62a7ca80ee5b66a /absl/container/internal/raw_hash_set_test.cc | |
parent | 2aa00ab2f22cf4e0e85e622c3254d483b2ddfb30 (diff) |
Export of internal Abseil changes
--
f9476c95cf7625d7b0fc4661f253b0aac4341044 by Abseil Team <absl-team@google.com>:
Add a test to verify that the new checksum field in Hashtablez is calculated
PiperOrigin-RevId: 356744293
--
ff8a3612463000e8c3d451e50367a3c65cb6cf21 by Abseil Team <absl-team@google.com>:
Remove the implied support comment for port.h, attributes.h, and integral_types.h's C compatibility from the header documentations.
Abseil-cpp is a C++ library; this brings port.h, attributes.h, and integral_types.h, into our stance for the rest of Abseil (aka, no assurance of C compatibility)
There is no guarantee that future changes to port.h, attributes.h, and integral_types.h, and their dependencies, will remain compatible with C, even for macros and definitions that currently are.
PiperOrigin-RevId: 356727505
--
be62292016381deee628dbb3f36cb6009bcc0282 by Abseil Team <absl-team@google.com>:
internal change
PiperOrigin-RevId: 356608125
--
13b35f17171df3d6853ea7088797b3be611505fc by Evan Brown <ezb@google.com>:
Clarify the comments for CapacityToGrowth/GrowthToLowerboundCapacity methods to specify the intent that capacity should equal growth when `capacity+1 < kWidth`.
Also add testing for this behavior.
PiperOrigin-RevId: 356579041
GitOrigin-RevId: f9476c95cf7625d7b0fc4661f253b0aac4341044
Change-Id: Iadd094d109b4869998f2427319ef66d1cf1e8eff
Diffstat (limited to 'absl/container/internal/raw_hash_set_test.cc')
-rw-r--r-- | absl/container/internal/raw_hash_set_test.cc | 34 |
1 files changed, 29 insertions, 5 deletions
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 0fba46ff..81c4b47c 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -14,6 +14,7 @@ #include "absl/container/internal/raw_hash_set.h" +#include <atomic> #include <cmath> #include <cstdint> #include <deque> @@ -22,6 +23,8 @@ #include <numeric> #include <random> #include <string> +#include <unordered_map> +#include <unordered_set> #include "gmock/gmock.h" #include "gtest/gtest.h" @@ -48,11 +51,10 @@ struct RawHashSetTestOnlyAccess { namespace { -using ::testing::DoubleNear; using ::testing::ElementsAre; +using ::testing::Eq; using ::testing::Ge; using ::testing::Lt; -using ::testing::Optional; using ::testing::Pair; using ::testing::UnorderedElementsAre; @@ -75,8 +77,14 @@ TEST(Util, GrowthAndCapacity) { for (size_t growth = 0; growth < 10000; ++growth) { SCOPED_TRACE(growth); size_t capacity = NormalizeCapacity(GrowthToLowerboundCapacity(growth)); - // The capacity is large enough for `growth` + // The capacity is large enough for `growth`. EXPECT_THAT(CapacityToGrowth(capacity), Ge(growth)); + // For (capacity+1) < kWidth, growth should equal capacity. + if (capacity + 1 < Group::kWidth) { + EXPECT_THAT(CapacityToGrowth(capacity), Eq(capacity)); + } else { + EXPECT_THAT(CapacityToGrowth(capacity), Lt(capacity)); + } if (growth != 0 && capacity > 1) { // There is no smaller capacity that works. EXPECT_THAT(CapacityToGrowth(capacity / 2), Lt(growth)); @@ -1875,18 +1883,34 @@ TEST(RawHashSamplerTest, Sample) { auto& sampler = HashtablezSampler::Global(); size_t start_size = 0; - start_size += sampler.Iterate([&](const HashtablezInfo&) { ++start_size; }); + std::unordered_set<const HashtablezInfo*> preexisting_info; + start_size += sampler.Iterate([&](const HashtablezInfo& info) { + preexisting_info.insert(&info); + ++start_size; + }); std::vector<IntTable> tables; for (int i = 0; i < 1000000; ++i) { tables.emplace_back(); tables.back().insert(1); + tables.back().insert(i % 5); } size_t end_size = 0; - end_size += sampler.Iterate([&](const HashtablezInfo&) { ++end_size; }); + std::unordered_map<size_t, int> observed_checksums; + end_size += sampler.Iterate([&](const HashtablezInfo& info) { + if (preexisting_info.count(&info) == 0) { + observed_checksums[info.hashes_bitwise_xor.load( + std::memory_order_relaxed)]++; + } + ++end_size; + }); EXPECT_NEAR((end_size - start_size) / static_cast<double>(tables.size()), 0.01, 0.005); + EXPECT_EQ(observed_checksums.size(), 5); + for (const auto& [_, count] : observed_checksums) { + EXPECT_NEAR((100 * count) / static_cast<double>(tables.size()), 0.2, 0.05); + } } #endif // ABSL_INTERNAL_HASHTABLEZ_SAMPLE |