test/stress/map/insdel_func/map_insdel_func.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #include "map_type.h"
  32
  33 namespace map {
  34
  35     class Map_InsDel_func: public cds_test::stress_fixture
  36     {
  37     public:
  38         static size_t s_nMapSize;           // map size
  39         static size_t s_nInsertThreadCount; // count of insertion thread
  40         static size_t s_nDeleteThreadCount; // count of deletion thread
  41         static size_t s_nUpdateThreadCount; // count of updating thread
  42         static size_t s_nThreadPassCount;   // pass count for each thread
  43         static size_t s_nMaxLoadFactor;     // maximum load factor
  44
  45         static size_t s_nCuckooInitialSize;         // initial size for CuckooMap
  46         static size_t s_nCuckooProbesetSize;        // CuckooMap probeset size (only for list-based probeset)
  47         static size_t s_nCuckooProbesetThreshold;   // CuckooMap probeset threshold (o - use default)
  48
  49         static size_t s_nFeldmanMap_HeadBits;
  50         static size_t s_nFeldmanMap_ArrayBits;
  51
  52         static size_t s_nLoadFactor;  // current load factor
  53
  54         static void SetUpTestCase();
  55         static void TearDownTestCase();
  56
  57         typedef size_t  key_type;
  58         struct value_type {
  59             size_t      nKey;
  60             size_t      nData;
  61             size_t      nUpdateCall;
  62             atomics::atomic<bool>   bInitialized;
  63             cds::OS::ThreadId       threadId;   // inserter thread id
  64
  65             typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
  66             mutable lock_type   m_access;
  67
  68             value_type()
  69                 : nKey(0)
  70                 , nData(0)
  71                 , nUpdateCall(0)
  72                 , bInitialized( false )
  73                 , threadId( cds::OS::get_current_thread_id())
  74             {}
  75
  76             value_type( value_type const& s )
  77                 : nKey(s.nKey)
  78                 , nData(s.nData)
  79                 , nUpdateCall( s.nUpdateCall )
  80                 , bInitialized( s.bInitialized.load(atomics::memory_order_relaxed))
  81                 , threadId( cds::OS::get_current_thread_id())
  82                 , m_access()
  83             {}
  84
  85             // boost::container::flat_map requires operator =
  86             // cppcheck-suppress operatorEqVarError
  87             value_type& operator=( value_type const& v )
  88             {
  89                 nKey = v.nKey;
  90                 nData = v.nData;
  91                 nUpdateCall = v.nUpdateCall;
  92                 threadId = v.threadId;
  93                 bInitialized.store(v.bInitialized.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed);
  94
  95                 return *this;
  96             }
  97         };
  98
  99         typedef std::vector<key_type>   key_array;
 100         static key_array                s_arrKeys;
 101
 102     protected:
 103         enum {
 104             insert_thread,
 105             delete_thread,
 106             update_thread
 107         };
 108
 109         template <class Map>
 110         class Inserter: public cds_test::thread
 111         {
 112             typedef cds_test::thread base_class;
 113             Map&     m_Map;
 114
 115             struct insert_functor {
 116                 size_t nTestFunctorRef;
 117
 118                 insert_functor()
 119                     : nTestFunctorRef(0)
 120                 {}
 121
 122                 template <typename Pair>
 123                 void operator()( Pair& val )
 124                 {
 125                     operator()( val.first, val.second );
 126                 }
 127
 128                 template <typename Key, typename Val >
 129                 void operator()( Key const& key, Val& v )
 130                 {
 131                     std::unique_lock< typename value_type::lock_type> ac( v.m_access );
 132
 133                     v.nKey  = key;
 134                     v.nData = key * 8;
 135
 136                     ++nTestFunctorRef;
 137                     v.bInitialized.store( true, atomics::memory_order_relaxed);
 138                 }
 139             };
 140
 141         public:
 142             size_t  m_nInsertSuccess = 0;
 143             size_t  m_nInsertFailed = 0;
 144
 145             size_t  m_nTestFunctorRef = 0;
 146
 147         public:
 148             Inserter( cds_test::thread_pool& pool, Map& map )
 149                 : base_class( pool, insert_thread )
 150                 , m_Map( map )
 151             {}
 152
 153             Inserter( Inserter& src )
 154                 : base_class( src )
 155                 , m_Map( src.m_Map )
 156             {}
 157
 158             virtual thread * clone()
 159             {
 160                 return new Inserter( *this );
 161             }
 162
 163             virtual void test()
 164             {
 165                 Map& rMap = m_Map;
 166
 167                 // func is passed by reference
 168                 insert_functor  func;
 169                 size_t const nPassCount = s_nThreadPassCount;
 170
 171                 if ( id() & 1 ) {
 172                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 173                         for ( key_array::const_iterator it = s_arrKeys.begin(), itEnd = s_arrKeys.end(); it != itEnd; ++it ) {
 174                             if ( rMap.insert_with( *it, std::ref(func)))
 175                                 ++m_nInsertSuccess;
 176                             else
 177                                 ++m_nInsertFailed;
 178                         }
 179                     }
 180                 }
 181                 else {
 182                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 183                         for ( key_array::const_reverse_iterator it = s_arrKeys.rbegin(), itEnd = s_arrKeys.rend(); it != itEnd; ++it ) {
 184                             if ( rMap.insert_with( *it, std::ref(func)))
 185                                 ++m_nInsertSuccess;
 186                             else
 187                                 ++m_nInsertFailed;
 188                         }
 189                     }
 190                 }
 191
 192                 m_nTestFunctorRef = func.nTestFunctorRef;
 193             }
 194         };
 195
 196         template <class Map>
 197         class Updater: public cds_test::thread
 198         {
 199             typedef cds_test::thread base_class;
 200             Map&     m_Map;
 201
 202             struct update_functor {
 203                 size_t  nCreated = 0;
 204                 size_t  nModified = 0;
 205
 206                 update_functor() = default;
 207
 208                 template <typename Key, typename Val>
 209                 void operator()( bool /*bNew*/, Key const& key, Val& v )
 210                 {
 211                     std::unique_lock<typename value_type::lock_type> ac( v.m_access );
 212                     if ( !v.bInitialized.load( atomics::memory_order_acquire )) {
 213                         ++nCreated;
 214                         v.nKey = key;
 215                         v.nData = key * 8;
 216                         v.bInitialized.store( true, atomics::memory_order_relaxed);
 217                     }
 218                     else {
 219                         ++v.nUpdateCall;
 220                         ++nModified;
 221                     }
 222                 }
 223
 224                 template <typename Pair>
 225                 void operator()( bool bNew, Pair& val )
 226                 {
 227                     operator()( bNew, val.first, val.second );
 228                 }
 229
 230                 // For FeldmanHashMap
 231                 template <typename Val>
 232                 void operator()( Val& cur, Val * old )
 233                 {
 234                     if ( old ) {
 235                         // If a key exists, FeldmanHashMap creates a new node too
 236                         // We should manually copy important values from old to cur
 237                         std::unique_lock<typename value_type::lock_type> ac( cur.second.m_access );
 238                         cur.second.nKey = cur.first;
 239                         cur.second.nData = cur.first * 8;
 240                         cur.second.bInitialized.store( true, atomics::memory_order_release );
 241                     }
 242                     operator()( old == nullptr, cur.first, cur.second );
 243                 }
 244
 245             private:
 246                 update_functor(const update_functor& ) = delete;
 247             };
 248
 249         public:
 250             size_t  m_nUpdateFailed = 0;
 251             size_t  m_nUpdateCreated = 0;
 252             size_t  m_nUpdateExisted = 0;
 253             size_t  m_nFunctorCreated = 0;
 254             size_t  m_nFunctorModified = 0;
 255
 256         public:
 257             Updater( cds_test::thread_pool& pool, Map& map )
 258                 : base_class( pool, update_thread )
 259                 , m_Map( map )
 260             {}
 261
 262             Updater( Updater& src )
 263                 : base_class( src )
 264                 , m_Map( src.m_Map )
 265             {}
 266
 267             virtual thread * clone()
 268             {
 269                 return new Updater( *this );
 270             }
 271
 272             virtual void test()
 273             {
 274                 Map& rMap = m_Map;
 275
 276                 update_functor func;
 277                 size_t const nPassCount = s_nThreadPassCount;
 278
 279                 if ( id() & 1 ) {
 280                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 281                         for ( key_array::const_iterator it = s_arrKeys.begin(), itEnd = s_arrKeys.end(); it != itEnd; ++it ) {
 282                             std::pair<bool, bool> ret = rMap.update( *it, std::ref( func ));
 283                             if ( ret.first  ) {
 284                                 if ( ret.second )
 285                                     ++m_nUpdateCreated;
 286                                 else
 287                                     ++m_nUpdateExisted;
 288                             }
 289                             else
 290                                 ++m_nUpdateFailed;
 291                         }
 292                     }
 293                 }
 294                 else {
 295                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 296                         for ( key_array::const_reverse_iterator it = s_arrKeys.rbegin(), itEnd = s_arrKeys.rend(); it != itEnd; ++it ) {
 297                             std::pair<bool, bool> ret = rMap.update( *it, std::ref( func ));
 298                             if ( ret.first  ) {
 299                                 if ( ret.second )
 300                                     ++m_nUpdateCreated;
 301                                 else
 302                                     ++m_nUpdateExisted;
 303                             }
 304                             else
 305                                 ++m_nUpdateFailed;
 306                         }
 307                     }
 308                 }
 309
 310                 m_nFunctorCreated = func.nCreated;
 311                 m_nFunctorModified = func.nModified;
 312             }
 313         };
 314
 315         template <class Map>
 316         class Deleter: public cds_test::thread
 317         {
 318             Map&     m_Map;
 319             typedef cds_test::thread base_class;
 320             typedef typename Map::mapped_type value_type;
 321
 322             struct value_container
 323             {
 324                 size_t      nKeyExpected;
 325
 326                 size_t      nSuccessItem;
 327                 size_t      nFailedItem;
 328
 329                 value_container()
 330                     : nKeyExpected()
 331                     , nSuccessItem(0)
 332                     , nFailedItem(0)
 333                 {}
 334             };
 335
 336             struct erase_functor {
 337                 value_container     m_cnt;
 338
 339                 template <typename Key, typename Val>
 340                 void operator()( Key const& /*key*/, Val& v )
 341                 {
 342                     while ( true ) {
 343                         if ( v.bInitialized.load( atomics::memory_order_relaxed )) {
 344                             std::unique_lock< typename value_type::lock_type> ac( v.m_access );
 345
 346                             if ( m_cnt.nKeyExpected == v.nKey && m_cnt.nKeyExpected * 8 == v.nData )
 347                                 ++m_cnt.nSuccessItem;
 348                             else
 349                                 ++m_cnt.nFailedItem;
 350                             v.nData++;
 351                             v.nKey = 0;
 352                             break;
 353                         }
 354                         else
 355                             cds::backoff::yield()();
 356                     }
 357                 }
 358
 359                 template <typename Pair>
 360                 void operator ()( Pair& item )
 361                 {
 362                     operator()( item.first, item.second );
 363                 }
 364             };
 365
 366         public:
 367             size_t  m_nDeleteSuccess = 0;
 368             size_t  m_nDeleteFailed = 0;
 369             size_t  m_nValueSuccess = 0;
 370             size_t  m_nValueFailed = 0;
 371
 372         public:
 373             Deleter( cds_test::thread_pool& pool, Map& map )
 374                 : base_class( pool, delete_thread )
 375                 , m_Map( map )
 376             {}
 377
 378             Deleter( Deleter& src )
 379                 : base_class( src )
 380                 , m_Map( src.m_Map )
 381             {}
 382
 383             virtual thread * clone()
 384             {
 385                 return new Deleter( *this );
 386             }
 387
 388             virtual void test()
 389             {
 390                 Map& rMap = m_Map;
 391
 392                 erase_functor   func;
 393                 size_t const nPassCount = s_nThreadPassCount;
 394
 395                 if ( id() & 1 ) {
 396                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 397                         for ( key_array::const_iterator it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend(); it != itEnd; ++it ) {
 398                             func.m_cnt.nKeyExpected = *it;
 399                             if ( rMap.erase( *it, std::ref(func)))
 400                                 ++m_nDeleteSuccess;
 401                             else
 402                                 ++m_nDeleteFailed;
 403                         }
 404                     }
 405                 }
 406                 else {
 407                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 408                         for ( key_array::const_reverse_iterator it = s_arrKeys.crbegin(), itEnd = s_arrKeys.crend(); it != itEnd; ++it ) {
 409                             func.m_cnt.nKeyExpected = *it;
 410                             if ( rMap.erase( *it, std::ref(func)))
 411                                 ++m_nDeleteSuccess;
 412                             else
 413                                 ++m_nDeleteFailed;
 414                         }
 415                     }
 416                 }
 417
 418                 m_nValueSuccess = func.m_cnt.nSuccessItem;
 419                 m_nValueFailed = func.m_cnt.nFailedItem;
 420             }
 421         };
 422
 423     protected:
 424
 425         template <class Map>
 426         void do_test( Map& testMap )
 427         {
 428             typedef Inserter<Map> inserter;
 429             typedef Deleter<Map>  deleter;
 430             typedef Updater<Map>  updater;
 431
 432             cds_test::thread_pool& pool = get_pool();
 433             pool.add( new inserter( pool, testMap ), s_nInsertThreadCount );
 434             pool.add( new deleter( pool, testMap ), s_nDeleteThreadCount );
 435             pool.add( new updater( pool, testMap ), s_nUpdateThreadCount );
 436
 437             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 438                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
 439                 << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
 440                 << std::make_pair( "pass_count", s_nThreadPassCount )
 441                 << std::make_pair( "map_size", s_nMapSize );
 442
 443             std::chrono::milliseconds duration = pool.run();
 444
 445             propout() << std::make_pair( "duration", duration );
 446
 447             size_t nInsertSuccess = 0;
 448             size_t nInsertFailed = 0;
 449             size_t nDeleteSuccess = 0;
 450             size_t nDeleteFailed = 0;
 451             size_t nDelValueSuccess = 0;
 452             size_t nDelValueFailed = 0;
 453             size_t nUpdateFailed = 0;
 454             size_t nUpdateCreated = 0;
 455             size_t nUpdateModified = 0;
 456             size_t nEnsFuncCreated = 0;
 457             size_t nEnsFuncModified = 0;
 458             size_t nInsFuncCalled = 0;
 459
 460             for ( size_t i = 0; i < pool.size(); ++i ) {
 461                 cds_test::thread& thr = pool.get( i );
 462                 switch ( thr.type() ) {
 463                 case insert_thread:
 464                     {
 465                         inserter& t = static_cast<inserter&>( thr );
 466                         nInsertSuccess += t.m_nInsertSuccess;
 467                         nInsertFailed += t.m_nInsertFailed;
 468                         nInsFuncCalled += t.m_nTestFunctorRef;
 469                     }
 470                     break;
 471                 case delete_thread:
 472                     {
 473                         deleter& t = static_cast<deleter&>(thr);
 474                         nDeleteSuccess += t.m_nDeleteSuccess;
 475                         nDeleteFailed += t.m_nDeleteFailed;
 476                         nDelValueSuccess += t.m_nValueSuccess;
 477                         nDelValueFailed += t.m_nValueFailed;
 478                     }
 479                     break;
 480                 case update_thread:
 481                     {
 482                         updater& t = static_cast<updater&>(thr);
 483                         nUpdateCreated += t.m_nUpdateCreated;
 484                         nUpdateModified += t.m_nUpdateExisted;
 485                         nUpdateFailed += t.m_nUpdateFailed;
 486                         nEnsFuncCreated += t.m_nFunctorCreated;
 487                         nEnsFuncModified += t.m_nFunctorModified;
 488                     }
 489                     break;
 490                 default:
 491                     assert( false );
 492                 }
 493             }
 494
 495             propout()
 496                 << std::make_pair( "insert_success", nInsertSuccess )
 497                 << std::make_pair( "insert_failed",  nInsertFailed )
 498                 << std::make_pair( "delete_success", nDeleteSuccess )
 499                 << std::make_pair( "delete_failed",  nDeleteFailed )
 500                 << std::make_pair( "update_success", nUpdateCreated + nUpdateModified )
 501                 << std::make_pair( "update_failed",  nUpdateFailed )
 502                 << std::make_pair( "update_functor_create", nEnsFuncCreated )
 503                 << std::make_pair( "update_functor_modify", nEnsFuncModified )
 504                 << std::make_pair( "finish_map_size", testMap.size() );
 505
 506             EXPECT_EQ( nDelValueFailed, 0 );
 507             EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
 508             EXPECT_EQ( nUpdateFailed, 0 );
 509             EXPECT_EQ( nUpdateCreated + nUpdateModified, nEnsFuncCreated + nEnsFuncModified );
 510
 511             // nInsFuncCalled is call count of insert functor
 512             EXPECT_EQ( nInsFuncCalled, nInsertSuccess );
 513
 514             check_before_cleanup( testMap );
 515
 516             for ( size_t nItem = 0; nItem < s_nMapSize; ++nItem )
 517                 testMap.erase( nItem );
 518
 519             EXPECT_TRUE( testMap.empty());
 520
 521             additional_check( testMap );
 522             print_stat( propout(), testMap );
 523             additional_cleanup( testMap );
 524         }
 525
 526         template <class Map>
 527         void run_test()
 528         {
 529             Map testMap( *this );
 530             do_test( testMap );
 531         }
 532     };
 533
 534     class Map_InsDel_func_LF: public Map_InsDel_func
 535         , public ::testing::WithParamInterface<size_t>
 536     {
 537     public:
 538         template <class Set>
 539         void run_test()
 540         {
 541             s_nLoadFactor = GetParam();
 542             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 543             Map_InsDel_func::run_test<Set>();
 544         }
 545
 546         static std::vector<size_t> get_load_factors();
 547     };
 548
 549 } // namespace map