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
|
#include <map>
#include <unordered_map>
#include <string>
#include <iostream>
#include <chrono>
#include <vector>
#include <parallel_hashmap/phmap.h>
#include <sstream>
template <typename T>
using milliseconds = std::chrono::duration<T, std::milli>;
// type containing std::string. Seems to take a long time to construct (and maybe move)
// ------------------------------------------------------------------------------------
class custom_type
{
std::string one = "one";
std::string two = "two";
std::uint32_t three = 3;
std::uint64_t four = 4;
std::uint64_t five = 5;
public:
custom_type() = default;
// Make object movable and non-copyable
custom_type(custom_type &&) = default;
custom_type& operator=(custom_type &&) = default;
// should be automatically deleted per http://www.slideshare.net/ripplelabs/howard-hinnant-accu2014
//custom_type(custom_type const&) = delete;
//custom_type& operator=(custom_type const&) = delete;
};
// type containing only integrals. should be faster to create.
// -----------------------------------------------------------
class custom_type_2
{
std::uint32_t three = 3;
std::uint64_t four = 4;
std::uint64_t five = 5;
std::uint64_t six = 6;
public:
custom_type_2() = default;
// Make object movable and non-copyable
custom_type_2(custom_type_2 &&) = default;
custom_type_2& operator=(custom_type_2 &&) = default;
// should be automatically deleted per http://www.slideshare.net/ripplelabs/howard-hinnant-accu2014
//custom_type_2(custom_type_2 const&) = delete;
//custom_type_2& operator=(custom_type_2 const&) = delete;
};
// convert std::size_t to appropriate key
// --------------------------------------
template <class K>
struct GenKey
{
K operator()(std::size_t j);
};
template <>
struct GenKey<std::string>
{
std::string operator()(std::size_t j) {
std::ostringstream stm;
stm << j;
return stm.str();
}
};
template <>
struct GenKey<int>
{
int operator()(std::size_t j) {
return (int)j;
}
};
// emplace key + large struct
// --------------------------
template <class Map, class K, class V, class T> struct _emplace
{
void operator()(Map &m, std::size_t j);
};
// "void" template parameter -> use emplace
template <class Map, class K, class V> struct _emplace<Map, K, V, void>
{
void operator()(Map &m, std::size_t j)
{
m.emplace(GenKey<K>()(j), V());
}
};
// "int" template parameter -> use emplace_back for std::vector
template <class Map, class K, class V> struct _emplace<Map, K, V, int>
{
void operator()(Map &m, std::size_t j)
{
m.emplace_back(GenKey<K>()(j), V());
}
};
// The test itself
// ---------------
template <class Map, class K, class V, class T, template <class, class, class, class> class INSERT>
void _test(std::size_t iterations, std::size_t container_size, const char *map_name)
{
std::size_t count = 0;
auto t1 = std::chrono::high_resolution_clock::now();
INSERT<Map, K, V, T> insert;
for (std::size_t i=0; i<iterations; ++i)
{
Map m;
for (std::size_t j=0; j<container_size; ++j)
insert(m, j);
count += m.size();
}
auto t2 = std::chrono::high_resolution_clock::now();
auto elapsed = milliseconds<double>(t2 - t1).count();
if (count != iterations*container_size)
std::clog << " invalid count: " << count << "\n";
std::clog << map_name << std::fixed << int(elapsed) << " ms\n";
}
template <class K, class V, template <class, class, class, class> class INSERT>
void test(std::size_t iterations, std::size_t container_size)
{
std::clog << "bench: iterations: " << iterations << " / container_size: " << container_size << "\n";
_test<std::map<K, V>, K, V, void, INSERT>(iterations, container_size, " std::map: ");
_test<std::unordered_map<K, V>, K, V, void, INSERT>(iterations, container_size, " std::unordered_map: ");
_test<phmap::flat_hash_map<K, V>, K, V, void, INSERT>(iterations, container_size, " phmap::flat_hash_map: ");
_test<std::vector<std::pair<K, V>>, K, V, int, INSERT> (iterations, container_size, " std::vector<std::pair>: ");
std::clog << "\n";
}
int main()
{
std::size_t iterations = 100000;
// test with custom_type_2 (int key + 32 byte value). This is representative
// of the hash table insertion speed.
// -------------------------------------------------------------------------
std::clog << "\n\n" << "testing with <int, custom_type_2>" "\n";
std::clog << "---------------------------------" "\n";
test<int, custom_type_2, _emplace>(iterations,10);
test<int, custom_type_2, _emplace>(iterations,100);
test<int, custom_type_2, _emplace>(iterations,500);
// test with custom_type, which contains two std::string values, and use
// a generated string key. This is not very indicative of the speed of the
// hash itself, as a good chunk of the time is spent creating the keys and
// values (as shown by the long times even for std::vector).
// -----------------------------------------------------------------------
std::clog << "\n" << "testing with <string, custom_type>" "\n";
std::clog << "---------------------------------" "\n";
test<std::string, custom_type, _emplace>(iterations,1);
test<std::string, custom_type, _emplace>(iterations,10);
test<std::string, custom_type, _emplace>(iterations,50);
}
|
