144 lines
3.3 KiB
C++
144 lines
3.3 KiB
C++
#include <string>
|
|
#include <array>
|
|
#include <cstdint>
|
|
#include <limits>
|
|
#include <random>
|
|
#include <utility>
|
|
#define PHMAP_ALLOCATOR_NOTHROW 1
|
|
#include <parallel_hashmap/phmap.h>
|
|
|
|
// this is probably the fastest high quality 64bit random number generator that exists.
|
|
// Implements Small Fast Counting v4 RNG from PractRand.
|
|
class sfc64 {
|
|
public:
|
|
using result_type = uint64_t;
|
|
|
|
// no copy ctors so we don't accidentally get the same random again
|
|
sfc64(sfc64 const&) = delete;
|
|
sfc64& operator=(sfc64 const&) = delete;
|
|
|
|
sfc64(sfc64&&) = default;
|
|
sfc64& operator=(sfc64&&) = default;
|
|
|
|
sfc64(std::array<uint64_t, 4> const& _state)
|
|
: m_a(_state[0])
|
|
, m_b(_state[1])
|
|
, m_c(_state[2])
|
|
, m_counter(_state[3]) {}
|
|
|
|
static constexpr uint64_t(min)() {
|
|
return (std::numeric_limits<uint64_t>::min)();
|
|
}
|
|
static constexpr uint64_t(max)() {
|
|
return (std::numeric_limits<uint64_t>::max)();
|
|
}
|
|
|
|
sfc64()
|
|
: sfc64(UINT64_C(0x853c49e6748fea9b)) {}
|
|
|
|
sfc64(uint64_t _seed)
|
|
: m_a(_seed)
|
|
, m_b(_seed)
|
|
, m_c(_seed)
|
|
, m_counter(1) {
|
|
for (int i = 0; i < 12; ++i) {
|
|
operator()();
|
|
}
|
|
}
|
|
|
|
void seed() {
|
|
*this = sfc64{std::random_device{}()};
|
|
}
|
|
|
|
uint64_t operator()() noexcept {
|
|
auto const tmp = m_a + m_b + m_counter++;
|
|
m_a = m_b ^ (m_b >> right_shift);
|
|
m_b = m_c + (m_c << left_shift);
|
|
m_c = rotl(m_c, rotation) + tmp;
|
|
return tmp;
|
|
}
|
|
|
|
// this is a bit biased, but for our use case that's not important.
|
|
uint64_t operator()(uint64_t boundExcluded) noexcept {
|
|
#ifdef PHMAP_HAS_UMUL128
|
|
uint64_t h;
|
|
(void)umul128(operator()(), boundExcluded, &h);
|
|
return h;
|
|
#else
|
|
return 0;
|
|
#endif
|
|
}
|
|
|
|
std::array<uint64_t, 4> state() const {
|
|
return {{m_a, m_b, m_c, m_counter}};
|
|
}
|
|
|
|
void state(std::array<uint64_t, 4> const& s) {
|
|
m_a = s[0];
|
|
m_b = s[1];
|
|
m_c = s[2];
|
|
m_counter = s[3];
|
|
}
|
|
|
|
private:
|
|
template <typename T>
|
|
T rotl(T const x, int k) {
|
|
return (x << k) | (x >> (8 * sizeof(T) - k));
|
|
}
|
|
|
|
static constexpr int rotation = 24;
|
|
static constexpr int right_shift = 11;
|
|
static constexpr int left_shift = 3;
|
|
uint64_t m_a;
|
|
uint64_t m_b;
|
|
uint64_t m_c;
|
|
uint64_t m_counter;
|
|
};
|
|
|
|
|
|
int main()
|
|
{
|
|
// Create an unordered_map of three strings (that map to strings)
|
|
using Map = phmap::parallel_node_hash_map<int, int>;
|
|
static size_t const n = 50000000;
|
|
sfc64 rng(123);
|
|
|
|
size_t checksum = 0;
|
|
|
|
if (0)
|
|
{
|
|
size_t const max_rng = n / 20;
|
|
Map map;
|
|
for (size_t i = 0; i < n; ++i) {
|
|
checksum += ++map[static_cast<int>(rng(max_rng))];
|
|
}
|
|
}
|
|
|
|
if (0)
|
|
{
|
|
size_t const max_rng = n / 4;
|
|
Map map;
|
|
for (size_t i = 0; i < n; ++i) {
|
|
checksum += ++map[static_cast<int>(rng(max_rng))];
|
|
}
|
|
}
|
|
|
|
if (1)
|
|
{
|
|
size_t const max_rng = n / 2;
|
|
Map map;
|
|
for (size_t i = 0; i < n; ++i) {
|
|
checksum += ++map[static_cast<int>(rng(max_rng))];
|
|
}
|
|
}
|
|
|
|
if (0)
|
|
{
|
|
Map map;
|
|
for (size_t i = 0; i < n; ++i) {
|
|
checksum += ++map[static_cast<int>(rng())];
|
|
}
|
|
}
|
|
printf("%zu\n", checksum);
|
|
}
|