tests/unit/set2/set_insdel_string.h

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