test/stress/set/insdel_func/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 "set_type.h"
  32
  33 namespace set {
  34
  35     class Set_InsDel_func: public cds_test::stress_fixture
  36     {
  37     public:
  38         static size_t s_nSetSize;               // set size
  39         static size_t s_nInsertThreadCount;     // count of insertion thread
  40         static size_t s_nDeleteThreadCount;     // count of deletion thread
  41         static size_t s_nUpdateThreadCount;     // count of updating thread
  42         static size_t s_nThreadPassCount;       // pass count for each thread
  43         static size_t s_nMaxLoadFactor;         // maximum load factor
  44
  45         static size_t s_nCuckooInitialSize;     // initial size for CuckooSet
  46         static size_t s_nCuckooProbesetSize;    // CuckooSet probeset size (only for list-based probeset)
  47         static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
  48
  49         static size_t s_nFeldmanSet_HeadBits;
  50         static size_t s_nFeldmanSet_ArrayBits;
  51
  52         static size_t s_nLoadFactor;
  53
  54         static void SetUpTestCase();
  55         //static void TearDownTestCase();
  56
  57     public:
  58         typedef size_t  key_type;
  59
  60         struct value {
  61             size_t      nKey;
  62             size_t      nData;
  63             atomics::atomic<size_t> nUpdateCall;
  64             bool volatile   bInitialized;
  65             cds::OS::ThreadId          threadId     ;   // insert thread id
  66
  67             typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
  68             mutable lock_type   m_access;
  69
  70             value()
  71                 : nKey(0)
  72                 , nData(0)
  73                 , nUpdateCall(0)
  74                 , bInitialized( false )
  75                 , threadId( cds::OS::get_current_thread_id() )
  76             {}
  77
  78             value( value const& s )
  79                 : nKey(s.nKey)
  80                 , nData(s.nData)
  81                 , nUpdateCall(s.nUpdateCall.load(atomics::memory_order_relaxed))
  82                 , bInitialized( s.bInitialized )
  83                 , threadId( cds::OS::get_current_thread_id() )
  84                 , m_access()
  85             {}
  86
  87             // boost::container::flat_map requires operator =
  88             value& operator=( value const& v )
  89             {
  90                 nKey = v.nKey;
  91                 nData = v.nData;
  92                 threadId = v.threadId;
  93                 nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
  94                 bInitialized = v.bInitialized;
  95
  96                 return *this;
  97             }
  98         };
  99
 100         size_t *    m_pKeyFirst;
 101         size_t *    m_pKeyLast;
 102         size_t *    m_pKeyArr;
 103
 104         enum {
 105             insert_thread,
 106             update_thread,
 107             delete_thread
 108         };
 109
 110         template <class Set>
 111         class Inserter: public cds_test::thread
 112         {
 113             typedef cds_test::thread base_class;
 114
 115             Set&     m_Set;
 116             typedef typename Set::value_type keyval_type;
 117
 118             struct insert_functor {
 119                 size_t nTestFunctorRef;
 120
 121                 insert_functor()
 122                     : nTestFunctorRef(0)
 123                 {}
 124                 insert_functor( insert_functor const& ) = delete;
 125
 126                 void operator()( keyval_type& val )
 127                 {
 128                     std::unique_lock< typename value::lock_type> ac( val.val.m_access );
 129
 130                     val.val.nKey  = val.key;
 131                     val.val.nData = val.key * 8;
 132
 133                     ++nTestFunctorRef;
 134                     val.val.bInitialized = true;
 135                 }
 136             };
 137
 138         public:
 139             size_t  m_nInsertSuccess = 0;
 140             size_t  m_nInsertFailed = 0;
 141             size_t  m_nTestFunctorRef = 0;
 142
 143         public:
 144             Inserter( cds_test::thread_pool& pool, Set& set )
 145                 : base_class( pool, insert_thread )
 146                 , m_Set( set )
 147             {}
 148
 149             Inserter( Inserter& src )
 150                 : base_class( src )
 151                 , m_Set( src.m_Set )
 152             {}
 153
 154             virtual thread * clone()
 155             {
 156                 return new Inserter( *this );
 157             }
 158
 159             virtual void test()
 160             {
 161                 Set& rSet = m_Set;
 162                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 163
 164                 size_t * pKeyFirst      = fixture.m_pKeyFirst;
 165                 size_t * pKeyLast       = fixture.m_pKeyLast;
 166                 size_t const nPassCount = fixture.s_nThreadPassCount;
 167
 168                 // func is passed by reference
 169                 insert_functor  func;
 170
 171                 if ( id() & 1 ) {
 172                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 173                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 174                             if ( rSet.insert( *p, std::ref( func )))
 175                                 ++m_nInsertSuccess;
 176                             else
 177                                 ++m_nInsertFailed;
 178                         }
 179                     }
 180                 }
 181                 else {
 182                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 183                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 184                             if ( rSet.insert( *p, std::ref( func )))
 185                                 ++m_nInsertSuccess;
 186                             else
 187                                 ++m_nInsertFailed;
 188                         }
 189                     }
 190                 }
 191
 192                 m_nTestFunctorRef = func.nTestFunctorRef;
 193             }
 194         };
 195
 196         template <class Set>
 197         class Updater: public cds_test::thread
 198         {
 199             typedef cds_test::thread base_class;
 200
 201             Set&     m_Set;
 202             typedef typename Set::value_type keyval_type;
 203
 204             struct update_functor {
 205                 size_t  nCreated = 0;
 206                 size_t  nModified = 0;
 207
 208                 update_functor() {}
 209                 update_functor( const update_functor& ) = delete;
 210
 211                 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
 212                 {
 213                     std::unique_lock<typename value::lock_type> ac( val.val.m_access );
 214                     if ( !val.val.bInitialized )
 215                     {
 216                         val.val.nKey = val.key;
 217                         val.val.nData = val.key * 8;
 218                         val.val.bInitialized = true;
 219                     }
 220
 221                     if ( bNew ) {
 222                         ++nCreated;
 223                     }
 224                     else {
 225                         val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
 226                         ++nModified;
 227                     }
 228                 }
 229
 230                 void operator()( keyval_type& cur, keyval_type * old )
 231                 {
 232                     operator()( old == nullptr, cur, 0 );
 233                 }
 234             };
 235
 236         public:
 237             size_t  m_nUpdateFailed = 0;
 238             size_t  m_nUpdateCreated = 0;
 239             size_t  m_nUpdateExisted = 0;
 240             size_t  m_nFunctorCreated = 0;
 241             size_t  m_nFunctorModified = 0;
 242
 243         public:
 244             Updater( cds_test::thread_pool& pool, Set& set )
 245                 : base_class( pool, update_thread )
 246                 , m_Set( set )
 247             {}
 248
 249             Updater( Updater& src )
 250                 : base_class( src )
 251                 , m_Set( src.m_Set )
 252             {}
 253
 254             virtual thread * clone()
 255             {
 256                 return new Updater( *this );
 257             }
 258
 259             virtual void test()
 260             {
 261                 Set& rSet = m_Set;
 262
 263                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 264                 size_t * pKeyFirst = fixture.m_pKeyFirst;
 265                 size_t * pKeyLast = fixture.m_pKeyLast;
 266                 size_t const nPassCount = fixture.s_nThreadPassCount;
 267
 268                 update_functor func;
 269
 270                 if ( id() & 1 ) {
 271                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 272                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 273                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 274                             if ( ret.first  ) {
 275                                 if ( ret.second )
 276                                     ++m_nUpdateCreated;
 277                                 else
 278                                     ++m_nUpdateExisted;
 279                             }
 280                             else
 281                                 ++m_nUpdateFailed;
 282                         }
 283                     }
 284                 }
 285                 else {
 286                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 287                         for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
 288                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 289                             if ( ret.first  ) {
 290                                 if ( ret.second )
 291                                     ++m_nUpdateCreated;
 292                                 else
 293                                     ++m_nUpdateExisted;
 294                             }
 295                             else
 296                                 ++m_nUpdateFailed;
 297                         }
 298                     }
 299                 }
 300
 301                 m_nFunctorCreated = func.nCreated;
 302                 m_nFunctorModified = func.nModified;
 303             }
 304         };
 305
 306         template <class Set>
 307         class Deleter: public cds_test::thread
 308         {
 309             typedef cds_test::thread base_class;
 310
 311             Set&     m_Set;
 312             typedef typename Set::value_type keyval_type;
 313
 314             struct value_container
 315             {
 316                 size_t      nKeyExpected;
 317
 318                 size_t      nSuccessItem = 0;
 319                 size_t      nFailedItem = 0;
 320             };
 321
 322             struct erase_functor {
 323                 value_container     m_cnt;
 324
 325                 void operator ()( keyval_type const& itm )
 326                 {
 327                     keyval_type& item = const_cast<keyval_type&>(itm);
 328                     while ( true ) {
 329                         bool bBkoff = false;
 330                         {
 331                             std::unique_lock< typename value::lock_type> ac( item.val.m_access );
 332                             if ( item.val.bInitialized ) {
 333                                 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
 334                                     ++m_cnt.nSuccessItem;
 335                                 else
 336                                     ++m_cnt.nFailedItem;
 337                                 item.val.nData++;
 338                                 item.val.nKey = 0;
 339                                 break;
 340                             }
 341                             else
 342                                 bBkoff = true;
 343                         }
 344                         if ( bBkoff )
 345                             cds::backoff::yield()();
 346                     }
 347                 }
 348             };
 349
 350         public:
 351             size_t  m_nDeleteSuccess = 0;
 352             size_t  m_nDeleteFailed = 0;
 353             size_t  m_nValueSuccess = 0;
 354             size_t  m_nValueFailed = 0;
 355
 356         public:
 357             Deleter( cds_test::thread_pool& pool, Set& set )
 358                 : base_class( pool, delete_thread )
 359                 , m_Set( set )
 360             {}
 361
 362             Deleter( Deleter& src )
 363                 : base_class( src )
 364                 , m_Set( src.m_Set )
 365             {}
 366
 367             virtual thread * clone()
 368             {
 369                 return new Deleter( *this );
 370             }
 371
 372             virtual void test()
 373             {
 374                 Set& rSet = m_Set;
 375
 376                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 377                 size_t * pKeyFirst      = fixture.m_pKeyFirst;
 378                 size_t * pKeyLast       = fixture.m_pKeyLast;
 379                 size_t const nPassCount = fixture.s_nThreadPassCount;
 380
 381                 erase_functor   func;
 382
 383                 if ( id() & 1 ) {
 384                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 385                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 386                             func.m_cnt.nKeyExpected = *p;
 387                             if ( rSet.erase( *p, std::ref( func )))
 388                                 ++m_nDeleteSuccess;
 389                             else
 390                                 ++m_nDeleteFailed;
 391                         }
 392                     }
 393                 }
 394                 else {
 395                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 396                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 397                             func.m_cnt.nKeyExpected = *p;
 398                             if ( rSet.erase( *p, std::ref( func )))
 399                                 ++m_nDeleteSuccess;
 400                             else
 401                                 ++m_nDeleteFailed;
 402                         }
 403                     }
 404                 }
 405
 406                 m_nValueSuccess = func.m_cnt.nSuccessItem;
 407                 m_nValueFailed = func.m_cnt.nFailedItem;
 408             }
 409         };
 410
 411     protected:
 412
 413         template <class Set>
 414         void run_test( Set& testSet )
 415         {
 416             typedef Inserter<Set>       InserterThread;
 417             typedef Deleter<Set>        DeleterThread;
 418             typedef Updater<Set>        UpdaterThread;
 419
 420             m_pKeyArr = new size_t[ s_nSetSize ];
 421             m_pKeyFirst = m_pKeyArr;
 422             m_pKeyLast = m_pKeyFirst + s_nSetSize;
 423             for ( size_t i = 0; i < s_nSetSize; ++i )
 424                 m_pKeyArr[i] = i;
 425             shuffle( m_pKeyFirst, m_pKeyLast );
 426
 427             cds_test::thread_pool& pool = get_pool();
 428             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
 429             pool.add( new DeleterThread( pool, testSet ),  s_nDeleteThreadCount );
 430             pool.add( new UpdaterThread( pool, testSet ),  s_nUpdateThreadCount );
 431
 432             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 433                 << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
 434                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
 435                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
 436                 << std::make_pair( "set_size", s_nSetSize );
 437
 438             std::chrono::milliseconds duration = pool.run();
 439
 440             propout() << std::make_pair( "duration", duration );
 441
 442             delete [] m_pKeyArr;
 443
 444             size_t nInsertSuccess = 0;
 445             size_t nInsertFailed = 0;
 446             size_t nDeleteSuccess = 0;
 447             size_t nDeleteFailed = 0;
 448             size_t nDelValueSuccess = 0;
 449             size_t nDelValueFailed = 0;
 450             size_t nUpdateFailed = 0;
 451             size_t nUpdateCreated = 0;
 452             size_t nUpdateModified = 0;
 453             size_t nEnsFuncCreated = 0;
 454             size_t nEnsFuncModified = 0;
 455             size_t nTestFunctorRef = 0;
 456
 457             for ( size_t i = 0; i < pool.size(); ++i ) {
 458                 cds_test::thread& thr = pool.get( i );
 459                 switch ( thr.type() ) {
 460                 case insert_thread:
 461                     {
 462                         InserterThread& inserter = static_cast<InserterThread&>( thr );
 463                         nInsertSuccess  += inserter.m_nInsertSuccess;
 464                         nInsertFailed   += inserter.m_nInsertFailed;
 465                         nTestFunctorRef += inserter.m_nTestFunctorRef;
 466                     }
 467                     break;
 468                 case update_thread:
 469                     {
 470                         UpdaterThread& updater = static_cast<UpdaterThread&>(thr);
 471                         nUpdateCreated   += updater.m_nUpdateCreated;
 472                         nUpdateModified  += updater.m_nUpdateExisted;
 473                         nUpdateFailed    += updater.m_nUpdateFailed;
 474                         nEnsFuncCreated  += updater.m_nFunctorCreated;
 475                         nEnsFuncModified += updater.m_nFunctorModified;
 476                     }
 477                     break;
 478                 case delete_thread:
 479                     {
 480                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 481                         nDeleteSuccess   += deleter.m_nDeleteSuccess;
 482                         nDeleteFailed    += deleter.m_nDeleteFailed;
 483                         nDelValueSuccess += deleter.m_nValueSuccess;
 484                         nDelValueFailed  += deleter.m_nValueFailed;
 485                     }
 486                     break;
 487                 }
 488             }
 489
 490             propout()
 491                 << std::make_pair( "insert_success", nInsertSuccess )
 492                 << std::make_pair( "delete_success", nDeleteSuccess )
 493                 << std::make_pair( "insert_failed", nInsertFailed )
 494                 << std::make_pair( "delete_failed", nDeleteFailed )
 495                 << std::make_pair( "update_created", nUpdateCreated )
 496                 << std::make_pair( "update_modified", nUpdateModified )
 497                 << std::make_pair( "update_failed", nUpdateFailed )
 498                 << std::make_pair( "final_set_size", testSet.size() );
 499
 500
 501             EXPECT_EQ( nDelValueFailed, 0 );
 502             EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
 503
 504             EXPECT_EQ( nUpdateFailed, 0 );
 505             EXPECT_EQ( nUpdateCreated, nEnsFuncCreated );
 506             EXPECT_EQ( nUpdateModified, nEnsFuncModified );
 507
 508             // nTestFunctorRef is call count of insert functor
 509             EXPECT_EQ( nTestFunctorRef, nInsertSuccess );
 510
 511             testSet.clear();
 512             EXPECT_TRUE( testSet.empty() );
 513
 514             additional_check( testSet );
 515             print_stat( propout(), testSet  );
 516
 517             additional_cleanup( testSet );
 518         }
 519
 520         template <class Set>
 521         void run_test()
 522         {
 523             Set s( *this );
 524             run_test( s );
 525         }
 526     };
 527
 528     class Set_InsDel_func_LF: public Set_InsDel_func
 529         , public ::testing::WithParamInterface<size_t>
 530     {
 531     public:
 532         template <class Set>
 533         void run_test()
 534         {
 535             s_nLoadFactor = GetParam();
 536             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 537             Set_InsDel_func::run_test<Set>();
 538         }
 539
 540         static std::vector<size_t> get_load_factors();
 541     };
 542
 543 } // namespace set