diff options
Diffstat (limited to 'absl/container/internal/raw_hash_set_test.cc')
-rw-r--r-- | absl/container/internal/raw_hash_set_test.cc | 138 |
1 files changed, 0 insertions, 138 deletions
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index 9d92e15c5206..76aba318da8d 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -14,7 +14,6 @@ #include "absl/container/internal/raw_hash_set.h" -#include <array> #include <cmath> #include <cstdint> #include <deque> @@ -1782,143 +1781,6 @@ TEST(Table, IterationOrderChangesForSmallTables) { FAIL() << "Iteration order remained the same across many attempts."; } -// Fill the table to 3 different load factors (min, median, max) and evaluate -// the percentage of perfect hits using the debug API. -template <class Table, class AddFn> -std::vector<double> CollectPerfectRatios(Table, AddFn add) { - std::vector<double> results(3); - - constexpr size_t kNumTrials = 10; - std::vector<Table> tables(kNumTrials); - - for (Table& t : tables) { - using Key = typename Table::key_type; - - // First, fill enough to have a good distribution. - constexpr size_t kMinSize = 10000; - std::vector<Key> keys; - while (t.size() < kMinSize) keys.push_back(add(t)); - // Then, insert until we reach min load factor. - double lf = t.load_factor(); - while (lf <= t.load_factor()) keys.push_back(add(t)); - - // We are now at min load factor. Take a snapshot. - size_t perfect = 0; - auto update_perfect = [&](Key k) { - perfect += GetHashtableDebugNumProbes(t, k) == 0; - }; - for (const auto& k : keys) update_perfect(k); - - std::vector<double> perfect_ratios; - // Keep going until we hit max load factor. - while (t.load_factor() < .6) { - perfect_ratios.push_back(1.0 * perfect / t.size()); - update_perfect(add(t)); - } - while (t.load_factor() > .5) { - perfect_ratios.push_back(1.0 * perfect / t.size()); - update_perfect(add(t)); - } - - results[0] += perfect_ratios.front(); - results[1] += perfect_ratios[perfect_ratios.size() / 2]; - results[2] += perfect_ratios.back(); - } - - results[0] /= kNumTrials; - results[1] /= kNumTrials; - results[2] /= kNumTrials; - - return results; -} - -std::vector<std::pair<double, double>> StringTablePefectRatios() { - constexpr bool kRandomizesInserts = -#if NDEBUG - false; -#else // NDEBUG - true; -#endif // NDEBUG - - // The effective load factor is larger in non-opt mode because we insert - // elements out of order. - switch (container_internal::Group::kWidth) { - case 8: - if (kRandomizesInserts) { - return {{0.986, 0.02}, {0.95, 0.02}, {0.89, 0.02}}; - } else { - return {{0.995, 0.01}, {0.97, 0.01}, {0.89, 0.02}}; - } - case 16: - if (kRandomizesInserts) { - return {{0.973, 0.01}, {0.965, 0.01}, {0.92, 0.02}}; - } else { - return {{0.995, 0.005}, {0.99, 0.005}, {0.94, 0.01}}; - } - } - ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width"); - return {}; -} - -// This is almost a change detector, but it allows us to know how we are -// affecting the probe distribution. -TEST(Table, EffectiveLoadFactorStrings) { - std::vector<double> perfect_ratios = - CollectPerfectRatios(StringTable(), [](StringTable& t) { - return t.emplace(std::to_string(t.size()), "").first->first; - }); - - auto ratios = StringTablePefectRatios(); - if (ratios.empty()) return; - EXPECT_THAT(perfect_ratios, - ElementsAre(DoubleNear(ratios[0].first, ratios[0].second), - DoubleNear(ratios[1].first, ratios[1].second), - DoubleNear(ratios[2].first, ratios[2].second))); -} - -std::vector<std::pair<double, double>> IntTablePefectRatios() { - constexpr bool kRandomizesInserts = -#ifdef NDEBUG - false; -#else // NDEBUG - true; -#endif // NDEBUG - - // The effective load factor is larger in non-opt mode because we insert - // elements out of order. - switch (container_internal::Group::kWidth) { - case 8: - if (kRandomizesInserts) { - return {{0.99, 0.02}, {0.985, 0.02}, {0.95, 0.05}}; - } else { - return {{0.99, 0.01}, {0.99, 0.01}, {0.95, 0.02}}; - } - case 16: - if (kRandomizesInserts) { - return {{0.98, 0.02}, {0.978, 0.02}, {0.96, 0.02}}; - } else { - return {{0.998, 0.003}, {0.995, 0.01}, {0.975, 0.02}}; - } - } - ABSL_RAW_LOG(FATAL, "%s", "Unknown Group width"); - return {}; -} - -// This is almost a change detector, but it allows us to know how we are -// affecting the probe distribution. -TEST(Table, EffectiveLoadFactorInts) { - std::vector<double> perfect_ratios = CollectPerfectRatios( - IntTable(), [](IntTable& t) { return *t.emplace(t.size()).first; }); - - auto ratios = IntTablePefectRatios(); - if (ratios.empty()) return; - - EXPECT_THAT(perfect_ratios, - ElementsAre(DoubleNear(ratios[0].first, ratios[0].second), - DoubleNear(ratios[1].first, ratios[1].second), - DoubleNear(ratios[2].first, ratios[2].second))); -} - // Confirm that we assert if we try to erase() end(). TEST(TableDeathTest, EraseOfEndAsserts) { // Use an assert with side-effects to figure out if they are actually enabled. |