test/stress/sequential/sequential-set/insdel_string/set_insdel_string.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-2017
   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 #define TEST_CASE(TAG, X)  void X();
  36
  37     class Set_InsDel_string: public cds_test::stress_fixture
  38     {
  39     public:
  40         static size_t s_nSetSize;               // set size
  41         static size_t s_nInsertThreadCount;     // count of insertion thread
  42         static size_t s_nDeleteThreadCount;     // count of deletion thread
  43         static size_t s_nThreadPassCount;       // pass count for each thread
  44         static size_t s_nMaxLoadFactor;         // maximum load factor
  45
  46         static size_t s_nCuckooInitialSize;     // initial size for CuckooSet
  47         static size_t s_nCuckooProbesetSize;    // CuckooSet probeset size (only for list-based probeset)
  48         static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
  49
  50         static size_t s_nFeldmanSet_HeadBits;
  51         static size_t s_nFeldmanSet_ArrayBits;
  52
  53         static size_t s_nLoadFactor;
  54         static std::vector<std::string>  m_arrString;
  55
  56         static void SetUpTestCase();
  57         static void TearDownTestCase();
  58
  59     private:
  60         typedef std::string key_type;
  61         typedef size_t      value_type;
  62
  63         enum {
  64             insert_thread,
  65             delete_thread,
  66             extract_thread
  67         };
  68
  69         template <class Set>
  70         class Inserter: public cds_test::thread
  71         {
  72             typedef cds_test::thread base_class;
  73
  74             Set&     m_Set;
  75             typedef typename Set::value_type    keyval_type;
  76
  77         public:
  78             size_t  m_nInsertSuccess = 0;
  79             size_t  m_nInsertFailed = 0;
  80
  81         public:
  82             Inserter( cds_test::thread_pool& pool, Set& set )
  83                 : base_class( pool, insert_thread )
  84                 , m_Set( set )
  85             {}
  86
  87             Inserter( Inserter& src )
  88                 : base_class( src )
  89                 , m_Set( src.m_Set )
  90             {}
  91
  92             virtual thread * clone()
  93             {
  94                 return new Inserter( *this );
  95             }
  96
  97             virtual void test()
  98             {
  99                 Set& rSet = m_Set;
 100
 101                 Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
 102                 size_t nArrSize = m_arrString.size();
 103                 size_t const nSetSize = fixture.s_nSetSize;
 104                 size_t const nPassCount = fixture.s_nThreadPassCount;
 105
 106                 if ( id() & 1 ) {
 107                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 108                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 109                             if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
 110                                 ++m_nInsertSuccess;
 111                             else
 112                                 ++m_nInsertFailed;
 113                         }
 114                     }
 115                 }
 116                 else {
 117                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 118                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 119                             if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
 120                                 ++m_nInsertSuccess;
 121                             else
 122                                 ++m_nInsertFailed;
 123                         }
 124                     }
 125                 }
 126             }
 127         };
 128
 129         template <class Set>
 130         class Deleter: public cds_test::thread
 131         {
 132             typedef cds_test::thread base_class;
 133
 134             Set&     m_Set;
 135         public:
 136             size_t  m_nDeleteSuccess = 0;
 137             size_t  m_nDeleteFailed = 0;
 138
 139         public:
 140             Deleter( cds_test::thread_pool& pool, Set& set )
 141                 : base_class( pool, delete_thread )
 142                 , m_Set( set )
 143             {}
 144
 145             Deleter( Deleter& src )
 146                 : base_class( src )
 147                 , m_Set( src.m_Set )
 148             {}
 149
 150             virtual thread * clone()
 151             {
 152                 return new Deleter( *this );
 153             }
 154
 155             virtual void test()
 156             {
 157                 Set& rSet = m_Set;
 158
 159                 Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
 160                 size_t nArrSize = m_arrString.size();
 161                 size_t const nSetSize = fixture.s_nSetSize;
 162                 size_t const nPassCount = fixture.s_nThreadPassCount;
 163
 164                 if ( id() & 1 ) {
 165                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 166                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 167                             if ( rSet.erase( m_arrString[nItem % nArrSize] ))
 168                                 ++m_nDeleteSuccess;
 169                             else
 170                                 ++m_nDeleteFailed;
 171                         }
 172                     }
 173                 }
 174                 else {
 175                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 176                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 177                             if ( rSet.erase( m_arrString[nItem % nArrSize] ))
 178                                 ++m_nDeleteSuccess;
 179                             else
 180                                 ++m_nDeleteFailed;
 181                         }
 182                     }
 183                 }
 184             }
 185         };
 186
 187         template <typename GC, class Set>
 188         class Extractor: public cds_test::thread
 189         {
 190             typedef cds_test::thread base_class;
 191             Set&     m_Set;
 192
 193         public:
 194             size_t  m_nDeleteSuccess = 0;
 195             size_t  m_nDeleteFailed = 0;
 196
 197         public:
 198             Extractor( cds_test::thread_pool& pool, Set& set )
 199                 : base_class( pool, extract_thread )
 200                 , m_Set( set )
 201             {}
 202
 203             Extractor( Extractor& src )
 204                 : base_class( src )
 205                 , m_Set( src.m_Set )
 206             {}
 207
 208             virtual thread * clone()
 209             {
 210                 return new Extractor( *this );
 211             }
 212
 213             virtual void test()
 214             {
 215                 Set& rSet = m_Set;
 216
 217                 typename Set::guarded_ptr gp;
 218
 219                 Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
 220                 size_t nArrSize = m_arrString.size();
 221                 size_t const nSetSize = fixture.s_nSetSize;
 222                 size_t const nPassCount = fixture.s_nThreadPassCount;
 223
 224                 if ( id() & 1 ) {
 225                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 226                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 227                             gp = rSet.extract( m_arrString[nItem % nArrSize] );
 228                             if ( gp )
 229                                 ++m_nDeleteSuccess;
 230                             else
 231                                 ++m_nDeleteFailed;
 232                             gp.release();
 233                         }
 234                     }
 235                 }
 236                 else {
 237                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 238                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 239                             gp = rSet.extract( m_arrString[nItem % nArrSize] );
 240                             if ( gp )
 241                                 ++m_nDeleteSuccess;
 242                             else
 243                                 ++m_nDeleteFailed;
 244                             gp.release();
 245                         }
 246                     }
 247                 }
 248             }
 249         };
 250
 251         template <typename RCU, class Set>
 252         class Extractor<cds::urcu::gc<RCU>, Set >: public cds_test::thread
 253         {
 254             typedef cds_test::thread base_class;
 255             Set&     m_Set;
 256
 257         public:
 258             size_t  m_nDeleteSuccess = 0;
 259             size_t  m_nDeleteFailed = 0;
 260
 261         public:
 262             Extractor( cds_test::thread_pool& pool, Set& set )
 263                 : base_class( pool, extract_thread )
 264                 , m_Set( set )
 265             {}
 266
 267             Extractor( Extractor& src )
 268                 : base_class( src )
 269                 , m_Set( src.m_Set )
 270             {}
 271
 272             virtual thread * clone()
 273             {
 274                 return new Extractor( *this );
 275             }
 276
 277             virtual void test()
 278             {
 279                 Set& rSet = m_Set;
 280
 281                 typename Set::exempt_ptr xp;
 282
 283                 Set_InsDel_string& fixture = pool().template fixture<Set_InsDel_string>();
 284                 size_t nArrSize = m_arrString.size();
 285                 size_t const nSetSize = fixture.s_nSetSize;
 286                 size_t const nPassCount = fixture.s_nThreadPassCount;
 287
 288                 if ( id() & 1 ) {
 289                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 290                         for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
 291                             if ( Set::c_bExtractLockExternal ) {
 292                                 typename Set::rcu_lock l;
 293                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 294                                 if ( xp )
 295                                     ++m_nDeleteSuccess;
 296                                 else
 297                                     ++m_nDeleteFailed;
 298                             }
 299                             else {
 300                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 301                                 if ( xp )
 302                                     ++m_nDeleteSuccess;
 303                                 else
 304                                     ++m_nDeleteFailed;
 305                             }
 306                             xp.release();
 307                         }
 308                     }
 309                 }
 310                 else {
 311                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 312                         for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
 313                             if ( Set::c_bExtractLockExternal ) {
 314                                 typename Set::rcu_lock l;
 315                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 316                                 if ( xp )
 317                                     ++m_nDeleteSuccess;
 318                                 else
 319                                     ++m_nDeleteFailed;
 320                             }
 321                             else {
 322                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 323                                 if ( xp )
 324                                     ++m_nDeleteSuccess;
 325                                 else
 326                                     ++m_nDeleteFailed;
 327                             }
 328                             xp.release();
 329                         }
 330                     }
 331                 }
 332             }
 333         };
 334
 335     protected:
 336         template <class Set>
 337         void do_test( Set& testSet )
 338         {
 339             typedef Inserter<Set> InserterThread;
 340             typedef Deleter<Set>  DeleterThread;
 341
 342             cds_test::thread_pool& pool = get_pool();
 343             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
 344             pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
 345
 346             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 347                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
 348                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
 349                 << std::make_pair( "set_size", s_nSetSize );
 350
 351             std::chrono::milliseconds duration = pool.run();
 352
 353             propout() << std::make_pair( "duration", duration );
 354
 355             size_t nInsertSuccess = 0;
 356             size_t nInsertFailed = 0;
 357             size_t nDeleteSuccess = 0;
 358             size_t nDeleteFailed = 0;
 359             for ( size_t i = 0; i < pool.size(); ++i ) {
 360                 cds_test::thread& thr = pool.get( i );
 361                 switch ( thr.type()) {
 362                 case insert_thread:
 363                     {
 364                         InserterThread& inserter = static_cast<InserterThread&>( thr );
 365                         nInsertSuccess += inserter.m_nInsertSuccess;
 366                         nInsertFailed += inserter.m_nInsertFailed;
 367                     }
 368                     break;
 369                 case delete_thread:
 370                     {
 371                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 372                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 373                         nDeleteFailed += deleter.m_nDeleteFailed;
 374                 }
 375                     break;
 376                 default:
 377                     assert( false ); // Forgot anything?..
 378                 }
 379             }
 380
 381             propout()
 382                 << std::make_pair( "insert_success", nInsertSuccess )
 383                 << std::make_pair( "delete_success", nDeleteSuccess )
 384                 << std::make_pair( "insert_failed", nInsertFailed )
 385                 << std::make_pair( "delete_failed", nDeleteFailed )
 386                 << std::make_pair( "final_set_size", testSet.size());
 387
 388             //testSet.clear();
 389             for (auto const& str: m_arrString )
 390                 testSet.erase( str );
 391             EXPECT_TRUE( testSet.empty());
 392             EXPECT_EQ( testSet.size(), 0u );
 393
 394             additional_check( testSet );
 395             print_stat( propout(), testSet );
 396             additional_cleanup( testSet );
 397         }
 398
 399         template <class Set>
 400         void do_test_extract( Set& testSet )
 401         {
 402             typedef Inserter<Set> InserterThread;
 403             typedef Deleter<Set>  DeleterThread;
 404             typedef Extractor<typename Set::gc, Set> ExtractThread;
 405
 406             size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
 407             size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
 408
 409             cds_test::thread_pool& pool = get_pool();
 410             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
 411             pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
 412             pool.add( new ExtractThread( pool, testSet ), nExtractThreadCount );
 413
 414             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 415                 << std::make_pair( "delete_thread_count", nDelThreadCount )
 416                 << std::make_pair( "extract_thread_count", nExtractThreadCount )
 417                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
 418                 << std::make_pair( "set_size", s_nSetSize );
 419
 420             std::chrono::milliseconds duration = pool.run();
 421
 422             propout() << std::make_pair( "duration", duration );
 423
 424             size_t nInsertSuccess = 0;
 425             size_t nInsertFailed = 0;
 426             size_t nDeleteSuccess = 0;
 427             size_t nDeleteFailed = 0;
 428             size_t nExtractSuccess = 0;
 429             size_t nExtractFailed = 0;
 430             for ( size_t i = 0; i < pool.size(); ++i ) {
 431                 cds_test::thread& thr = pool.get( i );
 432                 switch ( thr.type()) {
 433                 case insert_thread:
 434                     {
 435                         InserterThread& inserter = static_cast<InserterThread&>(thr);
 436                         nInsertSuccess += inserter.m_nInsertSuccess;
 437                         nInsertFailed += inserter.m_nInsertFailed;
 438                     }
 439                     break;
 440                 case delete_thread:
 441                     {
 442                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 443                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 444                         nDeleteFailed += deleter.m_nDeleteFailed;
 445                     }
 446                     break;
 447                 case extract_thread:
 448                     {
 449                         ExtractThread& extractor = static_cast<ExtractThread&>(thr);
 450                         nExtractSuccess += extractor.m_nDeleteSuccess;
 451                         nExtractFailed += extractor.m_nDeleteFailed;
 452                     }
 453                     break;
 454                 default:
 455                     assert( false ); // Forgot anything?..
 456                 }
 457             }
 458
 459             propout()
 460                 << std::make_pair( "insert_success", nInsertSuccess )
 461                 << std::make_pair( "delete_success", nDeleteSuccess )
 462                 << std::make_pair( "extract_success", nExtractSuccess )
 463                 << std::make_pair( "insert_failed",  nInsertFailed )
 464                 << std::make_pair( "delete_failed",  nDeleteFailed )
 465                 << std::make_pair( "extract_failed", nExtractFailed )
 466                 << std::make_pair( "final_set_size", testSet.size());
 467
 468             //testSet.clear();
 469             for ( auto const& str : m_arrString )
 470                 testSet.erase( str );
 471             EXPECT_TRUE( testSet.empty());
 472             EXPECT_EQ( testSet.size(), 0u );
 473
 474             additional_check( testSet );
 475             print_stat( propout(), testSet );
 476             additional_cleanup( testSet );
 477         }
 478
 479         template <class Set>
 480         void run_test()
 481         {
 482             ASSERT_TRUE( m_arrString.size() > 0 );
 483
 484             Set s( *this );
 485             do_test( s );
 486         }
 487
 488         template <class Set>
 489         void run_test_extract()
 490         {
 491             ASSERT_TRUE( m_arrString.size() > 0 );
 492
 493             Set s( *this );
 494             do_test_extract( s );
 495         }
 496     };
 497
 498     class Set_InsDel_string_LF: public Set_InsDel_string
 499         , public ::testing::WithParamInterface<size_t>
 500     {
 501     public:
 502         template <class Set>
 503         void run_test()
 504         {
 505             s_nLoadFactor = GetParam();
 506             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 507             Set_InsDel_string::run_test<Set>();
 508         }
 509
 510         template <class Set>
 511         void run_test_extract()
 512         {
 513             s_nLoadFactor = GetParam();
 514             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 515             Set_InsDel_string::run_test_extract<Set>();
 516         }
 517
 518         static std::vector<size_t> get_load_factors();
 519     };
 520
 521 } // namespace set