Add hash_integral_test2.cpp

.github/workflows/ci.yml

@@ -58,7 +58,7 @@ jobs:
             install: g++-11-multilib
             address-model: 32,64
           - toolset: gcc-12
-            cxxstd: "03,11,14,17,20"
+            cxxstd: "03,11,14,17,20,2b"
             os: ubuntu-22.04
             install: g++-12-multilib
             address-model: 32,64
@@ -111,12 +111,12 @@ jobs:
             os: ubuntu-20.04
           - toolset: clang
             compiler: clang++-13
-            cxxstd: "03,11,14,17,20"
+            cxxstd: "03,11,14,17,20,2b"
             os: ubuntu-22.04
             install: clang-13
           - toolset: clang
             compiler: clang++-14
-            cxxstd: "03,11,14,17,20"
+            cxxstd: "03,11,14,17,20,2b"
             os: ubuntu-22.04
             install: clang-14
           - toolset: clang

benchmark/.gitignore

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

benchmark/unordered.cpp

@@ -3,12 +3,19 @@
 // https://www.boost.org/LICENSE_1_0.txt
 
 #define _CRT_SECURE_NO_WARNINGS
+#define _SILENCE_CXX20_CISO646_REMOVED_WARNING
 
 #include <boost/container_hash/hash.hpp>
 #include <boost/unordered_set.hpp>
 #include <boost/core/detail/splitmix64.hpp>
 #include <boost/core/type_name.hpp>
 #include <boost/config.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/hash/hash.h"
+#endif
+#ifdef HAVE_MULXP_HASH
+# include "mulxp_hash.hpp"
+#endif
 #include <cstddef>
 #include <cstdio>
 #include <cstdint>
@@ -19,10 +26,8 @@
 
 // mul31_hash
 
-class mul31_hash
+struct mul31_hash
 {
-public:
-
     std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
     {
         char const * p = st.data();
@@ -43,18 +48,20 @@ public:
     }
 };
 
-// mul31_unrolled_hash
+// mul31_x4_hash
 
-template<int Bits> struct mul31_unrolled_hash_impl;
-
-template<> struct mul31_unrolled_hash_impl<32>
+struct mul31_x4_hash
 {
     std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
     {
         char const * p = st.data();
         std::size_t n = st.size();
 
+#if SIZE_MAX > UINT32_MAX
+        std::size_t h = 0xCBF29CE484222325ull;
+#else
         std::size_t h = 0x811C9DC5u;
+#endif
 
         while( n >= 4 )
         {
@@ -80,14 +87,20 @@ template<> struct mul31_unrolled_hash_impl<32>
     }
 };
 
-template<> struct mul31_unrolled_hash_impl<64>
+// mul31_x8_hash
+
+struct mul31_x8_hash
 {
     std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
     {
         char const * p = st.data();
         std::size_t n = st.size();
 
-        std::size_t h = 0xCBF29CE484222325ull;
+#if SIZE_MAX > UINT32_MAX
+        boost::uint64_t h = 0xCBF29CE484222325ull;
+#else
+        boost::uint64_t h = 0x811C9DC5u;
+#endif
 
         while( n >= 8 )
         {
@@ -113,12 +126,10 @@ template<> struct mul31_unrolled_hash_impl<64>
             --n;
         }
 
-        return h;
+        return static_cast<std::size_t>( h );
     }
 };
 
-struct mul31_unrolled_hash: mul31_unrolled_hash_impl< std::numeric_limits<std::size_t>::digits > {};
-
 // fnv1a_hash
 
 template<int Bits> struct fnv1a_hash_impl;
@@ -163,28 +174,52 @@ template<> struct fnv1a_hash_impl<64>
 
 struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits > {};
 
-// old_boost_hash
+// mulxp_hash
 
-class old_boost_hash
+#ifdef HAVE_MULXP_HASH
+
+struct mulxp0_hash_
 {
-public:
-
     std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
     {
-        char const * p = st.data();
-        std::size_t n = st.size();
-
-        std::size_t h = 0;
-
-        for( std::size_t i = 0; i < n; ++i )
-        {
-            h ^= static_cast<unsigned char>( p[i] ) + 0x9e3779b9 + ( h << 6 ) + ( h >> 2 );
-        }
-
-        return h;
+        return mulxp0_hash( (unsigned char const*)st.data(), st.size(), 0 );
     }
 };
 
+struct mulxp1_hash_
+{
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp1_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp2_hash_
+{
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp2_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash_
+{
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp3_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash32_
+{
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp3_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+#endif
+
 // test_hash_speed
 
 template<class H, class V> void test_hash_speed( int N, V const& v )
@@ -210,11 +245,11 @@ template<class H, class V> void test_hash_speed( int N, V const& v )
 
 #if defined( _MSC_VER )
 
-    std::printf( "%25s : q=%20Iu, %lld ms\n", hash.c_str(), q, ms1 );
+    std::printf( "%53s : q=%20Iu, %lld ms\n", hash.c_str(), q, ms1 );
 
 #else
 
-    std::printf( "%25s : q=%20zu, %lld ms\n", hash.c_str(), q, ms1 );
+    std::printf( "%53s : q=%20zu, %lld ms\n", hash.c_str(), q, ms1 );
 
 #endif
 }
@@ -235,11 +270,11 @@ template<class H, class V> void test_hash_collision( int N, V const& v, std::siz
 
 #if defined( _MSC_VER )
 
-    std::printf( "%25s : c=%Iu\n", hash.c_str(), n - s.size() );
+    std::printf( "%53s : c=%Iu\n", hash.c_str(), n - s.size() );
 
 #else
 
-    std::printf( "%25s : c=%zu\n", hash.c_str(), n - s.size() );
+    std::printf( "%53s : c=%zu\n", hash.c_str(), n - s.size() );
 
 #endif
 }
@@ -292,11 +327,11 @@ template<class V, class S> void test4( int N, V const& v, char const * hash, S s
 
 #if defined( _MSC_VER )
 
-    std::printf( "%25s : n=%Iu, m=%Iu, c=%Iu, q=%Iu, %lld + %lld ms\n", hash, n, m, c, q, ms1, ms2 );
+    std::printf( "%53s : n=%Iu, m=%Iu, c=%Iu, q=%Iu, %4lld + %4lld = %4lld ms\n", hash, n, m, c, q, ms1, ms2, ms1 + ms2 );
 
 #else
 
-    std::printf( "%25s : n=%zu, m=%zu, c=%zu, q=%zu, %lld + %lld ms\n", hash, n, m, c, q, ms1, ms2 );
+    std::printf( "%53s : n=%zu, m=%zu, c=%zu, q=%zu, %4lld + %4lld = %4lld ms\n", hash, n, m, c, q, ms1, ms2, ms1 + ms2 );
 
 #endif
 }
@@ -340,11 +375,21 @@ int main()
     std::puts( "Hash speed test:\n" );
 
     test_hash_speed<mul31_hash>( N * 16, v );
-    test_hash_speed<mul31_unrolled_hash>( N * 16, v );
+    test_hash_speed<mul31_x4_hash>( N * 16, v );
+    test_hash_speed<mul31_x8_hash>( N * 16, v );
     test_hash_speed<fnv1a_hash>( N * 16, v );
-    test_hash_speed<old_boost_hash>( N * 16, v );
     test_hash_speed<boost::hash<std::string> >( N * 16, v );
     test_hash_speed<std::hash<std::string> >( N * 16, v );
+#ifdef HAVE_ABSEIL
+    test_hash_speed<absl::Hash<std::string> >( N * 16, v );
+#endif
+#ifdef HAVE_MULXP_HASH
+    test_hash_speed<mulxp0_hash_>( N * 16, v );
+    test_hash_speed<mulxp1_hash_>( N * 16, v );
+    test_hash_speed<mulxp2_hash_>( N * 16, v );
+    test_hash_speed<mulxp3_hash_>( N * 16, v );
+    test_hash_speed<mulxp3_hash32_>( N * 16, v );
+#endif
 
     std::puts( "" );
 
@@ -365,11 +410,21 @@ int main()
         }
 
         test_hash_collision<mul31_hash>( N * 16, v, n );
-        test_hash_collision<mul31_unrolled_hash>( N * 16, v, n );
+        test_hash_collision<mul31_x4_hash>( N * 16, v, n );
+        test_hash_collision<mul31_x8_hash>( N * 16, v, n );
         test_hash_collision<fnv1a_hash>( N * 16, v, n );
-        test_hash_collision<old_boost_hash>( N * 16, v, n );
         test_hash_collision<boost::hash<std::string> >( N * 16, v, n );
         test_hash_collision<std::hash<std::string> >( N * 16, v, n );
+#ifdef HAVE_ABSEIL
+        test_hash_collision<absl::Hash<std::string> >( N * 16, v, n );
+#endif
+#ifdef HAVE_MULXP_HASH
+        test_hash_collision<mulxp0_hash_>( N * 16, v, n );
+        test_hash_collision<mulxp1_hash_>( N * 16, v, n );
+        test_hash_collision<mulxp2_hash_>( N * 16, v, n );
+        test_hash_collision<mulxp3_hash_>( N * 16, v, n );
+        test_hash_collision<mulxp3_hash32_>( N * 16, v, n );
+#endif
     }
 
     std::puts( "" );
@@ -379,11 +434,27 @@ int main()
     std::puts( "Container speed test:\n" );
 
     test_container_speed<K, mul31_hash>( N, v );
-    test_container_speed<K, mul31_unrolled_hash>( N, v );
+    test_container_speed<K, mul31_x4_hash>( N, v );
+    test_container_speed<K, mul31_x8_hash>( N, v );
     test_container_speed<K, fnv1a_hash>( N, v );
-    test_container_speed<K, old_boost_hash>( N, v );
     test_container_speed<K, boost::hash<std::string> >( N, v );
     test_container_speed<K, std::hash<std::string> >( N, v );
+#ifdef HAVE_ABSEIL
+    test_container_speed<K, absl::Hash<std::string> >( N, v );
+#endif
+#ifdef HAVE_MULXP_HASH
+    test_container_speed<K, mulxp0_hash_>( N, v );
+    test_container_speed<K, mulxp1_hash_>( N, v );
+    test_container_speed<K, mulxp2_hash_>( N, v );
+    test_container_speed<K, mulxp3_hash_>( N, v );
+    test_container_speed<K, mulxp3_hash32_>( N, v );
+#endif
 
     std::puts( "" );
 }
+
+#ifdef HAVE_ABSEIL
+# include "absl/hash/internal/hash.cc"
+# include "absl/hash/internal/low_level_hash.cc"
+# include "absl/hash/internal/city.cc"
+#endif

benchmark/unordered_flat.cpp

@@ -0,0 +1,495 @@
+// Copyright 2021 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/unordered_flat_map.hpp>
+#include <boost/core/detail/splitmix64.hpp>
+#include <boost/config.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/hash/hash.h"
+#endif
+#ifdef HAVE_MULXP_HASH
+# include "mulxp_hash.hpp"
+#endif
+#include <vector>
+#include <memory>
+#include <cstdint>
+#include <iostream>
+#include <iomanip>
+#include <chrono>
+
+using namespace std::chrono_literals;
+
+static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::uint32_t s, std::size_t size )
+{
+    auto t2 = std::chrono::steady_clock::now();
+
+    std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n";
+
+    t1 = t2;
+}
+
+constexpr unsigned N = 2'000'000;
+constexpr int K = 10;
+
+static std::vector<std::string> indices1, indices2;
+
+static std::string make_index( unsigned x )
+{
+    char buffer[ 64 ];
+    std::snprintf( buffer, sizeof(buffer), "pfx_%u_sfx", x );
+
+    return buffer;
+}
+
+static std::string make_random_index( unsigned x )
+{
+    char buffer[ 64 ];
+    std::snprintf( buffer, sizeof(buffer), "pfx_%0*d_%u_sfx", x % 8 + 1, 0, x );
+
+    return buffer;
+}
+
+static void init_indices()
+{
+    indices1.reserve( N*2+1 );
+    indices1.push_back( make_index( 0 ) );
+
+    for( unsigned i = 1; i <= N*2; ++i )
+    {
+        indices1.push_back( make_index( i ) );
+    }
+
+    indices2.reserve( N*2+1 );
+    indices2.push_back( make_index( 0 ) );
+
+    {
+        boost::detail::splitmix64 rng;
+
+        for( unsigned i = 1; i <= N*2; ++i )
+        {
+            indices2.push_back( make_random_index( static_cast<std::uint32_t>( rng() ) ) );
+        }
+    }
+}
+
+template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.insert( { indices1[ i ], i } );
+    }
+
+    print_time( t1, "Consecutive insert",  0, map.size() );
+
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.insert( { indices2[ i ], i } );
+    }
+
+    print_time( t1, "Random insert",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    std::uint32_t s;
+    
+    s = 0;
+
+    for( int j = 0; j < K; ++j )
+    {
+        for( unsigned i = 1; i <= N * 2; ++i )
+        {
+            auto it = map.find( indices1[ i ] );
+            if( it != map.end() ) s += it->second;
+        }
+    }
+
+    print_time( t1, "Consecutive lookup",  s, map.size() );
+
+    s = 0;
+
+    for( int j = 0; j < K; ++j )
+    {
+        for( unsigned i = 1; i <= N * 2; ++i )
+        {
+            auto it = map.find( indices2[ i ] );
+            if( it != map.end() ) s += it->second;
+        }
+    }
+
+    print_time( t1, "Random lookup",  s, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    auto it = map.begin();
+
+    while( it != map.end() )
+    {
+        if( it->second & 1 )
+        {
+            if constexpr( std::is_void_v< decltype( map.erase( it ) ) > )
+            {
+                map.erase( it++ );
+            }
+            else
+            {
+                it = map.erase( it );
+            }
+        }
+        else
+        {
+            ++it;
+        }
+    }
+
+    print_time( t1, "Iterate and erase odd elements",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::steady_clock::time_point & t1 )
+{
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.erase( indices1[ i ] );
+    }
+
+    print_time( t1, "Consecutive erase",  0, map.size() );
+
+    for( unsigned i = 1; i <= N; ++i )
+    {
+        map.erase( indices2[ i ] );
+    }
+
+    print_time( t1, "Random erase",  0, map.size() );
+
+    std::cout << std::endl;
+}
+
+//
+
+struct record
+{
+    std::string label_;
+    long long time_;
+};
+
+static std::vector<record> times;
+
+template<class Hash> BOOST_NOINLINE void test( char const* label )
+{
+    std::cout << label << ":\n\n";
+
+    boost::unordered_flat_map<std::string, std::uint32_t, Hash> map;
+
+    auto t0 = std::chrono::steady_clock::now();
+    auto t1 = t0;
+
+    test_insert( map, t1 );
+
+    record rec = { label, 0 };
+
+    test_lookup( map, t1 );
+    test_iteration( map, t1 );
+    test_lookup( map, t1 );
+    test_erase( map, t1 );
+
+    auto tN = std::chrono::steady_clock::now();
+    std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
+
+    rec.time_ = ( tN - t0 ) / 1ms;
+    times.push_back( rec );
+}
+
+// mul31_hash
+
+struct mul31_hash
+{
+    // not avalanching
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        char const * p = st.data();
+        std::size_t n = st.size();
+
+#if SIZE_MAX > UINT32_MAX
+        std::size_t h = 0xCBF29CE484222325ull;
+#else
+        std::size_t h = 0x811C9DC5u;
+#endif
+
+        for( std::size_t i = 0; i < n; ++i )
+        {
+            h = h * 31 + static_cast<unsigned char>( p[i] );
+        }
+
+        return h;
+    }
+};
+
+// mul31_x4_hash
+
+struct mul31_x4_hash
+{
+    // not avalanching
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        char const * p = st.data();
+        std::size_t n = st.size();
+
+#if SIZE_MAX > UINT32_MAX
+        std::size_t h = 0xCBF29CE484222325ull;
+#else
+        std::size_t h = 0x811C9DC5u;
+#endif
+
+        while( n >= 4 )
+        {
+            h = h * (31u * 31u * 31u * 31u)
+                + static_cast<unsigned char>( p[0] ) * (31u * 31u * 31u)
+                + static_cast<unsigned char>( p[1] ) * (31u * 31u)
+                + static_cast<unsigned char>( p[2] ) * 31u
+                + static_cast<unsigned char>( p[3] );
+
+            p += 4;
+            n -= 4;
+        }
+
+        while( n > 0 )
+        {
+            h = h * 31u + static_cast<unsigned char>( *p );
+
+            ++p;
+            --n;
+        }
+
+        return h;
+    }
+};
+
+// mul31_x8_hash
+
+struct mul31_x8_hash
+{
+    // not avalanching
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        char const * p = st.data();
+        std::size_t n = st.size();
+
+#if SIZE_MAX > UINT32_MAX
+        boost::uint64_t h = 0xCBF29CE484222325ull;
+#else
+        boost::uint64_t h = 0x811C9DC5u;
+#endif
+
+        while( n >= 8 )
+        {
+            h = h * (31ull * 31ull * 31ull * 31ull * 31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[0] ) * (31ull * 31ull * 31ull * 31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[1] ) * (31ull * 31ull * 31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[2] ) * (31ull * 31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[3] ) * (31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[4] ) * (31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[5] ) * (31ull * 31ull)
+                + static_cast<unsigned char>( p[6] ) * 31ull
+                + static_cast<unsigned char>( p[7] );
+
+            p += 8;
+            n -= 8;
+        }
+
+        while( n > 0 )
+        {
+            h = h * 31u + static_cast<unsigned char>( *p );
+
+            ++p;
+            --n;
+        }
+
+        return static_cast<std::size_t>( h );
+    }
+};
+
+// fnv1a_hash
+
+template<int Bits> struct fnv1a_hash_impl;
+
+template<> struct fnv1a_hash_impl<32>
+{
+    std::size_t operator()( std::string 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 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;
+};
+
+// std_hash
+
+struct std_hash: std::hash<std::string>
+{
+    using is_avalanching = void;
+};
+
+// absl_hash
+
+#ifdef HAVE_ABSEIL
+
+struct absl_hash: absl::Hash<std::string>
+{
+    using is_avalanching = void;
+};
+
+#endif
+
+// mulxp_hash
+
+#ifdef HAVE_MULXP_HASH
+
+struct mulxp0_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp0_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp1_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp1_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp2_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp2_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp3_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash32_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string const& st ) const BOOST_NOEXCEPT
+    {
+        std::size_t r = mulxp3_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+
+#if SIZE_MAX > UINT32_MAX
+
+        r |= r << 32;
+
+#endif
+
+        return r;
+    }
+};
+
+#endif
+
+//
+
+int main()
+{
+    init_indices();
+
+    test< boost::hash<std::string> >( "boost::hash" );
+    test< std_hash >( "std::hash" );
+    test< mul31_hash >( "mul31_hash" );
+    test< mul31_x4_hash >( "mul31_x4_hash" );
+    test< mul31_x8_hash >( "mul31_x8_hash" );
+    test< fnv1a_hash >( "fnv1a_hash" );
+
+#ifdef HAVE_ABSEIL
+
+    test< absl_hash >( "absl::Hash" );
+
+#endif
+
+#ifdef HAVE_MULXP_HASH
+
+    test< mulxp0_hash_ >( "mulxp0_hash" );
+    test< mulxp1_hash_ >( "mulxp1_hash" );
+    test< mulxp2_hash_ >( "mulxp2_hash" );
+    test< mulxp3_hash_ >( "mulxp3_hash" );
+    test< mulxp3_hash32_ >( "mulxp3_hash32" );
+
+#endif
+
+    std::cout << "---\n\n";
+
+    for( auto const& x: times )
+    {
+        std::cout << std::setw( 22 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms\n";
+    }
+}
+
+#ifdef HAVE_ABSEIL
+# include "absl/hash/internal/hash.cc"
+# include "absl/hash/internal/low_level_hash.cc"
+# include "absl/hash/internal/city.cc"
+#endif

benchmark/word_count.cpp

@@ -0,0 +1,420 @@
+// Copyright 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/unordered_flat_map.hpp>
+#ifdef HAVE_ABSEIL
+# include "absl/hash/hash.h"
+#endif
+#ifdef HAVE_MULXP_HASH
+# include "mulxp_hash.hpp"
+#endif
+#include <boost/regex.hpp>
+#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::uint32_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;
+}
+
+//
+
+struct record
+{
+    std::string label_;
+    long long time_;
+};
+
+static std::vector<record> times;
+
+template<class Hash> BOOST_NOINLINE void test( char const* label )
+{
+    std::cout << label << ":\n\n";
+
+    boost::unordered_flat_map<std::string_view, std::size_t, Hash> map;
+
+    auto t0 = std::chrono::steady_clock::now();
+    auto t1 = t0;
+
+    test_word_count( map, t1 );
+
+    record rec = { label, 0 };
+
+    test_contains( map, t1 );
+    test_count( 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 );
+}
+
+// mul31_hash
+
+struct mul31_hash
+{
+    // not avalanching
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        char const * p = st.data();
+        std::size_t n = st.size();
+
+#if SIZE_MAX > UINT32_MAX
+        std::size_t h = 0xCBF29CE484222325ull;
+#else
+        std::size_t h = 0x811C9DC5u;
+#endif
+
+        for( std::size_t i = 0; i < n; ++i )
+        {
+            h = h * 31 + static_cast<unsigned char>( p[i] );
+        }
+
+        return h;
+    }
+};
+
+// mul31_x4_hash
+
+struct mul31_x4_hash
+{
+    // not avalanching
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        char const * p = st.data();
+        std::size_t n = st.size();
+
+#if SIZE_MAX > UINT32_MAX
+        std::size_t h = 0xCBF29CE484222325ull;
+#else
+        std::size_t h = 0x811C9DC5u;
+#endif
+
+        while( n >= 4 )
+        {
+            h = h * (31u * 31u * 31u * 31u)
+                + static_cast<unsigned char>( p[0] ) * (31u * 31u * 31u)
+                + static_cast<unsigned char>( p[1] ) * (31u * 31u)
+                + static_cast<unsigned char>( p[2] ) * 31u
+                + static_cast<unsigned char>( p[3] );
+
+            p += 4;
+            n -= 4;
+        }
+
+        while( n > 0 )
+        {
+            h = h * 31u + static_cast<unsigned char>( *p );
+
+            ++p;
+            --n;
+        }
+
+        return h;
+    }
+};
+
+// mul31_x8_hash
+
+struct mul31_x8_hash
+{
+    // not avalanching
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        char const * p = st.data();
+        std::size_t n = st.size();
+
+#if SIZE_MAX > UINT32_MAX
+        boost::uint64_t h = 0xCBF29CE484222325ull;
+#else
+        boost::uint64_t h = 0x811C9DC5u;
+#endif
+
+        while( n >= 8 )
+        {
+            h = h * (31ull * 31ull * 31ull * 31ull * 31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[0] ) * (31ull * 31ull * 31ull * 31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[1] ) * (31ull * 31ull * 31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[2] ) * (31ull * 31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[3] ) * (31ull * 31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[4] ) * (31ull * 31ull * 31ull)
+                + static_cast<unsigned char>( p[5] ) * (31ull * 31ull)
+                + static_cast<unsigned char>( p[6] ) * 31ull
+                + static_cast<unsigned char>( p[7] );
+
+            p += 8;
+            n -= 8;
+        }
+
+        while( n > 0 )
+        {
+            h = h * 31u + static_cast<unsigned char>( *p );
+
+            ++p;
+            --n;
+        }
+
+        return static_cast<std::size_t>( h );
+    }
+};
+
+// 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;
+};
+
+// std_hash
+
+struct std_hash: std::hash<std::string_view>
+{
+    using is_avalanching = void;
+};
+
+// absl_hash
+
+#ifdef HAVE_ABSEIL
+
+struct absl_hash: absl::Hash<std::string_view>
+{
+    using is_avalanching = void;
+};
+
+#endif
+
+#ifdef HAVE_MULXP_HASH
+
+struct mulxp0_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp0_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp1_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp1_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp2_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp2_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        return mulxp3_hash( (unsigned char const*)st.data(), st.size(), 0 );
+    }
+};
+
+struct mulxp3_hash32_
+{
+    using is_avalanching = void;
+
+    std::size_t operator()( std::string_view const& st ) const BOOST_NOEXCEPT
+    {
+        std::size_t r = mulxp3_hash32( (unsigned char const*)st.data(), st.size(), 0 );
+
+#if SIZE_MAX > UINT32_MAX
+
+        r |= r << 32;
+
+#endif
+
+        return r;
+    }
+};
+
+#endif
+
+//
+
+int main()
+{
+    init_words();
+
+    test< boost::hash<std::string_view> >( "boost::hash" );
+    test< std_hash >( "std::hash" );
+    test< mul31_hash >( "mul31_hash" );
+    test< mul31_x4_hash >( "mul31_x4_hash" );
+    test< mul31_x8_hash >( "mul31_x8_hash" );
+    test< fnv1a_hash >( "fnv1a_hash" );
+
+#ifdef HAVE_ABSEIL
+
+    test< absl_hash >( "absl::Hash" );
+
+#endif
+
+#ifdef HAVE_MULXP_HASH
+
+    test< mulxp0_hash_ >( "mulxp0_hash" );
+    test< mulxp1_hash_ >( "mulxp1_hash" );
+    test< mulxp2_hash_ >( "mulxp2_hash" );
+    test< mulxp3_hash_ >( "mulxp3_hash" );
+    test< mulxp3_hash32_ >( "mulxp3_hash32" );
+
+#endif
+
+    std::cout << "---\n\n";
+
+    for( auto const& x: times )
+    {
+        std::cout << std::setw( 22 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms\n";
+    }
+}
+
+#ifdef HAVE_ABSEIL
+# include "absl/hash/internal/hash.cc"
+# include "absl/hash/internal/low_level_hash.cc"
+# include "absl/hash/internal/city.cc"
+#endif

include/boost/container_hash/hash.hpp

@@ -27,6 +27,7 @@
 #include <boost/type_traits/enable_if.hpp>
 #include <boost/type_traits/conjunction.hpp>
 #include <boost/type_traits/is_union.hpp>
+#include <boost/type_traits/is_same.hpp>
 #include <boost/describe/bases.hpp>
 #include <boost/describe/members.hpp>
 #include <boost/cstdint.hpp>
@@ -494,6 +495,19 @@ namespace boost
         return seed;
     }
 
+#endif
+
+    // std::nullptr_t
+
+#if !defined(BOOST_NO_CXX11_NULLPTR)
+
+    template <typename T>
+    typename boost::enable_if_<boost::is_same<T, std::nullptr_t>::value, std::size_t>::type
+        hash_value( T const& /*v*/ )
+    {
+        return boost::hash_value( static_cast<void*>( nullptr ) );
+    }
+
 #endif
 
     // std::optional

test/Jamfile.v2

@@ -115,3 +115,7 @@ run described_class_test.cpp
 
 run hash_is_avalanching_test.cpp ;
 run hash_is_avalanching_test2.cpp ;
+
+run hash_integral_test2.cpp ;
+
+run hash_nullptr_test.cpp ;

test/hash_complex_test.cpp

@@ -3,6 +3,8 @@
 // Distributed under the Boost Software License, Version 1.0. (See accompanying
 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 
+#define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING
+
 #include "./config.hpp"
 
 #if !defined(BOOST_HASH_TEST_EXTENSIONS)

test/hash_integral_test.cpp

@@ -7,7 +7,7 @@
 #include <boost/core/lightweight_test.hpp>
 #include <boost/core/type_name.hpp>
 #include <boost/type_traits/is_signed.hpp>
-#include <set>
+#include <boost/config.hpp>
 
 #if defined(BOOST_MSVC)
 #pragma warning(disable: 4127) // conditional expression is constant

test/hash_integral_test2.cpp

@@ -0,0 +1,52 @@
+// Copyright 2005-2009 Daniel James.
+// Copyright 2021 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#include <boost/container_hash/hash.hpp>
+#include <boost/core/lightweight_test.hpp>
+#include <boost/core/type_name.hpp>
+#include <boost/type_traits/is_signed.hpp>
+#include <boost/type_traits/make_unsigned.hpp>
+#include <boost/static_assert.hpp>
+#include <boost/config.hpp>
+
+// This test checks that values representable in a signed
+// and the corresponding unsigned type hash to the same value
+
+template<class T>
+void signed_unsigned_test()
+{
+    BOOST_STATIC_ASSERT( boost::is_signed<T>::value );
+
+    typedef typename boost::make_unsigned<T>::type U;
+
+    T x = std::numeric_limits<T>::max();
+
+    do
+    {
+        BOOST_TEST_EQ( boost::hash<T>()( x ), boost::hash<U>()( static_cast<U>( x ) ) );
+        x /= 3;
+    }
+    while( x > 0 );
+}
+
+#define TEST(type) std::cerr << "Testing: " #type " (" << boost::core::type_name<type>() << ")\n"; signed_unsigned_test<type>();
+
+int main()
+{
+    TEST(signed char)
+    TEST(short)
+    TEST(int)
+    TEST(long)
+
+#if !defined(BOOST_NO_LONG_LONG)
+    TEST(boost::long_long_type)
+#endif
+
+#if defined(BOOST_HAS_INT128)
+    TEST(boost::int128_type)
+#endif
+
+    return boost::report_errors();
+}

test/hash_is_avalanching_test.cpp

@@ -4,22 +4,8 @@
 
 #include <boost/container_hash/hash.hpp>
 #include <boost/core/lightweight_test_trait.hpp>
-#include <boost/config.hpp>
-#include <boost/config/pragma_message.hpp>
-
-#if defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
-
-BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_HDR_TYPE_TRAITS is defined" )
-int main() {}
-
-#elif defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
-
-BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_TEMPLATE_ALIASES is defined" )
-int main() {}
-
-#else
-
 #include <boost/unordered/hash_traits.hpp>
+#include <boost/config.hpp>
 #include <string>
 
 enum my_char { min = 0, max = 255 };
@@ -53,5 +39,3 @@ int main()
 
     return boost::report_errors();
 }
-
-#endif

test/hash_is_avalanching_test2.cpp

@@ -7,17 +7,7 @@
 #include <boost/config.hpp>
 #include <boost/config/pragma_message.hpp>
 
-#if defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
-
-BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_HDR_TYPE_TRAITS is defined" )
-int main() {}
-
-#elif defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
-
-BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_TEMPLATE_ALIASES is defined" )
-int main() {}
-
-#elif defined(BOOST_NO_CXX17_HDR_STRING_VIEW)
+#if defined(BOOST_NO_CXX17_HDR_STRING_VIEW)
 
 BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX17_HDR_STRING_VIEW is defined" )
 int main() {}

test/hash_nullptr_test.cpp

@@ -0,0 +1,41 @@
+// Copyright 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#include <boost/container_hash/hash.hpp>
+#include <boost/core/lightweight_test.hpp>
+#include <boost/config.hpp>
+#include <boost/config/pragma_message.hpp>
+#include <cstddef>
+
+#if defined(BOOST_NO_CXX11_NULLPTR)
+
+BOOST_PRAGMA_MESSAGE( "Test skipped, BOOST_NO_CXX11_NULLPTR is defined" )
+int main() {}
+
+#else
+
+template<class T> std::size_t hv( T const& x )
+{
+    return boost::hash<T>()( x );
+}
+
+int main()
+{
+    {
+        BOOST_TEST_EQ( hv((void*)0), hv(nullptr) );
+    }
+
+    {
+        int x = 0;
+
+        BOOST_TEST_EQ( hv((int*)0), hv(nullptr) );
+        BOOST_TEST_NE( hv(&x), hv(nullptr) );
+
+        (void)x;
+    }
+
+    return boost::report_errors();
+}
+
+#endif