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_nMaxLoadFactor;     // maximum load factor
  42         static unsigned int s_nInsertPercentage;
  43         static unsigned int s_nDeletePercentage;
  44         static unsigned int s_nDuration;    // test duration, seconds
  45
  46         static size_t s_nCuckooInitialSize;         // initial size for CuckooMap
  47         static size_t s_nCuckooProbesetSize;        // CuckooMap probeset size (only for list-based probeset)
  48         static size_t s_nCuckooProbesetThreshold;   // CuckooMap probeset threshold (o - use default)
  49
  50         static size_t s_nFeldmanMap_HeadBits;
  51         static size_t s_nFeldmanMap_ArrayBits;
  52
  53         static size_t  s_nLoadFactor;  // current load factor
  54
  55         static void SetUpTestCase();
  56         //static void TearDownTestCase();
  57
  58     public:
  59         enum actions
  60         {
  61             do_find,
  62             do_insert,
  63             do_delete
  64         };
  65         static const unsigned int c_nShuffleSize = 100;
  66         static actions s_arrShuffle[c_nShuffleSize];
  67
  68     protected:
  69         typedef size_t  key_type;
  70         typedef size_t  value_type;
  71
  72         template <class Map>
  73         class Worker: public cds_test::thread
  74         {
  75             typedef cds_test::thread base_class;
  76             Map&     m_Map;
  77
  78         public:
  79             size_t  m_nInsertSuccess = 0;
  80             size_t  m_nInsertFailed = 0;
  81             size_t  m_nDeleteSuccess = 0;
  82             size_t  m_nDeleteFailed = 0;
  83             size_t  m_nFindSuccess = 0;
  84             size_t  m_nFindFailed = 0;
  85
  86         public:
  87             Worker( cds_test::thread_pool& pool, Map& map )
  88                 : base_class( pool )
  89                 , m_Map( map )
  90             {}
  91
  92             Worker( Worker& src )
  93                 : base_class( src )
  94                 , m_Map( src.m_Map )
  95             {}
  96
  97             virtual thread * clone()
  98             {
  99                 return new Worker( *this );
 100             }
 101
 102             typedef std::pair< key_type const, value_type > map_value_type;
 103
 104             struct update_functor {
 105                 template <typename Q>
 106                 void operator()( bool /*bNew*/, map_value_type& /*cur*/, Q const& /*val*/ ) const
 107                 {}
 108
 109                 // FeldmanHashMap
 110                 void operator()( map_value_type& /*cur*/, map_value_type* /*old*/) const
 111                 {}
 112
 113                 // MichaelMap
 114                 void operator()( bool /*bNew*/, map_value_type& /*cur*/ ) const
 115                 {}
 116
 117                 // BronsonAVLTreeMap
 118                 void operator()( bool /*bNew*/, key_type /*key*/, value_type& /*val*/ ) const
 119                 {}
 120             };
 121
 122             virtual void test()
 123             {
 124                 Map& rMap = m_Map;
 125
 126                 unsigned int i = 0;
 127                 size_t const nNormalize = size_t(-1) / ( s_nMapSize * 2 );
 128
 129                 size_t nRand = 0;
 130                 while ( !time_elapsed()) {
 131                     nRand = cds::bitop::RandXorShift( nRand );
 132                     size_t n = nRand / nNormalize;
 133                     switch ( s_arrShuffle[i] ) {
 134                     case do_find:
 135                         if ( rMap.contains( n ))
 136                             ++m_nFindSuccess;
 137                         else
 138                             ++m_nFindFailed;
 139                         break;
 140                     case do_insert:
 141                         if ( n % 2 ) {
 142                             if ( rMap.insert( n, n ))
 143                                 ++m_nInsertSuccess;
 144                             else
 145                                 ++m_nInsertFailed;
 146                         }
 147                         else {
 148                             if ( rMap.update( n, update_functor(), true ).first )
 149                                 ++m_nInsertSuccess;
 150                             else
 151                                 ++m_nInsertFailed;
 152                         }
 153                         break;
 154                     case do_delete:
 155                         if ( rMap.erase( n ))
 156                             ++m_nDeleteSuccess;
 157                         else
 158                             ++m_nDeleteFailed;
 159                         break;
 160                     }
 161
 162                     if ( ++i >= c_nShuffleSize )
 163                         i = 0;
 164                 }
 165             }
 166         };
 167
 168     protected:
 169         template <class Map>
 170         void do_test( Map& testMap )
 171         {
 172             typedef Worker<Map> worker;
 173
 174             // fill map - only odd number
 175             {
 176                 std::vector<size_t> arr;
 177                 arr.reserve( s_nMapSize );
 178                 for ( size_t i = 0; i < s_nMapSize; ++i )
 179                     arr.push_back( i * 2 + 1);
 180                 shuffle( arr.begin(), arr.end());
 181                 for ( size_t i = 0; i < s_nMapSize; ++i )
 182                     testMap.insert( arr[i], arr[i] );
 183             }
 184
 185             cds_test::thread_pool& pool = get_pool();
 186             pool.add( new worker( pool, testMap ), s_nThreadCount );
 187
 188             propout() << std::make_pair( "thread_count", s_nThreadCount )
 189                 << std::make_pair( "insert_percentage", s_nInsertPercentage )
 190                 << std::make_pair( "delete_percentage", s_nDeletePercentage )
 191                 << std::make_pair( "map_size", s_nMapSize );
 192
 193             std::chrono::milliseconds duration = pool.run( std::chrono::seconds( s_nDuration ));
 194
 195             propout() << std::make_pair( "duration", duration );
 196
 197             size_t nInsertSuccess = 0;
 198             size_t nInsertFailed = 0;
 199             size_t nDeleteSuccess = 0;
 200             size_t nDeleteFailed = 0;
 201             size_t nFindSuccess = 0;
 202             size_t nFindFailed = 0;
 203             for ( size_t i = 0; i < pool.size(); ++i ) {
 204                 worker& thr = static_cast<worker&>( pool.get( i ));
 205
 206                 nInsertSuccess += thr.m_nInsertSuccess;
 207                 nInsertFailed += thr.m_nInsertFailed;
 208                 nDeleteSuccess += thr.m_nDeleteSuccess;
 209                 nDeleteFailed += thr.m_nDeleteFailed;
 210                 nFindSuccess += thr.m_nFindSuccess;
 211                 nFindFailed += thr.m_nFindFailed;
 212             }
 213
 214             propout()
 215                 << std::make_pair( "insert_success", nInsertSuccess )
 216                 << std::make_pair( "insert_failed", nInsertFailed )
 217                 << std::make_pair( "delete_success", nDeleteSuccess )
 218                 << std::make_pair( "delete_failed", nDeleteFailed )
 219                 << std::make_pair( "find_success", nFindSuccess )
 220                 << std::make_pair( "find_failed", nFindFailed )
 221                 << std::make_pair( "finish_map_size", testMap.size());
 222
 223             {
 224                 ASSERT_TRUE( std::chrono::duration_cast<std::chrono::seconds>(duration).count() > 0 );
 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
 247     class Map_InsDelFind_LF: public Map_InsDelFind
 248         , public ::testing::WithParamInterface<size_t>
 249     {
 250     public:
 251         template <class Map>
 252         void run_test()
 253         {
 254             s_nLoadFactor = GetParam();
 255             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 256             Map_InsDelFind::run_test<Map>();
 257         }
 258
 259         static std::vector<size_t> get_load_factors();
 260     };
 261
 262 } // namespace map