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