Export of internal Abseil changes.

--
ee19e203eca970ff88e8f25ce4e19c32e143b988 by Jon Cohen <cohenjon@google.com>:

Exception safety testing no longer uses absl::optional

PiperOrigin-RevId: 220336204

--
460666eb0b316a8b4aeedc589644d53b05251bd1 by Derek Mauro <dmauro@google.com>:

Rework SwissTable SSE2 support
  - Use SSE2 on MSVC when available
    https://github.com/abseil/abseil-cpp/issues/210
  - Emulate _mm_cmpgt_epi8 with other SSE2 instructions when using
    -funsigned-char under GCC
    https://github.com/abseil/abseil-cpp/issues/209

PiperOrigin-RevId: 220312351

--
1f4318ecedf8d539b7b698eb803d613ad6b69278 by Abseil Team <absl-team@google.com>:

Change CollectPerfectRatios to use 10 trials to smooth out the outliers in the
sample.

PiperOrigin-RevId: 220286579

--
6755abc2673553a7f578bb29c6e9ca8d991bc9c8 by Abseil Team <absl-team@google.com>:

Internal change

PiperOrigin-RevId: 220274307

--
8645b6187329ebf0aaf3c2de2888ba44466cd879 by Abseil Team <absl-team@google.com>:

* #endif for a header guard should reference the guard macro in a comment

PiperOrigin-RevId: 220206868

--
3987a7ad11319230910931cd2468b60b3fd1b85c by Gennadiy Civil <misterg@google.com>:

Internal Change

PiperOrigin-RevId: 220136674

--
cc908c1db2ee0d4523dc813e33f600583bb986c5 by Abseil Team <absl-team@google.com>:

absl: fix backoff logic in SpinLockWait

There are 3 bugs in loop variable handling:
1. It starts with 0, but AbslInternalSpinLockDelay ignores loop == 0.
So it does not actually wait when it should.
2. loop is incremented after successful state changes,
but it should not (why would be increase backoff delay after that?).
3. loop is incremented after CAS failures,
but it should not (why would be increase backoff delay after that?).

Use the same handling of loop as used in SpinLock.

PiperOrigin-RevId: 220136079

--
a0a1c6ef5910ebd28e07215d7df03cc0da0b3eed by Abseil Team <absl-team@google.com>:

absl: relax unnecessarily strong memory ordering in SpinLock::SlowLock

We don't need to acquire visibility over anything when setting kSpinLockSleeper.
Replace the confusing and unnecessarily strong memory order with relaxed.

PiperOrigin-RevId: 220023380

--
c50858b51af28b9fca1a62616324f85f3e84ea74 by Tom Manshreck <shreck@google.com>:

Update comments in flat_hash_map, node_hash_{set, map} and the containers developer guide

PiperOrigin-RevId: 219938692

--
e87b7d1a5f61e165b1c44d3b16d8d967197cdfce by CJ Johnson <johnsoncj@google.com>:

Rearranges the public methods of InlinedVector and cleans up the comments

PiperOrigin-RevId: 219896257

--
f3234c466f792e0fc4bfd21fc7919dba5e679375 by CJ Johnson <johnsoncj@google.com>:

Adds branch prediction to exceptional early exit cases of inlined vector's API

PiperOrigin-RevId: 219887173

--
4dfccf1a81ca0425912d3da25a8470f78c532ce4 by CJ Johnson <johnsoncj@google.com>:

Fixes the InlinedVector public interface to use the allocator type references instead of assuming the type
Also cleans up some cruft in formatting and comments

PiperOrigin-RevId: 219878876

--
4bb6a2b892abb10bd6a424db7e94ed8640802470 by Tom Manshreck <shreck@google.com>:

Add comments on constructor and assignment operator support to flat_hash_set

PiperOrigin-RevId: 219825338

--
c23f973e2f7f4feea0da36bf8a9c3f8a8954bb74 by Abseil Team <absl-team@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 219823847
GitOrigin-RevId: ee19e203eca970ff88e8f25ce4e19c32e143b988
Change-Id: I288c927ca481dc57340420dbb4c278a05cf15e83

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_