diff options
Diffstat (limited to 'absl/container/internal')
8 files changed, 87 insertions, 54 deletions
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 78382a35..26d9972c 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h @@ -92,7 +92,9 @@ #define ABSL_CONTAINER_INTERNAL_RAW_HASH_SET_H_ #ifndef SWISSTABLE_HAVE_SSE2 -#ifdef __SSE2__ +#if defined(__SSE2__) || \ + (defined(_MSC_VER) && \ + (defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2))) #define SWISSTABLE_HAVE_SSE2 1 #else #define SWISSTABLE_HAVE_SSE2 0 @@ -112,7 +114,11 @@ #endif #if SWISSTABLE_HAVE_SSE2 -#include <x86intrin.h> +#include <emmintrin.h> +#endif + +#if SWISSTABLE_HAVE_SSSE3 +#include <tmmintrin.h> #endif #include <algorithm> @@ -337,6 +343,23 @@ inline bool IsDeleted(ctrl_t c) { return c == kDeleted; } inline bool IsEmptyOrDeleted(ctrl_t c) { return c < kSentinel; } #if SWISSTABLE_HAVE_SSE2 + +// https://github.com/abseil/abseil-cpp/issues/209 +// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87853 +// _mm_cmpgt_epi8 is broken under GCC with -funsigned-char +// Work around this by using the portable implementation of Group +// when using -funsigned-char under GCC. +inline __m128i _mm_cmpgt_epi8_fixed(__m128i a, __m128i b) { +#if defined(__GNUC__) && !defined(__clang__) + if (std::is_unsigned<char>::value) { + const __m128i mask = _mm_set1_epi8(0x80); + const __m128i diff = _mm_subs_epi8(b, a); + return _mm_cmpeq_epi8(_mm_and_si128(diff, mask), mask); + } +#endif + return _mm_cmpgt_epi8(a, b); +} + struct GroupSse2Impl { static constexpr size_t kWidth = 16; // the number of slots per group @@ -366,13 +389,14 @@ struct GroupSse2Impl { BitMask<uint32_t, kWidth> MatchEmptyOrDeleted() const { auto special = _mm_set1_epi8(kSentinel); return BitMask<uint32_t, kWidth>( - _mm_movemask_epi8(_mm_cmpgt_epi8(special, ctrl))); + _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl))); } // Returns the number of trailing empty or deleted elements in the group. uint32_t CountLeadingEmptyOrDeleted() const { auto special = _mm_set1_epi8(kSentinel); - return TrailingZeros(_mm_movemask_epi8(_mm_cmpgt_epi8(special, ctrl)) + 1); + return TrailingZeros( + _mm_movemask_epi8(_mm_cmpgt_epi8_fixed(special, ctrl)) + 1); } void ConvertSpecialToEmptyAndFullToDeleted(ctrl_t* dst) const { @@ -382,7 +406,7 @@ struct GroupSse2Impl { auto res = _mm_or_si128(_mm_shuffle_epi8(x126, ctrl), msbs); #else auto zero = _mm_setzero_si128(); - auto special_mask = _mm_cmpgt_epi8(zero, ctrl); + auto special_mask = _mm_cmpgt_epi8_fixed(zero, ctrl); auto res = _mm_or_si128(msbs, _mm_andnot_si128(special_mask, x126)); #endif _mm_storeu_si128(reinterpret_cast<__m128i*>(dst), res); @@ -444,15 +468,7 @@ struct GroupPortableImpl { uint64_t ctrl; }; -#if SWISSTABLE_HAVE_SSE2 && defined(__GNUC__) && !defined(__clang__) -// https://github.com/abseil/abseil-cpp/issues/209 -// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=87853 -// _mm_cmpgt_epi8 is broken under GCC with -funsigned-char -// Work around this by using the portable implementation of Group -// when using -funsigned-char under GCC. -using Group = std::conditional<std::is_signed<char>::value, GroupSse2Impl, - GroupPortableImpl>::type; -#elif SWISSTABLE_HAVE_SSE2 +#if SWISSTABLE_HAVE_SSE2 using Group = GroupSse2Impl; #else using Group = GroupPortableImpl; diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index b66a8f16..9d92e15c 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc @@ -1785,35 +1785,51 @@ TEST(Table, IterationOrderChangesForSmallTables) { // 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 t, AddFn add) { - 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> 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)); + } - 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(); } - return perfect_ratios; + + results[0] /= kNumTrials; + results[1] /= kNumTrials; + results[2] /= kNumTrials; + + return results; } std::vector<std::pair<double, double>> StringTablePefectRatios() { @@ -1854,13 +1870,10 @@ TEST(Table, EffectiveLoadFactorStrings) { auto ratios = StringTablePefectRatios(); if (ratios.empty()) return; - - EXPECT_THAT(perfect_ratios.front(), - DoubleNear(ratios[0].first, ratios[0].second)); - EXPECT_THAT(perfect_ratios[perfect_ratios.size() / 2], - DoubleNear(ratios[1].first, ratios[1].second)); - EXPECT_THAT(perfect_ratios.back(), - DoubleNear(ratios[2].first, ratios[2].second)); + 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() { @@ -1900,12 +1913,10 @@ TEST(Table, EffectiveLoadFactorInts) { auto ratios = IntTablePefectRatios(); if (ratios.empty()) return; - EXPECT_THAT(perfect_ratios.front(), - DoubleNear(ratios[0].first, ratios[0].second)); - EXPECT_THAT(perfect_ratios[perfect_ratios.size() / 2], - DoubleNear(ratios[1].first, ratios[1].second)); - EXPECT_THAT(perfect_ratios.back(), - DoubleNear(ratios[2].first, ratios[2].second)); + 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(). diff --git a/absl/container/internal/unordered_map_constructor_test.h b/absl/container/internal/unordered_map_constructor_test.h index 2ffb646c..87d6c3c3 100644 --- a/absl/container/internal/unordered_map_constructor_test.h +++ b/absl/container/internal/unordered_map_constructor_test.h @@ -401,4 +401,5 @@ REGISTER_TYPED_TEST_CASE_P( } // namespace container_internal } // namespace absl + #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_CONSTRUCTOR_TEST_H_ diff --git a/absl/container/internal/unordered_map_lookup_test.h b/absl/container/internal/unordered_map_lookup_test.h index 1f1b6b48..a3d21595 100644 --- a/absl/container/internal/unordered_map_lookup_test.h +++ b/absl/container/internal/unordered_map_lookup_test.h @@ -111,4 +111,5 @@ REGISTER_TYPED_TEST_CASE_P(LookupTest, At, OperatorBracket, Count, Find, } // namespace container_internal } // namespace absl + #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_LOOKUP_TEST_H_ diff --git a/absl/container/internal/unordered_map_modifiers_test.h b/absl/container/internal/unordered_map_modifiers_test.h index b6c633ae..61ae7d63 100644 --- a/absl/container/internal/unordered_map_modifiers_test.h +++ b/absl/container/internal/unordered_map_modifiers_test.h @@ -269,4 +269,5 @@ REGISTER_TYPED_TEST_CASE_P(ModifiersTest, Clear, Insert, InsertHint, } // namespace container_internal } // namespace absl + #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_MAP_MODIFIERS_TEST_H_ diff --git a/absl/container/internal/unordered_set_constructor_test.h b/absl/container/internal/unordered_set_constructor_test.h index cb593704..9516e5ba 100644 --- a/absl/container/internal/unordered_set_constructor_test.h +++ b/absl/container/internal/unordered_set_constructor_test.h @@ -405,4 +405,5 @@ REGISTER_TYPED_TEST_CASE_P( } // namespace container_internal } // namespace absl + #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_CONSTRUCTOR_TEST_H_ diff --git a/absl/container/internal/unordered_set_lookup_test.h b/absl/container/internal/unordered_set_lookup_test.h index aca9c6a5..1421e7b6 100644 --- a/absl/container/internal/unordered_set_lookup_test.h +++ b/absl/container/internal/unordered_set_lookup_test.h @@ -85,4 +85,5 @@ REGISTER_TYPED_TEST_CASE_P(LookupTest, Count, Find, EqualRange); } // namespace container_internal } // namespace absl + #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_LOOKUP_TEST_H_ diff --git a/absl/container/internal/unordered_set_modifiers_test.h b/absl/container/internal/unordered_set_modifiers_test.h index 9beacf33..445dcec4 100644 --- a/absl/container/internal/unordered_set_modifiers_test.h +++ b/absl/container/internal/unordered_set_modifiers_test.h @@ -184,4 +184,5 @@ REGISTER_TYPED_TEST_CASE_P(ModifiersTest, Clear, Insert, InsertHint, } // namespace container_internal } // namespace absl + #endif // ABSL_CONTAINER_INTERNAL_UNORDERED_SET_MODIFIERS_TEST_H_ |