tests/unit/set2/set_insdel_func.h

   1 //$$CDS-header$$
   2
   3 #include "set2/set_types.h"
   4 #include "cppunit/thread.h"
   5
   6 #include <cds/lock/spinlock.h>
   7 #include <vector>
   8 #include <boost/ref.hpp>
   9
  10 namespace set2 {
  11
  12 #   define TEST_SET(X)          void X() { test<SetTypes<key_type, value_type>::X >()    ; }
  13 #   define TEST_SET_EXTRACT(X)  TEST_SET(X)
  14 #   define TEST_SET_NOLF(X)     void X() { test_nolf<SetTypes<key_type, value_type>::X >()    ; }
  15 #   define TEST_SET_NOLF_EXTRACT(X) TEST_SET_NOLF(X)
  16
  17     class Set_InsDel_func: public CppUnitMini::TestCase
  18     {
  19         static size_t  c_nMapSize           ;  // map size
  20         static size_t  c_nInsertThreadCount ;  // count of insertion thread
  21         static size_t  c_nDeleteThreadCount ;  // count of deletion thread
  22         static size_t  c_nEnsureThreadCount ;  // count of ensure thread
  23         static size_t  c_nThreadPassCount   ;  // pass count for each thread
  24         static size_t  c_nMaxLoadFactor     ;  // maximum load factor
  25         static bool    c_bPrintGCState;
  26
  27         typedef size_t  key_type;
  28         struct value_type {
  29             size_t      nKey;
  30             size_t      nData;
  31             CDS_ATOMIC::atomic<size_t>  nEnsureCall;
  32             bool volatile               bInitialized;
  33             std::thread::id             threadId;   // insert thread id
  34
  35             typedef cds::lock::Spinlock< cds::backoff::pause >   lock_type;
  36             mutable lock_type   m_access;
  37
  38             value_type()
  39                 : nKey(0)
  40                 , nData(0)
  41                 , nEnsureCall(0)
  42                 , bInitialized( false )
  43                 , threadId( std::this_thread::get_id() )
  44             {}
  45
  46             value_type( value_type const& s )
  47                 : nKey(s.nKey)
  48                 , nData(s.nData)
  49                 , nEnsureCall(s.nEnsureCall.load(CDS_ATOMIC::memory_order_relaxed))
  50                 , bInitialized( s.bInitialized )
  51                 , threadId( std::this_thread::get_id() )
  52             {}
  53
  54             // boost::container::flat_map requires operator =
  55             value_type& operator=( value_type const& v )
  56             {
  57                 nKey = v.nKey;
  58                 nData = v.nData;
  59                 nEnsureCall.store( v.nEnsureCall.load(CDS_ATOMIC::memory_order_relaxed), CDS_ATOMIC::memory_order_relaxed );
  60                 bInitialized = v.bInitialized;
  61
  62                 return *this;
  63             }
  64
  65         };
  66
  67
  68         size_t *    m_pKeyFirst;
  69         size_t *    m_pKeyLast;
  70         size_t *    m_pKeyArr;
  71
  72         template <class Set>
  73         class Inserter: public CppUnitMini::TestThread
  74         {
  75             Set&     m_Set;
  76             typedef typename Set::value_type keyval_type;
  77
  78             virtual Inserter *    clone()
  79             {
  80                 return new Inserter( *this );
  81             }
  82
  83             struct insert_functor {
  84                 size_t nTestFunctorRef;
  85
  86                 insert_functor()
  87                     : nTestFunctorRef(0)
  88                 {}
  89
  90                 void operator()( keyval_type& val )
  91                 {
  92                     cds::lock::scoped_lock< typename value_type::lock_type>    ac( val.val.m_access );
  93
  94                     val.val.nKey  = val.key;
  95                     val.val.nData = val.key * 8;
  96
  97                     ++nTestFunctorRef;
  98                     val.val.bInitialized = true;
  99                 }
 100             };
 101
 102         public:
 103             size_t  m_nInsertSuccess;
 104             size_t  m_nInsertFailed;
 105
 106             size_t  m_nTestFunctorRef;
 107
 108         public:
 109             Inserter( CppUnitMini::ThreadPool& pool, Set& rSet )
 110                 : CppUnitMini::TestThread( pool )
 111                 , m_Set( rSet )
 112             {}
 113             Inserter( Inserter& src )
 114                 : CppUnitMini::TestThread( src )
 115                 , m_Set( src.m_Set )
 116             {}
 117
 118             Set_InsDel_func&  getTest()
 119             {
 120                 return reinterpret_cast<Set_InsDel_func&>( 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_nInsertSuccess =
 131                     m_nInsertFailed =
 132                     m_nTestFunctorRef = 0;
 133
 134                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 135                 size_t * pKeyLast = getTest().m_pKeyLast;
 136
 137                 // func is passed by reference
 138                 insert_functor  func;
 139
 140                 if ( m_nThreadNo & 1 ) {
 141                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 142                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 143                             if ( rSet.insert( *p, cds::ref(func) ) )
 144                                 ++m_nInsertSuccess;
 145                             else
 146                                 ++m_nInsertFailed;
 147                         }
 148                     }
 149                 }
 150                 else {
 151                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 152                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 153                             if ( rSet.insert( *p, cds::ref(func) ) )
 154                                 ++m_nInsertSuccess;
 155                             else
 156                                 ++m_nInsertFailed;
 157                         }
 158                     }
 159                 }
 160
 161                 m_nTestFunctorRef = func.nTestFunctorRef;
 162             }
 163         };
 164
 165         template <class Set>
 166         class Ensurer: public CppUnitMini::TestThread
 167         {
 168             Set&     m_Set;
 169             typedef typename Set::value_type keyval_type;
 170
 171             virtual Ensurer *    clone()
 172             {
 173                 return new Ensurer( *this );
 174             }
 175
 176             struct ensure_functor {
 177                 size_t  nCreated;
 178                 size_t  nModified;
 179
 180                 ensure_functor()
 181                     : nCreated(0)
 182                     , nModified(0)
 183                 {}
 184
 185                 void operator()( bool bNew, keyval_type& val, size_t nKey )
 186                 {
 187                     cds::lock::scoped_lock<typename value_type::lock_type>    ac( val.val.m_access );
 188                     if ( !val.val.bInitialized )
 189                     {
 190                         val.val.nKey = val.key;
 191                         val.val.nData = val.key * 8;
 192                         val.val.bInitialized = true;
 193                     }
 194
 195                     if ( bNew ) {
 196                         ++nCreated;
 197                     }
 198                     else {
 199                         val.val.nEnsureCall.fetch_add( 1, CDS_ATOMIC::memory_order_relaxed );
 200                         ++nModified;
 201                     }
 202                 }
 203             private:
 204                 ensure_functor(const ensure_functor& );
 205             };
 206
 207         public:
 208             size_t  m_nEnsureFailed;
 209             size_t  m_nEnsureCreated;
 210             size_t  m_nEnsureExisted;
 211             size_t  m_nFunctorCreated;
 212             size_t  m_nFunctorModified;
 213
 214         public:
 215             Ensurer( CppUnitMini::ThreadPool& pool, Set& rSet )
 216                 : CppUnitMini::TestThread( pool )
 217                 , m_Set( rSet )
 218             {}
 219             Ensurer( Ensurer& src )
 220                 : CppUnitMini::TestThread( src )
 221                 , m_Set( src.m_Set )
 222             {}
 223
 224             Set_InsDel_func&  getTest()
 225             {
 226                 return reinterpret_cast<Set_InsDel_func&>( m_Pool.m_Test );
 227             }
 228
 229             virtual void init() { cds::threading::Manager::attachThread()   ; }
 230             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 231
 232             virtual void test()
 233             {
 234                 Set& rSet = m_Set;
 235
 236                 m_nEnsureCreated =
 237                     m_nEnsureExisted =
 238                     m_nEnsureFailed = 0;
 239
 240                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 241                 size_t * pKeyLast = getTest().m_pKeyLast;
 242
 243                 ensure_functor func;
 244
 245                 if ( m_nThreadNo & 1 ) {
 246                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 247                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 248                             std::pair<bool, bool> ret = rSet.ensure( *p, cds::ref( func ) );
 249                             if ( ret.first  ) {
 250                                 if ( ret.second )
 251                                     ++m_nEnsureCreated;
 252                                 else
 253                                     ++m_nEnsureExisted;
 254                             }
 255                             else
 256                                 ++m_nEnsureFailed;
 257                         }
 258                     }
 259                 }
 260                 else {
 261                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 262                         for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
 263                             std::pair<bool, bool> ret = rSet.ensure( *p, cds::ref( func ) );
 264                             if ( ret.first  ) {
 265                                 if ( ret.second )
 266                                     ++m_nEnsureCreated;
 267                                 else
 268                                     ++m_nEnsureExisted;
 269                             }
 270                             else
 271                                 ++m_nEnsureFailed;
 272                         }
 273                     }
 274                 }
 275
 276                 m_nFunctorCreated = func.nCreated;
 277                 m_nFunctorModified = func.nModified;
 278             }
 279         };
 280
 281         template <class Set>
 282         class Deleter: public CppUnitMini::TestThread
 283         {
 284             Set&     m_Set;
 285             typedef typename Set::value_type keyval_type;
 286
 287             virtual Deleter *    clone()
 288             {
 289                 return new Deleter( *this );
 290             }
 291
 292             struct value_container
 293             {
 294                 size_t      nKeyExpected;
 295
 296                 size_t      nSuccessItem;
 297                 size_t      nFailedItem;
 298
 299                 value_container()
 300                     : nSuccessItem(0)
 301                     , nFailedItem(0)
 302                 {}
 303             };
 304
 305             struct erase_functor {
 306                 value_container     m_cnt;
 307
 308                 void operator ()( keyval_type const& itm )
 309                 {
 310                     keyval_type& item = const_cast<keyval_type&>(itm);
 311                     while ( true ) {
 312                         bool bBkoff = false;
 313                         {
 314                             cds::lock::scoped_lock< typename value_type::lock_type>    ac( item.val.m_access );
 315                             if ( item.val.bInitialized ) {
 316                                 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
 317                                     ++m_cnt.nSuccessItem;
 318                                 else
 319                                     ++m_cnt.nFailedItem;
 320                                 item.val.nData++;
 321                                 item.val.nKey = 0;
 322                                 break;
 323                             }
 324                             else
 325                                 bBkoff = true;
 326                         }
 327                         if ( bBkoff )
 328                             cds::backoff::yield()();
 329                     }
 330                 }
 331             };
 332
 333         public:
 334             size_t  m_nDeleteSuccess;
 335             size_t  m_nDeleteFailed;
 336
 337             size_t  m_nValueSuccess;
 338             size_t  m_nValueFailed;
 339
 340         public:
 341             Deleter( CppUnitMini::ThreadPool& pool, Set& rSet )
 342                 : CppUnitMini::TestThread( pool )
 343                 , m_Set( rSet )
 344             {}
 345             Deleter( Deleter& src )
 346                 : CppUnitMini::TestThread( src )
 347                 , m_Set( src.m_Set )
 348             {}
 349
 350             Set_InsDel_func&  getTest()
 351             {
 352                 return reinterpret_cast<Set_InsDel_func&>( m_Pool.m_Test );
 353             }
 354
 355             virtual void init() { cds::threading::Manager::attachThread()   ; }
 356             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 357
 358             virtual void test()
 359             {
 360                 Set& rSet = m_Set;
 361
 362                 m_nDeleteSuccess =
 363                     m_nDeleteFailed = 0;
 364
 365                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 366                 size_t * pKeyLast = getTest().m_pKeyLast;
 367
 368                 erase_functor   func;
 369
 370                 if ( m_nThreadNo & 1 ) {
 371                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 372                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 373                             func.m_cnt.nKeyExpected = *p;
 374                             if ( rSet.erase( *p, cds::ref(func) ))
 375                                 ++m_nDeleteSuccess;
 376                             else
 377                                 ++m_nDeleteFailed;
 378                         }
 379                     }
 380                 }
 381                 else {
 382                     for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) {
 383                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 384                             func.m_cnt.nKeyExpected = *p;
 385                             if ( rSet.erase( *p, cds::ref(func) ))
 386                                 ++m_nDeleteSuccess;
 387                             else
 388                                 ++m_nDeleteFailed;
 389                         }
 390                     }
 391                 }
 392
 393                 m_nValueSuccess = func.m_cnt.nSuccessItem;
 394                 m_nValueFailed = func.m_cnt.nFailedItem;
 395             }
 396         };
 397
 398     protected:
 399         template <class Set>
 400         void do_test( size_t nLoadFactor )
 401         {
 402             CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 403
 404             Set  testSet( c_nMapSize, nLoadFactor );
 405             do_test_with( testSet );
 406         }
 407
 408         template <class Set>
 409         void do_test_with( Set& testSet )
 410         {
 411             typedef Inserter<Set>       InserterThread;
 412             typedef Deleter<Set>        DeleterThread;
 413             typedef Ensurer<Set>        EnsurerThread;
 414
 415             m_pKeyArr = new size_t[ c_nMapSize ];
 416             m_pKeyFirst = m_pKeyArr;
 417             m_pKeyLast = m_pKeyFirst + c_nMapSize;
 418             for ( size_t i = 0; i < c_nMapSize; ++i )
 419                 m_pKeyArr[i] = i;
 420             std::random_shuffle( m_pKeyFirst, m_pKeyLast );
 421
 422             cds::OS::Timer    timer;
 423
 424             CppUnitMini::ThreadPool pool( *this );
 425             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 426             pool.add( new DeleterThread( pool, testSet ), c_nDeleteThreadCount );
 427             pool.add( new EnsurerThread( pool, testSet ), c_nEnsureThreadCount );
 428             pool.run();
 429             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 430
 431             delete [] m_pKeyArr;
 432
 433             size_t nInsertSuccess = 0;
 434             size_t nInsertFailed = 0;
 435             size_t nDeleteSuccess = 0;
 436             size_t nDeleteFailed = 0;
 437             size_t nDelValueSuccess = 0;
 438             size_t nDelValueFailed = 0;
 439             size_t nEnsureFailed = 0;
 440             size_t nEnsureCreated = 0;
 441             size_t nEnsureModified = 0;
 442             size_t nEnsFuncCreated = 0;
 443             size_t nEnsFuncModified = 0;
 444             size_t nTestFunctorRef = 0;
 445
 446             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 447                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 448                 if ( pThread ) {
 449                     nInsertSuccess += pThread->m_nInsertSuccess;
 450                     nInsertFailed += pThread->m_nInsertFailed;
 451                     nTestFunctorRef += pThread->m_nTestFunctorRef;
 452                 }
 453                 else {
 454                     DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
 455                     if ( p ) {
 456                         nDeleteSuccess += p->m_nDeleteSuccess;
 457                         nDeleteFailed += p->m_nDeleteFailed;
 458                         nDelValueSuccess += p->m_nValueSuccess;
 459                         nDelValueFailed += p->m_nValueFailed;
 460                     }
 461                     else {
 462                         EnsurerThread * pEns = static_cast<EnsurerThread *>( *it );
 463                         nEnsureCreated += pEns->m_nEnsureCreated;
 464                         nEnsureModified += pEns->m_nEnsureExisted;
 465                         nEnsureFailed += pEns->m_nEnsureFailed;
 466                         nEnsFuncCreated += pEns->m_nFunctorCreated;
 467                         nEnsFuncModified += pEns->m_nFunctorModified;
 468                     }
 469                 }
 470             }
 471
 472             CPPUNIT_MSG(
 473                    "    Totals: Ins succ=" << nInsertSuccess
 474                 << " Del succ=" << nDeleteSuccess << "\n"
 475                 << "          : Ins fail=" << nInsertFailed
 476                 << " Del fail=" << nDeleteFailed << "\n"
 477                 << "          : Ensure succ=" << (nEnsureCreated + nEnsureModified) << " fail=" << nEnsureFailed
 478                 << " create=" << nEnsureCreated << " modify=" << nEnsureModified << "\n"
 479                 << "          Set size=" << testSet.size()
 480                 );
 481
 482             CPPUNIT_CHECK_EX( nDelValueFailed == 0, "Functor del failed=" << nDelValueFailed );
 483             CPPUNIT_CHECK_EX( nDelValueSuccess == nDeleteSuccess,  "Delete success=" << nDeleteSuccess << " functor=" << nDelValueSuccess );
 484
 485             CPPUNIT_CHECK( nEnsureFailed == 0 );
 486
 487             CPPUNIT_CHECK_EX( nEnsureCreated == nEnsFuncCreated, "Ensure created=" << nEnsureCreated << " functor=" << nEnsFuncCreated );
 488             CPPUNIT_CHECK_EX( nEnsureModified == nEnsFuncModified, "Ensure modified=" << nEnsureModified << " functor=" << nEnsFuncModified );
 489
 490             // nTestFunctorRef is call count of insert functor
 491             CPPUNIT_CHECK_EX( nTestFunctorRef == nInsertSuccess, "nInsertSuccess=" << nInsertSuccess << " functor nTestFunctorRef=" << nTestFunctorRef );
 492
 493             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 494             timer.reset();
 495             testSet.clear();
 496             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 497             CPPUNIT_CHECK( testSet.empty() );
 498
 499             additional_check( testSet );
 500             print_stat(  testSet  );
 501
 502             additional_cleanup( testSet );
 503         }
 504
 505         template <class Set>
 506         void test()
 507         {
 508             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 509                 << " delete=" << c_nDeleteThreadCount
 510                 << " ensure=" << c_nEnsureThreadCount
 511                 << " pass count=" << c_nThreadPassCount
 512                 << " map size=" << c_nMapSize
 513                 );
 514
 515             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 516                 do_test<Set>( nLoadFactor );
 517                 if ( c_bPrintGCState )
 518                     print_gc_state();
 519             }
 520         }
 521
 522         template <class Set>
 523         void test_nolf()
 524         {
 525             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 526                 << " delete=" << c_nDeleteThreadCount
 527                 << " ensure=" << c_nEnsureThreadCount
 528                 << " pass count=" << c_nThreadPassCount
 529                 << " map size=" << c_nMapSize
 530                 );
 531
 532             Set s;
 533             do_test_with( s );
 534             if ( c_bPrintGCState )
 535                 print_gc_state();
 536         }
 537
 538         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 539             c_nInsertThreadCount = cfg.getULong("InsertThreadCount", 4 );
 540             c_nDeleteThreadCount = cfg.getULong("DeleteThreadCount", 4 );
 541             c_nEnsureThreadCount = cfg.getULong("EnsureThreadCount", 4 );
 542             c_nThreadPassCount = cfg.getULong("ThreadPassCount", 4 );
 543             c_nMapSize = cfg.getULong("MapSize", 1000000 );
 544             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 545             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 546         }
 547
 548         void run_MichaelSet(const char *in_name, bool invert = false);
 549         void run_SplitList(const char *in_name, bool invert = false);
 550         void run_StripedSet(const char *in_name, bool invert = false);
 551         void run_RefinableSet(const char *in_name, bool invert = false);
 552         void run_CuckooSet(const char *in_name, bool invert = false);
 553         void run_SkipListSet(const char *in_name, bool invert = false);
 554         void run_EllenBinTreeSet(const char *in_name, bool invert = false);
 555
 556         typedef CppUnitMini::TestCase Base;
 557         virtual void myRun(const char *in_name, bool invert = false)
 558         {
 559             setUpParams( m_Cfg.get( "Map_InsDel_func" ));
 560
 561             run_MichaelSet(in_name, invert);
 562             run_SplitList(in_name, invert);
 563             run_SkipListSet(in_name, invert);
 564             run_EllenBinTreeSet(in_name, invert);
 565             run_StripedSet(in_name, invert);
 566             run_RefinableSet(in_name, invert);
 567             run_CuckooSet(in_name, invert);
 568
 569             endTestCase();
 570         }
 571
 572
 573 #   include "set2/set_defs.h"
 574     CDSUNIT_DECLARE_MichaelSet
 575     CDSUNIT_DECLARE_SplitList
 576     CDSUNIT_DECLARE_StripedSet
 577     CDSUNIT_DECLARE_RefinableSet
 578     CDSUNIT_DECLARE_CuckooSet
 579     CDSUNIT_DECLARE_SkipListSet
 580     CDSUNIT_DECLARE_EllenBinTreeSet
 581
 582     };
 583 } // namespace set2