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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
|
#include <stdio.h>
#include <time.h>
#include <stc/crandom.h>
#include <stc/cstr.h>
#include "others/khash.h"
#ifdef __cplusplus
#include <limits>
#include <unordered_map>
#include "others/robin_hood.hpp"
#include "others/skarupke/bytell_hash_map.hpp"
#include "others/tsl/hopscotch_map.h"
#include "others/parallel_hashmap/phmap.h"
template<typename C> inline void destroy_me(C& c) { C().swap(c); }
#endif
// cmap and khash template expansion
#define i_key int64_t
#define i_val int64_t
#define i_hash c_default_hash64
#define i_tag ii
#include <stc/cmap.h>
KHASH_MAP_INIT_INT64(ii, int64_t)
size_t seed;
static const float max_load_factor = 0.77f;
stc64_t rng;
#define SEED(s) rng = stc64_init(seed)
#define RAND(N) (stc64_rand(&rng) & ((1 << N) - 1))
#define CMAP_SETUP(X, Key, Value) cmap_##X map = cmap_##X##_init() \
; cmap_##X##_max_load_factor(&map, max_load_factor)
#define CMAP_PUT(X, key, val) cmap_##X##_emplace_or_assign(&map, key, val).ref->second
#define CMAP_EMPLACE(X, key, val) cmap_##X##_emplace(&map, key, val).ref->second
#define CMAP_ERASE(X, key) cmap_##X##_erase(&map, key)
#define CMAP_FIND(X, key) cmap_##X##_contains(map, key)
#define CMAP_FOR(X, i) c_foreach (i, cmap_##X, map)
#define CMAP_ITEM(X, i) i.ref->second
#define CMAP_SIZE(X) cmap_##X##_size(map)
#define CMAP_BUCKETS(X) cmap_##X##_bucket_count(map)
#define CMAP_CLEAR(X) cmap_##X##_clear(&map)
#define CMAP_DTOR(X) cmap_##X##_del(&map)
#define KMAP_SETUP(X, Key, Value) khash_t(ii)* map = kh_init(ii); khiter_t ki; int ret
#define KMAP_PUT(X, key, val) (*(ki = kh_put(ii, map, key, &ret), map->vals[ki] = val, map->vals+ki))
#define KMAP_EMPLACE(X, key, val) (*(ki = kh_put(ii, map, key, &ret), ret ? (map->vals[ki] = val, 0) : 1, map->vals+ki))
#define KMAP_ERASE(X, key) ((ki = kh_get(ii, map, key)) != kh_end(map) ? kh_del(ii, map, ki), 1 : 0)
#define KMAP_FIND(X, key) (kh_get(ii, map, key) != kh_end(map))
#define KMAP_SIZE(X) kh_size(map)
#define KMAP_BUCKETS(X) kh_n_buckets(map)
#define KMAP_CLEAR(X) kh_clear(ii, map)
#define KMAP_DTOR(X) kh_destroy(ii, map)
#define UMAP_SETUP(X, Key, Value) std::unordered_map<Key, Value> map; map.max_load_factor(max_load_factor)
#define UMAP_PUT(X, key, val) (map[key] = val)
#define UMAP_EMPLACE(X, key, val) map.emplace(key, val).first->second
#define UMAP_FIND(X, key) (map.find(key) != map.end())
#define UMAP_ERASE(X, key) map.erase(key)
#define UMAP_FOR(X, i) for (auto i: map)
#define UMAP_ITEM(X, i) i.second
#define UMAP_SIZE(X) map.size()
#define UMAP_BUCKETS(X) map.bucket_count()
#define UMAP_CLEAR(X) map.clear()
#define UMAP_DTOR(X) destroy_me(map)
#define BMAP_SETUP(X, Key, Value) ska::bytell_hash_map<Key, Value> map; map.max_load_factor(max_load_factor)
#define BMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
#define BMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
#define BMAP_FIND(X, key) UMAP_FIND(X, key)
#define BMAP_ERASE(X, key) UMAP_ERASE(X, key)
#define BMAP_FOR(X, i) UMAP_FOR(X, i)
#define BMAP_ITEM(X, i) UMAP_ITEM(X, i)
#define BMAP_SIZE(X) UMAP_SIZE(X)
#define BMAP_BUCKETS(X) UMAP_BUCKETS(X)
#define BMAP_CLEAR(X) UMAP_CLEAR(X)
#define BMAP_DTOR(X) UMAP_DTOR(X)
#define FMAP_SETUP(X, Key, Value) ska::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor)
#define FMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
#define FMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
#define FMAP_FIND(X, key) UMAP_FIND(X, key)
#define FMAP_ERASE(X, key) UMAP_ERASE(X, key)
#define FMAP_FOR(X, i) UMAP_FOR(X, i)
#define FMAP_ITEM(X, i) UMAP_ITEM(X, i)
#define FMAP_SIZE(X) UMAP_SIZE(X)
#define FMAP_BUCKETS(X) UMAP_BUCKETS(X)
#define FMAP_CLEAR(X) UMAP_CLEAR(X)
#define FMAP_DTOR(X) UMAP_DTOR(X)
#define HMAP_SETUP(X, Key, Value) tsl::hopscotch_map<Key, Value> map; map.max_load_factor(max_load_factor)
#define HMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
#define HMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
#define HMAP_FIND(X, key) UMAP_FIND(X, key)
#define HMAP_ERASE(X, key) UMAP_ERASE(X, key)
#define HMAP_FOR(X, i) UMAP_FOR(X, i)
#define HMAP_ITEM(X, i) UMAP_ITEM(X, i)
#define HMAP_SIZE(X) UMAP_SIZE(X)
#define HMAP_BUCKETS(X) UMAP_BUCKETS(X)
#define HMAP_CLEAR(X) UMAP_CLEAR(X)
#define HMAP_DTOR(X) UMAP_DTOR(X)
#define RMAP_SETUP(X, Key, Value) robin_hood::unordered_map<Key, Value> map
#define RMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
#define RMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
#define RMAP_FIND(X, key) UMAP_FIND(X, key)
#define RMAP_ERASE(X, key) UMAP_ERASE(X, key)
#define RMAP_FOR(X, i) UMAP_FOR(X, i)
#define RMAP_ITEM(X, i) UMAP_ITEM(X, i)
#define RMAP_SIZE(X) UMAP_SIZE(X)
#define RMAP_BUCKETS(X) map.mask()
#define RMAP_CLEAR(X) UMAP_CLEAR(X)
#define RMAP_DTOR(X) UMAP_DTOR(X)
#define PMAP_SETUP(X, Key, Value) phmap::flat_hash_map<Key, Value> map; map.max_load_factor(max_load_factor)
#define PMAP_PUT(X, key, val) UMAP_PUT(X, key, val)
#define PMAP_EMPLACE(X, key, val) UMAP_EMPLACE(X, key, val)
#define PMAP_FIND(X, key) UMAP_FIND(X, key)
#define PMAP_ERASE(X, key) UMAP_ERASE(X, key)
#define PMAP_FOR(X, i) UMAP_FOR(X, i)
#define PMAP_ITEM(X, i) UMAP_ITEM(X, i)
#define PMAP_SIZE(X) UMAP_SIZE(X)
#define PMAP_BUCKETS(X) UMAP_BUCKETS(X)
#define PMAP_CLEAR(X) UMAP_CLEAR(X)
#define PMAP_DTOR(X) UMAP_DTOR(X)
enum {
RR = 27,
FAC = 3,
N0 = 10000000 * FAC,
N1 = 10000000 * FAC,
N2 = 10000000 * FAC,
N3 = 10000000 * FAC,
N4 = 10000000 * FAC,
};
int rr = RR;
#define MAP_TEST0(M, X) \
{ \
M##_SETUP(X, int64_t, int64_t); \
uint64_t checksum = 0; \
SEED(seed); \
clock_t difference, before = clock(); \
for (size_t i = 0; i < N0; ++i) { \
checksum += ++ M##_EMPLACE(X, RAND(rr), i); \
} \
difference = clock() - before; \
printf(#M ": time: %5.02f, sum: %zu, size: %zu, buckets: %8zu\n", \
(float) difference / CLOCKS_PER_SEC, checksum, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \
M##_DTOR(X); \
}
#define MAP_TEST1(M, X) \
{ \
M##_SETUP(X, int64_t, int64_t); \
uint64_t checksum = 0, erased = 0; \
SEED(seed); \
clock_t difference, before = clock(); \
for (size_t i = 0; i < N1; ++i) { \
checksum += ++ M##_EMPLACE(X, RAND(rr), i); \
erased += M##_ERASE(X, RAND(rr)); \
} \
difference = clock() - before; \
printf(#M ": time: %5.02f, sum: %zu, erased %zu, size: %zu, buckets: %8zu\n", \
(float) difference / CLOCKS_PER_SEC, checksum, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \
M##_DTOR(X); \
}
#define MAP_TEST2(M, X) \
{ \
M##_SETUP(X, int64_t, int64_t); \
size_t erased = 0; \
clock_t difference, before = clock(); \
for (size_t i = 0; i < N2; ++i) \
M##_PUT(X, i, i); \
for (size_t i = 0; i < N2; ++i) \
erased += M##_ERASE(X, i); \
difference = clock() - before; \
printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \
(float) difference / CLOCKS_PER_SEC, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \
M##_DTOR(X); \
}
#define MAP_TEST3(M, X) \
{ \
M##_SETUP(X, int64_t, int64_t); \
size_t erased = 0; \
clock_t difference, before = clock(); \
SEED(seed); \
for (size_t i = 0; i < N3; ++i) \
M##_PUT(X, RAND(rr), i); \
SEED(seed); \
for (size_t i = 0; i < N3; ++i) \
erased += M##_ERASE(X, RAND(rr)); \
difference = clock() - before; \
printf(#M ": time: %5.02f, erased %zu, size: %zu, buckets: %8zu\n", \
(float) difference / CLOCKS_PER_SEC, erased, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \
M##_DTOR(X); \
}
#define MAP_TEST4(M, X) \
{ \
M##_SETUP(X, int64_t, int64_t); \
size_t sum = 0; \
SEED(seed); \
for (size_t i = 0; i < N4; ++i) \
M##_PUT(X, RAND(rr), i); \
clock_t difference, before = clock(); \
for (int k=0; k<5; k++) M##_FOR (X, i) \
sum += M##_ITEM(X, i); \
difference = clock() - before; \
printf(#M ": time: %5.02f, sum %zu, size: %zu, buckets: %8zu\n", \
(float) difference / CLOCKS_PER_SEC, sum, (size_t) M##_SIZE(X), (size_t) M##_BUCKETS(X)); \
M##_DTOR(X); \
}
#ifdef __cplusplus
#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii) MAP_TEST##n(UMAP, ii) MAP_TEST##n(PMAP, ii) \
MAP_TEST##n(BMAP, ii) MAP_TEST##n(FMAP, ii) MAP_TEST##n(RMAP, ii) /*MAP_TEST##n(HMAP, ii)*/
#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii) /*MAP_TEST##n(KMAP, ii)*/ MAP_TEST##n(UMAP, ii) MAP_TEST##n(PMAP, ii) \
MAP_TEST##n(BMAP, ii) MAP_TEST##n(FMAP, ii) MAP_TEST##n(RMAP, ii) /*MAP_TEST##n(HMAP, ii)*/
#else
#define RUN_TEST(n) MAP_TEST##n(CMAP, ii) MAP_TEST##n(KMAP, ii)
#define RUNX_TEST(n) MAP_TEST##n(CMAP, ii)
#endif
int main(int argc, char* argv[])
{
rr = argc == 2 ? atoi(argv[1]) : RR;
seed = time(NULL);
printf("\nRandom keys are in range [0, 2^%d), seed = %zu:\n", rr, seed);
printf("CMAP = STC cmap\n"
"KMAP = Klib khash\n"
"UMAP = std::unordered_map\n"
"PMAP = phmap::flat_hash_map\n"
"BMAP = ska::bytell_hash_map\n"
"FMAP = ska::flat_hash_map\n"
"RMAP = robin_hood::unordered_map\n");
printf("\nUnordered maps: Insert %d random keys:\n", N0);
RUN_TEST(0)
printf("\nUnordered maps: %d insert random key + try to remove another random key:\n", N1);
RUN_TEST(1)
printf("\nUnordered maps: Insert %d sequential keys, then remove them in same order:\n", N2);
RUN_TEST(2)
printf("\nUnordered maps: Insert %d random keys, then remove them in same order:\n", N3);
RUN_TEST(3)
printf("\nUnordered maps: Iterate %d random keys:\n", N4);
RUNX_TEST(4)
}
|
