tests/unit/set2/set_insdel_string.h

   1 //$$CDS-header$$
   2
   3 #include "set2/set_type.h"
   4 #include "cppunit/thread.h"
   5
   6 #include <vector>
   7
   8 namespace set2 {
   9
  10 #define TEST_CASE(TAG, X)  void X();
  11
  12     class Set_InsDel_string: public CppUnitMini::TestCase
  13     {
  14     public:
  15         size_t c_nSetSize = 1000000;            // set size
  16         size_t c_nInsertThreadCount = 4;  // count of insertion thread
  17         size_t c_nDeleteThreadCount = 4;  // count of deletion thread
  18         size_t c_nThreadPassCount = 4;    // pass count for each thread
  19         size_t c_nMaxLoadFactor = 8;      // maximum load factor
  20         bool   c_bPrintGCState = true;
  21
  22         size_t  c_nCuckooInitialSize = 1024;// initial size for CuckooSet
  23         size_t  c_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
  24         size_t  c_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
  25
  26         size_t c_nMultiLevelSet_HeadBits = 10;
  27         size_t c_nMultiLevelSet_ArrayBits = 4;
  28
  29         size_t c_nLoadFactor = 2;
  30
  31     private:
  32         typedef CppUnitMini::TestCase Base;
  33         typedef std::string key_type;
  34         typedef size_t      value_type;
  35
  36         const std::vector<std::string> *  m_parrString;
  37
  38         template <class Set>
  39         class Inserter: public CppUnitMini::TestThread
  40         {
  41             Set&     m_Set;
  42             typedef typename Set::value_type    keyval_type;
  43
  44             virtual Inserter *    clone()
  45             {
  46                 return new Inserter( *this );
  47             }
  48         public:
  49             size_t  m_nInsertSuccess;
  50             size_t  m_nInsertFailed;
  51
  52         public:
  53             Inserter( CppUnitMini::ThreadPool& pool, Set& rSet )
  54                 : CppUnitMini::TestThread( pool )
  55                 , m_Set( rSet )
  56             {}
  57             Inserter( Inserter& src )
  58                 : CppUnitMini::TestThread( src )
  59                 , m_Set( src.m_Set )
  60             {}
  61
  62             Set_InsDel_string&  getTest()
  63             {
  64                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
  65             }
  66
  67             virtual void init() { cds::threading::Manager::attachThread()   ; }
  68             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  69
  70             virtual void test()
  71             {
  72                 Set& rSet = m_Set;
  73
  74                 m_nInsertSuccess =
  75                     m_nInsertFailed = 0;
  76
  77                 const std::vector<std::string>& arrString = *getTest().m_parrString;
  78                 size_t nArrSize = arrString.size();
  79                 size_t const nSetSize = getTest().c_nSetSize;
  80                 size_t const nPassCount = getTest().c_nThreadPassCount;
  81
  82                 if ( m_nThreadNo & 1 ) {
  83                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
  84                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
  85                             if ( rSet.insert( keyval_type(arrString[nItem % nArrSize], nItem * 8) ) )
  86                                 ++m_nInsertSuccess;
  87                             else
  88                                 ++m_nInsertFailed;
  89                         }
  90                     }
  91                 }
  92                 else {
  93                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
  94                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
  95                             if ( rSet.insert( keyval_type( arrString[nItem % nArrSize], nItem * 8) ) )
  96                                 ++m_nInsertSuccess;
  97                             else
  98                                 ++m_nInsertFailed;
  99                         }
 100                     }
 101                 }
 102             }
 103         };
 104
 105         template <class Set>
 106         class Deleter: public CppUnitMini::TestThread
 107         {
 108             Set&     m_Set;
 109
 110             virtual Deleter *    clone()
 111             {
 112                 return new Deleter( *this );
 113             }
 114         public:
 115             size_t  m_nDeleteSuccess;
 116             size_t  m_nDeleteFailed;
 117
 118         public:
 119             Deleter( CppUnitMini::ThreadPool& pool, Set& rSet )
 120                 : CppUnitMini::TestThread( pool )
 121                 , m_Set( rSet )
 122             {}
 123             Deleter( Deleter& src )
 124                 : CppUnitMini::TestThread( src )
 125                 , m_Set( src.m_Set )
 126             {}
 127
 128             Set_InsDel_string&  getTest()
 129             {
 130                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 131             }
 132
 133             virtual void init() { cds::threading::Manager::attachThread()   ; }
 134             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 135
 136             virtual void test()
 137             {
 138                 Set& rSet = m_Set;
 139
 140                 m_nDeleteSuccess =
 141                     m_nDeleteFailed = 0;
 142
 143                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 144                 size_t nArrSize = arrString.size();
 145                 size_t const nSetSize = getTest().c_nSetSize;
 146                 size_t const nPassCount = getTest().c_nThreadPassCount;
 147
 148                 if ( m_nThreadNo & 1 ) {
 149                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 150                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 151                             if ( rSet.erase( arrString[nItem % nArrSize] ) )
 152                                 ++m_nDeleteSuccess;
 153                             else
 154                                 ++m_nDeleteFailed;
 155                         }
 156                     }
 157                 }
 158                 else {
 159                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 160                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 161                             if ( rSet.erase( arrString[nItem % nArrSize] ) )
 162                                 ++m_nDeleteSuccess;
 163                             else
 164                                 ++m_nDeleteFailed;
 165                         }
 166                     }
 167                 }
 168             }
 169         };
 170
 171         template <typename GC, class Set>
 172         class Extractor: public CppUnitMini::TestThread
 173         {
 174             Set&     m_Set;
 175
 176             virtual Extractor *    clone()
 177             {
 178                 return new Extractor( *this );
 179             }
 180         public:
 181             size_t  m_nDeleteSuccess;
 182             size_t  m_nDeleteFailed;
 183
 184         public:
 185             Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
 186                 : CppUnitMini::TestThread( pool )
 187                 , m_Set( rSet )
 188             {}
 189             Extractor( Extractor& src )
 190                 : CppUnitMini::TestThread( src )
 191                 , m_Set( src.m_Set )
 192             {}
 193
 194             Set_InsDel_string&  getTest()
 195             {
 196                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 197             }
 198
 199             virtual void init() { cds::threading::Manager::attachThread()   ; }
 200             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 201
 202             virtual void test()
 203             {
 204                 Set& rSet = m_Set;
 205
 206                 m_nDeleteSuccess =
 207                     m_nDeleteFailed = 0;
 208
 209                 typename Set::guarded_ptr gp;
 210
 211                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 212                 size_t nArrSize = arrString.size();
 213                 size_t const nSetSize = getTest().c_nSetSize;
 214                 size_t const nPassCount = getTest().c_nThreadPassCount;
 215
 216                 if ( m_nThreadNo & 1 ) {
 217                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 218                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 219                             gp = rSet.extract( arrString[nItem % nArrSize]);
 220                             if (  gp )
 221                                 ++m_nDeleteSuccess;
 222                             else
 223                                 ++m_nDeleteFailed;
 224                             gp.release();
 225                         }
 226                     }
 227                 }
 228                 else {
 229                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 230                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 231                             gp = rSet.extract( arrString[nItem % nArrSize]);
 232                             if ( gp )
 233                                 ++m_nDeleteSuccess;
 234                             else
 235                                 ++m_nDeleteFailed;
 236                             gp.release();
 237                         }
 238                     }
 239                 }
 240             }
 241         };
 242
 243         template <typename RCU, class Set>
 244         class Extractor<cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
 245         {
 246             Set&     m_Set;
 247
 248             virtual Extractor *    clone()
 249             {
 250                 return new Extractor( *this );
 251             }
 252         public:
 253             size_t  m_nDeleteSuccess;
 254             size_t  m_nDeleteFailed;
 255
 256         public:
 257             Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
 258                 : CppUnitMini::TestThread( pool )
 259                 , m_Set( rSet )
 260             {}
 261             Extractor( Extractor& src )
 262                 : CppUnitMini::TestThread( src )
 263                 , m_Set( src.m_Set )
 264             {}
 265
 266             Set_InsDel_string&  getTest()
 267             {
 268                 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
 269             }
 270
 271             virtual void init() { cds::threading::Manager::attachThread()   ; }
 272             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 273
 274             virtual void test()
 275             {
 276                 Set& rSet = m_Set;
 277
 278                 m_nDeleteSuccess =
 279                     m_nDeleteFailed = 0;
 280
 281                 typename Set::exempt_ptr xp;
 282
 283                 const std::vector<std::string>& arrString = *getTest().m_parrString;
 284                 size_t nArrSize = arrString.size();
 285                 size_t const nSetSize = getTest().c_nSetSize;
 286                 size_t const nPassCount = getTest().c_nThreadPassCount;
 287
 288                 if ( m_nThreadNo & 1 ) {
 289                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 290                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 291                             if ( Set::c_bExtractLockExternal ) {
 292                                 {
 293                                     typename Set::rcu_lock l;
 294                                     xp = rSet.extract( arrString[nItem % nArrSize] );
 295                                     if ( xp )
 296                                         ++m_nDeleteSuccess;
 297                                     else
 298                                         ++m_nDeleteFailed;
 299                                 }
 300                             }
 301                             else {
 302                                 xp = rSet.extract( arrString[nItem % nArrSize] );
 303                                 if ( xp )
 304                                     ++m_nDeleteSuccess;
 305                                 else
 306                                     ++m_nDeleteFailed;
 307                             }
 308                             xp.release();
 309                         }
 310                     }
 311                 }
 312                 else {
 313                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 314                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 315                             if ( Set::c_bExtractLockExternal ) {
 316                                 {
 317                                     typename Set::rcu_lock l;
 318                                     xp = rSet.extract( arrString[nItem % nArrSize] );
 319                                     if ( xp )
 320                                         ++m_nDeleteSuccess;
 321                                     else
 322                                         ++m_nDeleteFailed;
 323                                 }
 324                             }
 325                             else {
 326                                 xp = rSet.extract( arrString[nItem % nArrSize] );
 327                                 if ( xp )
 328                                     ++m_nDeleteSuccess;
 329                                 else
 330                                     ++m_nDeleteFailed;
 331                             }
 332                             xp.release();
 333                         }
 334                     }
 335                 }
 336             }
 337         };
 338
 339     protected:
 340         template <class Set>
 341         void do_test( 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( 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 run_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_nSetSize
 464                 );
 465
 466             if ( Set::c_bLoadFactorDepended ) {
 467                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 468                     CPPUNIT_MSG("  LoadFactor = " << c_nLoadFactor );
 469                     Set s( *this );
 470                     do_test( s );
 471                     if ( c_bPrintGCState )
 472                         print_gc_state();
 473                 }
 474             }
 475             else {
 476                 Set s( *this );
 477                 do_test( s );
 478                 if ( c_bPrintGCState )
 479                     print_gc_state();
 480             }
 481         }
 482
 483         template <class Set>
 484         void run_test_extract()
 485         {
 486             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 487
 488             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 489                 << " delete=" << c_nDeleteThreadCount
 490                 << " pass count=" << c_nThreadPassCount
 491                 << " set size=" << c_nSetSize
 492                 );
 493
 494             if ( Set::c_bLoadFactorDepended ) {
 495                 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 496                     CPPUNIT_MSG("  LoadFactor = " << c_nLoadFactor );
 497                     Set s( *this );
 498                     do_test_extract( s );
 499                     if ( c_bPrintGCState )
 500                         print_gc_state();
 501                 }
 502             }
 503             else {
 504                 Set s( *this );
 505                 do_test_extract( s );
 506                 if ( c_bPrintGCState )
 507                     print_gc_state();
 508             }
 509         }
 510
 511         void setUpParams( const CppUnitMini::TestCfg& cfg );
 512
 513 #   include "set2/set_defs.h"
 514         CDSUNIT_DECLARE_MichaelSet
 515         CDSUNIT_DECLARE_SplitList
 516         CDSUNIT_DECLARE_StripedSet
 517         CDSUNIT_DECLARE_RefinableSet
 518         CDSUNIT_DECLARE_CuckooSet
 519         CDSUNIT_DECLARE_SkipListSet
 520         CDSUNIT_DECLARE_EllenBinTreeSet
 521         CDSUNIT_DECLARE_MultiLevelHashSet
 522         CDSUNIT_DECLARE_StdSet
 523
 524         CPPUNIT_TEST_SUITE_(Set_InsDel_string, "Map_InsDel_func")
 525             CDSUNIT_TEST_MichaelSet
 526             CDSUNIT_TEST_SplitList
 527             CDSUNIT_TEST_SkipListSet
 528             CDSUNIT_TEST_MultiLevelHashSet
 529             CDSUNIT_TEST_EllenBinTreeSet
 530             CDSUNIT_TEST_StripedSet
 531             CDSUNIT_TEST_RefinableSet
 532             CDSUNIT_TEST_CuckooSet
 533             CDSUNIT_TEST_StdSet
 534         CPPUNIT_TEST_SUITE_END();
 535     };
 536 } // namespace set2