test/stress/sequential/sequential-set/insdel_func/set_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-2017
   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 "set_type.h"
  32
  33 namespace set {
  34
  35     class Set_InsDel_func: public cds_test::stress_fixture
  36     {
  37     public:
  38         static size_t s_nSetSize;               // set 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 CuckooSet
  46         static size_t s_nCuckooProbesetSize;    // CuckooSet probeset size (only for list-based probeset)
  47         static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
  48
  49         static size_t s_nFeldmanSet_HeadBits;
  50         static size_t s_nFeldmanSet_ArrayBits;
  51
  52         static size_t s_nLoadFactor;
  53
  54         static void SetUpTestCase();
  55         //static void TearDownTestCase();
  56
  57     public:
  58         typedef size_t  key_type;
  59
  60         struct value {
  61             size_t      nKey;
  62             size_t      nData;
  63             atomics::atomic<size_t> nUpdateCall;
  64             bool volatile           bInitialized;
  65             cds::OS::ThreadId       threadId;   // insert thread id
  66
  67             typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
  68             mutable lock_type   m_access;
  69
  70             value()
  71                 : nKey(0)
  72                 , nData(0)
  73                 , nUpdateCall(0)
  74                 , bInitialized( false )
  75                 , threadId( cds::OS::get_current_thread_id())
  76             {}
  77
  78             value( value const& s )
  79                 : nKey(s.nKey)
  80                 , nData(s.nData)
  81                 , nUpdateCall(s.nUpdateCall.load(atomics::memory_order_relaxed))
  82                 , bInitialized( s.bInitialized )
  83                 , threadId( cds::OS::get_current_thread_id())
  84                 , m_access()
  85             {}
  86
  87             // boost::container::flat_map requires operator =
  88             // cppcheck-suppress operatorEqVarError
  89             value& operator=( value const& v )
  90             {
  91                 nKey = v.nKey;
  92                 nData = v.nData;
  93                 threadId = v.threadId;
  94                 nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
  95                 bInitialized = v.bInitialized;
  96
  97                 return *this;
  98             }
  99         };
 100
 101         size_t *    m_pKeyFirst;
 102         size_t *    m_pKeyLast;
 103         std::unique_ptr< size_t[] > m_pKeyArr;
 104
 105         enum {
 106             insert_thread,
 107             update_thread,
 108             delete_thread
 109         };
 110
 111         template <class Set>
 112         class Inserter: public cds_test::thread
 113         {
 114             typedef cds_test::thread base_class;
 115
 116             Set&     m_Set;
 117             typedef typename Set::value_type keyval_type;
 118
 119             struct insert_functor {
 120                 size_t nTestFunctorRef;
 121
 122                 insert_functor()
 123                     : nTestFunctorRef(0)
 124                 {}
 125                 insert_functor( insert_functor const& ) = delete;
 126
 127                 void operator()( keyval_type& val )
 128                 {
 129                     std::unique_lock< typename value::lock_type> ac( val.val.m_access );
 130
 131                     val.val.nKey  = val.key;
 132                     val.val.nData = val.key * 8;
 133
 134                     ++nTestFunctorRef;
 135                     val.val.bInitialized = true;
 136                 }
 137             };
 138
 139         public:
 140             size_t  m_nInsertSuccess = 0;
 141             size_t  m_nInsertFailed = 0;
 142             size_t  m_nTestFunctorRef = 0;
 143
 144         public:
 145             Inserter( cds_test::thread_pool& pool, Set& set )
 146                 : base_class( pool, insert_thread )
 147                 , m_Set( set )
 148             {}
 149
 150             Inserter( Inserter& src )
 151                 : base_class( src )
 152                 , m_Set( src.m_Set )
 153             {}
 154
 155             virtual thread * clone()
 156             {
 157                 return new Inserter( *this );
 158             }
 159
 160             virtual void test()
 161             {
 162                 Set& rSet = m_Set;
 163                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 164
 165                 size_t * pKeyFirst      = fixture.m_pKeyFirst;
 166                 size_t * pKeyLast       = fixture.m_pKeyLast;
 167                 size_t const nPassCount = fixture.s_nThreadPassCount;
 168
 169                 // func is passed by reference
 170                 insert_functor  func;
 171
 172                 if ( id() & 1 ) {
 173                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 174                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 175                             if ( rSet.insert( *p, std::ref( func )))
 176                                 ++m_nInsertSuccess;
 177                             else
 178                                 ++m_nInsertFailed;
 179                         }
 180                     }
 181                 }
 182                 else {
 183                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 184                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 185                             if ( rSet.insert( *p, std::ref( func )))
 186                                 ++m_nInsertSuccess;
 187                             else
 188                                 ++m_nInsertFailed;
 189                         }
 190                     }
 191                 }
 192
 193                 m_nTestFunctorRef = func.nTestFunctorRef;
 194             }
 195         };
 196
 197         template <class Set>
 198         class Updater: public cds_test::thread
 199         {
 200             typedef cds_test::thread base_class;
 201
 202             Set&     m_Set;
 203             typedef typename Set::value_type keyval_type;
 204
 205             struct update_functor {
 206                 size_t  nCreated = 0;
 207                 size_t  nModified = 0;
 208
 209                 update_functor() {}
 210                 update_functor( const update_functor& ) = delete;
 211
 212                 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
 213                 {
 214                     std::unique_lock<typename value::lock_type> ac( val.val.m_access );
 215                     if ( !val.val.bInitialized )
 216                     {
 217                         val.val.nKey = val.key;
 218                         val.val.nData = val.key * 8;
 219                         val.val.bInitialized = true;
 220                     }
 221
 222                     if ( bNew ) {
 223                         ++nCreated;
 224                     }
 225                     else {
 226                         val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
 227                         ++nModified;
 228                     }
 229                 }
 230
 231                 void operator()( keyval_type& cur, keyval_type * old )
 232                 {
 233                     operator()( old == nullptr, cur, 0 );
 234                 }
 235             };
 236
 237         public:
 238             size_t  m_nUpdateFailed = 0;
 239             size_t  m_nUpdateCreated = 0;
 240             size_t  m_nUpdateExisted = 0;
 241             size_t  m_nFunctorCreated = 0;
 242             size_t  m_nFunctorModified = 0;
 243
 244         public:
 245             Updater( cds_test::thread_pool& pool, Set& set )
 246                 : base_class( pool, update_thread )
 247                 , m_Set( set )
 248             {}
 249
 250             Updater( Updater& src )
 251                 : base_class( src )
 252                 , m_Set( src.m_Set )
 253             {}
 254
 255             virtual thread * clone()
 256             {
 257                 return new Updater( *this );
 258             }
 259
 260             virtual void test()
 261             {
 262                 Set& rSet = m_Set;
 263
 264                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 265                 size_t * pKeyFirst = fixture.m_pKeyFirst;
 266                 size_t * pKeyLast = fixture.m_pKeyLast;
 267                 size_t const nPassCount = fixture.s_nThreadPassCount;
 268
 269                 update_functor func;
 270
 271                 if ( id() & 1 ) {
 272                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 273                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 274                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 275                             if ( ret.first  ) {
 276                                 if ( ret.second )
 277                                     ++m_nUpdateCreated;
 278                                 else
 279                                     ++m_nUpdateExisted;
 280                             }
 281                             else
 282                                 ++m_nUpdateFailed;
 283                         }
 284                     }
 285                 }
 286                 else {
 287                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 288                         for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
 289                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 290                             if ( ret.first  ) {
 291                                 if ( ret.second )
 292                                     ++m_nUpdateCreated;
 293                                 else
 294                                     ++m_nUpdateExisted;
 295                             }
 296                             else
 297                                 ++m_nUpdateFailed;
 298                         }
 299                     }
 300                 }
 301
 302                 m_nFunctorCreated = func.nCreated;
 303                 m_nFunctorModified = func.nModified;
 304             }
 305         };
 306
 307         template <class Set>
 308         class Deleter: public cds_test::thread
 309         {
 310             typedef cds_test::thread base_class;
 311
 312             Set&     m_Set;
 313             typedef typename Set::value_type keyval_type;
 314
 315             struct value_container
 316             {
 317                 size_t      nKeyExpected;
 318
 319                 size_t      nSuccessItem = 0;
 320                 size_t      nFailedItem = 0;
 321             };
 322
 323             struct erase_functor {
 324                 value_container     m_cnt;
 325
 326                 void operator ()( keyval_type const& itm )
 327                 {
 328                     keyval_type& item = const_cast<keyval_type&>(itm);
 329                     while ( true ) {
 330                         bool bBkoff = false;
 331                         {
 332                             std::unique_lock< typename value::lock_type> ac( item.val.m_access );
 333                             if ( item.val.bInitialized ) {
 334                                 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
 335                                     ++m_cnt.nSuccessItem;
 336                                 else
 337                                     ++m_cnt.nFailedItem;
 338                                 item.val.nData++;
 339                                 item.val.nKey = 0;
 340                                 break;
 341                             }
 342                             else
 343                                 bBkoff = true;
 344                         }
 345                         if ( bBkoff )
 346                             cds::backoff::yield()();
 347                     }
 348                 }
 349             };
 350
 351         public:
 352             size_t  m_nDeleteSuccess = 0;
 353             size_t  m_nDeleteFailed = 0;
 354             size_t  m_nValueSuccess = 0;
 355             size_t  m_nValueFailed = 0;
 356
 357         public:
 358             Deleter( cds_test::thread_pool& pool, Set& set )
 359                 : base_class( pool, delete_thread )
 360                 , m_Set( set )
 361             {}
 362
 363             Deleter( Deleter& src )
 364                 : base_class( src )
 365                 , m_Set( src.m_Set )
 366             {}
 367
 368             virtual thread * clone()
 369             {
 370                 return new Deleter( *this );
 371             }
 372
 373             virtual void test()
 374             {
 375                 Set& rSet = m_Set;
 376
 377                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 378                 size_t * pKeyFirst      = fixture.m_pKeyFirst;
 379                 size_t * pKeyLast       = fixture.m_pKeyLast;
 380                 size_t const nPassCount = fixture.s_nThreadPassCount;
 381
 382                 erase_functor   func;
 383
 384                 if ( id() & 1 ) {
 385                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 386                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 387                             func.m_cnt.nKeyExpected = *p;
 388                             if ( rSet.erase( *p, std::ref( func )))
 389                                 ++m_nDeleteSuccess;
 390                             else
 391                                 ++m_nDeleteFailed;
 392                         }
 393                     }
 394                 }
 395                 else {
 396                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 397                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 398                             func.m_cnt.nKeyExpected = *p;
 399                             if ( rSet.erase( *p, std::ref( func )))
 400                                 ++m_nDeleteSuccess;
 401                             else
 402                                 ++m_nDeleteFailed;
 403                         }
 404                     }
 405                 }
 406
 407                 m_nValueSuccess = func.m_cnt.nSuccessItem;
 408                 m_nValueFailed = func.m_cnt.nFailedItem;
 409             }
 410         };
 411
 412     protected:
 413
 414         template <class Set>
 415         void run_test( Set& testSet )
 416         {
 417             typedef Inserter<Set>       InserterThread;
 418             typedef Deleter<Set>        DeleterThread;
 419             typedef Updater<Set>        UpdaterThread;
 420
 421             m_pKeyArr.reset( new size_t[ s_nSetSize ] );
 422             m_pKeyFirst = m_pKeyArr.get();
 423             m_pKeyLast = m_pKeyFirst + s_nSetSize;
 424             for ( size_t i = 0; i < s_nSetSize; ++i )
 425                 m_pKeyArr[i] = i;
 426             shuffle( m_pKeyFirst, m_pKeyLast );
 427
 428             cds_test::thread_pool& pool = get_pool();
 429             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
 430             pool.add( new DeleterThread( pool, testSet ),  s_nDeleteThreadCount );
 431             pool.add( new UpdaterThread( pool, testSet ),  s_nUpdateThreadCount );
 432
 433             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 434                 << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
 435                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
 436                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
 437                 << std::make_pair( "set_size", s_nSetSize );
 438
 439             std::chrono::milliseconds duration = pool.run();
 440
 441             propout() << std::make_pair( "duration", duration );
 442
 443             size_t nInsertSuccess = 0;
 444             size_t nInsertFailed = 0;
 445             size_t nDeleteSuccess = 0;
 446             size_t nDeleteFailed = 0;
 447             size_t nDelValueSuccess = 0;
 448             size_t nDelValueFailed = 0;
 449             size_t nUpdateFailed = 0;
 450             size_t nUpdateCreated = 0;
 451             size_t nUpdateModified = 0;
 452             size_t nEnsFuncCreated = 0;
 453             size_t nEnsFuncModified = 0;
 454             size_t nTestFunctorRef = 0;
 455
 456             for ( size_t i = 0; i < pool.size(); ++i ) {
 457                 cds_test::thread& thr = pool.get( i );
 458                 switch ( thr.type()) {
 459                 case insert_thread:
 460                     {
 461                         InserterThread& inserter = static_cast<InserterThread&>( thr );
 462                         nInsertSuccess  += inserter.m_nInsertSuccess;
 463                         nInsertFailed   += inserter.m_nInsertFailed;
 464                         nTestFunctorRef += inserter.m_nTestFunctorRef;
 465                     }
 466                     break;
 467                 case update_thread:
 468                     {
 469                         UpdaterThread& updater = static_cast<UpdaterThread&>(thr);
 470                         nUpdateCreated   += updater.m_nUpdateCreated;
 471                         nUpdateModified  += updater.m_nUpdateExisted;
 472                         nUpdateFailed    += updater.m_nUpdateFailed;
 473                         nEnsFuncCreated  += updater.m_nFunctorCreated;
 474                         nEnsFuncModified += updater.m_nFunctorModified;
 475                     }
 476                     break;
 477                 case delete_thread:
 478                     {
 479                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 480                         nDeleteSuccess   += deleter.m_nDeleteSuccess;
 481                         nDeleteFailed    += deleter.m_nDeleteFailed;
 482                         nDelValueSuccess += deleter.m_nValueSuccess;
 483                         nDelValueFailed  += deleter.m_nValueFailed;
 484                     }
 485                     break;
 486                 }
 487             }
 488
 489             propout()
 490                 << std::make_pair( "insert_success", nInsertSuccess )
 491                 << std::make_pair( "delete_success", nDeleteSuccess )
 492                 << std::make_pair( "insert_failed", nInsertFailed )
 493                 << std::make_pair( "delete_failed", nDeleteFailed )
 494                 << std::make_pair( "update_created", nUpdateCreated )
 495                 << std::make_pair( "update_modified", nUpdateModified )
 496                 << std::make_pair( "update_failed", nUpdateFailed )
 497                 << std::make_pair( "final_set_size", testSet.size());
 498
 499
 500             EXPECT_EQ( nDelValueFailed, 0u );
 501             EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
 502
 503             EXPECT_EQ( nUpdateFailed, 0u );
 504             EXPECT_EQ( nUpdateCreated, nEnsFuncCreated );
 505             EXPECT_EQ( nUpdateModified, nEnsFuncModified );
 506
 507             // nTestFunctorRef is call count of insert functor
 508             EXPECT_EQ( nTestFunctorRef, nInsertSuccess );
 509
 510             //testSet.clear();
 511             for ( size_t * p = m_pKeyFirst; p != m_pKeyLast; ++p )
 512                 testSet.erase( *p );
 513
 514             EXPECT_TRUE( testSet.empty());
 515             EXPECT_EQ( testSet.size(), 0u );
 516
 517             additional_check( testSet );
 518             print_stat( propout(), testSet  );
 519
 520             additional_cleanup( testSet );
 521         }
 522
 523         template <class Set>
 524         void run_test()
 525         {
 526             Set s( *this );
 527             run_test( s );
 528         }
 529
 530         template <class Set>
 531         void run_test2()
 532         {
 533             Set s( *this );
 534             run_test( s );
 535
 536             for ( auto it = s.begin(); it != s.end(); ++it )
 537                 std::cout << "key=" << it->key << std::endl;
 538         }
 539     };
 540
 541     class Set_InsDel_func_LF: public Set_InsDel_func
 542         , public ::testing::WithParamInterface<size_t>
 543     {
 544     public:
 545         template <class Set>
 546         void run_test()
 547         {
 548             s_nLoadFactor = GetParam();
 549             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 550             Set_InsDel_func::run_test<Set>();
 551         }
 552
 553         template <class Set>
 554         void run_test2()
 555         {
 556             s_nLoadFactor = GetParam();
 557             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 558             Set_InsDel_func::run_test2<Set>();
 559         }
 560
 561         static std::vector<size_t> get_load_factors();
 562     };
 563
 564 } // namespace set