ceph/src/boost/libs/unordered/benchmark/string.cpp

   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::string> indices1, indices2;
  40
  41 static std::string make_index( unsigned x )
  42 {
  43     char buffer[ 64 ];
  44     std::snprintf( buffer, sizeof(buffer), "pfx_%u_sfx", x );
  45
  46     return buffer;
  47 }
  48
  49 static std::string make_random_index( unsigned x )
  50 {
  51     char buffer[ 64 ];
  52     std::snprintf( buffer, sizeof(buffer), "pfx_%0*d_%u_sfx", x % 8 + 1, 0, x );
  53
  54     return buffer;
  55 }
  56
  57 static void init_indices()
  58 {
  59     indices1.reserve( N*2+1 );
  60     indices1.push_back( make_index( 0 ) );
  61
  62     for( unsigned i = 1; i <= N*2; ++i )
  63     {
  64         indices1.push_back( make_index( i ) );
  65     }
  66
  67     indices2.reserve( N*2+1 );
  68     indices2.push_back( make_index( 0 ) );
  69
  70     {
  71         boost::detail::splitmix64 rng;
  72
  73         for( unsigned i = 1; i <= N*2; ++i )
  74         {
  75             indices2.push_back( make_random_index( static_cast<std::uint32_t>( rng() ) ) );
  76         }
  77     }
  78 }
  79
  80 template<class Map> BOOST_NOINLINE void test_insert( Map& map, std::chrono::steady_clock::time_point & t1 )
  81 {
  82     for( unsigned i = 1; i <= N; ++i )
  83     {
  84         map.insert( { indices1[ i ], i } );
  85     }
  86
  87     print_time( t1, "Consecutive insert",  0, map.size() );
  88
  89     for( unsigned i = 1; i <= N; ++i )
  90     {
  91         map.insert( { indices2[ i ], i } );
  92     }
  93
  94     print_time( t1, "Random insert",  0, map.size() );
  95
  96     std::cout << std::endl;
  97 }
  98
  99 template<class Map> BOOST_NOINLINE void test_lookup( Map& map, std::chrono::steady_clock::time_point & t1 )
 100 {
 101     std::uint32_t s;
 102
 103     s = 0;
 104
 105     for( int j = 0; j < K; ++j )
 106     {
 107         for( unsigned i = 1; i <= N * 2; ++i )
 108         {
 109             auto it = map.find( indices1[ i ] );
 110             if( it != map.end() ) s += it->second;
 111         }
 112     }
 113
 114     print_time( t1, "Consecutive lookup",  s, map.size() );
 115
 116     s = 0;
 117
 118     for( int j = 0; j < K; ++j )
 119     {
 120         for( unsigned i = 1; i <= N * 2; ++i )
 121         {
 122             auto it = map.find( indices2[ i ] );
 123             if( it != map.end() ) s += it->second;
 124         }
 125     }
 126
 127     print_time( t1, "Random lookup",  s, map.size() );
 128
 129     std::cout << std::endl;
 130 }
 131
 132 template<class Map> BOOST_NOINLINE void test_iteration( Map& map, std::chrono::steady_clock::time_point & t1 )
 133 {
 134     auto it = map.begin();
 135
 136     while( it != map.end() )
 137     {
 138         if( it->second & 1 )
 139         {
 140             map.erase( it++ );
 141         }
 142         else
 143         {
 144             ++it;
 145         }
 146     }
 147
 148     print_time( t1, "Iterate and erase odd elements",  0, map.size() );
 149
 150     std::cout << std::endl;
 151 }
 152
 153 template<class Map> BOOST_NOINLINE void test_erase( Map& map, std::chrono::steady_clock::time_point & t1 )
 154 {
 155     for( unsigned i = 1; i <= N; ++i )
 156     {
 157         map.erase( indices1[ i ] );
 158     }
 159
 160     print_time( t1, "Consecutive erase",  0, map.size() );
 161
 162     {
 163         boost::detail::splitmix64 rng;
 164
 165         for( unsigned i = 1; i <= N; ++i )
 166         {
 167             map.erase( indices2[ i ] );
 168         }
 169     }
 170
 171     print_time( t1, "Random erase",  0, map.size() );
 172
 173     std::cout << std::endl;
 174 }
 175
 176 // counting allocator
 177
 178 static std::size_t s_alloc_bytes = 0;
 179 static std::size_t s_alloc_count = 0;
 180
 181 template<class T> struct allocator
 182 {
 183     using value_type = T;
 184
 185     allocator() = default;
 186
 187     template<class U> allocator( allocator<U> const & ) noexcept
 188     {
 189     }
 190
 191     template<class U> bool operator==( allocator<U> const & ) const noexcept
 192     {
 193         return true;
 194     }
 195
 196     template<class U> bool operator!=( allocator<U> const& ) const noexcept
 197     {
 198         return false;
 199     }
 200
 201     T* allocate( std::size_t n ) const
 202     {
 203         s_alloc_bytes += n * sizeof(T);
 204         s_alloc_count++;
 205
 206         return std::allocator<T>().allocate( n );
 207     }
 208
 209     void deallocate( T* p, std::size_t n ) const noexcept
 210     {
 211         s_alloc_bytes -= n * sizeof(T);
 212         s_alloc_count--;
 213
 214         std::allocator<T>().deallocate( p, n );
 215     }
 216 };
 217
 218 //
 219
 220 struct record
 221 {
 222     std::string label_;
 223     long long time_;
 224     std::size_t bytes_;
 225     std::size_t count_;
 226 };
 227
 228 static std::vector<record> times;
 229
 230 template<template<class...> class Map> BOOST_NOINLINE void test( char const* label )
 231 {
 232     std::cout << label << ":\n\n";
 233
 234     s_alloc_bytes = 0;
 235     s_alloc_count = 0;
 236
 237     Map<std::string, std::uint32_t> map;
 238
 239     auto t0 = std::chrono::steady_clock::now();
 240     auto t1 = t0;
 241
 242     test_insert( map, t1 );
 243
 244     std::cout << "Memory: " << s_alloc_bytes << " bytes in " << s_alloc_count << " allocations\n\n";
 245
 246     record rec = { label, 0, s_alloc_bytes, s_alloc_count };
 247
 248     test_lookup( map, t1 );
 249     test_iteration( map, t1 );
 250     test_lookup( map, t1 );
 251     test_erase( map, t1 );
 252
 253     auto tN = std::chrono::steady_clock::now();
 254     std::cout << "Total: " << ( tN - t0 ) / 1ms << " ms\n\n";
 255
 256     rec.time_ = ( tN - t0 ) / 1ms;
 257     times.push_back( rec );
 258 }
 259
 260 // multi_index emulation of unordered_map
 261
 262 template<class K, class V> struct pair
 263 {
 264     K first;
 265     mutable V second;
 266 };
 267
 268 using namespace boost::multi_index;
 269
 270 template<class K, class V> using multi_index_map = multi_index_container<
 271   pair<K, V>,
 272   indexed_by<
 273     hashed_unique< member<pair<K, V>, K, &pair<K, V>::first> >
 274   >,
 275   ::allocator< pair<K, V> >
 276 >;
 277
 278 // aliases using the counting allocator
 279
 280 template<class K, class V> using allocator_for = ::allocator< std::pair<K const, V> >;
 281
 282 template<class K, class V> using std_unordered_map =
 283     std::unordered_map<K, V, std::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 284
 285 template<class K, class V> using boost_unordered_map =
 286     boost::unordered_map<K, V, boost::hash<K>, std::equal_to<K>, allocator_for<K, V>>;
 287
 288 #ifdef HAVE_ABSEIL
 289
 290 template<class K, class V> using absl_node_hash_map =
 291     absl::node_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
 292
 293 template<class K, class V> using absl_flat_hash_map =
 294     absl::flat_hash_map<K, V, absl::container_internal::hash_default_hash<K>, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
 295
 296 #endif
 297
 298 // fnv1a_hash
 299
 300 template<int Bits> struct fnv1a_hash_impl;
 301
 302 template<> struct fnv1a_hash_impl<32>
 303 {
 304     std::size_t operator()( std::string const& s ) const
 305     {
 306         std::size_t h = 0x811C9DC5u;
 307
 308         char const * first = s.data();
 309         char const * last = first + s.size();
 310
 311         for( ; first != last; ++first )
 312         {
 313             h ^= static_cast<unsigned char>( *first );
 314             h *= 0x01000193ul;
 315         }
 316
 317         return h;
 318     }
 319 };
 320
 321 template<> struct fnv1a_hash_impl<64>
 322 {
 323     std::size_t operator()( std::string const& s ) const
 324     {
 325         std::size_t h = 0xCBF29CE484222325ull;
 326
 327         char const * first = s.data();
 328         char const * last = first + s.size();
 329
 330         for( ; first != last; ++first )
 331         {
 332             h ^= static_cast<unsigned char>( *first );
 333             h *= 0x00000100000001B3ull;
 334         }
 335
 336         return h;
 337     }
 338 };
 339
 340 struct fnv1a_hash: fnv1a_hash_impl< std::numeric_limits<std::size_t>::digits > {};
 341
 342 template<class K, class V> using std_unordered_map_fnv1a =
 343 std::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 344
 345 template<class K, class V> using boost_unordered_map_fnv1a =
 346     boost::unordered_map<K, V, fnv1a_hash, std::equal_to<K>, allocator_for<K, V>>;
 347
 348 template<class K, class V> using multi_index_map_fnv1a = multi_index_container<
 349   pair<K, V>,
 350   indexed_by<
 351     hashed_unique< member<pair<K, V>, K, &pair<K, V>::first>, fnv1a_hash >
 352   >,
 353   ::allocator< pair<K, V> >
 354 >;
 355
 356 #ifdef HAVE_ABSEIL
 357
 358 template<class K, class V> using absl_node_hash_map_fnv1a =
 359     absl::node_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
 360
 361 template<class K, class V> using absl_flat_hash_map_fnv1a =
 362     absl::flat_hash_map<K, V, fnv1a_hash, absl::container_internal::hash_default_eq<K>, allocator_for<K, V>>;
 363
 364 #endif
 365
 366 //
 367
 368 int main()
 369 {
 370     init_indices();
 371
 372 #if 0
 373
 374     test<std_unordered_map>( "std::unordered_map" );
 375     test<boost_unordered_map>( "boost::unordered_map" );
 376     test<multi_index_map>( "multi_index_map" );
 377
 378 #ifdef HAVE_ABSEIL
 379
 380     test<absl_node_hash_map>( "absl::node_hash_map" );
 381     test<absl_flat_hash_map>( "absl::flat_hash_map" );
 382
 383 #endif
 384
 385 #endif
 386
 387     test<std_unordered_map_fnv1a>( "std::unordered_map, FNV-1a" );
 388     test<boost_unordered_map_fnv1a>( "boost::unordered_map, FNV-1a" );
 389     test<multi_index_map_fnv1a>( "multi_index_map, FNV-1a" );
 390
 391 #ifdef HAVE_ABSEIL
 392
 393     test<absl_node_hash_map_fnv1a>( "absl::node_hash_map, FNV-1a" );
 394     test<absl_flat_hash_map_fnv1a>( "absl::flat_hash_map, FNV-1a" );
 395
 396 #endif
 397
 398     std::cout << "---\n\n";
 399
 400     for( auto const& x: times )
 401     {
 402         std::cout << std::setw( 30 ) << ( x.label_ + ": " ) << std::setw( 5 ) << x.time_ << " ms, " << std::setw( 9 ) << x.bytes_ << " bytes in " << x.count_ << " allocations\n";
 403     }
 404 }
 405
 406 #ifdef HAVE_ABSEIL
 407 # include "absl/container/internal/raw_hash_set.cc"
 408 # include "absl/hash/internal/hash.cc"
 409 # include "absl/hash/internal/low_level_hash.cc"
 410 # include "absl/hash/internal/city.cc"
 411 #endif