Update appveyor.yml

.appveyor.yml

@@ -29,6 +29,10 @@ environment:
       TOOLSET: msvc-14.2
       CXXSTD: 14,17,latest
       ADDRMD: 32,64
+    - APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2017
+      TOOLSET: clang-win
+      ADDRMD: 64
+      CXXSTD: 14,17,latest
     - APPVEYOR_BUILD_WORKER_IMAGE: Visual Studio 2019
       TOOLSET: clang-win
       CXXSTD: 14,17,latest

.github/workflows/ci.yml

@@ -233,6 +233,7 @@ jobs:
         include:
           - os: ubuntu-18.04
           - os: ubuntu-20.04
+          - os: ubuntu-22.04
           - os: macos-10.15
 
     runs-on: ${{matrix.os}}
@@ -279,6 +280,7 @@ jobs:
         include:
           - os: ubuntu-18.04
           - os: ubuntu-20.04
+          - os: ubuntu-22.04
           - os: macos-10.15
 
     runs-on: ${{matrix.os}}
@@ -335,6 +337,7 @@ jobs:
         include:
           - os: ubuntu-18.04
           - os: ubuntu-20.04
+          - os: ubuntu-22.04
           - os: macos-10.15
 
     runs-on: ${{matrix.os}}

benchmark/char_seq.cpp

@@ -0,0 +1,101 @@
+// Copyright 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#define _CRT_SECURE_NO_WARNINGS
+
+#include <boost/container_hash/hash.hpp>
+#include <boost/core/detail/splitmix64.hpp>
+#include <boost/core/type_name.hpp>
+#include <boost/config.hpp>
+#include <cstddef>
+#include <cstdio>
+#include <cstdint>
+#include <string>
+#include <vector>
+#include <deque>
+#include <list>
+#include <chrono>
+
+// test_hash_speed
+
+template<class T, class V> void test_hash_speed( int N, V const& v )
+{
+    std::vector<T> w;
+
+    w.reserve( N );
+
+    for( int i = 0; i < N; ++i )
+    {
+        w.emplace_back( v[i].begin(), v[i].end() );
+    }
+
+    typedef std::chrono::steady_clock clock_type;
+
+    clock_type::time_point t1 = clock_type::now();
+
+    std::size_t q = 0;
+
+    boost::hash<T> const h;
+
+    for( int i = 0; i < N; ++i )
+    {
+        q += h( w[i] );
+    }
+
+    clock_type::time_point t2 = clock_type::now();
+
+    long long ms1 = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();
+
+    std::string type = boost::core::type_name<T>();
+
+#if defined( _MSC_VER )
+
+    std::printf( "%25s : q=%20Iu, %lld ms\n", type.c_str(), q, ms1 );
+
+#else
+
+    std::printf( "%25s : q=%20zu, %lld ms\n", type.c_str(), q, ms1 );
+
+#endif
+}
+
+int main()
+{
+    int const N = 1048576 * 8;
+
+    std::vector<std::string> v;
+
+    {
+        v.reserve( N );
+
+        boost::detail::splitmix64 rnd;
+
+        for( int i = 0; i < N; ++i )
+        {
+            char buffer[ 64 ];
+
+            unsigned long long k = rnd();
+
+            if( k & 1 )
+            {
+                sprintf( buffer, "prefix_%llu_suffix", k );
+            }
+            else
+            {
+                sprintf( buffer, "{%u}", static_cast<unsigned>( k ) );
+            }
+
+            v.push_back( buffer );
+        }
+    }
+
+    std::puts( "Char sequence hashing test:\n" );
+
+    test_hash_speed< std::string >( N, v );
+    test_hash_speed< std::vector<char> >( N, v );
+    test_hash_speed< std::deque<char> >( N, v );
+    test_hash_speed< std::list<char> >( N, v );
+
+    std::puts( "" );
+}

benchmark/unordered.cpp

@@ -0,0 +1,389 @@
+// Copyright 2022 Peter Dimov.
+// Distributed under the Boost Software License, Version 1.0.
+// https://www.boost.org/LICENSE_1_0.txt
+
+#define _CRT_SECURE_NO_WARNINGS
+
+#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>
+#include <cstddef>
+#include <cstdio>
+#include <cstdint>
+#include <string>
+#include <vector>
+#include <chrono>
+#include <functional>
+
+// mul31_hash
+
+class mul31_hash
+{
+public:
+
+    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_unrolled_hash
+
+template<int Bits> struct mul31_unrolled_hash_impl;
+
+template<> struct mul31_unrolled_hash_impl<32>
+{
+    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 = 0x811C9DC5u;
+
+        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;
+    }
+};
+
+template<> struct mul31_unrolled_hash_impl<64>
+{
+    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;
+
+        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 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;
+
+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 > {};
+
+// old_boost_hash
+
+class old_boost_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;
+    }
+};
+
+// test_hash_speed
+
+template<class H, class V> void test_hash_speed( int N, V const& v )
+{
+    typedef std::chrono::steady_clock clock_type;
+
+    clock_type::time_point t1 = clock_type::now();
+
+    std::size_t q = 0;
+
+    H const h;
+
+    for( int i = 0; i < N; ++i )
+    {
+        q += h( v[i] );
+    }
+
+    clock_type::time_point t2 = clock_type::now();
+
+    long long ms1 = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();
+
+    std::string hash = boost::core::type_name<H>();
+
+#if defined( _MSC_VER )
+
+    std::printf( "%25s : q=%20Iu, %lld ms\n", hash.c_str(), q, ms1 );
+
+#else
+
+    std::printf( "%25s : q=%20zu, %lld ms\n", hash.c_str(), q, ms1 );
+
+#endif
+}
+
+// test_hash_collision
+
+template<class H, class V> void test_hash_collision( int N, V const& v, std::size_t n )
+{
+    boost::unordered_set<std::size_t> s;
+    H const h;
+
+    for( int i = 0; i < N; ++i )
+    {
+        s.insert( h( v[i] ) );
+    }
+
+    std::string hash = boost::core::type_name<H>();
+
+#if defined( _MSC_VER )
+
+    std::printf( "%25s : c=%Iu\n", hash.c_str(), n - s.size() );
+
+#else
+
+    std::printf( "%25s : c=%zu\n", hash.c_str(), n - s.size() );
+
+#endif
+}
+
+// test_container_speed
+
+template<class V, class S> void test4( int N, V const& v, char const * hash, S s )
+{
+    typedef std::chrono::steady_clock clock_type;
+
+    clock_type::time_point t1 = clock_type::now();
+
+    for( int i = 0; i < N; ++i )
+    {
+        s.insert( v[ i * 16 ] );
+    }
+
+    clock_type::time_point t2 = clock_type::now();
+
+    std::size_t q = 0;
+
+    for( int i = 0; i < 16 * N; ++i )
+    {
+        q += s.count( v[ i ] );
+    }
+
+    clock_type::time_point t3 = clock_type::now();
+
+    long long ms1 = std::chrono::duration_cast<std::chrono::milliseconds>( t2 - t1 ).count();
+    long long ms2 = std::chrono::duration_cast<std::chrono::milliseconds>( t3 - t2 ).count();
+
+    std::size_t n = s.bucket_count();
+    std::size_t m = 0;
+    std::size_t c = 0;
+
+    for( std::size_t i = 0; i < n; ++i )
+    {
+        std::size_t k = s.bucket_size( i );
+
+        if( k > 1 )
+        {
+            c += k - 1;
+        }
+
+        if( k > m )
+        {
+            m = k;
+        }
+    }
+
+#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 );
+
+#else
+
+    std::printf( "%25s : n=%zu, m=%zu, c=%zu, q=%zu, %lld + %lld ms\n", hash, n, m, c, q, ms1, ms2 );
+
+#endif
+}
+
+template<class K, class H, class V> void test_container_speed( int N, V const& v )
+{
+    boost::unordered_set<K, H> s( 0 );
+    test4( N, v, boost::core::type_name<H>().c_str(), s );
+}
+
+int main()
+{
+    int const N = 1048576 / 2; // 1048576 is too much for 32 bit
+
+    std::vector<std::string> v;
+
+    {
+        v.reserve( N * 16 );
+
+        boost::detail::splitmix64 rnd;
+
+        for( int i = 0; i < 16 * N; ++i )
+        {
+            char buffer[ 64 ];
+
+            unsigned long long k = rnd();
+
+            if( k & 1 )
+            {
+                sprintf( buffer, "prefix_%llu_suffix", k );
+            }
+            else
+            {
+                sprintf( buffer, "{%u}", static_cast<unsigned>( k ) );
+            }
+
+            v.push_back( buffer );
+        }
+    }
+
+    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<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 );
+
+    std::puts( "" );
+
+    std::puts( "Hash collision test:\n" );
+
+    {
+        std::size_t n = 0;
+
+        {
+            boost::unordered_set<std::string> s;
+
+            for( int i = 0; i < N * 16; ++i )
+            {
+                s.insert( v[i] );
+            }
+
+            n = s.size();
+        }
+
+        test_hash_collision<mul31_hash>( N * 16, v, n );
+        test_hash_collision<mul31_unrolled_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 );
+    }
+
+    std::puts( "" );
+
+    typedef std::string K;
+
+    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, 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 );
+
+    std::puts( "" );
+}

examples/Jamfile.v2

@@ -6,4 +6,4 @@
 run books.cpp ;
 run point.cpp ;
 run portable.cpp ;
-run template.cpp ;
+run template.cpp : : : <toolset>msvc-8.0:<build>no ;

include/boost/container_hash/hash.hpp

@@ -77,11 +77,12 @@ namespace boost
     {
         template<class T,
             bool bigger_than_size_t = (sizeof(T) > sizeof(std::size_t)),
+            bool is_unsigned = boost::is_unsigned<T>::value,
             std::size_t size_t_bits = sizeof(std::size_t) * CHAR_BIT,
             std::size_t type_bits = sizeof(T) * CHAR_BIT>
         struct hash_integral_impl;
 
-        template<class T, std::size_t size_t_bits, std::size_t type_bits> struct hash_integral_impl<T, false, size_t_bits, type_bits>
+        template<class T, bool is_unsigned, std::size_t size_t_bits, std::size_t type_bits> struct hash_integral_impl<T, false, is_unsigned, size_t_bits, type_bits>
         {
             static std::size_t fn( T v )
             {
@@ -89,7 +90,24 @@ namespace boost
             }
         };
 
-        template<class T> struct hash_integral_impl<T, true, 32, 64>
+        template<class T, std::size_t size_t_bits, std::size_t type_bits> struct hash_integral_impl<T, true, false, size_t_bits, type_bits>
+        {
+            static std::size_t fn( T v )
+            {
+                typedef typename boost::make_unsigned<T>::type U;
+
+                if( v >= 0 )
+                {
+                    return hash_integral_impl<U>::fn( static_cast<U>( v ) );
+                }
+                else
+                {
+                    return ~hash_integral_impl<U>::fn( static_cast<U>( ~static_cast<U>( v ) ) );
+                }
+            }
+        };
+
+        template<class T> struct hash_integral_impl<T, true, true, 32, 64>
         {
             static std::size_t fn( T v )
             {
@@ -102,7 +120,7 @@ namespace boost
             }
         };
 
-        template<class T> struct hash_integral_impl<T, true, 32, 128>
+        template<class T> struct hash_integral_impl<T, true, true, 32, 128>
         {
             static std::size_t fn( T v )
             {
@@ -117,7 +135,7 @@ namespace boost
             }
         };
 
-        template<class T> struct hash_integral_impl<T, true, 64, 128>
+        template<class T> struct hash_integral_impl<T, true, true, 64, 128>
         {
             static std::size_t fn( T v )
             {
@@ -133,34 +151,32 @@ namespace boost
     } // namespace hash_detail
 
     template <typename T>
-    typename boost::enable_if_<boost::conjunction<boost::is_integral<T>, boost::is_unsigned<T> >::value, std::size_t>::type
+    typename boost::enable_if_<boost::is_integral<T>::value, std::size_t>::type
         hash_value( T v )
     {
         return hash_detail::hash_integral_impl<T>::fn( v );
     }
 
-    template <typename T>
-    typename boost::enable_if_<boost::conjunction<boost::is_integral<T>, boost::is_signed<T> >::value, std::size_t>::type
-        hash_value( T v )
-    {
-        typedef typename boost::make_unsigned<T>::type U;
-
-        if( v >= 0 )
-        {
-            return hash_value( static_cast<U>( v ) );
-        }
-        else
-        {
-            return ~hash_value( static_cast<U>( ~static_cast<U>( v ) ) );
-        }
-    }
-
     // enumeration types
 
     template <typename T>
     typename boost::enable_if_<boost::is_enum<T>::value, std::size_t>::type
         hash_value( T v )
     {
+        // This should in principle return the equivalent of
+        //
+        // boost::hash_value( to_underlying(v) );
+        //
+        // However, the C++03 implementation of underlying_type,
+        //
+        // conditional<is_signed<T>, make_signed<T>, make_unsigned<T>>::type::type
+        //
+        // generates a legitimate -Wconversion warning in is_signed,
+        // because -1 is not a valid enum value when all the enumerators
+        // are nonnegative.
+        //
+        // So the legacy implementation will have to do for now.
+
         return static_cast<std::size_t>( v );
     }
 
@@ -328,12 +344,11 @@ namespace boost
 
     // pointer types
 
-    // Implementation by Alberto Barbati and Dave Harris.
+    // `x + (x >> 3)` adjustment by Alberto Barbati and Dave Harris.
     template <class T> std::size_t hash_value( T* const& v )
     {
-        std::size_t x = static_cast<std::size_t>(
-           reinterpret_cast<boost::uintptr_t>(v));
-        return x + (x >> 3);
+        boost::uintptr_t x = reinterpret_cast<boost::uintptr_t>( v );
+        return boost::hash_value( x + (x >> 3) );
     }
 
     // array types

test/Jamfile.v2

@@ -79,3 +79,5 @@ local fs-path-req = "-<toolset>gcc:<cxxflags>-Wshadow" "-<toolset>gcc:<cxxflags>
 
 run hash_fs_path_test.cpp /boost//filesystem/<warnings>off : : : $(fs-path-req) <toolset>msvc-14.0,<cxxstd>latest:<build>no ;
 run detail_is_range_test2.cpp : : : $(fs-path-req) ;
+
+run hash_container_test.cpp ;

test/hash_complex_test.cpp

@@ -29,6 +29,7 @@ int main() {}
                                 // 'const std::complex<float>::_Ty'
 #pragma warning(disable:4309)   // truncation of constant value
 #pragma warning(disable:4512)   // assignment operator could not be generated
+#pragma warning(disable:4996)   // std::complex<Integer> is deprecated
 #if BOOST_MSVC < 1400
 #pragma warning(disable:4267)   // conversion from 'size_t' to 'unsigned int',
                                 // possible loss of data

test/hash_container_test.cpp

@@ -0,0 +1,52 @@
+// 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 <vector>
+#include <deque>
+#include <list>
+#if !defined(BOOST_NO_CXX11_HDR_FORWARD_LIST)
+# include <forward_list>
+#endif
+
+template<class T> std::size_t hv( T const& t )
+{
+    return boost::hash<T>()( t );
+}
+
+template<class T> void test()
+{
+    for( std::size_t i = 0; i < 8; ++i )
+    {
+        std::vector<T> v( i );
+        std::size_t h0 = hv( v );
+
+        std::deque<T> d( v.begin(), v.end() );
+        BOOST_TEST_EQ( h0, hv( d ) );
+
+        std::list<T> l( v.begin(), v.end() );
+        BOOST_TEST_EQ( h0, hv( l ) );
+
+#if !defined(BOOST_NO_CXX11_HDR_FORWARD_LIST)
+
+        std::forward_list<T> f( v.begin(), v.end() );
+        BOOST_TEST_EQ( h0, hv( f ) );
+
+#endif
+    }
+}
+
+int main()
+{
+    test<char>();
+    test<unsigned char>();
+    test<signed char>();
+    test<int>();
+    test<float>();
+    test<double>();
+
+    return boost::report_errors();
+}

test/hash_reference_values.cpp

@@ -2,6 +2,8 @@
 // Distributed under the Boost Software License, Version 1.0.
 // https://www.boost.org/LICENSE_1_0.txt
 
+#define _SILENCE_NONFLOATING_COMPLEX_DEPRECATION_WARNING
+
 #include <boost/config/pragma_message.hpp>
 
 #if defined(__GNUC__) && !defined(__clang__) && __cplusplus < 201100L

test/hash_string_test2.cpp

@@ -11,6 +11,12 @@
 #if !defined(BOOST_NO_CXX17_HDR_STRING_VIEW)
 #include <string_view>
 #endif
+#include <vector>
+#include <deque>
+#include <list>
+#if !defined(BOOST_NO_CXX11_HDR_FORWARD_LIST)
+# include <forward_list>
+#endif
 
 // Test whether the hash values of a string and a
 // string_view that refers to it match. This is
@@ -24,12 +30,21 @@ template<class T> std::size_t hv( T const& t )
 int main()
 {
     std::string s( "Test." );
+    std::size_t h0 = hv( s );
 
-    BOOST_TEST_EQ( hv( s ), hv( boost::string_view( s ) ) );
-    BOOST_TEST_EQ( hv( s ), hv( boost::core::string_view( s ) ) );
+    BOOST_TEST_EQ( h0, hv( boost::string_view( s ) ) );
+    BOOST_TEST_EQ( h0, hv( boost::core::string_view( s ) ) );
 
 #if !defined(BOOST_NO_CXX17_HDR_STRING_VIEW)
-    BOOST_TEST_EQ( hv( s ), hv( std::string_view( s ) ) );
+    BOOST_TEST_EQ( h0, hv( std::string_view( s ) ) );
+#endif
+
+    BOOST_TEST_EQ( h0, hv( std::vector<char>( s.begin(), s.end() ) ) );
+    BOOST_TEST_EQ( h0, hv( std::deque<char>( s.begin(), s.end() ) ) );
+    BOOST_TEST_EQ( h0, hv( std::list<char>( s.begin(), s.end() ) ) );
+
+#if !defined(BOOST_NO_CXX11_HDR_FORWARD_LIST)
+    BOOST_TEST_EQ( h0, hv( std::forward_list<char>( s.begin(), s.end() ) ) );
 #endif
 
     return boost::report_errors();