test/stress/map/insdelfind/map_insdelfind.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 "map_type.h"
  32
  33 namespace map {
  34
  35
  36     class Map_InsDelFind: public cds_test::stress_fixture
  37     {
  38     public:
  39         static size_t s_nMapSize;           // initial map size
  40         static size_t s_nThreadCount;       // thread count
  41         static size_t s_nPassCount;         // pass count
  42
  43         static size_t s_nBronsonAVLTreeMapPassCount;
  44
  45         static size_t s_nHpEllenBinTreeMapPassCount;
  46         static size_t s_nHpFeldmanPassCount;
  47         static size_t s_nHpMichaelMapPassCount;
  48         static size_t s_nHpMichaelIterableMapPassCount;
  49         static size_t s_nHpSkipListMapPassCount;
  50         static size_t s_nHpSplitListMapPassCount;
  51         static size_t s_nHpSplitListIterableMapPassCount;
  52
  53         static size_t s_nRcuEllenBinTreeMapPassCount;
  54         static size_t s_nRcuFeldmanPassCount;
  55         static size_t s_nRcuMichaelMapPassCount;
  56         static size_t s_nRcuSkipListMapPassCount;
  57         static size_t s_nRcuSplitListMapPassCount;
  58
  59         static size_t s_nMaxLoadFactor;     // maximum load factor
  60         static unsigned int s_nInsertPercentage;
  61         static unsigned int s_nDeletePercentage;
  62         static unsigned int s_nDuration;    // test duration, seconds
  63
  64         static size_t s_nCuckooInitialSize;         // initial size for CuckooMap
  65         static size_t s_nCuckooProbesetSize;        // CuckooMap probeset size (only for list-based probeset)
  66         static size_t s_nCuckooProbesetThreshold;   // CuckooMap probeset threshold (o - use default)
  67
  68         static size_t s_nFeldmanMap_HeadBits;
  69         static size_t s_nFeldmanMap_ArrayBits;
  70
  71         static size_t  s_nLoadFactor;  // current load factor
  72
  73         static void SetUpTestCase();
  74         //static void TearDownTestCase();
  75
  76     public:
  77         enum actions
  78         {
  79             do_find,
  80             do_insert,
  81             do_delete
  82         };
  83         static const unsigned int c_nShuffleSize = 100;
  84         static actions s_arrShuffle[c_nShuffleSize];
  85
  86     protected:
  87         typedef size_t  key_type;
  88         typedef size_t  value_type;
  89
  90         template <class Map>
  91         class Worker: public cds_test::thread
  92         {
  93             typedef cds_test::thread base_class;
  94             Map&     m_Map;
  95
  96         public:
  97             size_t  m_nInsertSuccess = 0;
  98             size_t  m_nInsertFailed = 0;
  99             size_t  m_nDeleteSuccess = 0;
 100             size_t  m_nDeleteFailed = 0;
 101             size_t  m_nFindSuccess = 0;
 102             size_t  m_nFindFailed = 0;
 103
 104         public:
 105             Worker( cds_test::thread_pool& pool, Map& map )
 106                 : base_class( pool )
 107                 , m_Map( map )
 108             {}
 109
 110             Worker( Worker& src )
 111                 : base_class( src )
 112                 , m_Map( src.m_Map )
 113             {}
 114
 115             virtual thread * clone()
 116             {
 117                 return new Worker( *this );
 118             }
 119
 120             typedef std::pair< key_type const, value_type > map_value_type;
 121
 122             struct update_functor {
 123                 template <typename Q>
 124                 void operator()( bool /*bNew*/, map_value_type& /*cur*/, Q const& /*val*/ ) const
 125                 {}
 126
 127                 // FeldmanHashMap
 128                 void operator()( map_value_type& /*cur*/, map_value_type* /*old*/) const
 129                 {}
 130
 131                 // MichaelMap
 132                 void operator()( bool /*bNew*/, map_value_type& /*cur*/ ) const
 133                 {}
 134
 135                 // BronsonAVLTreeMap
 136                 void operator()( bool /*bNew*/, key_type /*key*/, value_type& /*val*/ ) const
 137                 {}
 138             };
 139
 140             virtual void test()
 141             {
 142                 Map& rMap = m_Map;
 143
 144                 unsigned int i = 0;
 145                 size_t const nNormalize = size_t(-1) / ( s_nMapSize * 2 );
 146
 147                 size_t nRand = 0;
 148                 for (size_t pCount = 0; pCount < s_nPassCount; pCount++) {
 149                     nRand = cds::bitop::RandXorShift( nRand );
 150                     size_t key = nRand / nNormalize;
 151                     nRand = cds::bitop::RandXorShift( nRand );
 152                     size_t value = nRand / nNormalize;
 153                     switch ( s_arrShuffle[i] ) {
 154                     case do_find:
 155                         if ( rMap.contains( key ))
 156                             ++m_nFindSuccess;
 157                         else
 158                             ++m_nFindFailed;
 159                         break;
 160                     case do_insert:
 161                         if ( key % 2 ) {
 162                             if ( rMap.insert( key, value ))
 163                                 ++m_nInsertSuccess;
 164                             else
 165                                 ++m_nInsertFailed;
 166                         }
 167                         else {
 168                             if ( rMap.update( key, update_functor(), true ).first )
 169                                 ++m_nInsertSuccess;
 170                             else
 171                                 ++m_nInsertFailed;
 172                         }
 173                         break;
 174                     case do_delete:
 175                         if ( rMap.erase( key ))
 176                             ++m_nDeleteSuccess;
 177                         else
 178                             ++m_nDeleteFailed;
 179                         break;
 180                     }
 181
 182                     if ( ++i >= c_nShuffleSize )
 183                         i = 0;
 184                 }
 185             }
 186         };
 187
 188     protected:
 189         template <class Map>
 190         void do_test( Map& testMap )
 191         {
 192             typedef Worker<Map> worker;
 193             cds_test::thread_pool& pool = get_pool();
 194             pool.add( new worker( pool, testMap ), s_nThreadCount );
 195
 196             std::chrono::milliseconds duration = pool.run();
 197
 198             size_t nInsertSuccess = 0;
 199             size_t nInsertFailed = 0;
 200             size_t nDeleteSuccess = 0;
 201             size_t nDeleteFailed = 0;
 202             size_t nFindSuccess = 0;
 203             size_t nFindFailed = 0;
 204             for ( size_t i = 0; i < pool.size(); ++i ) {
 205                 worker& thr = static_cast<worker&>( pool.get( i ));
 206
 207                 nInsertSuccess += thr.m_nInsertSuccess;
 208                 nInsertFailed += thr.m_nInsertFailed;
 209                 nDeleteSuccess += thr.m_nDeleteSuccess;
 210                 nDeleteFailed += thr.m_nDeleteFailed;
 211                 nFindSuccess += thr.m_nFindSuccess;
 212                 nFindFailed += thr.m_nFindFailed;
 213             }
 214
 215             propout()
 216                 << std::make_pair( "insert_success", nInsertSuccess )
 217                 << std::make_pair( "insert_failed", nInsertFailed )
 218                 << std::make_pair( "delete_success", nDeleteSuccess )
 219                 << std::make_pair( "delete_failed", nDeleteFailed )
 220                 << std::make_pair( "find_success", nFindSuccess )
 221                 << std::make_pair( "find_failed", nFindFailed )
 222                 << std::make_pair( "finish_map_size", testMap.size());
 223
 224             {
 225                 size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 226                 propout() << std::make_pair( "avg_speed", nTotalOps / std::chrono::duration_cast<std::chrono::seconds>( duration ).count());
 227             }
 228
 229             check_before_cleanup( testMap );
 230
 231             testMap.clear();
 232             EXPECT_TRUE( testMap.empty());
 233
 234             additional_check( testMap );
 235             print_stat( propout(), testMap );
 236             additional_cleanup( testMap );
 237         }
 238
 239         template <class Map>
 240         void run_test()
 241         {
 242             Map testMap( *this );
 243             do_test( testMap );
 244         }
 245
 246         template <class Map>
 247         void run_bronson_avl_tree() {
 248           Map_InsDelFind::s_nPassCount =
 249               Map_InsDelFind::s_nBronsonAVLTreeMapPassCount;
 250           run_test<Map>();
 251         }
 252
 253         template <class Map>
 254         void run_ellen_bin_tree_hp() {
 255           Map_InsDelFind::s_nPassCount =
 256               Map_InsDelFind::s_nHpEllenBinTreeMapPassCount;
 257           run_test<Map>();
 258         }
 259
 260         template <class Map>
 261         void run_skip_list_hp() {
 262           Map_InsDelFind::s_nPassCount =
 263               Map_InsDelFind::s_nHpSkipListMapPassCount;
 264           run_test<Map>();
 265         }
 266
 267                                 template <class Map>
 268         void run_feldman_hp() {
 269           Map_InsDelFind::s_nPassCount =
 270               Map_InsDelFind::s_nHpFeldmanPassCount;
 271           run_test<Map>();
 272         }
 273
 274         template <class Map>
 275         void run_ellen_bin_tree_rcu() {
 276           Map_InsDelFind::s_nPassCount =
 277               Map_InsDelFind::s_nRcuEllenBinTreeMapPassCount;
 278           run_test<Map>();
 279         }
 280
 281         template <class Map>
 282         void run_skip_list_rcu() {
 283           Map_InsDelFind::s_nPassCount =
 284               Map_InsDelFind::s_nRcuSkipListMapPassCount;
 285           run_test<Map>();
 286         }
 287
 288                                 template <class Map>
 289         void run_feldman_rcu() {
 290           Map_InsDelFind::s_nPassCount =
 291               Map_InsDelFind::s_nRcuFeldmanPassCount;
 292           run_test<Map>();
 293         }
 294     };
 295
 296     class Map_InsDelFind_LF: public Map_InsDelFind
 297         , public ::testing::WithParamInterface<size_t>
 298     {
 299     public:
 300         template <class Map>
 301         void run_test()
 302         {
 303             s_nLoadFactor = GetParam();
 304             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 305             Map_InsDelFind::run_test<Map>();
 306         }
 307
 308                                 template <class Map>
 309         void run_michael_hp() {
 310           Map_InsDelFind::s_nPassCount =
 311               Map_InsDelFind::s_nHpMichaelMapPassCount;
 312           Map_InsDelFind_LF::run_test<Map>();
 313         }
 314
 315         template <class Map>
 316         void run_split_list_hp() {
 317           Map_InsDelFind::s_nPassCount =
 318               Map_InsDelFind::s_nHpSplitListMapPassCount;
 319           Map_InsDelFind_LF::run_test<Map>();
 320         }
 321
 322         template <class Map>
 323         void run_iterable_michael_hp() {
 324           Map_InsDelFind::s_nPassCount =
 325               Map_InsDelFind::s_nHpMichaelIterableMapPassCount;
 326           Map_InsDelFind_LF::run_test<Map>();
 327         }
 328
 329         template <class Map>
 330         void run_iterable_split_list_hp() {
 331           Map_InsDelFind::s_nPassCount =
 332               Map_InsDelFind::s_nHpSplitListIterableMapPassCount;
 333           Map_InsDelFind_LF::run_test<Map>();
 334         }
 335
 336         template <class Map>
 337         void run_michael_rcu() {
 338           Map_InsDelFind::s_nPassCount =
 339               Map_InsDelFind::s_nRcuMichaelMapPassCount;
 340           Map_InsDelFind_LF::run_test<Map>();
 341         }
 342
 343                                 template <class Map>
 344         void run_split_list_rcu() {
 345           Map_InsDelFind::s_nPassCount =
 346               Map_InsDelFind::s_nRcuSplitListMapPassCount;
 347           Map_InsDelFind_LF::run_test<Map>();
 348         }
 349
 350         static std::vector<size_t> get_load_factors();
 351     };
 352
 353 } // namespace map