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                             if ( rSet.extract( gp, arrString[nItem % nArrSize] ) )
 207                                 ++m_nDeleteSuccess;
 208                             else
 209                                 ++m_nDeleteFailed;
 210                         }
 211                     }
 212                 }
 213                 else {
 214                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 215                         for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
 216                             if ( rSet.extract( gp, arrString[nItem % nArrSize] ) )
 217                                 ++m_nDeleteSuccess;
 218                             else
 219                                 ++m_nDeleteFailed;
 220                         }
 221                     }
 222                 }
 223             }
 224         };
 225
 226         template <typename RCU, class Set>
 227         class Extractor<cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
 228         {
 229             Set&     m_Set;
 230
 231             virtual Extractor *    clone()
 232             {
 233                 return new Extractor( *this );
 234             }
 235         public:
 236             size_t  m_nDeleteSuccess;
 237             size_t  m_nDeleteFailed;
 238
 239         public:
 240             Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
 241                 : CppUnitMini::TestThread( pool )
 242                 , m_Set( rSet )
 243             {}
 244             Extractor( Extractor& src )
 245                 : CppUnitMini::TestThread( src )
 246                 , m_Set( src.m_Set )
 247             {}
 248
 249             Set_InsDel_string&  getTest()
 250             {
 251                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 252             }
 253
 254             virtual void init() { cds::threading::Manager::attachThread()   ; }
 255             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 256
 257             virtual void test()
 258             {
 259                 Set& rSet = m_Set;
 260
 261                 m_nDeleteSuccess =
 262                     m_nDeleteFailed = 0;
 263
 264                 typename Set::exempt_ptr xp;
 265
 266                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 267                 size_t nArrSize = arrString.size();
 268
 269                 if ( m_nThreadNo & 1 ) {
 270                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 271                         for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
 272                             if ( Set::c_bExtractLockExternal ) {
 273                                 {
 274                                     typename Set::rcu_lock l;
 275                                     xp = rSet.extract( arrString[nItem % nArrSize] );
 276                                     if ( xp )
 277                                         ++m_nDeleteSuccess;
 278                                     else
 279                                         ++m_nDeleteFailed;
 280                                 }
 281                             }
 282                             else {
 283                                 xp = rSet.extract( arrString[nItem % nArrSize] );
 284                                 if ( xp )
 285                                     ++m_nDeleteSuccess;
 286                                 else
 287                                     ++m_nDeleteFailed;
 288                             }
 289                             xp.release();
 290                         }
 291                     }
 292                 }
 293                 else {
 294                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 295                         for ( size_t nItem = c_nMapSize; nItem > 0; --nItem ) {
 296                             if ( Set::c_bExtractLockExternal ) {
 297                                 {
 298                                     typename Set::rcu_lock l;
 299                                     xp = rSet.extract( arrString[nItem % nArrSize] );
 300                                     if ( xp )
 301                                         ++m_nDeleteSuccess;
 302                                     else
 303                                         ++m_nDeleteFailed;
 304                                 }
 305                             }
 306                             else {
 307                                 xp = rSet.extract( arrString[nItem % nArrSize] );
 308                                 if ( xp )
 309                                     ++m_nDeleteSuccess;
 310                                 else
 311                                     ++m_nDeleteFailed;
 312                             }
 313                             xp.release();
 314                         }
 315                     }
 316                 }
 317             }
 318         };
 319
 320     protected:
 321
 322         template <class Set>
 323         void do_test( size_t nLoadFactor )
 324         {
 325             CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 326
 327             Set  testSet( c_nMapSize, nLoadFactor );
 328             do_test_with( testSet );
 329         }
 330
 331         template <class Set>
 332         void do_test_extract( size_t nLoadFactor )
 333         {
 334             CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 335
 336             Set  testSet( c_nMapSize, nLoadFactor );
 337             do_test_extract_with( testSet );
 338         }
 339
 340         template <class Set>
 341         void do_test_with( Set& testSet )
 342         {
 343             typedef Inserter<Set>       InserterThread;
 344             typedef Deleter<Set>        DeleterThread;
 345             cds::OS::Timer    timer;
 346
 347             CppUnitMini::ThreadPool pool( *this );
 348             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 349             pool.add( new DeleterThread( pool, testSet ), c_nDeleteThreadCount );
 350             pool.run();
 351             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 352
 353             size_t nInsertSuccess = 0;
 354             size_t nInsertFailed = 0;
 355             size_t nDeleteSuccess = 0;
 356             size_t nDeleteFailed = 0;
 357             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 358                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 359                 if ( pThread ) {
 360                     nInsertSuccess += pThread->m_nInsertSuccess;
 361                     nInsertFailed += pThread->m_nInsertFailed;
 362                 }
 363                 else {
 364                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 365                     nDeleteSuccess += p->m_nDeleteSuccess;
 366                     nDeleteFailed += p->m_nDeleteFailed;
 367                 }
 368             }
 369
 370             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 371                 << " Del succ=" << nDeleteSuccess << "\n"
 372                       << "          : Ins fail=" << nInsertFailed
 373                 << " Del fail=" << nDeleteFailed
 374                 << " Set size=" << testSet.size()
 375                 );
 376
 377
 378             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 379             timer.reset();
 380             for ( size_t i = 0; i < m_parrString->size(); ++i )
 381                 testSet.erase( (*m_parrString)[i] );
 382             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 383             CPPUNIT_ASSERT( testSet.empty() );
 384
 385             additional_check( testSet );
 386             print_stat(  testSet  );
 387             additional_cleanup( testSet );
 388         }
 389
 390         template <class Set>
 391         void do_test_extract_with( Set& testSet )
 392         {
 393             typedef Inserter<Set>       InserterThread;
 394             typedef Deleter<Set>        DeleterThread;
 395             typedef Extractor<typename Set::gc, Set> ExtractThread;
 396
 397             size_t nDelThreadCount = c_nDeleteThreadCount / 2;
 398
 399             CppUnitMini::ThreadPool pool( *this );
 400             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 401             pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
 402             pool.add( new ExtractThread( pool, testSet ), c_nDeleteThreadCount - nDelThreadCount );
 403             pool.run();
 404             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 405
 406             size_t nInsertSuccess = 0;
 407             size_t nInsertFailed = 0;
 408             size_t nDeleteSuccess = 0;
 409             size_t nDeleteFailed = 0;
 410             size_t nExtractSuccess = 0;
 411             size_t nExtractFailed = 0;
 412             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 413                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 414                 if ( pThread ) {
 415                     nInsertSuccess += pThread->m_nInsertSuccess;
 416                     nInsertFailed += pThread->m_nInsertFailed;
 417                 }
 418                 else {
 419                     DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
 420                     if ( p ) {
 421                         nDeleteSuccess += p->m_nDeleteSuccess;
 422                         nDeleteFailed += p->m_nDeleteFailed;
 423                     }
 424                     else {
 425                         ExtractThread * pExtract = dynamic_cast<ExtractThread *>( *it );
 426                         assert( pExtract );
 427                         nExtractSuccess += pExtract->m_nDeleteSuccess;
 428                         nExtractFailed += pExtract->m_nDeleteFailed;
 429                     }
 430                 }
 431             }
 432
 433             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 434                 << " Del succ=" << nDeleteSuccess
 435                 << " Extract succ= " << nExtractSuccess << "\n"
 436                 << "          : Ins fail=" << nInsertFailed
 437                 << " Del fail=" << nDeleteFailed
 438                 << " Extract fail=" << nExtractFailed
 439                 << " Set size=" << testSet.size()
 440                 );
 441
 442
 443             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 444             cds::OS::Timer    timer;
 445             for ( size_t i = 0; i < m_parrString->size(); ++i )
 446                 testSet.erase( (*m_parrString)[i] );
 447             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 448             CPPUNIT_ASSERT( testSet.empty() );
 449
 450             additional_check( testSet );
 451             print_stat(  testSet  );
 452             additional_cleanup( testSet );
 453         }
 454
 455         template <class Set>
 456         void test()
 457         {
 458             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 459
 460             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 461                 << " delete=" << c_nDeleteThreadCount
 462                 << " pass count=" << c_nThreadPassCount
 463                 << " set size=" << c_nMapSize
 464                 );
 465
 466             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 467                 do_test<Set>( nLoadFactor );
 468                 if ( c_bPrintGCState )
 469                     print_gc_state();
 470             }
 471         }
 472
 473         template <class Set>
 474         void test_extract()
 475         {
 476             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 477
 478             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 479                 << " delete=" << c_nDeleteThreadCount
 480                 << " pass count=" << c_nThreadPassCount
 481                 << " set size=" << c_nMapSize
 482                 );
 483
 484             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 485                 do_test_extract<Set>( nLoadFactor );
 486                 if ( c_bPrintGCState )
 487                     print_gc_state();
 488             }
 489         }
 490
 491         template <class Set>
 492         void test_nolf()
 493         {
 494             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 495
 496             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 497                 << " delete=" << c_nDeleteThreadCount
 498                 << " pass count=" << c_nThreadPassCount
 499                 << " set size=" << c_nMapSize
 500                 );
 501
 502             Set s;
 503             do_test_with( s );
 504             if ( c_bPrintGCState )
 505                 print_gc_state();
 506         }
 507
 508         template <class Set>
 509         void test_nolf_extract()
 510         {
 511             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 512
 513             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 514                 << " delete=" << c_nDeleteThreadCount
 515                 << " pass count=" << c_nThreadPassCount
 516                 << " set size=" << c_nMapSize
 517                 );
 518
 519             Set s;
 520             do_test_extract_with( s );
 521             if ( c_bPrintGCState )
 522                 print_gc_state();
 523         }
 524
 525         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 526             c_nInsertThreadCount = cfg.getULong("InsertThreadCount", 4 );
 527             c_nDeleteThreadCount = cfg.getULong("DeleteThreadCount", 4 );
 528             c_nThreadPassCount = cfg.getULong("ThreadPassCount", 4 );
 529             c_nMapSize = cfg.getULong("MapSize", 1000000 );
 530             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 531             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 532         }
 533
 534 #   include "set2/set_defs.h"
 535         CDSUNIT_DECLARE_MichaelSet
 536         CDSUNIT_DECLARE_SplitList
 537         CDSUNIT_DECLARE_StripedSet
 538         CDSUNIT_DECLARE_RefinableSet
 539         CDSUNIT_DECLARE_CuckooSet
 540         CDSUNIT_DECLARE_SkipListSet
 541         CDSUNIT_DECLARE_EllenBinTreeSet
 542         CDSUNIT_DECLARE_StdSet
 543
 544         CPPUNIT_TEST_SUITE_( Set_InsDel_string, "Map_InsDel_string" )
 545             CDSUNIT_TEST_MichaelSet
 546             CDSUNIT_TEST_SplitList
 547             CDSUNIT_TEST_SkipListSet
 548             CDSUNIT_TEST_EllenBinTreeSet
 549             CDSUNIT_TEST_StripedSet
 550             CDSUNIT_TEST_RefinableSet
 551             CDSUNIT_TEST_CuckooSet
 552             CDSUNIT_TEST_StdSet
 553         CPPUNIT_TEST_SUITE_END()
 554
 555     };
 556
 557     CPPUNIT_TEST_SUITE_REGISTRATION( Set_InsDel_string );
 558 } // namespace set2