tests/unit/set2/set_insdel_func.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #include <functional>
  32 #include <vector>
  33 #include <mutex>    //unique_lock
  34
  35 #include "set2/set_type.h"
  36 #include "cppunit/thread.h"
  37 #include <cds/sync/spinlock.h>
  38
  39 namespace set2 {
  40
  41 #define TEST_CASE(TAG, X)  void X();
  42
  43     class Set_InsDel_func: public CppUnitMini::TestCase
  44     {
  45     public:
  46         size_t  c_nSetSize = 1000000;      // set size
  47         size_t  c_nInsertThreadCount = 4;  // count of insertion thread
  48         size_t  c_nDeleteThreadCount = 4;  // count of deletion thread
  49         size_t  c_nUpdateThreadCount = 4;  // count of ensure thread
  50         size_t  c_nThreadPassCount = 4;    // pass count for each thread
  51         size_t  c_nMaxLoadFactor = 8;      // maximum load factor
  52         bool    c_bPrintGCState;
  53
  54         size_t  c_nCuckooInitialSize = 1024;// initial size for CuckooSet
  55         size_t  c_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
  56         size_t  c_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
  57
  58         size_t c_nFeldmanSet_HeadBits = 10;
  59         size_t c_nFeldmanSet_ArrayBits = 4;
  60
  61         size_t c_nLoadFactor = 2;
  62
  63     private:
  64         typedef size_t  key_type;
  65         struct value_type {
  66             size_t      nKey;
  67             size_t      nData;
  68             atomics::atomic<size_t> nUpdateCall;
  69             bool volatile   bInitialized;
  70             cds::OS::ThreadId          threadId     ;   // insert thread id
  71
  72             typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
  73             mutable lock_type   m_access;
  74
  75             value_type()
  76                 : nKey(0)
  77                 , nData(0)
  78                 , nUpdateCall(0)
  79                 , bInitialized( false )
  80                 , threadId( cds::OS::get_current_thread_id() )
  81             {}
  82
  83             value_type( value_type const& s )
  84                 : nKey(s.nKey)
  85                 , nData(s.nData)
  86                 , nUpdateCall(s.nUpdateCall.load(atomics::memory_order_relaxed))
  87                 , bInitialized( s.bInitialized )
  88                 , threadId( cds::OS::get_current_thread_id() )
  89             {}
  90
  91             // boost::container::flat_map requires operator =
  92             value_type& operator=( value_type const& v )
  93             {
  94                 nKey = v.nKey;
  95                 nData = v.nData;
  96                 nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
  97                 bInitialized = v.bInitialized;
  98
  99                 return *this;
 100             }
 101
 102         };
 103
 104
 105         size_t *    m_pKeyFirst;
 106         size_t *    m_pKeyLast;
 107         size_t *    m_pKeyArr;
 108
 109         template <class Set>
 110         class Inserter: public CppUnitMini::TestThread
 111         {
 112             Set&     m_Set;
 113             typedef typename Set::value_type keyval_type;
 114
 115             virtual Inserter *    clone()
 116             {
 117                 return new Inserter( *this );
 118             }
 119
 120             struct insert_functor {
 121                 size_t nTestFunctorRef;
 122
 123                 insert_functor()
 124                     : nTestFunctorRef(0)
 125                 {}
 126
 127                 void operator()( keyval_type& val )
 128                 {
 129                     std::unique_lock< typename value_type::lock_type>    ac( val.val.m_access );
 130
 131                     val.val.nKey  = val.key;
 132                     val.val.nData = val.key * 8;
 133
 134                     ++nTestFunctorRef;
 135                     val.val.bInitialized = true;
 136                 }
 137             };
 138
 139         public:
 140             size_t  m_nInsertSuccess;
 141             size_t  m_nInsertFailed;
 142
 143             size_t  m_nTestFunctorRef;
 144
 145         public:
 146             Inserter( CppUnitMini::ThreadPool& pool, Set& rSet )
 147                 : CppUnitMini::TestThread( pool )
 148                 , m_Set( rSet )
 149             {}
 150             Inserter( Inserter& src )
 151                 : CppUnitMini::TestThread( src )
 152                 , m_Set( src.m_Set )
 153             {}
 154
 155             Set_InsDel_func&  getTest()
 156             {
 157                 return reinterpret_cast<Set_InsDel_func&>( m_Pool.m_Test );
 158             }
 159
 160             virtual void init() { cds::threading::Manager::attachThread()   ; }
 161             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 162
 163             virtual void test()
 164             {
 165                 Set& rSet = m_Set;
 166
 167                 m_nInsertSuccess =
 168                     m_nInsertFailed =
 169                     m_nTestFunctorRef = 0;
 170
 171                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 172                 size_t * pKeyLast = getTest().m_pKeyLast;
 173                 size_t const nPassCount = getTest().c_nThreadPassCount;
 174
 175                 // func is passed by reference
 176                 insert_functor  func;
 177
 178                 if ( m_nThreadNo & 1 ) {
 179                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 180                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 181                             if ( rSet.insert( *p, std::ref(func) ) )
 182                                 ++m_nInsertSuccess;
 183                             else
 184                                 ++m_nInsertFailed;
 185                         }
 186                     }
 187                 }
 188                 else {
 189                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 190                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 191                             if ( rSet.insert( *p, std::ref(func) ) )
 192                                 ++m_nInsertSuccess;
 193                             else
 194                                 ++m_nInsertFailed;
 195                         }
 196                     }
 197                 }
 198
 199                 m_nTestFunctorRef = func.nTestFunctorRef;
 200             }
 201         };
 202
 203         template <class Set>
 204         class Updater: public CppUnitMini::TestThread
 205         {
 206             Set&     m_Set;
 207             typedef typename Set::value_type keyval_type;
 208
 209             virtual Updater *    clone()
 210             {
 211                 return new Updater( *this );
 212             }
 213
 214             struct update_functor {
 215                 size_t  nCreated;
 216                 size_t  nModified;
 217
 218                 update_functor()
 219                     : nCreated(0)
 220                     , nModified(0)
 221                 {}
 222
 223                 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
 224                 {
 225                     std::unique_lock<typename value_type::lock_type> ac( val.val.m_access );
 226                     if ( !val.val.bInitialized )
 227                     {
 228                         val.val.nKey = val.key;
 229                         val.val.nData = val.key * 8;
 230                         val.val.bInitialized = true;
 231                     }
 232
 233                     if ( bNew ) {
 234                         ++nCreated;
 235                     }
 236                     else {
 237                         val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
 238                         ++nModified;
 239                     }
 240                 }
 241
 242                 void operator()( keyval_type& cur, keyval_type * old )
 243                 {
 244                     operator()( old == nullptr, cur, 0 );
 245                 }
 246
 247             private:
 248                 update_functor(const update_functor& );
 249             };
 250
 251         public:
 252             size_t  m_nUpdateFailed;
 253             size_t  m_nUpdateCreated;
 254             size_t  m_nUpdateExisted;
 255             size_t  m_nFunctorCreated;
 256             size_t  m_nFunctorModified;
 257
 258         public:
 259             Updater( CppUnitMini::ThreadPool& pool, Set& rSet )
 260                 : CppUnitMini::TestThread( pool )
 261                 , m_Set( rSet )
 262             {}
 263             Updater( Updater& src )
 264                 : CppUnitMini::TestThread( src )
 265                 , m_Set( src.m_Set )
 266             {}
 267
 268             Set_InsDel_func&  getTest()
 269             {
 270                 return reinterpret_cast<Set_InsDel_func&>( m_Pool.m_Test );
 271             }
 272
 273             virtual void init() { cds::threading::Manager::attachThread()   ; }
 274             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 275
 276             virtual void test()
 277             {
 278                 Set& rSet = m_Set;
 279
 280                 m_nUpdateCreated =
 281                     m_nUpdateExisted =
 282                     m_nUpdateFailed = 0;
 283
 284                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 285                 size_t * pKeyLast = getTest().m_pKeyLast;
 286                 size_t const nPassCount = getTest().c_nThreadPassCount;
 287
 288                 update_functor func;
 289
 290                 if ( m_nThreadNo & 1 ) {
 291                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 292                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 293                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 294                             if ( ret.first  ) {
 295                                 if ( ret.second )
 296                                     ++m_nUpdateCreated;
 297                                 else
 298                                     ++m_nUpdateExisted;
 299                             }
 300                             else
 301                                 ++m_nUpdateFailed;
 302                         }
 303                     }
 304                 }
 305                 else {
 306                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 307                         for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
 308                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 309                             if ( ret.first  ) {
 310                                 if ( ret.second )
 311                                     ++m_nUpdateCreated;
 312                                 else
 313                                     ++m_nUpdateExisted;
 314                             }
 315                             else
 316                                 ++m_nUpdateFailed;
 317                         }
 318                     }
 319                 }
 320
 321                 m_nFunctorCreated = func.nCreated;
 322                 m_nFunctorModified = func.nModified;
 323             }
 324         };
 325
 326         template <class Set>
 327         class Deleter: public CppUnitMini::TestThread
 328         {
 329             Set&     m_Set;
 330             typedef typename Set::value_type keyval_type;
 331
 332             virtual Deleter *    clone()
 333             {
 334                 return new Deleter( *this );
 335             }
 336
 337             struct value_container
 338             {
 339                 size_t      nKeyExpected;
 340
 341                 size_t      nSuccessItem;
 342                 size_t      nFailedItem;
 343
 344                 value_container()
 345                     : nSuccessItem(0)
 346                     , nFailedItem(0)
 347                 {}
 348             };
 349
 350             struct erase_functor {
 351                 value_container     m_cnt;
 352
 353                 void operator ()( keyval_type const& itm )
 354                 {
 355                     keyval_type& item = const_cast<keyval_type&>(itm);
 356                     while ( true ) {
 357                         bool bBkoff = false;
 358                         {
 359                             std::unique_lock< typename value_type::lock_type> ac( item.val.m_access );
 360                             if ( item.val.bInitialized ) {
 361                                 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
 362                                     ++m_cnt.nSuccessItem;
 363                                 else
 364                                     ++m_cnt.nFailedItem;
 365                                 item.val.nData++;
 366                                 item.val.nKey = 0;
 367                                 break;
 368                             }
 369                             else
 370                                 bBkoff = true;
 371                         }
 372                         if ( bBkoff )
 373                             cds::backoff::yield()();
 374                     }
 375                 }
 376             };
 377
 378         public:
 379             size_t  m_nDeleteSuccess;
 380             size_t  m_nDeleteFailed;
 381
 382             size_t  m_nValueSuccess;
 383             size_t  m_nValueFailed;
 384
 385         public:
 386             Deleter( CppUnitMini::ThreadPool& pool, Set& rSet )
 387                 : CppUnitMini::TestThread( pool )
 388                 , m_Set( rSet )
 389             {}
 390             Deleter( Deleter& src )
 391                 : CppUnitMini::TestThread( src )
 392                 , m_Set( src.m_Set )
 393             {}
 394
 395             Set_InsDel_func&  getTest()
 396             {
 397                 return reinterpret_cast<Set_InsDel_func&>( m_Pool.m_Test );
 398             }
 399
 400             virtual void init() { cds::threading::Manager::attachThread()   ; }
 401             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 402
 403             virtual void test()
 404             {
 405                 Set& rSet = m_Set;
 406
 407                 m_nDeleteSuccess =
 408                     m_nDeleteFailed = 0;
 409
 410                 size_t * pKeyFirst = getTest().m_pKeyFirst;
 411                 size_t * pKeyLast = getTest().m_pKeyLast;
 412                 size_t const nPassCount = getTest().c_nThreadPassCount;
 413
 414                 erase_functor   func;
 415
 416                 if ( m_nThreadNo & 1 ) {
 417                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 418                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 419                             func.m_cnt.nKeyExpected = *p;
 420                             if ( rSet.erase( *p, std::ref(func) ))
 421                                 ++m_nDeleteSuccess;
 422                             else
 423                                 ++m_nDeleteFailed;
 424                         }
 425                     }
 426                 }
 427                 else {
 428                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 429                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 430                             func.m_cnt.nKeyExpected = *p;
 431                             if ( rSet.erase( *p, std::ref(func) ))
 432                                 ++m_nDeleteSuccess;
 433                             else
 434                                 ++m_nDeleteFailed;
 435                         }
 436                     }
 437                 }
 438
 439                 m_nValueSuccess = func.m_cnt.nSuccessItem;
 440                 m_nValueFailed = func.m_cnt.nFailedItem;
 441             }
 442         };
 443
 444     protected:
 445
 446         template <class Set>
 447         void do_test( Set& testSet )
 448         {
 449             typedef Inserter<Set>       InserterThread;
 450             typedef Deleter<Set>        DeleterThread;
 451             typedef Updater<Set>        UpdaterThread;
 452
 453             m_pKeyArr = new size_t[ c_nSetSize ];
 454             m_pKeyFirst = m_pKeyArr;
 455             m_pKeyLast = m_pKeyFirst + c_nSetSize;
 456             for ( size_t i = 0; i < c_nSetSize; ++i )
 457                 m_pKeyArr[i] = i;
 458             shuffle( m_pKeyFirst, m_pKeyLast );
 459
 460             cds::OS::Timer    timer;
 461
 462             CppUnitMini::ThreadPool pool( *this );
 463             pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
 464             pool.add( new DeleterThread( pool, testSet ), c_nDeleteThreadCount );
 465             pool.add( new UpdaterThread( pool, testSet ), c_nUpdateThreadCount );
 466             pool.run();
 467             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 468
 469             delete [] m_pKeyArr;
 470
 471             size_t nInsertSuccess = 0;
 472             size_t nInsertFailed = 0;
 473             size_t nDeleteSuccess = 0;
 474             size_t nDeleteFailed = 0;
 475             size_t nDelValueSuccess = 0;
 476             size_t nDelValueFailed = 0;
 477             size_t nUpdateFailed = 0;
 478             size_t nUpdateCreated = 0;
 479             size_t nUpdateModified = 0;
 480             size_t nEnsFuncCreated = 0;
 481             size_t nEnsFuncModified = 0;
 482             size_t nTestFunctorRef = 0;
 483
 484             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 485                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 486                 if ( pThread ) {
 487                     nInsertSuccess += pThread->m_nInsertSuccess;
 488                     nInsertFailed += pThread->m_nInsertFailed;
 489                     nTestFunctorRef += pThread->m_nTestFunctorRef;
 490                 }
 491                 else {
 492                     DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
 493                     if ( p ) {
 494                         nDeleteSuccess += p->m_nDeleteSuccess;
 495                         nDeleteFailed += p->m_nDeleteFailed;
 496                         nDelValueSuccess += p->m_nValueSuccess;
 497                         nDelValueFailed += p->m_nValueFailed;
 498                     }
 499                     else {
 500                         UpdaterThread * pEns = static_cast<UpdaterThread *>( *it );
 501                         nUpdateCreated += pEns->m_nUpdateCreated;
 502                         nUpdateModified += pEns->m_nUpdateExisted;
 503                         nUpdateFailed += pEns->m_nUpdateFailed;
 504                         nEnsFuncCreated += pEns->m_nFunctorCreated;
 505                         nEnsFuncModified += pEns->m_nFunctorModified;
 506                     }
 507                 }
 508             }
 509
 510             CPPUNIT_MSG(
 511                    "    Totals: Ins succ=" << nInsertSuccess
 512                 << " Del succ=" << nDeleteSuccess << "\n"
 513                 << "          : Ins fail=" << nInsertFailed
 514                 << " Del fail=" << nDeleteFailed << "\n"
 515                 << "          : Update succ=" << (nUpdateCreated + nUpdateModified) << " fail=" << nUpdateFailed
 516                 << " create=" << nUpdateCreated << " modify=" << nUpdateModified << "\n"
 517                 << "          Set size=" << testSet.size()
 518                 );
 519
 520             CPPUNIT_CHECK_EX( nDelValueFailed == 0, "Functor del failed=" << nDelValueFailed );
 521             CPPUNIT_CHECK_EX( nDelValueSuccess == nDeleteSuccess,  "Delete success=" << nDeleteSuccess << " functor=" << nDelValueSuccess );
 522
 523             CPPUNIT_CHECK( nUpdateFailed == 0 );
 524
 525             CPPUNIT_CHECK_EX( nUpdateCreated == nEnsFuncCreated, "Update created=" << nUpdateCreated << " functor=" << nEnsFuncCreated );
 526             CPPUNIT_CHECK_EX( nUpdateModified == nEnsFuncModified, "Update modified=" << nUpdateModified << " functor=" << nEnsFuncModified );
 527
 528             // nTestFunctorRef is call count of insert functor
 529             CPPUNIT_CHECK_EX( nTestFunctorRef == nInsertSuccess, "nInsertSuccess=" << nInsertSuccess << " functor nTestFunctorRef=" << nTestFunctorRef );
 530
 531             CPPUNIT_MSG( "  Clear set (single-threaded)..." );
 532             timer.reset();
 533             testSet.clear();
 534             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 535             CPPUNIT_CHECK( testSet.empty() );
 536
 537             additional_check( testSet );
 538             print_stat(  testSet  );
 539
 540             additional_cleanup( testSet );
 541         }
 542
 543         template <class Set>
 544         void run_test()
 545         {
 546             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 547                 << " delete=" << c_nDeleteThreadCount
 548                 << " ensure=" << c_nUpdateThreadCount
 549                 << " pass count=" << c_nThreadPassCount
 550                 << " set size=" << c_nSetSize
 551                 );
 552
 553             if ( Set::c_bLoadFactorDepended ) {
 554                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 555                     CPPUNIT_MSG("  LoadFactor = " << c_nLoadFactor );
 556                     Set s( *this );
 557                     do_test( s );
 558                     if ( c_bPrintGCState )
 559                         print_gc_state();
 560                 }
 561             }
 562             else {
 563                 Set s( *this );
 564                 do_test( s );
 565                 if ( c_bPrintGCState )
 566                     print_gc_state();
 567             }
 568         }
 569
 570         void setUpParams( const CppUnitMini::TestCfg& cfg );
 571
 572 #   include "set2/set_defs.h"
 573     CDSUNIT_DECLARE_MichaelSet
 574     CDSUNIT_DECLARE_SkipListSet
 575     CDSUNIT_DECLARE_SplitList
 576     CDSUNIT_DECLARE_StripedSet
 577     CDSUNIT_DECLARE_RefinableSet
 578     CDSUNIT_DECLARE_CuckooSet
 579     CDSUNIT_DECLARE_EllenBinTreeSet
 580     CDSUNIT_DECLARE_FeldmanHashSet_fixed
 581     CDSUNIT_DECLARE_FeldmanHashSet_city
 582
 583     CPPUNIT_TEST_SUITE_(Set_InsDel_func, "Map_InsDel_func")
 584         CDSUNIT_TEST_MichaelSet
 585         CDSUNIT_TEST_SplitList
 586         CDSUNIT_TEST_SkipListSet
 587         CDSUNIT_TEST_FeldmanHashSet_fixed
 588         CDSUNIT_TEST_FeldmanHashSet_city
 589         CDSUNIT_TEST_EllenBinTreeSet
 590         CDSUNIT_TEST_StripedSet
 591         CDSUNIT_TEST_RefinableSet
 592         CDSUNIT_TEST_CuckooSet
 593     CPPUNIT_TEST_SUITE_END();
 594
 595     };
 596 } // namespace set2