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