]>
Commit | Line | Data |
---|---|---|
1e59de90 TL |
1 | // Copyright 2021 Peter Dimov. |
2 | // Distributed under the Boost Software License, Version 1.0. | |
3 | // https://www.boost.org/LICENSE_1_0.txt | |
4 | ||
5 | #define _SILENCE_CXX17_OLD_ALLOCATOR_MEMBERS_DEPRECATION_WARNING | |
6 | ||
7 | #include <boost/unordered_map.hpp> | |
8 | #include <boost/multi_index_container.hpp> | |
9 | #include <boost/multi_index/hashed_index.hpp> | |
10 | #include <boost/multi_index/member.hpp> | |
11 | #include <boost/core/detail/splitmix64.hpp> | |
12 | #include <boost/config.hpp> | |
13 | #ifdef HAVE_ABSEIL | |
14 | # include "absl/container/node_hash_map.h" | |
15 | # include "absl/container/flat_hash_map.h" | |
16 | #endif | |
17 | #include <unordered_map> | |
18 | #include <vector> | |
19 | #include <memory> | |
20 | #include <cstdint> | |
21 | #include <iostream> | |
22 | #include <iomanip> | |
23 | #include <chrono> | |
24 | ||
25 | using namespace std::chrono_literals; | |
26 | ||
27 | static void print_time( std::chrono::steady_clock::time_point & t1, char const* label, std::uint32_t s, std::size_t size ) | |
28 | { | |
29 | auto t2 = std::chrono::steady_clock::now(); | |
30 | ||
31 | std::cout << label << ": " << ( t2 - t1 ) / 1ms << " ms (s=" << s << ", size=" << size << ")\n"; | |
32 | ||
33 | t1 = t2; | |
34 | } | |
35 | ||
36 | constexpr unsigned N = 2'000'000; | |
37 | constexpr int K = 10; | |
38 | ||
39 | static std::vector< std::uint32_t > indices1, indices2, indices3; | |
40 | ||
41 | static void init_indices() | |
42 | { | |
43 | indices1.push_back( 0 ); | |
44 | ||
45 | for( unsigned i = 1; i <= N*2; ++i ) | |
46 | { | |
47 | indices1.push_back( i ); | |
48 | } | |
49 | ||
50 | indices2.push_back( 0 ); | |
51 | ||
52 | { | |
53 | boost::detail::splitmix64 rng; | |
54 | ||
55 | for( unsigned i = 1; i <= N*2; ++i ) | |
56 | { | |
57 | indices2.push_back( static_cast<std::uint32_t>( rng() ) ); | |
58 | } | |
59 | } | |
60 | ||
61 | indices3.push_back( 0 ); | |
62 | ||
63 | for( unsigned i = 1; i <= N*2; ++i ) | |
64 | { | |
65 | indices3.push_back( (std::uint32_t)i << 11 ); | |
66 | } | |
67 | } | |
68 | ||
69 | template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::steady_clock::time_point & t1 ) | |
70 | { | |
71 | for( unsigned i = 1; i <= N; ++i ) | |
72 | { | |
73 | map.insert( { indices1[ i ], i } ); | |
74 | } | |
75 | ||
76 | print_time( t1, "Consecutive insert", 0, map.size() ); | |
77 | ||
78 | for( unsigned i = 1; i <= N; ++i ) | |
79 | { | |
80 | map.insert( { indices2[ i ], i } ); | |
81 | } | |
82 | ||
83 | print_time( t1, "Random insert", 0, map.size() ); | |
84 | ||
85 | for( unsigned i = 1; i <= N; ++i ) | |
86 | { | |
87 | map.insert( { indices3[ i ], i } ); | |
88 | } | |
89 | ||
90 | print_time( t1, "Consecutive shifted insert", 0, map.size() ); | |
91 | ||
92 | std::cout << std::endl; | |
93 | } | |
94 | ||
95 | template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::steady_clock::time_point & t1 ) | |
96 | { | |
97 | std::uint32_t s; | |
98 | ||
99 | s = 0; | |
100 | ||
101 | for( int j = 0; j < K; ++j ) | |
102 | { | |
103 | for( unsigned i = 1; i <= N * 2; ++i ) | |
104 | { | |
105 | auto it = map.find( indices1[ i ] ); | |
106 | if( it != map.end() ) s += it->second; | |
107 | } | |
108 | } | |
109 | ||
110 | print_time( t1, "Consecutive lookup", s, map.size() ); | |
111 | ||
112 | s = 0; | |
113 | ||
114 | for( int j = 0; j < K; ++j ) | |
115 | { | |
116 | for( unsigned i = 1; i <= N * 2; ++i ) | |
117 | { | |
118 | auto it = map.find( indices2[ i ] ); | |
119 | if( it != map.end() ) s += it->second; | |
120 | } | |
121 | } | |
122 | ||
123 | print_time( t1, "Random lookup", s, map.size() ); | |
124 | ||
125 | s = 0; | |
126 | ||
127 | for( int j = 0; j < K; ++j ) | |
128 | { | |
129 | for( unsigned i = 1; i <= N * 2; ++i ) | |
130 | { | |
131 | auto it = map.find( indices3[ i ] ); | |
132 | if( it != map.end() ) s += it->second; | |
133 | } | |
134 | } | |
135 | ||
136 | print_time( t1, "Consecutive shifted lookup", s, map.size() ); | |
137 | ||
138 | std::cout << std::endl; | |
139 | } | |
140 | ||
141 | template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 ) | |
142 | { | |
143 | auto it = map.begin(); | |
144 | ||
145 | while( it != map.end() ) | |
146 | { | |
147 | if( it->second & 1 ) | |
148 | { | |
149 | map.erase( it++ ); | |
150 | } | |
151 | else | |
152 | { | |
153 | ++it; | |
154 | } | |
155 | } | |
156 | ||
157 | print_time( t1, "Iterate and erase odd elements", 0, map.size() ); | |
158 | ||
159 | std::cout << std::endl; | |
160 | } | |
161 | ||
162 | template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::steady_clock::time_point & t1 ) | |
163 | { | |
164 | for( unsigned i = 1; i <= N; ++i ) | |
165 | { | |
166 | map.erase( indices1[ i ] ); | |
167 | } | |
168 | ||
169 | print_time( t1, "Consecutive erase", 0, map.size() ); | |
170 | ||
171 | { | |
172 | boost::detail::splitmix64 rng; | |
173 | ||
174 | for( unsigned i = 1; i <= N; ++i ) | |
175 | { | |
176 | map.erase( indices2[ i ] ); | |
177 | } | |
178 | } | |
179 | ||
180 | print_time( t1, "Random erase", 0, map.size() ); | |
181 | ||
182 | for( unsigned i = 1; i <= N; ++i ) | |
183 | { | |
184 | map.erase( indices3[ i ] ); | |
185 | } | |
186 | ||
187 | print_time( t1, "Consecutive shifted erase", 0, map.size() ); | |
188 | ||
189 | std::cout << std::endl; | |
190 | } | |
191 | ||
192 | // counting allocator | |
193 | ||
194 | static std::size_t s_alloc_bytes = 0; | |
195 | static std::size_t s_alloc_count = 0; | |
196 | ||
197 | template<class T> struct allocator | |
198 | { | |
199 | using value_type = T; | |
200 | ||
201 | allocator() = default; | |
202 | ||
203 | template<class U> allocator( allocator<U> const & ) noexcept | |
204 | { | |
205 | } | |
206 | ||
207 | template<class U> bool operator==( allocator<U> const & ) const noexcept | |
208 | { | |
209 | return true; | |
210 | } | |
211 | ||
212 | template<class U> bool operator!=( allocator<U> const& ) const noexcept | |
213 | { | |
214 | return false; | |
215 | } | |
216 | ||
217 | T* allocate( std::size_t n ) const | |
218 | { | |
219 | s_alloc_bytes += n * sizeof(T); | |
220 | s_alloc_count++; | |
221 | ||
222 | return std::allocator<T>().allocate( n ); | |
223 | } | |
224 | ||
225 | void deallocate( T* p, std::size_t n ) const noexcept | |
226 | { | |
227 | s_alloc_bytes -= n * sizeof(T); | |
228 | s_alloc_count--; | |
229 | ||
230 | std::allocator<T>().deallocate( p, n ); | |
231 | } | |
232 | }; | |
233 | ||
234 | // | |
235 | ||
236 | struct record | |
237 | { | |
238 | std::string label_; | |
239 | long long time_; | |
240 | std::size_t bytes_; | |
241 | std::size_t count_; | |
242 | }; | |
243 | ||
244 | static std::vector<record> times; | |
245 | ||
246 | template<template<class...> class Map> BOOST_NOINLINE void test( char const* label ) | |
247 | { | |
248 | std::cout << label << ":\n\n"; | |
249 | ||
250 | s_alloc_bytes = 0; | |
251 | s_alloc_count = 0; | |
252 | ||
253 | Map<std::uint32_t, std::uint32_t> map; | |
254 | ||
255 | auto t0 = std::chrono::steady_clock::now(); | |
256 | auto t1 = t0; | |
257 | ||
258 | test_insert( map, t1 ); | |
259 | ||
260 | std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n"; | |
261 | ||
262 | record rec = { label, 0, s_alloc_bytes, s_alloc_count }; | |
263 | ||
264 | test_lookup( map, t1 ); | |
265 | test_iteration( map, t1 ); | |
266 | test_lookup( map, t1 ); | |
267 | test_erase( map, t1 ); | |
268 | ||
269 | auto tN = std::chrono::steady_clock::now(); | |
270 | std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n"; | |
271 | ||
272 | rec.time_ = ( tN - t0 ) / 1ms; | |
273 | times.push_back( rec ); | |
274 | } | |
275 | ||
276 | // multi_index emulation of unordered_map | |
277 | ||
278 | template<class K, class V> struct pair | |
279 | { | |
280 | K first; | |
281 | mutable V second; | |
282 | }; | |
283 | ||
284 | using namespace boost::multi_index; | |
285 | ||
286 | template<class K, class V> using multi_index_map = multi_index_container< | |
287 | pair<K, V>, | |
288 | indexed_by< | |
289 | hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> > | |
290 | >, | |
291 | ::allocator< pair<K, V> > | |
292 | >; | |
293 | ||
294 | // aliases using the counting allocator | |
295 | ||
296 | template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >; | |
297 | ||
298 | template<class K, class V> using std_unordered_map = | |
299 | std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>; | |
300 | ||
301 | template<class K, class V> using boost_unordered_map = | |
302 | boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>; | |
303 | ||
304 | #ifdef HAVE_ABSEIL | |
305 | ||
306 | template<class K, class V> using absl_node_hash_map = | |
307 | absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>; | |
308 | ||
309 | template<class K, class V> using absl_flat_hash_map = | |
310 | absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>; | |
311 | ||
312 | #endif | |
313 | ||
314 | int main() | |
315 | { | |
316 | init_indices(); | |
317 | ||
318 | test<std_unordered_map>( "std::unordered_map" ); | |
319 | test<boost_unordered_map>( "boost::unordered_map" ); | |
320 | test<multi_index_map>( "multi_index_map" ); | |
321 | ||
322 | #ifdef HAVE_ABSEIL | |
323 | ||
324 | test<absl_node_hash_map>( "absl::node_hash_map" ); | |
325 | test<absl_flat_hash_map>( "absl::flat_hash_map" ); | |
326 | ||
327 | #endif | |
328 | ||
329 | std::cout << "---\n\n"; | |
330 | ||
331 | for( auto const& x: times ) | |
332 | { | |
333 | std::cout << std::setw( 25 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n"; | |
334 | } | |
335 | } | |
336 | ||
337 | #ifdef HAVE_ABSEIL | |
338 | # include "absl/container/internal/raw_hash_set.cc" | |
339 | # include "absl/hash/internal/hash.cc" | |
340 | # include "absl/hash/internal/low_level_hash.cc" | |
341 | # include "absl/hash/internal/city.cc" | |
342 | #endif |