tests/unit/set2/set_insdel_string.cpp

   1 //$$CDS-header$$
   2
   3 #include "set2/set_types.h"
   4 #include "cppunit/thread.h"
   5
   6 #include <vector>
   7
   8 namespace set2 {
   9
  10 #   define TEST_SET(X)          void X() { test<SetTypes<key_type, value_type>::X >(); }
  11 #   define TEST_SET_EXTRACT(X)  void X() { test_extract<SetTypes<key_type, value_type>::X >(); }
  12 #   define TEST_SET_NOLF(X)     void X() { test_nolf<SetTypes<key_type, value_type>::X >(); }
  13 #   define TEST_SET_NOLF_EXTRACT(X) void X() { test_nolf_extract<SetTypes<key_type, value_type>::X >(); }
  14
  15     namespace {
  16         static size_t  c_nMapSize = 1000000    ;  // set size
  17         static size_t  c_nInsertThreadCount = 4;  // count of insertion thread
  18         static size_t  c_nDeleteThreadCount = 4;  // count of deletion thread
  19         static size_t  c_nThreadPassCount = 4  ;  // pass count for each thread
  20         static size_t  c_nMaxLoadFactor = 8    ;  // maximum load factor
  21         static bool    c_bPrintGCState = true;
  22     }
  23
  24     class Set_InsDel_string: public CppUnitMini::TestCase
  25     {
  26         typedef std::string key_type;
  27         typedef size_t      value_type;
  28
  29         const std::vector<std::string> *  m_parrString;
  30
  31         template <class Set>
  32         class Inserter: public CppUnitMini::TestThread
  33         {
  34             Set&     m_Set;
  35             typedef typename Set::value_type    keyval_type;
  36
  37             virtual Inserter *    clone()
  38             {
  39                 return new Inserter( *this );
  40             }
  41         public:
  42             size_t  m_nInsertSuccess;
  43             size_t  m_nInsertFailed;
  44
  45         public:
  46             Inserter( CppUnitMini::ThreadPool& pool, Set& rSet )
  47                 : CppUnitMini::TestThread( pool )
  48                 , m_Set( rSet )
  49             {}
  50             Inserter( Inserter& src )
  51                 : CppUnitMini::TestThread( src )
  52                 , m_Set( src.m_Set )
  53             {}
  54
  55             Set_InsDel_string&  getTest()
  56             {
  57                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
  58             }
  59
  60             virtual void init() { cds::threading::Manager::attachThread()   ; }
  61             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  62
  63             virtual void test()
  64             {
  65                 Set& rSet = m_Set;
  66
  67                 m_nInsertSuccess =
  68                     m_nInsertFailed = 0;
  69
  70                 const std::vector<std::string>& arrString = *getTest().m_parrString;
  71                 size_t nArrSize = arrString.size();
  72
  73                 if ( m_nThreadNo & 1 ) {
  74                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
  75                         for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
  76                             if ( rSet.insert( keyval_type(arrString[nItem % nArrSize], nItem * 8) ) )
  77                                 ++m_nInsertSuccess;
  78                             else
  79                                 ++m_nInsertFailed;
  80                         }
  81                     }
  82                 }
  83                 else {
  84                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
  85                         for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
  86                             if ( rSet.insert( keyval_type( arrString[nItem % nArrSize], nItem * 8) ) )
  87                                 ++m_nInsertSuccess;
  88                             else
  89                                 ++m_nInsertFailed;
  90                         }
  91                     }
  92                 }
  93             }
  94         };
  95
  96         template <class Set>
  97         class Deleter: public CppUnitMini::TestThread
  98         {
  99             Set&     m_Set;
 100
 101             virtual Deleter *    clone()
 102             {
 103                 return new Deleter( *this );
 104             }
 105         public:
 106             size_t  m_nDeleteSuccess;
 107             size_t  m_nDeleteFailed;
 108
 109         public:
 110             Deleter( CppUnitMini::ThreadPool& pool, Set& rSet )
 111                 : CppUnitMini::TestThread( pool )
 112                 , m_Set( rSet )
 113             {}
 114             Deleter( Deleter& src )
 115                 : CppUnitMini::TestThread( src )
 116                 , m_Set( src.m_Set )
 117             {}
 118
 119             Set_InsDel_string&  getTest()
 120             {
 121                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 122             }
 123
 124             virtual void init() { cds::threading::Manager::attachThread()   ; }
 125             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 126
 127             virtual void test()
 128             {
 129                 Set& rSet = m_Set;
 130
 131                 m_nDeleteSuccess =
 132                     m_nDeleteFailed = 0;
 133
 134                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 135                 size_t nArrSize = arrString.size();
 136
 137                 if ( m_nThreadNo & 1 ) {
 138                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 139                         for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
 140                             if ( rSet.erase( arrString[nItem % nArrSize] ) )
 141                                 ++m_nDeleteSuccess;
 142                             else
 143                                 ++m_nDeleteFailed;
 144                         }
 145                     }
 146                 }
 147                 else {
 148                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 149                         for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
 150                             if ( rSet.erase( arrString[nItem % nArrSize] ) )
 151                                 ++m_nDeleteSuccess;
 152                             else
 153                                 ++m_nDeleteFailed;
 154                         }
 155                     }
 156                 }
 157             }
 158         };
 159
 160         template <typename GC, class Set>
 161         class Extractor: public CppUnitMini::TestThread
 162         {
 163             Set&     m_Set;
 164
 165             virtual Extractor *    clone()
 166             {
 167                 return new Extractor( *this );
 168             }
 169         public:
 170             size_t  m_nDeleteSuccess;
 171             size_t  m_nDeleteFailed;
 172
 173         public:
 174             Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
 175                 : CppUnitMini::TestThread( pool )
 176                 , m_Set( rSet )
 177             {}
 178             Extractor( Extractor& src )
 179                 : CppUnitMini::TestThread( src )
 180                 , m_Set( src.m_Set )
 181             {}
 182
 183             Set_InsDel_string&  getTest()
 184             {
 185                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 186             }
 187
 188             virtual void init() { cds::threading::Manager::attachThread()   ; }
 189             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 190
 191             virtual void test()
 192             {
 193                 Set& rSet = m_Set;
 194
 195                 m_nDeleteSuccess =
 196                     m_nDeleteFailed = 0;
 197
 198                 typename Set::guarded_ptr gp;
 199
 200                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 201                 size_t nArrSize = arrString.size();
 202
 203                 if ( m_nThreadNo & 1 ) {
 204                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 205                         for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
 206                             gp = rSet.extract( arrString[nItem % nArrSize]);
 207                             if (  gp )
 208                                 ++m_nDeleteSuccess;
 209                             else
 210                                 ++m_nDeleteFailed;
 211                             gp.release();
 212                         }
 213                     }
 214                 }
 215                 else {
 216                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 217                         for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
 218                             gp = rSet.extract( arrString[nItem % nArrSize]);
 219                             if ( gp )
 220                                 ++m_nDeleteSuccess;
 221                             else
 222                                 ++m_nDeleteFailed;
 223                             gp.release();
 224                         }
 225                     }
 226                 }
 227             }
 228         };
 229
 230         template <typename RCU, class Set>
 231         class Extractor<cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
 232         {
 233             Set&     m_Set;
 234
 235             virtual Extractor *    clone()
 236             {
 237                 return new Extractor( *this );
 238             }
 239         public:
 240             size_t  m_nDeleteSuccess;
 241             size_t  m_nDeleteFailed;
 242
 243         public:
 244             Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
 245                 : CppUnitMini::TestThread( pool )
 246                 , m_Set( rSet )
 247             {}
 248             Extractor( Extractor& src )
 249                 : CppUnitMini::TestThread( src )
 250                 , m_Set( src.m_Set )
 251             {}
 252
 253             Set_InsDel_string&  getTest()
 254             {
 255                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 256             }
 257
 258             virtual void init() { cds::threading::Manager::attachThread()   ; }
 259             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 260
 261             virtual void test()
 262             {
 263                 Set& rSet = m_Set;
 264
 265                 m_nDeleteSuccess =
 266                     m_nDeleteFailed = 0;
 267
 268                 typename Set::exempt_ptr xp;
 269
 270                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 271                 size_t nArrSize = arrString.size();
 272
 273                 if ( m_nThreadNo & 1 ) {
 274                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 275                         for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
 276                             if ( Set::c_bExtractLockExternal ) {
 277                                 {
 278                                     typename Set::rcu_lock l;
 279                                     xp = rSet.extract( arrString[nItem % nArrSize] );
 280                                     if ( xp )
 281                                         ++m_nDeleteSuccess;
 282                                     else
 283                                         ++m_nDeleteFailed;
 284                                 }
 285                             }
 286                             else {
 287                                 xp = rSet.extract( arrString[nItem % nArrSize] );
 288                                 if ( xp )
 289                                     ++m_nDeleteSuccess;
 290                                 else
 291                                     ++m_nDeleteFailed;
 292                             }
 293                             xp.release();
 294                         }
 295                     }
 296                 }
 297                 else {
 298                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 299                         for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
 300                             if ( Set::c_bExtractLockExternal ) {
 301                                 {
 302                                     typename Set::rcu_lock l;
 303                                     xp = rSet.extract( arrString[nItem % nArrSize] );
 304                                     if ( xp )
 305                                         ++m_nDeleteSuccess;
 306                                     else
 307                                         ++m_nDeleteFailed;
 308                                 }
 309                             }
 310                             else {
 311                                 xp = rSet.extract( arrString[nItem % nArrSize] );
 312                                 if ( xp )
 313                                     ++m_nDeleteSuccess;
 314                                 else
 315                                     ++m_nDeleteFailed;
 316                             }
 317                             xp.release();
 318                         }
 319                     }
 320                 }
 321             }
 322         };
 323
 324     protected:
 325
 326         template <class Set>
 327         void do_test( size_t nLoadFactor )
 328         {
 329             CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 330
 331             Set  testSet( c_nMapSize, nLoadFactor );
 332             do_test_with( testSet );
 333         }
 334
 335         template <class Set>
 336         void do_test_extract( size_t nLoadFactor )
 337         {
 338             CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 339
 340             Set  testSet( c_nMapSize, nLoadFactor );
 341             do_test_extract_with( testSet );
 342         }
 343
 344         template <class Set>
 345         void do_test_with( Set& testSet )
 346         {
 347             typedef Inserter<Set>       InserterThread;
 348             typedef Deleter<Set>        DeleterThread;
 349             cds::OS::Timer    timer;
 350
 351             CppUnitMini::ThreadPool pool( *this );
 352             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 353             pool.add( new DeleterThread( pool, testSet ), c_nDeleteThreadCount );
 354             pool.run();
 355             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 356
 357             size_t nInsertSuccess = 0;
 358             size_t nInsertFailed = 0;
 359             size_t nDeleteSuccess = 0;
 360             size_t nDeleteFailed = 0;
 361             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 362                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 363                 if ( pThread ) {
 364                     nInsertSuccess += pThread->m_nInsertSuccess;
 365                     nInsertFailed += pThread->m_nInsertFailed;
 366                 }
 367                 else {
 368                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 369                     nDeleteSuccess += p->m_nDeleteSuccess;
 370                     nDeleteFailed += p->m_nDeleteFailed;
 371                 }
 372             }
 373
 374             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 375                 << " Del succ=" << nDeleteSuccess << "\n"
 376                       << "          : Ins fail=" << nInsertFailed
 377                 << " Del fail=" << nDeleteFailed
 378                 << " Set size=" << testSet.size()
 379                 );
 380
 381
 382             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 383             timer.reset();
 384             for ( size_t i = 0; i < m_parrString->size(); ++i )
 385                 testSet.erase( (*m_parrString)[i] );
 386             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 387             CPPUNIT_ASSERT( testSet.empty() );
 388
 389             additional_check( testSet );
 390             print_stat(  testSet  );
 391             additional_cleanup( testSet );
 392         }
 393
 394         template <class Set>
 395         void do_test_extract_with( Set& testSet )
 396         {
 397             typedef Inserter<Set>       InserterThread;
 398             typedef Deleter<Set>        DeleterThread;
 399             typedef Extractor<typename Set::gc, Set> ExtractThread;
 400
 401             size_t nDelThreadCount = c_nDeleteThreadCount / 2;
 402
 403             CppUnitMini::ThreadPool pool( *this );
 404             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 405             pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
 406             pool.add( new ExtractThread( pool, testSet ), c_nDeleteThreadCount - nDelThreadCount );
 407             pool.run();
 408             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 409
 410             size_t nInsertSuccess = 0;
 411             size_t nInsertFailed = 0;
 412             size_t nDeleteSuccess = 0;
 413             size_t nDeleteFailed = 0;
 414             size_t nExtractSuccess = 0;
 415             size_t nExtractFailed = 0;
 416             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 417                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 418                 if ( pThread ) {
 419                     nInsertSuccess += pThread->m_nInsertSuccess;
 420                     nInsertFailed += pThread->m_nInsertFailed;
 421                 }
 422                 else {
 423                     DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
 424                     if ( p ) {
 425                         nDeleteSuccess += p->m_nDeleteSuccess;
 426                         nDeleteFailed += p->m_nDeleteFailed;
 427                     }
 428                     else {
 429                         ExtractThread * pExtract = dynamic_cast<ExtractThread *>( *it );
 430                         assert( pExtract );
 431                         nExtractSuccess += pExtract->m_nDeleteSuccess;
 432                         nExtractFailed += pExtract->m_nDeleteFailed;
 433                     }
 434                 }
 435             }
 436
 437             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 438                 << " Del succ=" << nDeleteSuccess
 439                 << " Extract succ= " << nExtractSuccess << "\n"
 440                 << "          : Ins fail=" << nInsertFailed
 441                 << " Del fail=" << nDeleteFailed
 442                 << " Extract fail=" << nExtractFailed
 443                 << " Set size=" << testSet.size()
 444                 );
 445
 446
 447             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 448             cds::OS::Timer    timer;
 449             for ( size_t i = 0; i < m_parrString->size(); ++i )
 450                 testSet.erase( (*m_parrString)[i] );
 451             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 452             CPPUNIT_ASSERT( testSet.empty() );
 453
 454             additional_check( testSet );
 455             print_stat(  testSet  );
 456             additional_cleanup( testSet );
 457         }
 458
 459         template <class Set>
 460         void test()
 461         {
 462             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 463
 464             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 465                 << " delete=" << c_nDeleteThreadCount
 466                 << " pass count=" << c_nThreadPassCount
 467                 << " set size=" << c_nMapSize
 468                 );
 469
 470             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 471                 do_test<Set>( nLoadFactor );
 472                 if ( c_bPrintGCState )
 473                     print_gc_state();
 474             }
 475         }
 476
 477         template <class Set>
 478         void test_extract()
 479         {
 480             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 481
 482             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 483                 << " delete=" << c_nDeleteThreadCount
 484                 << " pass count=" << c_nThreadPassCount
 485                 << " set size=" << c_nMapSize
 486                 );
 487
 488             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 489                 do_test_extract<Set>( nLoadFactor );
 490                 if ( c_bPrintGCState )
 491                     print_gc_state();
 492             }
 493         }
 494
 495         template <class Set>
 496         void test_nolf()
 497         {
 498             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 499
 500             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 501                 << " delete=" << c_nDeleteThreadCount
 502                 << " pass count=" << c_nThreadPassCount
 503                 << " set size=" << c_nMapSize
 504                 );
 505
 506             Set s;
 507             do_test_with( s );
 508             if ( c_bPrintGCState )
 509                 print_gc_state();
 510         }
 511
 512         template <class Set>
 513         void test_nolf_extract()
 514         {
 515             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 516
 517             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 518                 << " delete=" << c_nDeleteThreadCount
 519                 << " pass count=" << c_nThreadPassCount
 520                 << " set size=" << c_nMapSize
 521                 );
 522
 523             Set s;
 524             do_test_extract_with( s );
 525             if ( c_bPrintGCState )
 526                 print_gc_state();
 527         }
 528
 529         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 530             c_nInsertThreadCount = cfg.getULong("InsertThreadCount", 4 );
 531             c_nDeleteThreadCount = cfg.getULong("DeleteThreadCount", 4 );
 532             c_nThreadPassCount = cfg.getULong("ThreadPassCount", 4 );
 533             c_nMapSize = cfg.getULong("MapSize", 1000000 );
 534             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 535             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 536         }
 537
 538 #   include "set2/set_defs.h"
 539         CDSUNIT_DECLARE_MichaelSet
 540         CDSUNIT_DECLARE_SplitList
 541         CDSUNIT_DECLARE_StripedSet
 542         CDSUNIT_DECLARE_RefinableSet
 543         CDSUNIT_DECLARE_CuckooSet
 544         CDSUNIT_DECLARE_SkipListSet
 545         CDSUNIT_DECLARE_EllenBinTreeSet
 546         CDSUNIT_DECLARE_StdSet
 547
 548         CPPUNIT_TEST_SUITE_( Set_InsDel_string, "Map_InsDel_string" )
 549             CDSUNIT_TEST_MichaelSet
 550             CDSUNIT_TEST_SplitList
 551             CDSUNIT_TEST_SkipListSet
 552             CDSUNIT_TEST_EllenBinTreeSet
 553             CDSUNIT_TEST_StripedSet
 554             CDSUNIT_TEST_RefinableSet
 555             CDSUNIT_TEST_CuckooSet
 556             CDSUNIT_TEST_StdSet
 557         CPPUNIT_TEST_SUITE_END()
 558
 559     };
 560
 561     CPPUNIT_TEST_SUITE_REGISTRATION( Set_InsDel_string );
 562 } // namespace set2