tests/unit/set2/set_insdel_func.h

   1 //$$CDS-header$$
   2
   3 #include <functional>
   4 #include <vector>
   5 #include <mutex>    //unique_lock
   6
   7 #include "set2/set_type.h"
   8 #include "cppunit/thread.h"
   9 #include <cds/sync/spinlock.h>
  10
  11 namespace set2 {
  12
  13 #define TEST_CASE(TAG, X)  void X();
  14
  15     class Set_InsDel_func: public CppUnitMini::TestCase
  16     {
  17     public:
  18         size_t  c_nSetSize = 1000000;      // set size
  19         size_t  c_nInsertThreadCount = 4;  // count of insertion thread
  20         size_t  c_nDeleteThreadCount = 4;  // count of deletion thread
  21         size_t  c_nUpdateThreadCount = 4;  // count of ensure thread
  22         size_t  c_nThreadPassCount = 4;    // pass count for each thread
  23         size_t  c_nMaxLoadFactor = 8;      // maximum load factor
  24         bool    c_bPrintGCState;
  25
  26         size_t  c_nCuckooInitialSize = 1024;// initial size for CuckooSet
  27         size_t  c_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
  28         size_t  c_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
  29
  30         size_t c_nMultiLevelSet_HeadBits = 10;
  31         size_t c_nMultiLevelSet_ArrayBits = 4;
  32
  33         size_t c_nLoadFactor = 2;
  34
  35     private:
  36         typedef size_t  key_type;
  37         struct value_type {
  38             size_t      nKey;
  39             size_t      nData;
  40             atomics::atomic<size_t> nUpdateCall;
  41             bool volatile   bInitialized;
  42             cds::OS::ThreadId          threadId     ;   // insert thread id
  43
  44             typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
  45             mutable lock_type   m_access;
  46
  47             value_type()
  48                 : nKey(0)
  49                 , nData(0)
  50                 , nUpdateCall(0)
  51                 , bInitialized( false )
  52                 , threadId( cds::OS::get_current_thread_id() )
  53             {}
  54
  55             value_type( value_type const& s )
  56                 : nKey(s.nKey)
  57                 , nData(s.nData)
  58                 , nUpdateCall(s.nUpdateCall.load(atomics::memory_order_relaxed))
  59                 , bInitialized( s.bInitialized )
  60                 , threadId( cds::OS::get_current_thread_id() )
  61             {}
  62
  63             // boost::container::flat_map requires operator =
  64             value_type& operator=( value_type const& v )
  65             {
  66                 nKey = v.nKey;
  67                 nData = v.nData;
  68                 nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
  69                 bInitialized = v.bInitialized;
  70
  71                 return *this;
  72             }
  73
  74         };
  75
  76
  77         size_t *    m_pKeyFirst;
  78         size_t *    m_pKeyLast;
  79         size_t *    m_pKeyArr;
  80
  81         template <class Set>
  82         class Inserter: public CppUnitMini::TestThread
  83         {
  84             Set&     m_Set;
  85             typedef typename Set::value_type keyval_type;
  86
  87             virtual Inserter *    clone()
  88             {
  89                 return new Inserter( *this );
  90             }
  91
  92             struct insert_functor {
  93                 size_t nTestFunctorRef;
  94
  95                 insert_functor()
  96                     : nTestFunctorRef(0)
  97                 {}
  98
  99                 void operator()( keyval_type& val )
 100                 {
 101                     std::unique_lock< typename value_type::lock_type>    ac( val.val.m_access );
 102
 103                     val.val.nKey  = val.key;
 104                     val.val.nData = val.key * 8;
 105
 106                     ++nTestFunctorRef;
 107                     val.val.bInitialized = true;
 108                 }
 109             };
 110
 111         public:
 112             size_t  m_nInsertSuccess;
 113             size_t  m_nInsertFailed;
 114
 115             size_t  m_nTestFunctorRef;
 116
 117         public:
 118             Inserter( CppUnitMini::ThreadPool& pool, Set& rSet )
 119                 : CppUnitMini::TestThread( pool )
 120                 , m_Set( rSet )
 121             {}
 122             Inserter( Inserter& src )
 123                 : CppUnitMini::TestThread( src )
 124                 , m_Set( src.m_Set )
 125             {}
 126
 127             Set_InsDel_func&  getTest()
 128             {
 129                 return reinterpret_cast<Set_InsDel_func&>( m_Pool.m_Test );
 130             }
 131
 132             virtual void init() { cds::threading::Manager::attachThread()   ; }
 133             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 134
 135             virtual void test()
 136             {
 137                 Set& rSet = m_Set;
 138
 139                 m_nInsertSuccess =
 140                     m_nInsertFailed =
 141                     m_nTestFunctorRef = 0;
 142
 143                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 144                 size_t * pKeyLast = getTest().m_pKeyLast;
 145                 size_t const nPassCount = getTest().c_nThreadPassCount;
 146
 147                 // func is passed by reference
 148                 insert_functor  func;
 149
 150                 if ( m_nThreadNo & 1 ) {
 151                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 152                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 153                             if ( rSet.insert( *p, std::ref(func) ) )
 154                                 ++m_nInsertSuccess;
 155                             else
 156                                 ++m_nInsertFailed;
 157                         }
 158                     }
 159                 }
 160                 else {
 161                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 162                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 163                             if ( rSet.insert( *p, std::ref(func) ) )
 164                                 ++m_nInsertSuccess;
 165                             else
 166                                 ++m_nInsertFailed;
 167                         }
 168                     }
 169                 }
 170
 171                 m_nTestFunctorRef = func.nTestFunctorRef;
 172             }
 173         };
 174
 175         template <class Set>
 176         class Updater: public CppUnitMini::TestThread
 177         {
 178             Set&     m_Set;
 179             typedef typename Set::value_type keyval_type;
 180
 181             virtual Updater *    clone()
 182             {
 183                 return new Updater( *this );
 184             }
 185
 186             struct update_functor {
 187                 size_t  nCreated;
 188                 size_t  nModified;
 189
 190                 update_functor()
 191                     : nCreated(0)
 192                     , nModified(0)
 193                 {}
 194
 195                 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
 196                 {
 197                     std::unique_lock<typename value_type::lock_type> ac( val.val.m_access );
 198                     if ( !val.val.bInitialized )
 199                     {
 200                         val.val.nKey = val.key;
 201                         val.val.nData = val.key * 8;
 202                         val.val.bInitialized = true;
 203                     }
 204
 205                     if ( bNew ) {
 206                         ++nCreated;
 207                     }
 208                     else {
 209                         val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
 210                         ++nModified;
 211                     }
 212                 }
 213
 214                 void operator()( keyval_type& cur, keyval_type * old )
 215                 {
 216                     operator()( old == nullptr, cur, 0 );
 217                 }
 218
 219             private:
 220                 update_functor(const update_functor& );
 221             };
 222
 223         public:
 224             size_t  m_nUpdateFailed;
 225             size_t  m_nUpdateCreated;
 226             size_t  m_nUpdateExisted;
 227             size_t  m_nFunctorCreated;
 228             size_t  m_nFunctorModified;
 229
 230         public:
 231             Updater( CppUnitMini::ThreadPool& pool, Set& rSet )
 232                 : CppUnitMini::TestThread( pool )
 233                 , m_Set( rSet )
 234             {}
 235             Updater( Updater& src )
 236                 : CppUnitMini::TestThread( src )
 237                 , m_Set( src.m_Set )
 238             {}
 239
 240             Set_InsDel_func&  getTest()
 241             {
 242                 return reinterpret_cast<Set_InsDel_func&>( m_Pool.m_Test );
 243             }
 244
 245             virtual void init() { cds::threading::Manager::attachThread()   ; }
 246             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 247
 248             virtual void test()
 249             {
 250                 Set& rSet = m_Set;
 251
 252                 m_nUpdateCreated =
 253                     m_nUpdateExisted =
 254                     m_nUpdateFailed = 0;
 255
 256                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 257                 size_t * pKeyLast = getTest().m_pKeyLast;
 258                 size_t const nPassCount = getTest().c_nThreadPassCount;
 259
 260                 update_functor func;
 261
 262                 if ( m_nThreadNo & 1 ) {
 263                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 264                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 265                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 266                             if ( ret.first  ) {
 267                                 if ( ret.second )
 268                                     ++m_nUpdateCreated;
 269                                 else
 270                                     ++m_nUpdateExisted;
 271                             }
 272                             else
 273                                 ++m_nUpdateFailed;
 274                         }
 275                     }
 276                 }
 277                 else {
 278                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 279                         for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
 280                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 281                             if ( ret.first  ) {
 282                                 if ( ret.second )
 283                                     ++m_nUpdateCreated;
 284                                 else
 285                                     ++m_nUpdateExisted;
 286                             }
 287                             else
 288                                 ++m_nUpdateFailed;
 289                         }
 290                     }
 291                 }
 292
 293                 m_nFunctorCreated = func.nCreated;
 294                 m_nFunctorModified = func.nModified;
 295             }
 296         };
 297
 298         template <class Set>
 299         class Deleter: public CppUnitMini::TestThread
 300         {
 301             Set&     m_Set;
 302             typedef typename Set::value_type keyval_type;
 303
 304             virtual Deleter *    clone()
 305             {
 306                 return new Deleter( *this );
 307             }
 308
 309             struct value_container
 310             {
 311                 size_t      nKeyExpected;
 312
 313                 size_t      nSuccessItem;
 314                 size_t      nFailedItem;
 315
 316                 value_container()
 317                     : nSuccessItem(0)
 318                     , nFailedItem(0)
 319                 {}
 320             };
 321
 322             struct erase_functor {
 323                 value_container     m_cnt;
 324
 325                 void operator ()( keyval_type const& itm )
 326                 {
 327                     keyval_type& item = const_cast<keyval_type&>(itm);
 328                     while ( true ) {
 329                         bool bBkoff = false;
 330                         {
 331                             std::unique_lock< typename value_type::lock_type> ac( item.val.m_access );
 332                             if ( item.val.bInitialized ) {
 333                                 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
 334                                     ++m_cnt.nSuccessItem;
 335                                 else
 336                                     ++m_cnt.nFailedItem;
 337                                 item.val.nData++;
 338                                 item.val.nKey = 0;
 339                                 break;
 340                             }
 341                             else
 342                                 bBkoff = true;
 343                         }
 344                         if ( bBkoff )
 345                             cds::backoff::yield()();
 346                     }
 347                 }
 348             };
 349
 350         public:
 351             size_t  m_nDeleteSuccess;
 352             size_t  m_nDeleteFailed;
 353
 354             size_t  m_nValueSuccess;
 355             size_t  m_nValueFailed;
 356
 357         public:
 358             Deleter( CppUnitMini::ThreadPool& pool, Set& rSet )
 359                 : CppUnitMini::TestThread( pool )
 360                 , m_Set( rSet )
 361             {}
 362             Deleter( Deleter& src )
 363                 : CppUnitMini::TestThread( src )
 364                 , m_Set( src.m_Set )
 365             {}
 366
 367             Set_InsDel_func&  getTest()
 368             {
 369                 return reinterpret_cast<Set_InsDel_func&>( m_Pool.m_Test );
 370             }
 371
 372             virtual void init() { cds::threading::Manager::attachThread()   ; }
 373             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 374
 375             virtual void test()
 376             {
 377                 Set& rSet = m_Set;
 378
 379                 m_nDeleteSuccess =
 380                     m_nDeleteFailed = 0;
 381
 382                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 383                 size_t * pKeyLast = getTest().m_pKeyLast;
 384                 size_t const nPassCount = getTest().c_nThreadPassCount;
 385
 386                 erase_functor   func;
 387
 388                 if ( m_nThreadNo & 1 ) {
 389                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 390                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 391                             func.m_cnt.nKeyExpected = *p;
 392                             if ( rSet.erase( *p, std::ref(func) ))
 393                                 ++m_nDeleteSuccess;
 394                             else
 395                                 ++m_nDeleteFailed;
 396                         }
 397                     }
 398                 }
 399                 else {
 400                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 401                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 402                             func.m_cnt.nKeyExpected = *p;
 403                             if ( rSet.erase( *p, std::ref(func) ))
 404                                 ++m_nDeleteSuccess;
 405                             else
 406                                 ++m_nDeleteFailed;
 407                         }
 408                     }
 409                 }
 410
 411                 m_nValueSuccess = func.m_cnt.nSuccessItem;
 412                 m_nValueFailed = func.m_cnt.nFailedItem;
 413             }
 414         };
 415
 416     protected:
 417
 418         template <class Set>
 419         void do_test( Set& testSet )
 420         {
 421             typedef Inserter<Set>       InserterThread;
 422             typedef Deleter<Set>        DeleterThread;
 423             typedef Updater<Set>        UpdaterThread;
 424
 425             m_pKeyArr = new size_t[ c_nSetSize ];
 426             m_pKeyFirst = m_pKeyArr;
 427             m_pKeyLast = m_pKeyFirst + c_nSetSize;
 428             for ( size_t i = 0; i < c_nSetSize; ++i )
 429                 m_pKeyArr[i] = i;
 430             shuffle( m_pKeyFirst, m_pKeyLast );
 431
 432             cds::OS::Timer    timer;
 433
 434             CppUnitMini::ThreadPool pool( *this );
 435             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 436             pool.add( new DeleterThread( pool, testSet ), c_nDeleteThreadCount );
 437             pool.add( new UpdaterThread( pool, testSet ), c_nUpdateThreadCount );
 438             pool.run();
 439             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 440
 441             delete [] m_pKeyArr;
 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 ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 457                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 458                 if ( pThread ) {
 459                     nInsertSuccess += pThread->m_nInsertSuccess;
 460                     nInsertFailed += pThread->m_nInsertFailed;
 461                     nTestFunctorRef += pThread->m_nTestFunctorRef;
 462                 }
 463                 else {
 464                     DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
 465                     if ( p ) {
 466                         nDeleteSuccess += p->m_nDeleteSuccess;
 467                         nDeleteFailed += p->m_nDeleteFailed;
 468                         nDelValueSuccess += p->m_nValueSuccess;
 469                         nDelValueFailed += p->m_nValueFailed;
 470                     }
 471                     else {
 472                         UpdaterThread * pEns = static_cast<UpdaterThread *>( *it );
 473                         nUpdateCreated += pEns->m_nUpdateCreated;
 474                         nUpdateModified += pEns->m_nUpdateExisted;
 475                         nUpdateFailed += pEns->m_nUpdateFailed;
 476                         nEnsFuncCreated += pEns->m_nFunctorCreated;
 477                         nEnsFuncModified += pEns->m_nFunctorModified;
 478                     }
 479                 }
 480             }
 481
 482             CPPUNIT_MSG(
 483                    "    Totals: Ins succ=" << nInsertSuccess
 484                 << " Del succ=" << nDeleteSuccess << "\n"
 485                 << "          : Ins fail=" << nInsertFailed
 486                 << " Del fail=" << nDeleteFailed << "\n"
 487                 << "          : Update succ=" << (nUpdateCreated + nUpdateModified) << " fail=" << nUpdateFailed
 488                 << " create=" << nUpdateCreated << " modify=" << nUpdateModified << "\n"
 489                 << "          Set size=" << testSet.size()
 490                 );
 491
 492             CPPUNIT_CHECK_EX( nDelValueFailed == 0, "Functor del failed=" << nDelValueFailed );
 493             CPPUNIT_CHECK_EX( nDelValueSuccess == nDeleteSuccess,  "Delete success=" << nDeleteSuccess << " functor=" << nDelValueSuccess );
 494
 495             CPPUNIT_CHECK( nUpdateFailed == 0 );
 496
 497             CPPUNIT_CHECK_EX( nUpdateCreated == nEnsFuncCreated, "Update created=" << nUpdateCreated << " functor=" << nEnsFuncCreated );
 498             CPPUNIT_CHECK_EX( nUpdateModified == nEnsFuncModified, "Update modified=" << nUpdateModified << " functor=" << nEnsFuncModified );
 499
 500             // nTestFunctorRef is call count of insert functor
 501             CPPUNIT_CHECK_EX( nTestFunctorRef == nInsertSuccess, "nInsertSuccess=" << nInsertSuccess << " functor nTestFunctorRef=" << nTestFunctorRef );
 502
 503             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 504             timer.reset();
 505             testSet.clear();
 506             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 507             CPPUNIT_CHECK( testSet.empty() );
 508
 509             additional_check( testSet );
 510             print_stat(  testSet  );
 511
 512             additional_cleanup( testSet );
 513         }
 514
 515         template <class Set>
 516         void run_test()
 517         {
 518             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 519                 << " delete=" << c_nDeleteThreadCount
 520                 << " ensure=" << c_nUpdateThreadCount
 521                 << " pass count=" << c_nThreadPassCount
 522                 << " set size=" << c_nSetSize
 523                 );
 524
 525             if ( Set::c_bLoadFactorDepended ) {
 526                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 527                     CPPUNIT_MSG("  LoadFactor = " << c_nLoadFactor );
 528                     Set s( *this );
 529                     do_test( s );
 530                     if ( c_bPrintGCState )
 531                         print_gc_state();
 532                 }
 533             }
 534             else {
 535                 Set s( *this );
 536                 do_test( s );
 537                 if ( c_bPrintGCState )
 538                     print_gc_state();
 539             }
 540         }
 541
 542         void setUpParams( const CppUnitMini::TestCfg& cfg );
 543
 544 #   include "set2/set_defs.h"
 545     CDSUNIT_DECLARE_MichaelSet
 546     CDSUNIT_DECLARE_SkipListSet
 547     CDSUNIT_DECLARE_SplitList
 548     CDSUNIT_DECLARE_StripedSet
 549     CDSUNIT_DECLARE_RefinableSet
 550     CDSUNIT_DECLARE_CuckooSet
 551     CDSUNIT_DECLARE_EllenBinTreeSet
 552     CDSUNIT_DECLARE_MultiLevelHashSet
 553
 554     CPPUNIT_TEST_SUITE_(Set_InsDel_func, "Map_InsDel_func")
 555         CDSUNIT_TEST_MichaelSet
 556         CDSUNIT_TEST_SplitList
 557         CDSUNIT_TEST_SkipListSet
 558         CDSUNIT_TEST_MultiLevelHashSet
 559         CDSUNIT_TEST_EllenBinTreeSet
 560         CDSUNIT_TEST_StripedSet
 561         CDSUNIT_TEST_RefinableSet
 562         CDSUNIT_TEST_CuckooSet
 563     CPPUNIT_TEST_SUITE_END();
 564
 565     };
 566 } // namespace set2