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