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                 size_t const nKeyRange = s_nMapSize * 4;
 147
 148                 size_t nRand = 0;
 149                 for (size_t pCount = 0; pCount < s_nPassCount; pCount++) {
 150                     nRand = cds::bitop::RandXorShift( nRand );
 151                     size_t key = nRand % nKeyRange + s_nMapSize;
 152                     nRand = cds::bitop::RandXorShift( nRand );
 153                     size_t value = nRand / nNormalize;
 154                     switch ( s_arrShuffle[i] ) {
 155                     case do_find:
 156                         if ( rMap.contains( key ))
 157                             ++m_nFindSuccess;
 158                         else
 159                             ++m_nFindFailed;
 160                         break;
 161                     case do_insert:
 162                         if ( key % 2 ) {
 163                             if ( rMap.insert( key, value ))
 164                                 ++m_nInsertSuccess;
 165                             else
 166                                 ++m_nInsertFailed;
 167                         }
 168                         else {
 169                             if ( rMap.update( key, update_functor(), true ).first )
 170                                 ++m_nInsertSuccess;
 171                             else
 172                                 ++m_nInsertFailed;
 173                         }
 174                         break;
 175                     case do_delete:
 176                         if ( rMap.erase( key ))
 177                             ++m_nDeleteSuccess;
 178                         else
 179                             ++m_nDeleteFailed;
 180                         break;
 181                     }
 182
 183                     if ( ++i >= c_nShuffleSize )
 184                         i = 0;
 185                 }
 186             }
 187         };
 188
 189     protected:
 190         template <class Map>
 191         void do_test( Map& testMap )
 192         {
 193             typedef Worker<Map> worker;
 194             cds_test::thread_pool& pool = get_pool();
 195             pool.add( new worker( pool, testMap ), s_nThreadCount );
 196
 197             std::chrono::milliseconds duration = pool.run();
 198
 199             size_t nInsertSuccess = 0;
 200             size_t nInsertFailed = 0;
 201             size_t nDeleteSuccess = 0;
 202             size_t nDeleteFailed = 0;
 203             size_t nFindSuccess = 0;
 204             size_t nFindFailed = 0;
 205             for ( size_t i = 0; i < pool.size(); ++i ) {
 206                 worker& thr = static_cast<worker&>( pool.get( i ));
 207
 208                 nInsertSuccess += thr.m_nInsertSuccess;
 209                 nInsertFailed += thr.m_nInsertFailed;
 210                 nDeleteSuccess += thr.m_nDeleteSuccess;
 211                 nDeleteFailed += thr.m_nDeleteFailed;
 212                 nFindSuccess += thr.m_nFindSuccess;
 213                 nFindFailed += thr.m_nFindFailed;
 214             }
 215
 216             propout()
 217                 << std::make_pair( "insert_success", nInsertSuccess )
 218                 << std::make_pair( "insert_failed", nInsertFailed )
 219                 << std::make_pair( "delete_success", nDeleteSuccess )
 220                 << std::make_pair( "delete_failed", nDeleteFailed )
 221                 << std::make_pair( "find_success", nFindSuccess )
 222                 << std::make_pair( "find_failed", nFindFailed )
 223                 << std::make_pair( "finish_map_size", testMap.size());
 224
 225             {
 226                 size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 227                 propout() << std::make_pair( "avg_speed", nTotalOps / std::chrono::duration_cast<std::chrono::seconds>( duration ).count());
 228             }
 229
 230             check_before_cleanup( testMap );
 231
 232             testMap.clear();
 233             EXPECT_TRUE( testMap.empty());
 234
 235             additional_check( testMap );
 236             print_stat( propout(), testMap );
 237             additional_cleanup( testMap );
 238         }
 239
 240         template <class Map>
 241         void run_test()
 242         {
 243             Map testMap( *this );
 244             do_test( testMap );
 245         }
 246
 247         template <class Map>
 248         void run_bronson_avl_tree() {
 249           Map_InsDelFind::s_nPassCount =
 250               Map_InsDelFind::s_nBronsonAVLTreeMapPassCount;
 251           run_test<Map>();
 252         }
 253
 254         template <class Map>
 255         void run_ellen_bin_tree_hp() {
 256           Map_InsDelFind::s_nPassCount =
 257               Map_InsDelFind::s_nHpEllenBinTreeMapPassCount;
 258           run_test<Map>();
 259         }
 260
 261         template <class Map>
 262         void run_skip_list_hp() {
 263           Map_InsDelFind::s_nPassCount =
 264               Map_InsDelFind::s_nHpSkipListMapPassCount;
 265           run_test<Map>();
 266         }
 267
 268                                 template <class Map>
 269         void run_feldman_hp() {
 270           Map_InsDelFind::s_nPassCount =
 271               Map_InsDelFind::s_nHpFeldmanPassCount;
 272           run_test<Map>();
 273         }
 274
 275         template <class Map>
 276         void run_ellen_bin_tree_rcu() {
 277           Map_InsDelFind::s_nPassCount =
 278               Map_InsDelFind::s_nRcuEllenBinTreeMapPassCount;
 279           run_test<Map>();
 280         }
 281
 282         template <class Map>
 283         void run_skip_list_rcu() {
 284           Map_InsDelFind::s_nPassCount =
 285               Map_InsDelFind::s_nRcuSkipListMapPassCount;
 286           run_test<Map>();
 287         }
 288
 289                                 template <class Map>
 290         void run_feldman_rcu() {
 291           Map_InsDelFind::s_nPassCount =
 292               Map_InsDelFind::s_nRcuFeldmanPassCount;
 293           run_test<Map>();
 294         }
 295     };
 296
 297     class Map_InsDelFind_LF: public Map_InsDelFind
 298         , public ::testing::WithParamInterface<size_t>
 299     {
 300     public:
 301         template <class Map>
 302         void run_test()
 303         {
 304             s_nLoadFactor = GetParam();
 305             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 306             Map_InsDelFind::run_test<Map>();
 307         }
 308
 309                                 template <class Map>
 310         void run_michael_hp() {
 311           Map_InsDelFind::s_nPassCount =
 312               Map_InsDelFind::s_nHpMichaelMapPassCount;
 313           Map_InsDelFind_LF::run_test<Map>();
 314         }
 315
 316         template <class Map>
 317         void run_split_list_hp() {
 318           Map_InsDelFind::s_nPassCount =
 319               Map_InsDelFind::s_nHpSplitListMapPassCount;
 320           Map_InsDelFind_LF::run_test<Map>();
 321         }
 322
 323         template <class Map>
 324         void run_iterable_michael_hp() {
 325           Map_InsDelFind::s_nPassCount =
 326               Map_InsDelFind::s_nHpMichaelIterableMapPassCount;
 327           Map_InsDelFind_LF::run_test<Map>();
 328         }
 329
 330         template <class Map>
 331         void run_iterable_split_list_hp() {
 332           Map_InsDelFind::s_nPassCount =
 333               Map_InsDelFind::s_nHpSplitListIterableMapPassCount;
 334           Map_InsDelFind_LF::run_test<Map>();
 335         }
 336
 337         template <class Map>
 338         void run_michael_rcu() {
 339           Map_InsDelFind::s_nPassCount =
 340               Map_InsDelFind::s_nRcuMichaelMapPassCount;
 341           Map_InsDelFind_LF::run_test<Map>();
 342         }
 343
 344                                 template <class Map>
 345         void run_split_list_rcu() {
 346           Map_InsDelFind::s_nPassCount =
 347               Map_InsDelFind::s_nRcuSplitListMapPassCount;
 348           Map_InsDelFind_LF::run_test<Map>();
 349         }
 350
 351         static std::vector<size_t> get_load_factors();
 352     };
 353
 354 } // namespace map