tests/unit/map2/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 <functional>
  32 #include <mutex>    //unique_lock
  33 #include "map2/map_type.h"
  34 #include "cppunit/thread.h"
  35
  36 #include <cds/sync/spinlock.h>
  37 #include <vector>
  38
  39 namespace map2 {
  40
  41 #define TEST_CASE(TAG, X)  void X();
  42
  43     class Map_InsDel_func: public CppUnitMini::TestCase
  44     {
  45     public:
  46         size_t c_nMapSize = 1000000;      // map size
  47         size_t c_nInsertThreadCount = 4;  // count of insertion thread
  48         size_t c_nDeleteThreadCount = 4;  // count of deletion thread
  49         size_t c_nUpdateThreadCount = 4;  // count of updating thread
  50         size_t c_nThreadPassCount   = 4;  // pass count for each thread
  51         size_t c_nMaxLoadFactor = 8;      // maximum load factor
  52         bool   c_bPrintGCState = true;
  53
  54         size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
  55         size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
  56         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  57
  58         size_t c_nFeldmanMap_HeadBits = 10;
  59         size_t c_nFeldmanMap_ArrayBits = 4;
  60
  61         size_t  c_nLoadFactor;  // current load factor
  62
  63     private:
  64         typedef size_t  key_type;
  65         struct value_type {
  66             size_t      nKey;
  67             size_t      nData;
  68             size_t      nUpdateCall;
  69             atomics::atomic<bool>   bInitialized;
  70             cds::OS::ThreadId       threadId;   // inserter thread id
  71
  72             typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
  73             mutable lock_type   m_access;
  74
  75             value_type()
  76                 : nKey(0)
  77                 , nData(0)
  78                 , nUpdateCall(0)
  79                 , bInitialized( false )
  80                 , threadId( cds::OS::get_current_thread_id())
  81             {}
  82
  83             value_type( value_type const& s )
  84                 : nKey(s.nKey)
  85                 , nData(s.nData)
  86                 , nUpdateCall( s.nUpdateCall )
  87                 , bInitialized( s.bInitialized.load(atomics::memory_order_relaxed))
  88                 , threadId( cds::OS::get_current_thread_id())
  89             {}
  90
  91             // boost::container::flat_map requires operator =
  92             value_type& operator=( value_type const& v )
  93             {
  94                 nKey = v.nKey;
  95                 nData = v.nData;
  96                 nUpdateCall = v.nUpdateCall;
  97                 bInitialized.store(v.bInitialized.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed);
  98
  99                 return *this;
 100             }
 101         };
 102
 103         typedef std::vector<key_type>   key_array;
 104         key_array                       m_arrValues;
 105
 106         template <class Map>
 107         class Inserter: public CppUnitMini::TestThread
 108         {
 109             Map&     m_Map;
 110
 111             virtual Inserter *    clone()
 112             {
 113                 return new Inserter( *this );
 114             }
 115
 116             struct insert_functor {
 117                 size_t nTestFunctorRef;
 118
 119                 insert_functor()
 120                     : nTestFunctorRef(0)
 121                 {}
 122
 123                 template <typename Pair>
 124                 void operator()( Pair& val )
 125                 {
 126                     operator()( val.first, val.second );
 127                 }
 128
 129                 template <typename Key, typename Val >
 130                 void operator()( Key const& key, Val& v )
 131                 {
 132                     std::unique_lock< typename value_type::lock_type> ac( v.m_access );
 133
 134                     v.nKey  = key;
 135                     v.nData = key * 8;
 136
 137                     ++nTestFunctorRef;
 138                     v.bInitialized.store( true, atomics::memory_order_relaxed);
 139                 }
 140             };
 141
 142         public:
 143             size_t  m_nInsertSuccess;
 144             size_t  m_nInsertFailed;
 145
 146             size_t  m_nTestFunctorRef;
 147
 148         public:
 149             Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
 150                 : CppUnitMini::TestThread( pool )
 151                 , m_Map( rMap )
 152             {}
 153             Inserter( Inserter& src )
 154                 : CppUnitMini::TestThread( src )
 155                 , m_Map( src.m_Map )
 156             {}
 157
 158             Map_InsDel_func&  getTest()
 159             {
 160                 return reinterpret_cast<Map_InsDel_func&>( m_Pool.m_Test );
 161             }
 162
 163             virtual void init() { cds::threading::Manager::attachThread()   ; }
 164             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 165
 166             virtual void test()
 167             {
 168                 Map& rMap = m_Map;
 169
 170                 m_nInsertSuccess =
 171                     m_nInsertFailed =
 172                     m_nTestFunctorRef = 0;
 173
 174                 // func is passed by reference
 175                 insert_functor  func;
 176                 key_array const& arr = getTest().m_arrValues;
 177                 size_t const nPassCount = getTest().c_nThreadPassCount;
 178
 179                 if ( m_nThreadNo & 1 ) {
 180                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 181                         for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) {
 182                             if ( rMap.insert_with( *it, std::ref(func)))
 183                                 ++m_nInsertSuccess;
 184                             else
 185                                 ++m_nInsertFailed;
 186                         }
 187                     }
 188                 }
 189                 else {
 190                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 191                         for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) {
 192                             if ( rMap.insert_with( *it, std::ref(func)))
 193                                 ++m_nInsertSuccess;
 194                             else
 195                                 ++m_nInsertFailed;
 196                         }
 197                     }
 198                 }
 199
 200                 m_nTestFunctorRef = func.nTestFunctorRef;
 201             }
 202         };
 203
 204         template <class Map>
 205         class Updater: public CppUnitMini::TestThread
 206         {
 207             Map&     m_Map;
 208
 209             virtual Updater *    clone()
 210             {
 211                 return new Updater( *this );
 212             }
 213
 214             struct update_functor {
 215                 size_t  nCreated;
 216                 size_t  nModified;
 217
 218                 update_functor()
 219                     : nCreated(0)
 220                     , nModified(0)
 221                 {}
 222
 223                 template <typename Key, typename Val>
 224                 void operator()( bool /*bNew*/, Key const& key, Val& v )
 225                 {
 226                     std::unique_lock<typename value_type::lock_type> ac( v.m_access );
 227                     if ( !v.bInitialized.load( atomics::memory_order_acquire )) {
 228                         ++nCreated;
 229                         v.nKey = key;
 230                         v.nData = key * 8;
 231                         v.bInitialized.store( true, atomics::memory_order_relaxed);
 232                     }
 233                     else {
 234                         ++v.nUpdateCall;
 235                         ++nModified;
 236                     }
 237                 }
 238
 239                 template <typename Pair>
 240                 void operator()( bool bNew, Pair& val )
 241                 {
 242                     operator()( bNew, val.first, val.second );
 243                 }
 244
 245                 // For FeldmanHashMap
 246                 template <typename Val>
 247                 void operator()( Val& cur, Val * old )
 248                 {
 249                     if ( old ) {
 250                         // If a key exists, FeldmanHashMap creates a new node too
 251                         // We should manually copy important values from old to cur
 252                         std::unique_lock<typename value_type::lock_type> ac( cur.second.m_access );
 253                         cur.second.nKey = cur.first;
 254                         cur.second.nData = cur.first * 8;
 255                         cur.second.bInitialized.store( true, atomics::memory_order_release );
 256                     }
 257                     operator()( old == nullptr, cur.first, cur.second );
 258                 }
 259
 260             private:
 261                 update_functor(const update_functor& ) = delete;
 262             };
 263
 264         public:
 265             size_t  m_nUpdateFailed;
 266             size_t  m_nUpdateCreated;
 267             size_t  m_nUpdateExisted;
 268             size_t  m_nFunctorCreated;
 269             size_t  m_nFunctorModified;
 270
 271         public:
 272             Updater( CppUnitMini::ThreadPool& pool, Map& rMap )
 273                 : CppUnitMini::TestThread( pool )
 274                 , m_Map( rMap )
 275             {}
 276             Updater( Updater& src )
 277                 : CppUnitMini::TestThread( src )
 278                 , m_Map( src.m_Map )
 279             {}
 280
 281             Map_InsDel_func&  getTest()
 282             {
 283                 return reinterpret_cast<Map_InsDel_func&>( m_Pool.m_Test );
 284             }
 285
 286             virtual void init() { cds::threading::Manager::attachThread()   ; }
 287             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 288
 289             virtual void test()
 290             {
 291                 Map& rMap = m_Map;
 292
 293                 m_nUpdateCreated =
 294                     m_nUpdateExisted =
 295                     m_nUpdateFailed = 0;
 296
 297                 update_functor func;
 298
 299                 key_array const& arr = getTest().m_arrValues;
 300                 size_t const nPassCount = getTest().c_nThreadPassCount;
 301
 302                 if ( m_nThreadNo & 1 ) {
 303                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 304                         for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) {
 305                             std::pair<bool, bool> ret = rMap.update( *it, std::ref( func ));
 306                             if ( ret.first  ) {
 307                                 if ( ret.second )
 308                                     ++m_nUpdateCreated;
 309                                 else
 310                                     ++m_nUpdateExisted;
 311                             }
 312                             else
 313                                 ++m_nUpdateFailed;
 314                         }
 315                     }
 316                 }
 317                 else {
 318                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 319                         for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) {
 320                             std::pair<bool, bool> ret = rMap.update( *it, std::ref( func ));
 321                             if ( ret.first  ) {
 322                                 if ( ret.second )
 323                                     ++m_nUpdateCreated;
 324                                 else
 325                                     ++m_nUpdateExisted;
 326                             }
 327                             else
 328                                 ++m_nUpdateFailed;
 329                         }
 330                     }
 331                 }
 332
 333                 m_nFunctorCreated = func.nCreated;
 334                 m_nFunctorModified = func.nModified;
 335             }
 336         };
 337
 338         template <class Map>
 339         class Deleter: public CppUnitMini::TestThread
 340         {
 341             Map&     m_Map;
 342             typedef typename Map::mapped_type value_type;
 343
 344             virtual Deleter *    clone()
 345             {
 346                 return new Deleter( *this );
 347             }
 348
 349             struct value_container
 350             {
 351                 size_t      nKeyExpected;
 352
 353                 size_t      nSuccessItem;
 354                 size_t      nFailedItem;
 355
 356                 value_container()
 357                     : nSuccessItem(0)
 358                     , nFailedItem(0)
 359                 {}
 360             };
 361
 362             struct erase_functor {
 363                 value_container     m_cnt;
 364
 365                 template <typename Key, typename Val>
 366                 void operator()( Key const& /*key*/, Val& v )
 367                 {
 368                     while ( true ) {
 369                         if ( v.bInitialized.load( atomics::memory_order_relaxed )) {
 370                             std::unique_lock< typename value_type::lock_type> ac( v.m_access );
 371
 372                             if ( m_cnt.nKeyExpected == v.nKey && m_cnt.nKeyExpected * 8 == v.nData )
 373                                 ++m_cnt.nSuccessItem;
 374                             else
 375                                 ++m_cnt.nFailedItem;
 376                             v.nData++;
 377                             v.nKey = 0;
 378                             break;
 379                         }
 380                         else
 381                             cds::backoff::yield()();
 382                     }
 383                 }
 384
 385                 template <typename Pair>
 386                 void operator ()( Pair& item )
 387                 {
 388                     operator()( item.first, item.second );
 389                 }
 390             };
 391
 392         public:
 393             size_t  m_nDeleteSuccess;
 394             size_t  m_nDeleteFailed;
 395
 396             size_t  m_nValueSuccess;
 397             size_t  m_nValueFailed;
 398
 399         public:
 400             Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
 401                 : CppUnitMini::TestThread( pool )
 402                 , m_Map( rMap )
 403             {}
 404             Deleter( Deleter& src )
 405                 : CppUnitMini::TestThread( src )
 406                 , m_Map( src.m_Map )
 407             {}
 408
 409             Map_InsDel_func&  getTest()
 410             {
 411                 return reinterpret_cast<Map_InsDel_func&>( m_Pool.m_Test );
 412             }
 413
 414             virtual void init() { cds::threading::Manager::attachThread()   ; }
 415             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 416
 417             virtual void test()
 418             {
 419                 Map& rMap = m_Map;
 420
 421                 m_nDeleteSuccess =
 422                     m_nDeleteFailed = 0;
 423
 424                 erase_functor   func;
 425                 key_array const& arr = getTest().m_arrValues;
 426                 size_t const nPassCount = getTest().c_nThreadPassCount;
 427
 428                 if ( m_nThreadNo & 1 ) {
 429                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 430                         for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) {
 431                             func.m_cnt.nKeyExpected = *it;
 432                             if ( rMap.erase( *it, std::ref(func)))
 433                                 ++m_nDeleteSuccess;
 434                             else
 435                                 ++m_nDeleteFailed;
 436                         }
 437                     }
 438                 }
 439                 else {
 440                     for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
 441                         for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) {
 442                             func.m_cnt.nKeyExpected = *it;
 443                             if ( rMap.erase( *it, std::ref(func)))
 444                                 ++m_nDeleteSuccess;
 445                             else
 446                                 ++m_nDeleteFailed;
 447                         }
 448                     }
 449                 }
 450
 451                 m_nValueSuccess = func.m_cnt.nSuccessItem;
 452                 m_nValueFailed = func.m_cnt.nFailedItem;
 453             }
 454         };
 455
 456     protected:
 457
 458         template <class Map>
 459         void do_test( Map& testMap )
 460         {
 461             typedef Inserter<Map>       InserterThread;
 462             typedef Deleter<Map>        DeleterThread;
 463             typedef Updater<Map>        UpdaterThread;
 464             cds::OS::Timer    timer;
 465
 466             m_arrValues.clear();
 467             m_arrValues.reserve( c_nMapSize );
 468             for ( size_t i = 0; i < c_nMapSize; ++i )
 469                 m_arrValues.push_back( i );
 470             shuffle( m_arrValues.begin(), m_arrValues.end());
 471
 472             CppUnitMini::ThreadPool pool( *this );
 473             pool.add( new InserterThread( pool, testMap ), c_nInsertThreadCount );
 474             pool.add( new DeleterThread( pool, testMap ), c_nDeleteThreadCount );
 475             pool.add( new UpdaterThread( pool, testMap ), c_nUpdateThreadCount );
 476             pool.run();
 477             CPPUNIT_MSG( "   Duration=" << pool.avgDuration());
 478
 479             size_t nInsertSuccess = 0;
 480             size_t nInsertFailed = 0;
 481             size_t nDeleteSuccess = 0;
 482             size_t nDeleteFailed = 0;
 483             size_t nDelValueSuccess = 0;
 484             size_t nDelValueFailed = 0;
 485             size_t nUpdateFailed = 0;
 486             size_t nUpdateCreated = 0;
 487             size_t nUpdateModified = 0;
 488             size_t nEnsFuncCreated = 0;
 489             size_t nEnsFuncModified = 0;
 490             size_t nInsFuncCalled = 0;
 491
 492             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 493                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 494                 if ( pThread ) {
 495                     nInsertSuccess += pThread->m_nInsertSuccess;
 496                     nInsertFailed += pThread->m_nInsertFailed;
 497                     nInsFuncCalled += pThread->m_nTestFunctorRef;
 498                 }
 499                 else {
 500                     DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
 501                     if ( p ) {
 502                         nDeleteSuccess += p->m_nDeleteSuccess;
 503                         nDeleteFailed += p->m_nDeleteFailed;
 504                         nDelValueSuccess += p->m_nValueSuccess;
 505                         nDelValueFailed += p->m_nValueFailed;
 506                     }
 507                     else {
 508                         UpdaterThread * pEns = static_cast<UpdaterThread *>( *it );
 509                         nUpdateCreated += pEns->m_nUpdateCreated;
 510                         nUpdateModified += pEns->m_nUpdateExisted;
 511                         nUpdateFailed += pEns->m_nUpdateFailed;
 512                         nEnsFuncCreated += pEns->m_nFunctorCreated;
 513                         nEnsFuncModified += pEns->m_nFunctorModified;
 514                     }
 515                 }
 516             }
 517
 518             CPPUNIT_MSG( "    Totals: Ins succ=" << nInsertSuccess
 519                 << " Del succ=" << nDeleteSuccess << "\n"
 520                 << "          : Ins fail=" << nInsertFailed
 521                 << " Del fail=" << nDeleteFailed << "\n"
 522                 << "          : Update succ=" << (nUpdateCreated + nUpdateModified) << " fail=" << nUpdateFailed
 523                 << " create=" << nUpdateCreated << " modify=" << nUpdateModified << "\n"
 524                 << "          : update functor: create=" << nEnsFuncCreated << " modify=" << nEnsFuncModified << "\n"
 525                 << "          Map size=" << testMap.size()
 526                 );
 527
 528             CPPUNIT_CHECK_EX( nDelValueFailed == 0, "Functor del failed=" << nDelValueFailed );
 529             CPPUNIT_CHECK_EX( nDelValueSuccess == nDeleteSuccess,  "Delete success=" << nDeleteSuccess << " functor=" << nDelValueSuccess );
 530
 531             CPPUNIT_CHECK( nUpdateFailed == 0 );
 532             CPPUNIT_CHECK( nUpdateCreated + nUpdateModified == nEnsFuncCreated + nEnsFuncModified );
 533
 534             // nInsFuncCalled is call count of insert functor
 535             CPPUNIT_CHECK_EX( nInsFuncCalled == nInsertSuccess, "nInsertSuccess=" << nInsertSuccess << " functor nInsFuncCalled=" << nInsFuncCalled );
 536
 537             check_before_cleanup( testMap );
 538
 539             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 540             timer.reset();
 541             for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) {
 542                 testMap.erase( nItem );
 543             }
 544             CPPUNIT_MSG( "   Duration=" << timer.duration());
 545             CPPUNIT_CHECK( testMap.empty());
 546
 547             additional_check( testMap );
 548             print_stat( testMap );
 549             additional_cleanup( testMap );
 550         }
 551
 552         template <class Map>
 553         void run_test()
 554         {
 555             CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
 556                 << " delete=" << c_nDeleteThreadCount
 557                 << " update=" << c_nUpdateThreadCount
 558                 << " pass count=" << c_nThreadPassCount
 559                 << " map size=" << c_nMapSize
 560                 );
 561
 562             if ( Map::c_bLoadFactorDepended ) {
 563                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 564                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 565                     Map  testMap( *this );
 566                     do_test( testMap );
 567                     if ( c_bPrintGCState )
 568                         print_gc_state();
 569                 }
 570             }
 571             else {
 572                 Map testMap( *this );
 573                 do_test( testMap );
 574                 if ( c_bPrintGCState )
 575                     print_gc_state();
 576             }
 577         }
 578
 579         void setUpParams( const CppUnitMini::TestCfg& cfg );
 580
 581 #   include "map2/map_defs.h"
 582         CDSUNIT_DECLARE_MichaelMap
 583         CDSUNIT_DECLARE_SplitList
 584         CDSUNIT_DECLARE_SkipListMap
 585         CDSUNIT_DECLARE_EllenBinTreeMap
 586         CDSUNIT_DECLARE_BronsonAVLTreeMap
 587         CDSUNIT_DECLARE_FeldmanHashMap_fixed
 588         CDSUNIT_DECLARE_FeldmanHashMap_city
 589         CDSUNIT_DECLARE_StripedMap
 590         CDSUNIT_DECLARE_RefinableMap
 591         CDSUNIT_DECLARE_CuckooMap
 592
 593         CPPUNIT_TEST_SUITE(Map_InsDel_func)
 594             CDSUNIT_TEST_MichaelMap
 595             CDSUNIT_TEST_SplitList
 596             CDSUNIT_TEST_SkipListMap
 597             CDSUNIT_TEST_EllenBinTreeMap
 598             CDSUNIT_TEST_BronsonAVLTreeMap
 599             CDSUNIT_TEST_FeldmanHashMap_fixed
 600             CDSUNIT_TEST_FeldmanHashMap_city
 601             CDSUNIT_TEST_CuckooMap
 602             CDSUNIT_TEST_StripedMap
 603             CDSUNIT_TEST_RefinableMap
 604         CPPUNIT_TEST_SUITE_END();
 605
 606     };
 607 } // namespace map2