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