test/stress/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-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 #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             EXPECT_TRUE( testSet.empty() );
 390
 391             additional_check( testSet );
 392             print_stat( propout(), testSet );
 393             additional_cleanup( testSet );
 394         }
 395
 396         template <class Set>
 397         void do_test_extract( Set& testSet )
 398         {
 399             typedef Inserter<Set> InserterThread;
 400             typedef Deleter<Set>  DeleterThread;
 401             typedef Extractor<typename Set::gc, Set> ExtractThread;
 402
 403             size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
 404             size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
 405
 406             cds_test::thread_pool& pool = get_pool();
 407             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
 408             pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
 409             pool.add( new ExtractThread( pool, testSet ), nExtractThreadCount );
 410
 411             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 412                 << std::make_pair( "delete_thread_count", nDelThreadCount )
 413                 << std::make_pair( "extract_thread_count", nExtractThreadCount )
 414                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
 415                 << std::make_pair( "set_size", s_nSetSize );
 416
 417             std::chrono::milliseconds duration = pool.run();
 418
 419             propout() << std::make_pair( "duration", duration );
 420
 421             size_t nInsertSuccess = 0;
 422             size_t nInsertFailed = 0;
 423             size_t nDeleteSuccess = 0;
 424             size_t nDeleteFailed = 0;
 425             size_t nExtractSuccess = 0;
 426             size_t nExtractFailed = 0;
 427             for ( size_t i = 0; i < pool.size(); ++i ) {
 428                 cds_test::thread& thr = pool.get( i );
 429                 switch ( thr.type() ) {
 430                 case insert_thread:
 431                     {
 432                         InserterThread& inserter = static_cast<InserterThread&>(thr);
 433                         nInsertSuccess += inserter.m_nInsertSuccess;
 434                         nInsertFailed += inserter.m_nInsertFailed;
 435                     }
 436                     break;
 437                 case delete_thread:
 438                     {
 439                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 440                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 441                         nDeleteFailed += deleter.m_nDeleteFailed;
 442                     }
 443                     break;
 444                 case extract_thread:
 445                     {
 446                         ExtractThread& extractor = static_cast<ExtractThread&>(thr);
 447                         nExtractSuccess += extractor.m_nDeleteSuccess;
 448                         nExtractFailed += extractor.m_nDeleteFailed;
 449                     }
 450                     break;
 451                 default:
 452                     assert( false ); // Forgot anything?..
 453                 }
 454             }
 455
 456             propout()
 457                 << std::make_pair( "insert_success", nInsertSuccess )
 458                 << std::make_pair( "delete_success", nDeleteSuccess )
 459                 << std::make_pair( "extract_success", nExtractSuccess )
 460                 << std::make_pair( "insert_failed",  nInsertFailed )
 461                 << std::make_pair( "delete_failed",  nDeleteFailed )
 462                 << std::make_pair( "extract_failed", nExtractFailed )
 463                 << std::make_pair( "final_set_size", testSet.size() );
 464
 465             testSet.clear();
 466             EXPECT_TRUE( testSet.empty() );
 467
 468             additional_check( testSet );
 469             print_stat( propout(), testSet );
 470             additional_cleanup( testSet );
 471         }
 472
 473         template <class Set>
 474         void run_test()
 475         {
 476             ASSERT_TRUE( m_arrString.size() > 0 );
 477
 478             Set s( *this );
 479             do_test( s );
 480         }
 481
 482         template <class Set>
 483         void run_test_extract()
 484         {
 485             ASSERT_TRUE( m_arrString.size() > 0 );
 486
 487             Set s( *this );
 488             do_test_extract( s );
 489         }
 490     };
 491
 492     class Set_InsDel_string_LF: public Set_InsDel_string
 493         , public ::testing::WithParamInterface<size_t>
 494     {
 495     public:
 496         template <class Set>
 497         void run_test()
 498         {
 499             s_nLoadFactor = GetParam();
 500             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 501             Set_InsDel_string::run_test<Set>();
 502         }
 503
 504         template <class Set>
 505         void run_test_extract()
 506         {
 507             s_nLoadFactor = GetParam();
 508             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 509             Set_InsDel_string::run_test_extract<Set>();
 510         }
 511
 512         static std::vector<size_t> get_load_factors();
 513     };
 514
 515 } // namespace set