test/stress/map/insdel_func/map_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 "map_type.h"
  32
  33 namespace map {
  34
  35     class Map_InsDel_func: public cds_test::stress_fixture
  36     {
  37     public:
  38         static size_t s_nMapSize;           // map 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 CuckooMap
  46         static size_t s_nCuckooProbesetSize;        // CuckooMap probeset size (only for list-based probeset)
  47         static size_t s_nCuckooProbesetThreshold;   // CuckooMap probeset threshold (o - use default)
  48
  49         static size_t s_nFeldmanMap_HeadBits;
  50         static size_t s_nFeldmanMap_ArrayBits;
  51
  52         static size_t s_nLoadFactor;  // current load factor
  53
  54         static void SetUpTestCase();
  55         static void TearDownTestCase();
  56
  57         typedef size_t  key_type;
  58         struct value_type {
  59             size_t      nKey;
  60             size_t      nData;
  61             size_t      nUpdateCall;
  62             atomics::atomic<bool>   bInitialized;
  63             cds::OS::ThreadId       threadId;   // inserter thread id
  64
  65             typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
  66             mutable lock_type   m_access;
  67
  68             value_type()
  69                 : nKey(0)
  70                 , nData(0)
  71                 , nUpdateCall(0)
  72                 , bInitialized( false )
  73                 , threadId( cds::OS::get_current_thread_id())
  74             {}
  75
  76             value_type( value_type const& s )
  77                 : nKey(s.nKey)
  78                 , nData(s.nData)
  79                 , nUpdateCall( s.nUpdateCall )
  80                 , bInitialized( s.bInitialized.load(atomics::memory_order_relaxed))
  81                 , threadId( cds::OS::get_current_thread_id())
  82             {}
  83
  84             // boost::container::flat_map requires operator =
  85             value_type& operator=( value_type const& v )
  86             {
  87                 nKey = v.nKey;
  88                 nData = v.nData;
  89                 nUpdateCall = v.nUpdateCall;
  90                 bInitialized.store(v.bInitialized.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed);
  91
  92                 return *this;
  93             }
  94         };
  95
  96         typedef std::vector<key_type>   key_array;
  97         static key_array                s_arrKeys;
  98
  99     protected:
 100         enum {
 101             insert_thread,
 102             delete_thread,
 103             update_thread
 104         };
 105
 106         template <class Map>
 107         class Inserter: public cds_test::thread
 108         {
 109             typedef cds_test::thread base_class;
 110             Map&     m_Map;
 111
 112             struct insert_functor {
 113                 size_t nTestFunctorRef;
 114
 115                 insert_functor()
 116                     : nTestFunctorRef(0)
 117                 {}
 118
 119                 template <typename Pair>
 120                 void operator()( Pair& val )
 121                 {
 122                     operator()( val.first, val.second );
 123                 }
 124
 125                 template <typename Key, typename Val >
 126                 void operator()( Key const& key, Val& v )
 127                 {
 128                     std::unique_lock< typename value_type::lock_type> ac( v.m_access );
 129
 130                     v.nKey  = key;
 131                     v.nData = key * 8;
 132
 133                     ++nTestFunctorRef;
 134                     v.bInitialized.store( true, atomics::memory_order_relaxed);
 135                 }
 136             };
 137
 138         public:
 139             size_t  m_nInsertSuccess = 0;
 140             size_t  m_nInsertFailed = 0;
 141
 142             size_t  m_nTestFunctorRef = 0;
 143
 144         public:
 145             Inserter( cds_test::thread_pool& pool, Map& map )
 146                 : base_class( pool, insert_thread )
 147                 , m_Map( map )
 148             {}
 149
 150             Inserter( Inserter& src )
 151                 : base_class( src )
 152                 , m_Map( src.m_Map )
 153             {}
 154
 155             virtual thread * clone()
 156             {
 157                 return new Inserter( *this );
 158             }
 159
 160             virtual void test()
 161             {
 162                 Map& rMap = m_Map;
 163
 164                 // func is passed by reference
 165                 insert_functor  func;
 166                 size_t const nPassCount = s_nThreadPassCount;
 167
 168                 if ( id() & 1 ) {
 169                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 170                         for ( key_array::const_iterator it = s_arrKeys.begin(), itEnd = s_arrKeys.end(); it != itEnd; ++it ) {
 171                             if ( rMap.insert_with( *it, std::ref(func)))
 172                                 ++m_nInsertSuccess;
 173                             else
 174                                 ++m_nInsertFailed;
 175                         }
 176                     }
 177                 }
 178                 else {
 179                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 180                         for ( key_array::const_reverse_iterator it = s_arrKeys.rbegin(), itEnd = s_arrKeys.rend(); it != itEnd; ++it ) {
 181                             if ( rMap.insert_with( *it, std::ref(func)))
 182                                 ++m_nInsertSuccess;
 183                             else
 184                                 ++m_nInsertFailed;
 185                         }
 186                     }
 187                 }
 188
 189                 m_nTestFunctorRef = func.nTestFunctorRef;
 190             }
 191         };
 192
 193         template <class Map>
 194         class Updater: public cds_test::thread
 195         {
 196             typedef cds_test::thread base_class;
 197             Map&     m_Map;
 198
 199             struct update_functor {
 200                 size_t  nCreated = 0;
 201                 size_t  nModified = 0;
 202
 203                 update_functor() = default;
 204
 205                 template <typename Key, typename Val>
 206                 void operator()( bool /*bNew*/, Key const& key, Val& v )
 207                 {
 208                     std::unique_lock<typename value_type::lock_type> ac( v.m_access );
 209                     if ( !v.bInitialized.load( atomics::memory_order_acquire )) {
 210                         ++nCreated;
 211                         v.nKey = key;
 212                         v.nData = key * 8;
 213                         v.bInitialized.store( true, atomics::memory_order_relaxed);
 214                     }
 215                     else {
 216                         ++v.nUpdateCall;
 217                         ++nModified;
 218                     }
 219                 }
 220
 221                 template <typename Pair>
 222                 void operator()( bool bNew, Pair& val )
 223                 {
 224                     operator()( bNew, val.first, val.second );
 225                 }
 226
 227                 // For FeldmanHashMap
 228                 template <typename Val>
 229                 void operator()( Val& cur, Val * old )
 230                 {
 231                     if ( old ) {
 232                         // If a key exists, FeldmanHashMap creates a new node too
 233                         // We should manually copy important values from old to cur
 234                         std::unique_lock<typename value_type::lock_type> ac( cur.second.m_access );
 235                         cur.second.nKey = cur.first;
 236                         cur.second.nData = cur.first * 8;
 237                         cur.second.bInitialized.store( true, atomics::memory_order_release );
 238                     }
 239                     operator()( old == nullptr, cur.first, cur.second );
 240                 }
 241
 242             private:
 243                 update_functor(const update_functor& ) = delete;
 244             };
 245
 246         public:
 247             size_t  m_nUpdateFailed = 0;
 248             size_t  m_nUpdateCreated = 0;
 249             size_t  m_nUpdateExisted = 0;
 250             size_t  m_nFunctorCreated = 0;
 251             size_t  m_nFunctorModified = 0;
 252
 253         public:
 254             Updater( cds_test::thread_pool& pool, Map& map )
 255                 : base_class( pool, update_thread )
 256                 , m_Map( map )
 257             {}
 258
 259             Updater( Updater& src )
 260                 : base_class( src )
 261                 , m_Map( src.m_Map )
 262             {}
 263
 264             virtual thread * clone()
 265             {
 266                 return new Updater( *this );
 267             }
 268
 269             virtual void test()
 270             {
 271                 Map& rMap = m_Map;
 272
 273                 update_functor func;
 274                 size_t const nPassCount = s_nThreadPassCount;
 275
 276                 if ( id() & 1 ) {
 277                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 278                         for ( key_array::const_iterator it = s_arrKeys.begin(), itEnd = s_arrKeys.end(); it != itEnd; ++it ) {
 279                             std::pair<bool, bool> ret = rMap.update( *it, std::ref( func ));
 280                             if ( ret.first  ) {
 281                                 if ( ret.second )
 282                                     ++m_nUpdateCreated;
 283                                 else
 284                                     ++m_nUpdateExisted;
 285                             }
 286                             else
 287                                 ++m_nUpdateFailed;
 288                         }
 289                     }
 290                 }
 291                 else {
 292                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 293                         for ( key_array::const_reverse_iterator it = s_arrKeys.rbegin(), itEnd = s_arrKeys.rend(); it != itEnd; ++it ) {
 294                             std::pair<bool, bool> ret = rMap.update( *it, std::ref( func ));
 295                             if ( ret.first  ) {
 296                                 if ( ret.second )
 297                                     ++m_nUpdateCreated;
 298                                 else
 299                                     ++m_nUpdateExisted;
 300                             }
 301                             else
 302                                 ++m_nUpdateFailed;
 303                         }
 304                     }
 305                 }
 306
 307                 m_nFunctorCreated = func.nCreated;
 308                 m_nFunctorModified = func.nModified;
 309             }
 310         };
 311
 312         template <class Map>
 313         class Deleter: public cds_test::thread
 314         {
 315             Map&     m_Map;
 316             typedef cds_test::thread base_class;
 317             typedef typename Map::mapped_type value_type;
 318
 319             struct value_container
 320             {
 321                 size_t      nKeyExpected;
 322
 323                 size_t      nSuccessItem;
 324                 size_t      nFailedItem;
 325
 326                 value_container()
 327                     : nSuccessItem(0)
 328                     , nFailedItem(0)
 329                 {}
 330             };
 331
 332             struct erase_functor {
 333                 value_container     m_cnt;
 334
 335                 template <typename Key, typename Val>
 336                 void operator()( Key const& /*key*/, Val& v )
 337                 {
 338                     while ( true ) {
 339                         if ( v.bInitialized.load( atomics::memory_order_relaxed )) {
 340                             std::unique_lock< typename value_type::lock_type> ac( v.m_access );
 341
 342                             if ( m_cnt.nKeyExpected == v.nKey && m_cnt.nKeyExpected * 8 == v.nData )
 343                                 ++m_cnt.nSuccessItem;
 344                             else
 345                                 ++m_cnt.nFailedItem;
 346                             v.nData++;
 347                             v.nKey = 0;
 348                             break;
 349                         }
 350                         else
 351                             cds::backoff::yield()();
 352                     }
 353                 }
 354
 355                 template <typename Pair>
 356                 void operator ()( Pair& item )
 357                 {
 358                     operator()( item.first, item.second );
 359                 }
 360             };
 361
 362         public:
 363             size_t  m_nDeleteSuccess = 0;
 364             size_t  m_nDeleteFailed = 0;
 365             size_t  m_nValueSuccess = 0;
 366             size_t  m_nValueFailed = 0;
 367
 368         public:
 369             Deleter( cds_test::thread_pool& pool, Map& map )
 370                 : base_class( pool, delete_thread )
 371                 , m_Map( map )
 372             {}
 373
 374             Deleter( Deleter& src )
 375                 : base_class( src )
 376                 , m_Map( src.m_Map )
 377             {}
 378
 379             virtual thread * clone()
 380             {
 381                 return new Deleter( *this );
 382             }
 383
 384             virtual void test()
 385             {
 386                 Map& rMap = m_Map;
 387
 388                 erase_functor   func;
 389                 size_t const nPassCount = s_nThreadPassCount;
 390
 391                 if ( id() & 1 ) {
 392                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 393                         for ( key_array::const_iterator it = s_arrKeys.cbegin(), itEnd = s_arrKeys.cend(); it != itEnd; ++it ) {
 394                             func.m_cnt.nKeyExpected = *it;
 395                             if ( rMap.erase( *it, std::ref(func)))
 396                                 ++m_nDeleteSuccess;
 397                             else
 398                                 ++m_nDeleteFailed;
 399                         }
 400                     }
 401                 }
 402                 else {
 403                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 404                         for ( key_array::const_reverse_iterator it = s_arrKeys.crbegin(), itEnd = s_arrKeys.crend(); it != itEnd; ++it ) {
 405                             func.m_cnt.nKeyExpected = *it;
 406                             if ( rMap.erase( *it, std::ref(func)))
 407                                 ++m_nDeleteSuccess;
 408                             else
 409                                 ++m_nDeleteFailed;
 410                         }
 411                     }
 412                 }
 413
 414                 m_nValueSuccess = func.m_cnt.nSuccessItem;
 415                 m_nValueFailed = func.m_cnt.nFailedItem;
 416             }
 417         };
 418
 419     protected:
 420
 421         template <class Map>
 422         void do_test( Map& testMap )
 423         {
 424             typedef Inserter<Map> inserter;
 425             typedef Deleter<Map>  deleter;
 426             typedef Updater<Map>  updater;
 427
 428             cds_test::thread_pool& pool = get_pool();
 429             pool.add( new inserter( pool, testMap ), s_nInsertThreadCount );
 430             pool.add( new deleter( pool, testMap ), s_nDeleteThreadCount );
 431             pool.add( new updater( pool, testMap ), s_nUpdateThreadCount );
 432
 433             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
 434                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
 435                 << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
 436                 << std::make_pair( "pass_count", s_nThreadPassCount )
 437                 << std::make_pair( "map_size", s_nMapSize );
 438
 439             std::chrono::milliseconds duration = pool.run();
 440
 441             propout() << std::make_pair( "duration", duration );
 442
 443             size_t nInsertSuccess = 0;
 444             size_t nInsertFailed = 0;
 445             size_t nDeleteSuccess = 0;
 446             size_t nDeleteFailed = 0;
 447             size_t nDelValueSuccess = 0;
 448             size_t nDelValueFailed = 0;
 449             size_t nUpdateFailed = 0;
 450             size_t nUpdateCreated = 0;
 451             size_t nUpdateModified = 0;
 452             size_t nEnsFuncCreated = 0;
 453             size_t nEnsFuncModified = 0;
 454             size_t nInsFuncCalled = 0;
 455
 456             for ( size_t i = 0; i < pool.size(); ++i ) {
 457                 cds_test::thread& thr = pool.get( i );
 458                 switch ( thr.type() ) {
 459                 case insert_thread:
 460                     {
 461                         inserter& t = static_cast<inserter&>( thr );
 462                         nInsertSuccess += t.m_nInsertSuccess;
 463                         nInsertFailed += t.m_nInsertFailed;
 464                         nInsFuncCalled += t.m_nTestFunctorRef;
 465                     }
 466                     break;
 467                 case delete_thread:
 468                     {
 469                         deleter& t = static_cast<deleter&>(thr);
 470                         nDeleteSuccess += t.m_nDeleteSuccess;
 471                         nDeleteFailed += t.m_nDeleteFailed;
 472                         nDelValueSuccess += t.m_nValueSuccess;
 473                         nDelValueFailed += t.m_nValueFailed;
 474                     }
 475                     break;
 476                 case update_thread:
 477                     {
 478                         updater& t = static_cast<updater&>(thr);
 479                         nUpdateCreated += t.m_nUpdateCreated;
 480                         nUpdateModified += t.m_nUpdateExisted;
 481                         nUpdateFailed += t.m_nUpdateFailed;
 482                         nEnsFuncCreated += t.m_nFunctorCreated;
 483                         nEnsFuncModified += t.m_nFunctorModified;
 484                     }
 485                     break;
 486                 default:
 487                     assert( false );
 488                 }
 489             }
 490
 491             propout()
 492                 << std::make_pair( "insert_success", nInsertSuccess )
 493                 << std::make_pair( "insert_failed",  nInsertFailed )
 494                 << std::make_pair( "delete_success", nDeleteSuccess )
 495                 << std::make_pair( "delete_failed",  nDeleteFailed )
 496                 << std::make_pair( "update_success", nUpdateCreated + nUpdateModified )
 497                 << std::make_pair( "update_failed",  nUpdateFailed )
 498                 << std::make_pair( "update_functor_create", nEnsFuncCreated )
 499                 << std::make_pair( "update_functor_modify", nEnsFuncModified )
 500                 << std::make_pair( "finish_map_size", testMap.size() );
 501
 502             EXPECT_EQ( nDelValueFailed, 0 );
 503             EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
 504             EXPECT_EQ( nUpdateFailed, 0 );
 505             EXPECT_EQ( nUpdateCreated + nUpdateModified, nEnsFuncCreated + nEnsFuncModified );
 506
 507             // nInsFuncCalled is call count of insert functor
 508             EXPECT_EQ( nInsFuncCalled, nInsertSuccess );
 509
 510             check_before_cleanup( testMap );
 511
 512             for ( size_t nItem = 0; nItem < s_nMapSize; ++nItem )
 513                 testMap.erase( nItem );
 514
 515             EXPECT_TRUE( testMap.empty());
 516
 517             additional_check( testMap );
 518             print_stat( propout(), testMap );
 519             additional_cleanup( testMap );
 520         }
 521
 522         template <class Map>
 523         void run_test()
 524         {
 525             Map testMap( *this );
 526             do_test( testMap );
 527         }
 528     };
 529
 530     class Map_InsDel_func_LF: public Map_InsDel_func
 531         , public ::testing::WithParamInterface<size_t>
 532     {
 533     public:
 534         template <class Set>
 535         void run_test()
 536         {
 537             s_nLoadFactor = GetParam();
 538             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 539             Map_InsDel_func::run_test<Set>();
 540         }
 541
 542         static std::vector<size_t> get_load_factors();
 543     };
 544
 545 } // namespace map