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, IterableList
 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             if ( s_nUpdateThreadCount )
 436                 pool.add( new updater( pool, testMap ), s_nUpdateThreadCount );
 437
 438             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 439                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
 440                 << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
 441                 << std::make_pair( "pass_count", s_nThreadPassCount )
 442                 << std::make_pair( "map_size", s_nMapSize );
 443
 444             std::chrono::milliseconds duration = pool.run();
 445
 446             propout() << std::make_pair( "duration", duration );
 447
 448             size_t nInsertSuccess = 0;
 449             size_t nInsertFailed = 0;
 450             size_t nDeleteSuccess = 0;
 451             size_t nDeleteFailed = 0;
 452             size_t nDelValueSuccess = 0;
 453             size_t nDelValueFailed = 0;
 454             size_t nUpdateFailed = 0;
 455             size_t nUpdateCreated = 0;
 456             size_t nUpdateModified = 0;
 457             size_t nEnsFuncCreated = 0;
 458             size_t nEnsFuncModified = 0;
 459             size_t nInsFuncCalled = 0;
 460
 461             for ( size_t i = 0; i < pool.size(); ++i ) {
 462                 cds_test::thread& thr = pool.get( i );
 463                 switch ( thr.type()) {
 464                 case insert_thread:
 465                     {
 466                         inserter& t = static_cast<inserter&>( thr );
 467                         nInsertSuccess += t.m_nInsertSuccess;
 468                         nInsertFailed += t.m_nInsertFailed;
 469                         nInsFuncCalled += t.m_nTestFunctorRef;
 470                     }
 471                     break;
 472                 case delete_thread:
 473                     {
 474                         deleter& t = static_cast<deleter&>(thr);
 475                         nDeleteSuccess += t.m_nDeleteSuccess;
 476                         nDeleteFailed += t.m_nDeleteFailed;
 477                         nDelValueSuccess += t.m_nValueSuccess;
 478                         nDelValueFailed += t.m_nValueFailed;
 479                     }
 480                     break;
 481                 case update_thread:
 482                     {
 483                         updater& t = static_cast<updater&>(thr);
 484                         nUpdateCreated += t.m_nUpdateCreated;
 485                         nUpdateModified += t.m_nUpdateExisted;
 486                         nUpdateFailed += t.m_nUpdateFailed;
 487                         nEnsFuncCreated += t.m_nFunctorCreated;
 488                         nEnsFuncModified += t.m_nFunctorModified;
 489                     }
 490                     break;
 491                 default:
 492                     assert( false );
 493                 }
 494             }
 495
 496             propout()
 497                 << std::make_pair( "insert_success", nInsertSuccess )
 498                 << std::make_pair( "insert_failed",  nInsertFailed )
 499                 << std::make_pair( "delete_success", nDeleteSuccess )
 500                 << std::make_pair( "delete_failed",  nDeleteFailed )
 501                 << std::make_pair( "update_success", nUpdateCreated + nUpdateModified )
 502                 << std::make_pair( "update_failed",  nUpdateFailed )
 503                 << std::make_pair( "update_functor_create", nEnsFuncCreated )
 504                 << std::make_pair( "update_functor_modify", nEnsFuncModified )
 505                 << std::make_pair( "finish_map_size", testMap.size());
 506
 507             EXPECT_EQ( nDelValueFailed, 0u );
 508             EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
 509             EXPECT_EQ( nUpdateFailed, 0u );
 510             EXPECT_EQ( nUpdateCreated + nUpdateModified, nEnsFuncCreated + nEnsFuncModified );
 511
 512             // nInsFuncCalled is call count of insert functor
 513             EXPECT_EQ( nInsFuncCalled, nInsertSuccess );
 514
 515             check_before_cleanup( testMap );
 516
 517             for ( size_t nItem = 0; nItem < s_nMapSize; ++nItem )
 518                 testMap.erase( nItem );
 519
 520             EXPECT_TRUE( testMap.empty());
 521             EXPECT_EQ( testMap.size(), 0u );
 522
 523             additional_check( testMap );
 524             print_stat( propout(), testMap );
 525             additional_cleanup( testMap );
 526         }
 527
 528         template <class Map>
 529         void run_test()
 530         {
 531             Map testMap( *this );
 532             do_test( testMap );
 533         }
 534
 535         template <class Map>
 536         void run_test2()
 537         {
 538             Map testMap( *this );
 539             do_test( testMap );
 540
 541             if ( testMap.size() != 0 ) {
 542                 for ( auto it = testMap.begin(); it != testMap.end(); ++it ) {
 543                     std::cout << "key=" << it->first << std::endl;
 544                 }
 545             }
 546         }
 547     };
 548
 549     class Map_InsDel_func_LF: public Map_InsDel_func
 550         , public ::testing::WithParamInterface<size_t>
 551     {
 552     public:
 553         template <class Set>
 554         void run_test()
 555         {
 556             s_nLoadFactor = GetParam();
 557             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 558             Map_InsDel_func::run_test<Set>();
 559         }
 560
 561         template <class Set>
 562         void run_test2()
 563         {
 564             s_nLoadFactor = GetParam();
 565             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 566             Map_InsDel_func::run_test2<Set>();
 567         }
 568
 569         static std::vector<size_t> get_load_factors();
 570     };
 571
 572 } // namespace map