Merge pull request #165 from cmazakas/fix/msvc-rtc

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/string.cpp

@@ -6,9 +6,6 @@
 
 #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
@@ -267,24 +264,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> >;
@@ -384,14 +363,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 =
@@ -428,12 +399,9 @@ 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_ABSEIL
 
@@ -454,14 +422,11 @@ int main()
     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_ABSEIL
 

benchmark/string_view.cpp

@@ -6,9 +6,6 @@
 
 #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
@@ -268,24 +265,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> >;
@@ -385,14 +364,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 =
@@ -429,12 +400,9 @@ 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_ABSEIL
 
@@ -455,14 +423,11 @@ int main()
     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_ABSEIL
 

benchmark/uint32.cpp

@@ -6,9 +6,6 @@
 
 #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>
@@ -284,24 +281,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> >;
@@ -352,7 +331,6 @@ 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
 

benchmark/uint64.cpp

@@ -6,9 +6,6 @@
 
 #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>
@@ -284,24 +281,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> >;
@@ -352,7 +331,6 @@ 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
 

benchmark/uuid.cpp

@@ -6,9 +6,6 @@
 
 #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>
@@ -329,24 +326,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> >;
@@ -377,7 +356,6 @@ 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
 

benchmark/word_count.cpp

@@ -0,0 +1,339 @@
+// 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
+#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()
+{
+    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
+
+    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
+
+// 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
+
+//
+
+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_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_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( 35 ) << ( 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,213 @@
+// 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/regex.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>
+#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()
+{
+    char const* fn = "enwik9"; // http://mattmahoney.net/dc/textdata
+
+    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
+
+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_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

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

@@ -261,12 +261,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)
@@ -517,7 +525,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 +544,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 +583,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 +676,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 +699,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 +1014,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 =