adjusted hysteresis factor

Add unordered_flat_map, unordered_flat_set

benchmark/string.cpp

@@ -5,6 +5,7 @@
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/multi_index_container.hpp>
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/member.hpp>
@@ -294,6 +295,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_flat_map =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map =
@@ -374,6 +378,9 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
     boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_flat_map_fnv1a =
+    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
   pair<K, V>,
   indexed_by<
@@ -418,10 +425,11 @@ int main()
 {
     init_indices();
 
-#if 0
+#if 1
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
     test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
@@ -449,6 +457,7 @@ int main()
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
     test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
     test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
 
 #ifdef HAVE_ABSEIL
@@ -476,7 +485,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 31 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 35 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/string_view.cpp

@@ -5,6 +5,7 @@
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/multi_index_container.hpp>
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/member.hpp>
@@ -295,6 +296,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_flat_map =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map =
@@ -375,6 +379,9 @@ std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 template<class K, class V> using boost_unordered_map_fnv1a =
     boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_flat_map_fnv1a =
+    boost::unordered_flat_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
+
 template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
   pair<K, V>,
   indexed_by<
@@ -419,10 +426,11 @@ int main()
 {
     init_indices();
 
-#if 0
+#if 1
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
     test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
@@ -450,6 +458,7 @@ int main()
 
     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
     test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
+    test<boost_unordered_flat_map_fnv1a>( "boost::unordered_flat_map, FNV-1a" );
     test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
 
 #ifdef HAVE_ABSEIL
@@ -477,7 +486,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 31 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 35 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint32.cpp

@@ -5,6 +5,7 @@
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/multi_index_container.hpp>
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/member.hpp>
@@ -311,6 +312,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_flat_map =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map =
@@ -347,6 +351,7 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
     test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
@@ -374,7 +379,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 25 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint64.cpp

@@ -5,6 +5,7 @@
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
 
 #include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
 #include <boost/multi_index_container.hpp>
 #include <boost/multi_index/hashed_index.hpp>
 #include <boost/multi_index/member.hpp>
@@ -311,6 +312,9 @@ template<class K, class V> using std_unordered_map =
 template<class K, class V> using boost_unordered_map =
     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 
+template<class K, class V> using boost_unordered_flat_map =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map =
@@ -347,6 +351,7 @@ int main()
 
     test<std_unordered_map>( "std::unordered_map" );
     test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
     test<multi_index_map>( "multi_index_map" );
 
 #ifdef HAVE_ABSEIL
@@ -374,7 +379,7 @@ int main()
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 25 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uuid.cpp

@@ -0,0 +1,393 @@
+// Copyright 2021, 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
+
+#include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/multi_index_container.hpp>
+#include <boost/multi_index/hashed_index.hpp>
+#include <boost/multi_index/member.hpp>
+#include <boost/endian/conversion.hpp>
+#include <boost/core/detail/splitmix64.hpp>
+#include <boost/container_hash/hash.hpp>
+#include <boost/config.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/container/node_hash_map.h"
+# include "absl/container/flat_hash_map.h"
+#endif
+#include <unordered_map>
+#include <vector>
+#include <memory>
+#include <cstdint>
+#include <iostream>
+#include <iomanip>
+#include <chrono>
+
+using namespace std::chrono_literals;
+
+static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::uint64_t s, std::size_t size )
+{
+    auto t2 = std::chrono::steady_clock::now();
+
+    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
+
+    t1 = t2;
+}
+
+constexpr unsigned N = 2'000'000;
+constexpr int K = 10;
+
+struct uuid
+{
+    unsigned char data[ 16 ];
+
+    uuid(): data()
+    {
+    }
+
+    uuid( std::uint64_t low, std::uint64_t high ) noexcept
+    {
+        boost::endian::store_little_u64( data + 0, low );
+        boost::endian::store_little_u64( data + 8, high );
+    }
+
+    inline friend std::size_t hash_value( uuid const& u ) noexcept
+    {
+        return boost::hash_value( u.data );
+    }
+
+    inline friend bool operator==( uuid const& u1, uuid const& u2 ) noexcept
+    {
+        return std::equal( u1.data + 0, u1.data + 16, u2.data );
+    }
+};
+
+namespace std
+{
+
+template<> struct hash< ::uuid >
+{
+    std::size_t operator()( uuid const& u ) const noexcept
+    {
+        return boost::hash_value( u.data );
+    }
+};
+
+} // namespace std
+
+static std::vector< uuid > indices1, indices2, indices3;
+
+static void init_indices()
+{
+    indices1.push_back( {} );
+
+    for( unsigned i = 1; i <= N*2; ++i )
+    {
+        indices1.push_back( { i, 0 } );
+    }
+
+    indices2.push_back( {} );
+
+    {
+        boost::detail::splitmix64 rng;
+
+        for( unsigned i = 1; i <= N*2; ++i )
+        {
+            indices2.push_back( { rng(), rng() } );
+        }
+    }
+
+    indices3.push_back( {} );
+
+    for( unsigned i = 1; i <= N*2; ++i )
+    {
+        uuid k( i, 0 );
+        std::reverse( k.data + 0, k.data + 16 );
+
+        indices3.push_back( k );
+    }
+}
+
+template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.insert( { indices1[ i ], i } );
+    }
+
+    print_time( t1, "Consecutive insert",  0, map.size() );
+
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.insert( { indices2[ i ], i } );
+    }
+
+    print_time( t1, "Random insert",  0, map.size() );
+
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.insert( { indices3[ i ], i } );
+    }
+
+    print_time( t1, "Consecutive reversed insert",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::uint64_t s;
+
+    s = 0;
+
+    for( int j = 0; j < K; ++j )
+    {
+        for( unsigned i = 1; i <= N * 2; ++i )
+        {
+            auto it = map.find( indices1[ i ] );
+            if( it != map.end() ) s += it->second;
+        }
+    }
+
+    print_time( t1, "Consecutive lookup",  s, map.size() );
+
+    s = 0;
+
+    for( int j = 0; j < K; ++j )
+    {
+        for( unsigned i = 1; i <= N * 2; ++i )
+        {
+            auto it = map.find( indices2[ i ] );
+            if( it != map.end() ) s += it->second;
+        }
+    }
+
+    print_time( t1, "Random lookup",  s, map.size() );
+
+    s = 0;
+
+    for( int j = 0; j < K; ++j )
+    {
+        for( unsigned i = 1; i <= N * 2; ++i )
+        {
+            auto it = map.find( indices3[ i ] );
+            if( it != map.end() ) s += it->second;
+        }
+    }
+
+    print_time( t1, "Consecutive reversed lookup",  s, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    auto it = map.begin();
+
+    while( it != map.end() )
+    {
+        if( it->second & 1 )
+        {
+            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
+            {
+                map.erase( it++ );
+            }
+            else
+            {
+                it = map.erase( it );
+            }
+        }
+        else
+        {
+            ++it;
+        }
+    }
+
+    print_time( t1, "Iterate and erase odd elements",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.erase( indices1[ i ] );
+    }
+
+    print_time( t1, "Consecutive erase",  0, map.size() );
+
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.erase( indices2[ i ] );
+    }
+
+    print_time( t1, "Random erase",  0, map.size() );
+
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.erase( indices3[ i ] );
+    }
+
+    print_time( t1, "Consecutive reversed erase",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+// counting allocator
+
+static std::size_t s_alloc_bytes = 0;
+static std::size_t s_alloc_count = 0;
+
+template<class T> struct allocator
+{
+    using value_type = T;
+
+    allocator() = default;
+
+    template<class U> allocator( allocator<U> const & ) noexcept
+    {
+    }
+
+    template<class U> bool operator==( allocator<U> const & ) const noexcept
+    {
+        return true;
+    }
+
+    template<class U> bool operator!=( allocator<U> const& ) const noexcept
+    {
+        return false;
+    }
+
+    T* allocate( std::size_t n ) const
+    {
+        s_alloc_bytes += n * sizeof(T);
+        s_alloc_count++;
+
+        return std::allocator<T>().allocate( n );
+    }
+
+    void deallocate( T* p, std::size_t n ) const noexcept
+    {
+        s_alloc_bytes -= n * sizeof(T);
+        s_alloc_count--;
+
+        std::allocator<T>().deallocate( p, n );
+    }
+};
+
+//
+
+struct record
+{
+    std::string label_;
+    long long time_;
+    std::size_t bytes_;
+    std::size_t count_;
+};
+
+static std::vector<record> times;
+
+template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
+{
+    std::cout << label << ":\n\n";
+
+    s_alloc_bytes = 0;
+    s_alloc_count = 0;
+
+    Map<uuid, std::uint64_t> map;
+
+    auto t0 = std::chrono::steady_clock::now();
+    auto t1 = t0;
+
+    test_insert( map, t1 );
+
+    std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
+
+    record rec = { label, 0, s_alloc_bytes, s_alloc_count };
+
+    test_lookup( map, t1 );
+    test_iteration( map, t1 );
+    test_lookup( map, t1 );
+    test_erase( map, t1 );
+
+    auto tN = std::chrono::steady_clock::now();
+    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
+
+    rec.time_ = ( tN - t0 ) / 1ms;
+    times.push_back( rec );
+}
+
+// multi_index emulation of unordered_map
+
+template<class K, class V> struct pair
+{
+    K first;
+    mutable V second;
+};
+
+using namespace boost::multi_index;
+
+template<class K, class V> using multi_index_map = multi_index_container<
+  pair<K, V>,
+  indexed_by<
+    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
+  >,
+  ::allocator< pair<K, V> >
+>;
+
+// aliases using the counting allocator
+
+template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
+
+template<class K, class V> using std_unordered_map =
+    std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
+template<class K, class V> using boost_unordered_map =
+    boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
+template<class K, class V> using boost_unordered_flat_map =
+    boost::unordered_flat_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
+
+#ifdef HAVE_ABSEIL
+
+template<class K, class V> using absl_node_hash_map =
+    absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
+
+template<class K, class V> using absl_flat_hash_map =
+    absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
+
+#endif
+
+int main()
+{
+    init_indices();
+
+    test<std_unordered_map>( "std::unordered_map" );
+    test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
+    test<multi_index_map>( "multi_index_map" );
+
+#ifdef HAVE_ABSEIL
+
+    test<absl_node_hash_map>( "absl::node_hash_map" );
+    test<absl_flat_hash_map>( "absl::flat_hash_map" );
+
+#endif
+
+    std::cout << "---\n\n";
+
+    for( auto const& x: times )
+    {
+        std::cout << std::setw( 27 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+    }
+}
+
+#ifdef HAVE_ABSEIL
+# include "absl/container/internal/raw_hash_set.cc"
+# include "absl/hash/internal/hash.cc"
+# include "absl/hash/internal/low_level_hash.cc"
+# include "absl/hash/internal/city.cc"
+#endif

include/boost/unordered/detail/foa.hpp

@@ -114,7 +114,8 @@ namespace foa{
  *     bits for signalling overflow makes it very likely that we stop at the
  *     current group (this happens when no element with the same (h%8) value
  *     has overflowed in the group), saving us an additional group check even
- *     under high-load/high-erase conditions.
+ *     under high-load/high-erase conditions. It is critical that hash
+ *     reduction is invariant under modulo 8 (see maybe_caused_overflow).
  *
  * When looking for an element with hash value h, match(h) returns a bitmask
  * signalling which slots have the same reduced hash value. If available,
@@ -189,6 +190,13 @@ struct group15
     overflow()|=static_cast<unsigned char>(1<<(hash%8));
   }
 
+  static inline bool maybe_caused_overflow(unsigned char* pc)
+  {
+    std::size_t pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
+    group15    *pg=reinterpret_cast<group15*>(pc-pos);
+    return !pg->is_not_overflowed(*pc);
+  };
+
   inline int match_available()const
   {
     return _mm_movemask_epi8(
@@ -213,7 +221,7 @@ private:
   {
     static constexpr boost::uint32_t word[]=
     {
-      0x02020202u,0x03030303u,0x02020202u,0x03030303u,0x04040404u,0x05050505u,0x06060606u,0x07070707u,
+      0x08080808u,0x09090909u,0x02020202u,0x03030303u,0x04040404u,0x05050505u,0x06060606u,0x07070707u,
       0x08080808u,0x09090909u,0x0A0A0A0Au,0x0B0B0B0Bu,0x0C0C0C0Cu,0x0D0D0D0Du,0x0E0E0E0Eu,0x0F0F0F0Fu,
       0x10101010u,0x11111111u,0x12121212u,0x13131313u,0x14141414u,0x15151515u,0x16161616u,0x17171717u,
       0x18181818u,0x19191919u,0x1A1A1A1Au,0x1B1B1B1Bu,0x1C1C1C1Cu,0x1D1D1D1Du,0x1E1E1E1Eu,0x1F1F1F1Fu,
@@ -337,6 +345,13 @@ struct group15
     overflow()|=static_cast<unsigned char>(1<<(hash%8));
   }
 
+  static inline bool maybe_caused_overflow(unsigned char* pc)
+  {
+    std::size_t pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
+    group15    *pg=reinterpret_cast<group15*>(pc-pos);
+    return !pg->is_not_overflowed(*pc);
+  };
+
   inline int match_available()const
   {
     return simde_mm_movemask_epi8(vceqq_s8(m,vdupq_n_s8(0)))&0x7FFF;
@@ -360,7 +375,7 @@ private:
   inline static unsigned char reduced_hash(std::size_t hash)
   {
     static constexpr unsigned char table[]={
-      2,3,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
+      8,9,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
       16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
       32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
       48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
@@ -491,6 +506,15 @@ struct group15
     reinterpret_cast<boost::uint16_t*>(m)[hash%8]|=0x8000u;
   }
 
+  static inline bool maybe_caused_overflow(unsigned char* pc)
+  {
+    std::size_t     pos=reinterpret_cast<uintptr_t>(pc)%sizeof(group15);
+    group15        *pg=reinterpret_cast<group15*>(pc-pos);
+    boost::uint64_t x=((pg->m[0])>>pos)&0x000100010001ull;
+    boost::uint32_t y=static_cast<boost::uint32_t>(x|(x>>15)|(x>>30));
+    return !pg->is_not_overflowed(y);
+  };
+
   inline int match_available()const
   {
     boost::uint64_t x=~(m[0]|m[1]);
@@ -519,7 +543,7 @@ private:
   inline static unsigned char reduced_hash(std::size_t hash)
   {
     static constexpr unsigned char table[]={
-      2,3,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
+      8,9,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
       16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,
       32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,
       48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,
@@ -1105,7 +1129,7 @@ public:
     const Allocator& al_=Allocator()):
     hash_base{empty_init,h_},pred_base{empty_init,pred_},
     allocator_base{empty_init,al_},size_{0},arrays(new_arrays(n)),
-    ml{max_load()}
+    ml{initial_max_load()}
     {}
 
   table(const table& x):
@@ -1123,7 +1147,7 @@ public:
   {
     x.size_=0;
     x.arrays=x.new_arrays(0);
-    x.ml=x.max_load();
+    x.ml=x.initial_max_load();
   }
 
   table(const table& x,const Allocator& al_):
@@ -1303,8 +1327,7 @@ public:
   void erase(const_iterator pos)noexcept
   {
     destroy_element(pos.p);
-    group_type::reset(pos.pc);
-    --size_;
+    recover_slot(pos.pc);
   }
 
   template<typename Key>
@@ -1361,6 +1384,7 @@ public:
       }
       arrays.groups[arrays.groups_size_mask].set_sentinel();
       size_=0;
+      ml=initial_max_load();
     }
   }
 
@@ -1407,6 +1431,8 @@ public:
 
   float max_load_factor()const noexcept{return mlf;}
 
+  std::size_t max_load()const noexcept{return ml;}
+
   void rehash(std::size_t n)
   {
     auto m=size_t(std::ceil(float(size())/mlf));
@@ -1472,7 +1498,23 @@ private:
     value_type *p;
   };
 
-  std::size_t max_load()const
+  void recover_slot(unsigned char* pc)
+  {
+    /* If this slot potentially caused overflow, we decrease the maximum load so
+     * that average probe length won't increase unboundedly in repeated
+     * insert/erase cycles (drift).
+     */
+    ml-=group_type::maybe_caused_overflow(pc);
+    group_type::reset(pc);
+    --size_;
+  }
+
+  void recover_slot(group_type* pg,std::size_t pos)
+  {
+    recover_slot(reinterpret_cast<unsigned char*>(pg)+pos);
+  }
+
+  std::size_t initial_max_load()const
   {
     static constexpr std::size_t small_capacity=2*N-1;
 
@@ -1611,11 +1653,21 @@ private:
   BOOST_NOINLINE iterator
   unchecked_emplace_with_rehash(std::size_t hash,Args&&... args)
   {
-    /* strong exception guarantee -> try insertion before rehash */
-    auto     new_arrays_=new_arrays(
-               std::size_t(std::ceil(static_cast<float>(size_+1)/mlf)));
+    /* Due to the anti-drift mechanism (see recover_slot), new_arrays_ may be
+     * of the same size as the old arrays; in the limit, erasing one element at
+     * full load and then inserting could bring us back to the same capacity
+     * after a costly rehash. To avoid this, we jump to the next capacity level
+     * when the number of erased elements is <= 10% of total elements at full
+     * load, which is implemented by requesting additional F*size elements,
+     * with F = P * 10% / (1 - P * 10%), where P is the probability of an
+     * element having caused overflow; P has been measured as ~0.162 under
+     * ideal conditions, yielding F ~ 0.0165 ~ 1/61.
+     */
+    auto     new_arrays_=new_arrays(std::size_t(
+               std::ceil(static_cast<float>(size_+size_/61+1)/mlf)));
     iterator it;
     BOOST_TRY{
+      /* strong exception guarantee -> try insertion before rehash */
       it=nosize_unchecked_emplace_at(
         new_arrays_,position_for(hash,new_arrays_),
         hash,std::forward<Args>(args)...);
@@ -1648,12 +1700,11 @@ private:
     }
     BOOST_CATCH(...){
       if(num_destroyed){
-        size_-=num_destroyed;
         for(auto pg=arrays.groups;;++pg){
           auto mask=pg->match_occupied();
           while(mask){
             auto nz=unchecked_countr_zero(mask);
-            pg->reset(nz);
+            recover_slot(pg,nz);
             if(!(--num_destroyed))goto continue_;
             mask&=mask-1;
           }
@@ -1677,7 +1728,7 @@ private:
     }
     delete_arrays(arrays);
     arrays=new_arrays_;
-    ml=max_load();
+    ml=initial_max_load();
   }
 
   void noshrink_reserve(std::size_t n)
@@ -1693,7 +1744,7 @@ private:
         auto new_arrays_=new_arrays(n);
         delete_arrays(arrays);
         arrays=new_arrays_;
-        ml=max_load();
+        ml=initial_max_load();
       }
     }
   }

include/boost/unordered/unordered_flat_map.hpp

@@ -552,6 +552,8 @@ namespace boost {
 
       void max_load_factor(float) {}
 
+      size_type max_load() const noexcept { return table_.max_load(); }
+
       void rehash(size_type n) { table_.rehash(n); }
 
       void reserve(size_type n) { table_.reserve(n); }

include/boost/unordered/unordered_flat_set.hpp

@@ -428,6 +428,8 @@ namespace boost {
 
       void max_load_factor(float) {}
 
+      size_type max_load() const noexcept { return table_.max_load(); }
+
       void rehash(size_type n) { table_.rehash(n); }
 
       void reserve(size_type n) { table_.reserve(n); }