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