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