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
 140             size_t  m_nTestFunctorRef = 0;
 141
 142         public:
 143             Inserter( cds_test::thread_pool& pool, Set& set )
 144                 : base_class( pool, insert_thread )
 145                 , m_Set( set )
 146             {}
 147
 148             Inserter( Inserter& src )
 149                 : base_class( src )
 150                 , m_Set( src.m_Set )
 151             {}
 152
 153             virtual thread * clone()
 154             {
 155                 return new Inserter( *this );
 156             }
 157
 158             virtual void test()
 159             {
 160                 Set& rSet = m_Set;
 161                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 162
 163                 size_t * pKeyFirst      = fixture.m_pKeyFirst;
 164                 size_t * pKeyLast       = fixture.m_pKeyLast;
 165                 size_t const nPassCount = fixture.s_nThreadPassCount;
 166
 167                 // func is passed by reference
 168                 insert_functor  func;
 169
 170                 if ( id() & 1 ) {
 171                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 172                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 173                             if ( rSet.insert( *p, std::ref( func )))
 174                                 ++m_nInsertSuccess;
 175                             else
 176                                 ++m_nInsertFailed;
 177                         }
 178                     }
 179                 }
 180                 else {
 181                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 182                         for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
 183                             if ( rSet.insert( *p, std::ref( func )))
 184                                 ++m_nInsertSuccess;
 185                             else
 186                                 ++m_nInsertFailed;
 187                         }
 188                     }
 189                 }
 190
 191                 m_nTestFunctorRef = func.nTestFunctorRef;
 192             }
 193         };
 194
 195         template <class Set>
 196         class Updater: public cds_test::thread
 197         {
 198             typedef cds_test::thread base_class;
 199
 200             Set&     m_Set;
 201             typedef typename Set::value_type keyval_type;
 202
 203             struct update_functor {
 204                 size_t  nCreated = 0;
 205                 size_t  nModified = 0;
 206
 207                 update_functor() {}
 208                 update_functor( const update_functor& ) = delete;
 209
 210                 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
 211                 {
 212                     std::unique_lock<typename value::lock_type> ac( val.val.m_access );
 213                     if ( !val.val.bInitialized )
 214                     {
 215                         val.val.nKey = val.key;
 216                         val.val.nData = val.key * 8;
 217                         val.val.bInitialized = true;
 218                     }
 219
 220                     if ( bNew ) {
 221                         ++nCreated;
 222                     }
 223                     else {
 224                         val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
 225                         ++nModified;
 226                     }
 227                 }
 228
 229                 void operator()( keyval_type& cur, keyval_type * old )
 230                 {
 231                     operator()( old == nullptr, cur, 0 );
 232                 }
 233             };
 234
 235         public:
 236             size_t  m_nUpdateFailed = 0;
 237             size_t  m_nUpdateCreated = 0;
 238             size_t  m_nUpdateExisted = 0;
 239             size_t  m_nFunctorCreated = 0;
 240             size_t  m_nFunctorModified = 0;
 241
 242         public:
 243             Updater( cds_test::thread_pool& pool, Set& set )
 244                 : base_class( pool, update_thread )
 245                 , m_Set( set )
 246             {}
 247
 248             Updater( Updater& src )
 249                 : base_class( src )
 250                 , m_Set( src.m_Set )
 251             {}
 252
 253             virtual thread * clone()
 254             {
 255                 return new Updater( *this );
 256             }
 257
 258             virtual void test()
 259             {
 260                 Set& rSet = m_Set;
 261
 262                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 263                 size_t * pKeyFirst = fixture.m_pKeyFirst;
 264                 size_t * pKeyLast = fixture.m_pKeyLast;
 265                 size_t const nPassCount = fixture.s_nThreadPassCount;
 266
 267                 update_functor func;
 268
 269                 if ( id() & 1 ) {
 270                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 271                         for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
 272                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 273                             if ( ret.first  ) {
 274                                 if ( ret.second )
 275                                     ++m_nUpdateCreated;
 276                                 else
 277                                     ++m_nUpdateExisted;
 278                             }
 279                             else
 280                                 ++m_nUpdateFailed;
 281                         }
 282                     }
 283                 }
 284                 else {
 285                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 286                         for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
 287                             std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
 288                             if ( ret.first  ) {
 289                                 if ( ret.second )
 290                                     ++m_nUpdateCreated;
 291                                 else
 292                                     ++m_nUpdateExisted;
 293                             }
 294                             else
 295                                 ++m_nUpdateFailed;
 296                         }
 297                     }
 298                 }
 299
 300                 m_nFunctorCreated = func.nCreated;
 301                 m_nFunctorModified = func.nModified;
 302             }
 303         };
 304
 305         template <class Set>
 306         class Deleter: public cds_test::thread
 307         {
 308             typedef cds_test::thread base_class;
 309
 310             Set&     m_Set;
 311             typedef typename Set::value_type keyval_type;
 312
 313             struct value_container
 314             {
 315                 size_t      nKeyExpected;
 316
 317                 size_t      nSuccessItem = 0;
 318                 size_t      nFailedItem = 0;
 319             };
 320
 321             struct erase_functor {
 322                 value_container     m_cnt;
 323
 324                 void operator ()( keyval_type const& itm )
 325                 {
 326                     keyval_type& item = const_cast<keyval_type&>(itm);
 327                     while ( true ) {
 328                         bool bBkoff = false;
 329                         {
 330                             std::unique_lock< typename value::lock_type> ac( item.val.m_access );
 331                             if ( item.val.bInitialized ) {
 332                                 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
 333                                     ++m_cnt.nSuccessItem;
 334                                 else
 335                                     ++m_cnt.nFailedItem;
 336                                 item.val.nData++;
 337                                 item.val.nKey = 0;
 338                                 break;
 339                             }
 340                             else
 341                                 bBkoff = true;
 342                         }
 343                         if ( bBkoff )
 344                             cds::backoff::yield()();
 345                     }
 346                 }
 347             };
 348
 349         public:
 350             size_t  m_nDeleteSuccess = 0;
 351             size_t  m_nDeleteFailed = 0;
 352
 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