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