1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
|
#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);
}
|
