optimized SSE2-based group15

Add msvc RTC to select test targets

.github/workflows/ci.yml

@@ -217,11 +217,13 @@ jobs:
       fail-fast: false
       matrix:
         include:
-          - { toolset: msvc-14.0, cxxstd: '14,latest',       addrmd: '32,64', os: windows-2019 }
-          - { toolset: msvc-14.2, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2019 }
-          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2022 }
-          - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: windows-2022 }
-          - { toolset: gcc,       cxxstd: '03,11,14,17,2a',  addrmd: '64',    os: windows-2019 }
+          - { toolset: msvc-14.0, cxxstd: '14,latest',       addrmd: '32,64', os: windows-2019, variant: 'debug,release' }
+          - { toolset: msvc-14.2, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2019, variant: 'debug,release' }
+          - { toolset: msvc-14.3, cxxstd: '14,17,20,latest', addrmd: '32,64', os: windows-2022, variant: 'debug,release' }
+          - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '64',    os: windows-2022, variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '/RTCc'              }
+          - { toolset: msvc-14.3, cxxstd: '14',              addrmd: '32',    os: windows-2022, variant: 'debug', defines: '_ALLOW_RTCc_IN_STL', cxxflags: '"/RTCc /arch:IA32"' }
+          - { toolset: clang-win, cxxstd: '14,17,latest',    addrmd: '32,64', os: windows-2022, variant: 'debug,release' }
+          - { toolset: gcc,       cxxstd: '03,11,14,17,2a',  addrmd: '64',    os: windows-2019, variant: 'debug,release' }
 
     runs-on: ${{matrix.os}}
 
@@ -250,6 +252,9 @@ jobs:
           B2_TOOLSET: ${{matrix.toolset}}
           B2_CXXSTD: ${{matrix.cxxstd}}
           B2_ADDRESS_MODEL: ${{matrix.addrmd}}
+          B2_DEFINES: ${{matrix.defines}}
+          B2_VARIANT: ${{matrix.variant}}
+          B2_CXXFLAGS: ${{matrix.cxxflags}}
 
       - name: Collect coverage
         shell: powershell

benchmark/.gitignore

@@ -0,0 +1,3 @@
+enwik8
+enwik9
+*.exe

benchmark/string.cpp

@@ -3,23 +3,18 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
+#define _SILENCE_CXX20_CISO646_REMOVED_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/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
 #ifdef HAVE_ABSEIL
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_TSL_HOPSCOTCH
-# include "tsl/hopscotch_map.h"
-#endif
-#ifdef HAVE_TSL_ROBIN
-# include "tsl/robin_map.h"
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -267,24 +262,6 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     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> >;
@@ -308,23 +285,10 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_TSL_HOPSCOTCH
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
 
-template<class K, class V> using tsl_hopscotch_map =
-    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_hopscotch_pg_map =
-    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-template<class K, class V> using tsl_robin_map =
-    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_robin_pg_map =
-    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using ankerl_unordered_dense_map =
+    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -384,14 +348,6 @@ template<class K, class V> using boost_unordered_map_fnv1a =
 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<
-    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
-  >,
-  ::allocator< pair<K, V> >
->;
-
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map_fnv1a =
@@ -402,23 +358,10 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =
 
 #endif
 
-#ifdef HAVE_TSL_HOPSCOTCH
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
 
-template<class K, class V> using tsl_hopscotch_map_fnv1a =
-    tsl::hopscotch_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_hopscotch_pg_map_fnv1a =
-    tsl::hopscotch_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-template<class K, class V> using tsl_robin_map_fnv1a =
-    tsl::robin_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_robin_pg_map_fnv1a =
-    tsl::robin_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
+    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -428,67 +371,45 @@ int main()
 {
     init_indices();
 
-#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_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
+
+#endif
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
-#endif
-
-#ifdef HAVE_TSL_HOPSCOTCH
-
-    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
-    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-    test<tsl_robin_map>( "tsl::robin_map" );
-    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
-
-#endif
-
 #endif
 
     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_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
+
+#endif
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 
-#endif
-
-#ifdef HAVE_TSL_HOPSCOTCH
-
-    test<tsl_hopscotch_map_fnv1a>( "tsl::hopscotch_map, FNV-1a" );
-    test<tsl_hopscotch_pg_map_fnv1a>( "tsl::hopscotch_pg_map, FNV-1a" );
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-    test<tsl_robin_map_fnv1a>( "tsl::robin_map, FNV-1a" );
-    test<tsl_robin_pg_map_fnv1a>( "tsl::robin_pg_map, FNV-1a" );
-
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 35 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/string_view.cpp

@@ -3,23 +3,18 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
+#define _SILENCE_CXX20_CISO646_REMOVED_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/core/detail/splitmix64.hpp>
 #include <boost/config.hpp>
 #ifdef HAVE_ABSEIL
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_TSL_HOPSCOTCH
-# include "tsl/hopscotch_map.h"
-#endif
-#ifdef HAVE_TSL_ROBIN
-# include "tsl/robin_map.h"
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
 #endif
 #include <unordered_map>
 #include <string_view>
@@ -268,24 +263,6 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     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> >;
@@ -309,23 +286,10 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_TSL_HOPSCOTCH
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
 
-template<class K, class V> using tsl_hopscotch_map =
-    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_hopscotch_pg_map =
-    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-template<class K, class V> using tsl_robin_map =
-    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_robin_pg_map =
-    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using ankerl_unordered_dense_map =
+    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -385,14 +349,6 @@ template<class K, class V> using boost_unordered_map_fnv1a =
 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<
-    hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
-  >,
-  ::allocator< pair<K, V> >
->;
-
 #ifdef HAVE_ABSEIL
 
 template<class K, class V> using absl_node_hash_map_fnv1a =
@@ -403,23 +359,10 @@ template<class K, class V> using absl_flat_hash_map_fnv1a =
 
 #endif
 
-#ifdef HAVE_TSL_HOPSCOTCH
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
 
-template<class K, class V> using tsl_hopscotch_map_fnv1a =
-    tsl::hopscotch_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_hopscotch_pg_map_fnv1a =
-    tsl::hopscotch_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-template<class K, class V> using tsl_robin_map_fnv1a =
-    tsl::robin_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_robin_pg_map_fnv1a =
-    tsl::robin_pg_map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
+    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -429,67 +372,45 @@ int main()
 {
     init_indices();
 
-#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_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
+
+#endif
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
-#endif
-
-#ifdef HAVE_TSL_HOPSCOTCH
-
-    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
-    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-    test<tsl_robin_map>( "tsl::robin_map" );
-    test<tsl_robin_pg_map>( "tsl::robin_pg_map" );
-
-#endif
-
 #endif
 
     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_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
+
+#endif
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 
-#endif
-
-#ifdef HAVE_TSL_HOPSCOTCH
-
-    test<tsl_hopscotch_map_fnv1a>( "tsl::hopscotch_map, FNV-1a" );
-    test<tsl_hopscotch_pg_map_fnv1a>( "tsl::hopscotch_pg_map, FNV-1a" );
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-    test<tsl_robin_map_fnv1a>( "tsl::robin_map, FNV-1a" );
-    test<tsl_robin_pg_map_fnv1a>( "tsl::robin_pg_map, FNV-1a" );
-
 #endif
 
     std::cout << "---\n\n";
 
     for( auto const& x: times )
     {
-        std::cout << std::setw( 35 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
+        std::cout << std::setw( 38 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint32.cpp

@@ -3,12 +3,10 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
+#define _SILENCE_CXX20_CISO646_REMOVED_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/config.hpp>
@@ -16,11 +14,8 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_TSL_HOPSCOTCH
-# include "tsl/hopscotch_map.h"
-#endif
-#ifdef HAVE_TSL_ROBIN
-# include "tsl/robin_map.h"
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -284,24 +279,6 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     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> >;
@@ -325,23 +302,10 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_TSL_HOPSCOTCH
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
 
-template<class K, class V> using tsl_hopscotch_map =
-    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_hopscotch_pg_map =
-    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-template<class K, class V> using tsl_robin_map =
-    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_robin_pg_map =
-    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using ankerl_unordered_dense_map =
+    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -352,34 +316,25 @@ 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_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
+
+#endif
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
-#endif
-
-#ifdef HAVE_TSL_HOPSCOTCH
-
-    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
-    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-    test<tsl_robin_map>( "tsl::robin_map" );
-    test<tsl_robin_pg_map>( "tsl::robin_pg_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";
+        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uint64.cpp

@@ -3,12 +3,10 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
+#define _SILENCE_CXX20_CISO646_REMOVED_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/config.hpp>
@@ -16,11 +14,8 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
-#ifdef HAVE_TSL_HOPSCOTCH
-# include "tsl/hopscotch_map.h"
-#endif
-#ifdef HAVE_TSL_ROBIN
-# include "tsl/robin_map.h"
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
 #endif
 #include <unordered_map>
 #include <vector>
@@ -284,24 +279,6 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     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> >;
@@ -325,23 +302,10 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
-#ifdef HAVE_TSL_HOPSCOTCH
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
 
-template<class K, class V> using tsl_hopscotch_map =
-    tsl::hopscotch_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_hopscotch_pg_map =
-    tsl::hopscotch_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-template<class K, class V> using tsl_robin_map =
-    tsl::robin_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
-
-template<class K, class V> using tsl_robin_pg_map =
-    tsl::robin_pg_map<K, V, std::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+template<class K, class V> using ankerl_unordered_dense_map =
+    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
 
 #endif
 
@@ -349,37 +313,38 @@ int main()
 {
     init_indices();
 
+#if defined(BOOST_LIBSTDCXX_VERSION) && __SIZE_WIDTH__ == 32
+
+    // Pathological behavior:
+    // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=104945
+
+#else
+
     test<std_unordered_map>( "std::unordered_map" );
+
+#endif
+
     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_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
+
+#endif
 
 #ifdef HAVE_ABSEIL
 
     test<absl_node_hash_map>( "absl::node_hash_map" );
     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 
-#endif
-
-#ifdef HAVE_TSL_HOPSCOTCH
-
-    test<tsl_hopscotch_map>( "tsl::hopscotch_map" );
-    test<tsl_hopscotch_pg_map>( "tsl::hopscotch_pg_map" );
-
-#endif
-
-#ifdef HAVE_TSL_ROBIN
-
-    test<tsl_robin_map>( "tsl::robin_map" );
-    test<tsl_robin_pg_map>( "tsl::robin_pg_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";
+        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/uuid.cpp

@@ -3,12 +3,10 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING
+#define _SILENCE_CXX20_CISO646_REMOVED_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>
@@ -17,6 +15,9 @@
 # include "absl/container/node_hash_map.h"
 # include "absl/container/flat_hash_map.h"
 #endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
+#endif
 #include <unordered_map>
 #include <vector>
 #include <memory>
@@ -329,24 +330,6 @@ template<template<class...> class Map> BOOST_NOINLINE void test( char const* lab
     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> >;
@@ -370,6 +353,13 @@ template<class K, class V> using absl_flat_hash_map =
 
 #endif
 
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+template<class K, class V> using ankerl_unordered_dense_map =
+    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
 int main()
 {
     init_indices();
@@ -377,7 +367,12 @@ 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_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
+
+#endif
 
 #ifdef HAVE_ABSEIL
 
@@ -390,7 +385,7 @@ int main()
 
     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";
+        std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
     }
 }
 

benchmark/word_count.cpp

@@ -0,0 +1,376 @@
+// 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
+#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
+
+#include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/regex.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/container/node_hash_map.h"
+# include "absl/container/flat_hash_map.h"
+#endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
+#endif
+#include <unordered_map>
+#include <vector>
+#include <memory>
+#include <cstdint>
+#include <iostream>
+#include <iomanip>
+#include <chrono>
+#include <fstream>
+#include <string_view>
+#include <string>
+
+using namespace std::chrono_literals;
+
+static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::size_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;
+}
+
+static std::vector<std::string> words;
+
+static void init_words()
+{
+#if SIZE_MAX > UINT32_MAX
+
+    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
+
+#else
+
+    char const* fn = "enwik8"; // ditto
+
+#endif
+
+    auto t1 = std::chrono::steady_clock::now();
+
+    std::ifstream is( fn );
+    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
+
+    boost::regex re( "[a-zA-Z]+");
+    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
+
+    words.assign( it, end );
+
+    auto t2 = std::chrono::steady_clock::now();
+
+    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
+}
+
+template<class Map> BOOST_NOINLINE void test_word_count( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::size_t s = 0;
+
+    for( auto const& word: words )
+    {
+        ++map[ word ];
+        ++s;
+    }
+
+    print_time( t1, "Word count", s, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_contains( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::size_t s = 0;
+
+    for( auto const& word: words )
+    {
+        std::string_view w2( word );
+        w2.remove_prefix( 1 );
+
+        s += map.contains( w2 );
+    }
+
+    print_time( t1, "Contains", s, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_count( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::size_t s = 0;
+
+    for( auto const& word: words )
+    {
+        std::string_view w2( word );
+        w2.remove_prefix( 1 );
+
+        s += map.count( w2 );
+    }
+
+    print_time( t1, "Count", s, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::size_t max = 0;
+    std::string_view word;
+
+    for( auto const& x: map )
+    {
+        if( x.second > max )
+        {
+            word = x.first;
+            max = x.second;
+        }
+    }
+
+    print_time( t1, "Iterate and find max element",  max, 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<std::string_view, std::size_t> map;
+
+    auto t0 = std::chrono::steady_clock::now();
+    auto t1 = t0;
+
+    test_word_count( 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_contains( map, t1 );
+    test_count( map, t1 );
+    test_iteration( 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 );
+}
+
+// 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
+
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+template<class K, class V> using ankerl_unordered_dense_map =
+    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+// fnv1a_hash
+
+template<int Bits> struct fnv1a_hash_impl;
+
+template<> struct fnv1a_hash_impl<32>
+{
+    std::size_t operator()( std::string_view const& s ) const
+    {
+        std::size_t h = 0x811C9DC5u;
+
+        char const * first = s.data();
+        char const * last = first + s.size();
+
+        for( ; first != last; ++first )
+        {
+            h ^= static_cast<unsigned char>( *first );
+            h *= 0x01000193ul;
+        }
+
+        return h;
+    }
+};
+
+template<> struct fnv1a_hash_impl<64>
+{
+    std::size_t operator()( std::string_view const& s ) const
+    {
+        std::size_t h = 0xCBF29CE484222325ull;
+
+        char const * first = s.data();
+        char const * last = first + s.size();
+
+        for( ; first != last; ++first )
+        {
+            h ^= static_cast<unsigned char>( *first );
+            h *= 0x00000100000001B3ull;
+        }
+
+        return h;
+    }
+};
+
+struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits >
+{
+    using is_avalanching = void;
+};
+
+template<class K, class V> using std_unordered_map_fnv1a =
+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>>;
+
+#ifdef HAVE_ABSEIL
+
+template<class K, class V> using absl_node_hash_map_fnv1a =
+    absl::node_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
+
+template<class K, class V> using absl_flat_hash_map_fnv1a =
+    absl::flat_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
+
+#endif
+
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+template<class K, class V> using ankerl_unordered_dense_map_fnv1a =
+    ankerl::unordered_dense::map<K, V, fnv1a_hash, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+//
+
+int main()
+{
+    init_words();
+
+    test<std_unordered_map>( "std::unordered_map" );
+    test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
+
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
+
+#endif
+
+#ifdef HAVE_ABSEIL
+
+    test<absl_node_hash_map>( "absl::node_hash_map" );
+    test<absl_flat_hash_map>( "absl::flat_hash_map" );
+
+#endif
+
+    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" );
+
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map_fnv1a>( "ankerl::unordered_dense::map, FNV-1a" );
+
+#endif
+
+#ifdef HAVE_ABSEIL
+
+    test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
+    test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
+
+#endif
+
+    std::cout << "---\n\n";
+
+    for( auto const& x: times )
+    {
+        std::cout << std::setw( 38 ) << ( 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

benchmark/word_size.cpp

@@ -0,0 +1,238 @@
+// 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
+#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
+
+#include <boost/unordered_map.hpp>
+#include <boost/unordered/unordered_flat_map.hpp>
+#include <boost/regex.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/container/node_hash_map.h"
+# include "absl/container/flat_hash_map.h"
+#endif
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+# include "ankerl/unordered_dense.h"
+#endif
+#include <unordered_map>
+#include <vector>
+#include <memory>
+#include <cstdint>
+#include <iostream>
+#include <iomanip>
+#include <chrono>
+#include <fstream>
+
+using namespace std::chrono_literals;
+
+static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::size_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;
+}
+
+static std::vector<std::string> words;
+
+static void init_words()
+{
+#if SIZE_MAX > UINT32_MAX
+
+    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
+
+#else
+
+    char const* fn = "enwik8"; // ditto
+
+#endif
+
+    auto t1 = std::chrono::steady_clock::now();
+
+    std::ifstream is( fn );
+    std::string in( std::istreambuf_iterator<char>( is ), std::istreambuf_iterator<char>{} );
+
+    boost::regex re( "[a-zA-Z]+");
+    boost::sregex_token_iterator it( in.begin(), in.end(), re, 0 ), end;
+
+    words.assign( it, end );
+
+    auto t2 = std::chrono::steady_clock::now();
+
+    std::cout << fn << ": " << words.size() << " words, " << ( t2 - t1 ) / 1ms << " ms\n\n";
+}
+
+template<class Map> BOOST_NOINLINE void test_word_size( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    for( auto const& word: words )
+    {
+        ++map[ word.size() ];
+    }
+
+    print_time( t1, "Word size count",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::size_t s = 0;
+
+    for( auto const& x: map )
+    {
+        s += x.second;
+    }
+
+    print_time( t1, "Iterate and sum counts",  s, 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<std::size_t, std::size_t> map;
+
+    auto t0 = std::chrono::steady_clock::now();
+    auto t1 = t0;
+
+    test_word_size( 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_iteration( 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 );
+}
+
+// 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
+
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+template<class K, class V> using ankerl_unordered_dense_map =
+    ankerl::unordered_dense::map<K, V, ankerl::unordered_dense::hash<K>, std::equal_to<K>, ::allocator< std::pair<K, V> >>;
+
+#endif
+
+int main()
+{
+    init_words();
+
+    test<std_unordered_map>( "std::unordered_map" );
+    test<boost_unordered_map>( "boost::unordered_map" );
+    test<boost_unordered_flat_map>( "boost::unordered_flat_map" );
+
+#ifdef HAVE_ANKERL_UNORDERED_DENSE
+
+    test<ankerl_unordered_dense_map>( "ankerl::unordered_dense::map" );
+
+#endif
+
+#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( 30 ) << ( 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

doc/unordered/buckets.adoc

@@ -244,4 +244,69 @@ image::fca.png[align=center]
 
 Thus container-wide iteration is turned into traversing the non-empty bucket groups (an operation with constant time complexity) which reduces the time complexity back to `O(size())`. In total, a bucket group is only 4 words in size and it views `sizeof(std::size_t) * CHAR_BIT` buckets meaning that for all common implementations, there's only 4 bits of space overhead per bucket introduced by the bucket groups.
 
-For more information on implementation rationale, read the <<Implementation Rationale, corresponding section>>.
+A more detailed description of Boost.Unordered's closed-addressing implementation is
+given in an
+https://bannalia.blogspot.com/2022/06/advancing-state-of-art-for.html[external article].
+For more information on implementation rationale, read the
+xref:#rationale_boostunordered_multiset_and_boostunordered_multimap[corresponding section].
+
+== Open Addressing Implementation
+
+The diagram shows the basic internal layout of `boost::unordered_flat_map` and
+`boost:unordered_flat_set`.
+
+
+[#img-foa-layout]
+.Open-addressing layout used by Boost.Unordered.
+image::foa.png[align=center]
+
+As with all open-addressing containers, elements are stored directly in the bucket array.
+This array is logically divided into 2^_n_^ _groups_ of 15 elements each.
+In addition to the bucket array, there is an associated _metadata array_ with 2^_n_^
+16-byte words.
+
+[#img-foa-metadata]
+.Breakdown of a metadata word.
+image::foa-metadata.png[align=center]
+
+A metadata word is divided into 15 _h_~_i_~ bytes (one for each associated
+bucket), and an _overflow byte_ (_ofw_ in the diagram). The value of _h_~_i_~ is:
+
+  - 0 if the corresponding bucket is empty.
+  - 1 to encode a special empty bucket called a _sentinel_, which is used internally to
+  stop iteration when the container has been fully traversed.
+  - If the bucket is occupied, a _reduced hash value_ obtained from the hash value of
+  the element.
+
+When looking for an element with hash value _h_, SIMD technologies such as
+https://en.wikipedia.org/wiki/SSE2[SSE2] and
+https://en.wikipedia.org/wiki/ARM_architecture_family#Advanced_SIMD_(Neon)[Neon] allow us
+to very quickly inspect the full metadata word and look for the reduced value of _h_ among all the
+15 buckets with just a handful of CPU instructions: non-matching buckets can be
+readily discarded, and those whose reduced hash value matches need be inspected via full
+comparison with the corresponding element. If the looked-for element is not present,
+the overflow byte is inspected:
+
+- If the bit in the position _h_ mod 8 is zero, lookup terminates (and the
+element is not present).
+- If the bit is set to 1 (the group has been _overflowed_), further groups are
+checked using https://en.wikipedia.org/wiki/Quadratic_probing[_quadratic probing_], and
+the process is repeated.
+
+Insertion is algorithmically similar: empty buckets are located using SIMD,
+and when going past a full group its corresponding overflow bit is set to 1.
+
+In architectures without SIMD support, the logical layout stays the same, but the metadata
+word is codified using a technique we call _bit interleaving_: this layout allows us
+to emulate SIMD with reasonably good performance using only standard arithmetic and
+logical operations.
+
+[#img-foa-metadata-interleaving]
+.Bit-interleaved metadata word.
+image::foa-metadata-interleaving.png[align=center]
+
+A more detailed description of Boost.Unordered's open-addressing implementation is
+given in an
+https://bannalia.blogspot.com/2022/11/inside-boostunorderedflatmap.html[external article].
+For more information on implementation rationale, read the
+xref:#rationale_boostunordered_flat_set_and_boostunordered_flat_map[corresponding section].

doc/unordered/changes.adoc

@@ -10,6 +10,8 @@
 
 * Added fast containers `boost::unordered_flat_map` and `boost::unordered_flat_set`
   based on open addressing.
+* Added CTAD deduction guides for all containers.
+* Added missing constructors as specified in https://cplusplus.github.io/LWG/issue2713[LWG issue 2713].
 
 == Release 1.80.0 - Major update
 

include/boost/unordered/detail/foa.hpp

@@ -135,6 +135,7 @@ static const std::size_t default_bucket_count = 0;
 
 #if defined(BOOST_UNORDERED_SSE2)
 
+#if 0
 struct group15
 {
   static constexpr int N=15;
@@ -261,12 +262,20 @@ private:
       0xF8F8F8F8u,0xF9F9F9F9u,0xFAFAFAFAu,0xFBFBFBFBu,0xFCFCFCFCu,0xFDFDFDFDu,0xFEFEFEFEu,0xFFFFFFFFu,
     };
 
+#if defined(__MSVC_RUNTIME_CHECKS)
+    return (int)word[hash&0xffu];
+#else
     return (int)word[(unsigned char)hash];
+#endif
   }
 
   inline static unsigned char reduced_hash(std::size_t hash)
   {
+#if defined(__MSVC_RUNTIME_CHECKS)
+    return match_word(hash)&0xffu;
+#else
     return (unsigned char)match_word(hash);
+#endif
   }
 
   inline unsigned char& at(std::size_t pos)
@@ -291,6 +300,157 @@ private:
 
   alignas(16) __m128i m;
 };
+#else
+struct group15
+{
+  static constexpr int N=15;
+
+  struct dummy_group_type
+  {
+    alignas(16) unsigned char storage[N+1]={0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0};
+  };
+
+  inline void initialize(){m=_mm_setzero_si128();}
+
+  inline void set(std::size_t pos,std::size_t hash)
+  {
+    BOOST_ASSERT(pos<N);
+    at(pos)=reduced_hash(hash+pos);
+  }
+
+  inline void set_sentinel()
+  {
+    at(N-1)=sentinel_;
+  }
+
+  inline bool is_sentinel(std::size_t pos)const
+  {
+    BOOST_ASSERT(pos<N);
+    return at(pos)==sentinel_;
+  }
+
+  inline void reset(std::size_t pos)
+  {
+    BOOST_ASSERT(pos<N);
+    at(pos)=available_;
+  }
+
+  static inline void reset(unsigned char* pc)
+  {
+    *pc=available_;
+  }
+
+  inline int match(std::size_t hash)const
+  {
+    return _mm_movemask_epi8(_mm_cmpeq_epi8(m,match_word(hash)))&0x7FFF;
+  }
+
+  inline bool is_not_overflowed(std::size_t hash)const
+  {
+    static constexpr unsigned char shift[]={1,2,4,8,16,32,64,128};
+
+    return !(overflow()&shift[hash%8]);
+  }
+
+  inline void mark_overflow(std::size_t hash)
+  {
+#if BOOST_WORKAROUND(BOOST_GCC, >= 50000 && BOOST_GCC < 60000)
+    overflow() = static_cast<unsigned char>( overflow() | static_cast<unsigned char>(1<<(hash%8)) );
+#else
+    overflow()|=static_cast<unsigned char>(1<<(hash%8));
+#endif
+  }
+
+  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-pos);
+  };
+
+  inline int match_available()const
+  {
+    return _mm_movemask_epi8(
+      _mm_cmpeq_epi8(m,_mm_setzero_si128()))&0x7FFF;
+  }
+
+  inline int match_occupied()const
+  {
+    return (~match_available())&0x7FFF;
+  }
+
+  inline int match_really_occupied()const /* excluding sentinel */
+  {
+    return at(N-1)==sentinel_?match_occupied()&0x3FFF:match_occupied();
+  }
+
+private:
+  static constexpr unsigned char available_=0,
+                                 sentinel_=1;
+
+  static constexpr unsigned char reduced_hash_table[]={
+    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,
+    64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,
+    80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,
+    96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,
+    112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,
+    128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,
+    144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,
+    160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,
+    176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,
+    192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,
+    208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,
+    224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,
+    240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
+    8,9,2,3,4,5,6,7,8,9,10,11,12,13,14,
+  };
+
+  inline static __m128i match_word(std::size_t hash)
+  {
+#if defined(__MSVC_RUNTIME_CHECKS)
+    return _mm_loadu_si128(reinterpret_cast<const __m128i*>(
+      reduced_hash_table+(hash&0xffu)));
+#else
+    return _mm_loadu_si128(reinterpret_cast<const __m128i*>(
+      reduced_hash_table+(unsigned char)(hash)));
+#endif
+  }
+
+  inline static unsigned char reduced_hash(std::size_t hash)
+  {
+#if defined(__MSVC_RUNTIME_CHECKS)
+    return reduced_hash_table[hash&0xffu];
+#else
+    return reduced_hash_table[(unsigned char)hash];
+#endif
+  }
+
+  inline unsigned char& at(std::size_t pos)
+  {
+    return reinterpret_cast<unsigned char*>(&m)[pos];
+  }
+
+  inline unsigned char at(std::size_t pos)const
+  {
+    return reinterpret_cast<const unsigned char*>(&m)[pos];
+  }
+
+  inline unsigned char& overflow()
+  {
+    return at(N);
+  }
+
+  inline unsigned char overflow()const
+  {
+    return at(N);
+  }
+
+  alignas(16) __m128i m;
+};
+#endif
 
 #elif defined(BOOST_UNORDERED_LITTLE_ENDIAN_NEON)
 
@@ -517,7 +677,11 @@ struct group15
     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;
+#if defined(__MSVC_RUNTIME_CHECKS)
+    boost::uint32_t y=(x|(x>>15)|(x>>30))&0xffffffffu;
+#else
     boost::uint32_t y=static_cast<boost::uint32_t>(x|(x>>15)|(x>>30));
+#endif
     return !pg->is_not_overflowed(y);
   };
 
@@ -532,7 +696,11 @@ struct group15
   inline int match_occupied()const
   {
     boost::uint64_t x=m[0]|m[1];
+#if defined(__MSVC_RUNTIME_CHECKS)
+    boost::uint32_t y=(x|(x>>32))&0xffffffffu;
+#else
     boost::uint32_t y=static_cast<boost::uint32_t>(x|(x>>32));
+#endif
     y|=y>>16;
     return y&0x7FFF;
   }
@@ -567,7 +735,11 @@ private:
       240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255,
     };
     
+#if defined(__MSVC_RUNTIME_CHECKS)
+  return table[hash&0xffu];
+#else
     return table[(unsigned char)hash];
+#endif
   }
 
   inline void set_impl(std::size_t pos,std::size_t n)
@@ -656,7 +828,6 @@ private:
  *     these values and positioning to be as uncorrelated as possible.
  */
 
-#if 0
 struct pow2_size_policy
 {
   static inline std::size_t size_index(std::size_t n)
@@ -680,47 +851,6 @@ struct pow2_size_policy
     return hash>>size_index_;
   }
 };
-#else
-struct pow2_size_policy
-{
-  static inline std::size_t size_index(std::size_t n)
-  {
-    // TODO: min size is 2, see if we can bring it down to 1 without loss
-    // of performance
-
-    std::size_t used_bits_=n<=2?1:((std::size_t)(boost::core::bit_width(n-1)));
-    std::size_t shift_right_=total_bits-used_bits_;
-    std::size_t shift_left_=shift_right_%2?0:shift_right_-8;
-
-    return (shift_left_<<16)|shift_right_;
-  }
-
-  static inline std::size_t size(std::size_t size_index_)
-  {
-    return std::size_t(1)<<(total_bits-shift_right(size_index_));
-  }
-    
-  static constexpr std::size_t min_size(){return 2;}
-
-  static inline std::size_t position(std::size_t hash,std::size_t size_index_)
-  {
-    return (hash<<shift_left(size_index_))>>shift_right(size_index_);
-  }
-
-private:
-  static constexpr std::size_t total_bits=sizeof(std::size_t)*CHAR_BIT;
-
-  static inline std::size_t shift_left(std::size_t size_index_)
-  {
-    return size_index_>>16;
-  }
-
-  static inline std::size_t shift_right(std::size_t size_index_)
-  {
-    return size_index_&0xffffu;
-  }
-};
-#endif
 
 /* size index of a group array for a given *element* capacity */
 
@@ -1036,6 +1166,7 @@ void swap_if(T&,T&){}
 
 inline void prefetch(const void* p)
 {
+  (void) p;
 #if defined(BOOST_GCC)||defined(BOOST_CLANG)
   __builtin_prefetch((const char*)p);
 #elif defined(BOOST_UNORDERED_SSE2)

include/boost/unordered/detail/prime_fmod.hpp

@@ -117,9 +117,15 @@ namespace boost {
 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
           std::size_t sizes_under_32bit = inv_sizes32_len;
           if (BOOST_LIKELY(size_index < sizes_under_32bit)) {
+#if defined(__MSVC_RUNTIME_CHECKS)
+            return fast_modulo(
+              boost::uint32_t(hash & 0xffffffffu) + boost::uint32_t(hash >> 32),
+              inv_sizes32[size_index], boost::uint32_t(sizes[size_index]));
+#else
             return fast_modulo(
               boost::uint32_t(hash) + boost::uint32_t(hash >> 32),
               inv_sizes32[size_index], boost::uint32_t(sizes[size_index]));
+#endif
           } else {
             return positions[size_index - sizes_under_32bit](hash);
           }

include/boost/unordered/unordered_flat_map.hpp

@@ -427,24 +427,24 @@ namespace boost {
           std::out_of_range("key was not found in unordered_flat_map"));
       }
 
-      mapped_type& operator[](key_type const& key)
+      BOOST_FORCEINLINE mapped_type& operator[](key_type const& key)
       {
         return table_.try_emplace(key).first->second;
       }
 
-      mapped_type& operator[](key_type&& key)
+      BOOST_FORCEINLINE mapped_type& operator[](key_type&& key)
       {
         return table_.try_emplace(std::move(key)).first->second;
       }
 
-      size_type count(key_type const& key) const
+      BOOST_FORCEINLINE size_type count(key_type const& key) const
       {
         auto pos = table_.find(key);
         return pos != table_.end() ? 1 : 0;
       }
 
       template <class K>
-      typename std::enable_if<
+      BOOST_FORCEINLINE typename std::enable_if<
         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
       count(K const& key) const
       {
@@ -480,13 +480,13 @@ namespace boost {
         return table_.find(key);
       }
 
-      bool contains(key_type const& key) const
+      BOOST_FORCEINLINE bool contains(key_type const& key) const
       {
         return this->find(key) != this->end();
       }
 
       template <class K>
-      typename std::enable_if<
+      BOOST_FORCEINLINE typename std::enable_if<
         boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
         bool>::type
       contains(K const& key) const

include/boost/unordered/unordered_flat_set.hpp

@@ -313,14 +313,14 @@ namespace boost {
       /// Lookup
       ///
 
-      size_type count(key_type const& key) const
+      BOOST_FORCEINLINE size_type count(key_type const& key) const
       {
         auto pos = table_.find(key);
         return pos != table_.end() ? 1 : 0;
       }
 
       template <class K>
-      typename std::enable_if<
+      BOOST_FORCEINLINE typename std::enable_if<
         detail::are_transparent<K, hasher, key_equal>::value, size_type>::type
       count(K const& key) const
       {
@@ -356,13 +356,13 @@ namespace boost {
         return table_.find(key);
       }
 
-      bool contains(key_type const& key) const
+      BOOST_FORCEINLINE bool contains(key_type const& key) const
       {
         return this->find(key) != this->end();
       }
 
       template <class K>
-      typename std::enable_if<
+      BOOST_FORCEINLINE typename std::enable_if<
         boost::unordered::detail::are_transparent<K, hasher, key_equal>::value,
         bool>::type
       contains(K const& key) const

test/unordered/prime_fmod_tests.cpp

@@ -21,8 +21,7 @@ void macros_test()
     BOOST_ERROR("std::numeric_limits<size_t>::digits >= 64, but "
                 "BOOST_UNORDERED_FCA_HAS_64B_SIZE_T is not defined");
 #endif
-  }
-  else {
+  } else {
 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
     BOOST_ERROR("std::numeric_limits<size_t>::digits < 64, but "
                 "BOOST_UNORDERED_FCA_HAS_64B_SIZE_T is defined");
@@ -155,7 +154,7 @@ void get_remainder_test()
 
   for (std::size_t i = 0; i < 1000000u; ++i) {
     boost::uint64_t f = rng();
-    boost::uint32_t d = static_cast<uint32_t>(rng());
+    boost::uint32_t d = rng() & 0xffffffffu;
 
     boost::uint64_t r1 =
       boost::unordered::detail::prime_fmod_size<>::get_remainder(f, d);
@@ -180,14 +179,14 @@ void modulo_test()
   boost::detail::splitmix64 rng;
 
   for (std::size_t i = 0; i < 1000000u; ++i) {
-    std::size_t hash = static_cast<std::size_t>(rng());
+    std::size_t hash = static_cast<std::size_t>(-1) & rng();
 
     for (std::size_t j = 0; j < sizes_len; ++j) {
       std::size_t h = hash;
 
 #if defined(BOOST_UNORDERED_FCA_HAS_64B_SIZE_T)
       if (sizes[j] <= UINT_MAX) {
-        h = boost::uint32_t(h) + boost::uint32_t(h >> 32);
+        h = boost::uint32_t(h & 0xffffffffu) + boost::uint32_t(h >> 32);
       }
 #endif
       std::size_t p1 =