Re: Good hash for pointers

With the code I've shown I proved that the hash AES hashfunction
is totally stochastically and thereby a good hash function. But
I was still discontent with the speed of the code.
Usually you're not able to update the buckets of a hashtable with
multiple threads without any locking. But with my code the buckets
are only simple counters which could be updated atomically.
So I could reduce the code and partitioned the input range to the
hash function with the available number of cores. Here's the code:
#include <iostream>
#include <vector>
#include <cstdint>
#include <thread>
#include <span>
#include <intrin.h>
using namespace std;
uint64_t MichaelsHash( uint64_t key );
int main( int argc, char ** )
{
#if defined(NDEBUG)
constexpr ptrdiff_t N_BUCKETS = 1ull << 32;
#else
constexpr ptrdiff_t N_BUCKETS = 1 << 16;
#endif
vector<uint8_t> buckets( N_BUCKETS );
int hc = thread::hardware_concurrency(), p = hc;
vector<jthread> threads;
threads.reserve( hc );
ptrdiff_t end = N_BUCKETS, begin;
do
begin = (ptrdiff_t)((double)--p / hc * N_BUCKETS),
threads.emplace_back( [&]( size_t begin, size_t end )
{
span<atomic_uint8_t> atomics( (atomic_uint8_t *)buckets.data(), buckets.size() );
for( ; begin != end; ++begin )
if( !++atomics[MichaelsHash( begin ) % (size_t)N_BUCKETS] )
terminate();
}, begin, end );
while( (end = begin) );
threads.resize( 0 );
// sum up loads
vector<size_t> loads;
for( size_t bucketLoad : buckets )
{
if( loads.size() <= bucketLoad )
loads.resize( bucketLoad + 1 );
++loads[bucketLoad];
}
// print loads percentage
for( size_t ld = 0; ptrdiff_t nLoad : loads )
cout << ld++ << ": " << 100.0 * nLoad / (ptrdiff_t)buckets.size() << "%" << endl;
}
uint64_t MichaelsHash( uint64_t key )
{
__m128i xkey = _mm_set_epi64x( key, 42 );
using bar_t = pair<uint64_t, uint64_t>;
static bar_t const bars[8] =
{
{ 0xBB09BBCC90B24BF2, 0x825C622FF2792A01 },
{ 0x94F0535CB06D4060, 0x939C756246DBFD1D },
{ 0x5B835E01A7E14CA1, 0xAC2BDAFC023CDD06 },
{ 0xE0B6A4735B774AEC, 0x9CAFB43E7DDE494C },
};
for( bar_t const &bar : bars )
xkey = _mm_aesenc_si128( xkey, _mm_set_epi64x( bar.second, bar.first ) );
return xkey.m128i_u64[0];
}
Now the code is about six times faster and I get a eight times
speedup over single-threaded processing with the same code. Of
course the results are still the same.