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