tests/unit/map2/map_insdelfind.h

   1 //$$CDS-header$$
   2
   3 #include "map2/map_type.h"
   4 #include "cppunit/thread.h"
   5 #include <vector>
   6
   7 namespace map2 {
   8
   9 #define TEST_CASE(TAG, X)  void X();
  10
  11     class Map_InsDelFind: public CppUnitMini::TestCase
  12     {
  13     public:
  14         size_t  c_nMapSize = 500000;          // initial map size
  15         size_t  c_nThreadCount = 8;      // thread count
  16         size_t  c_nMaxLoadFactor = 8;    // maximum load factor
  17         unsigned int c_nInsertPercentage = 5;
  18         unsigned int c_nDeletePercentage = 5;
  19         unsigned int c_nDuration = 30;    // test duration, seconds
  20         bool    c_bPrintGCState = true;
  21
  22         size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
  23         size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
  24         size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
  25
  26         size_t c_nMultiLevelMap_HeadBits = 10;
  27         size_t c_nMultiLevelMap_ArrayBits = 4;
  28
  29         size_t  c_nLoadFactor = 2;  // current load factor
  30
  31     public:
  32         enum actions
  33         {
  34             do_find,
  35             do_insert,
  36             do_delete
  37         };
  38         static const unsigned int c_nShuffleSize = 100;
  39         actions m_arrShuffle[c_nShuffleSize];
  40
  41     protected:
  42         typedef size_t  key_type;
  43         typedef size_t  value_type;
  44
  45         template <class Map>
  46         class WorkThread: public CppUnitMini::TestThread
  47         {
  48             Map&     m_Map;
  49
  50             virtual WorkThread *    clone()
  51             {
  52                 return new WorkThread( *this );
  53             }
  54         public:
  55             size_t  m_nInsertSuccess;
  56             size_t  m_nInsertFailed;
  57             size_t  m_nDeleteSuccess;
  58             size_t  m_nDeleteFailed;
  59             size_t  m_nFindSuccess;
  60             size_t  m_nFindFailed;
  61
  62         public:
  63             WorkThread( CppUnitMini::ThreadPool& pool, Map& rMap )
  64                 : CppUnitMini::TestThread( pool )
  65                 , m_Map( rMap )
  66             {}
  67             WorkThread( WorkThread& src )
  68                 : CppUnitMini::TestThread( src )
  69                 , m_Map( src.m_Map )
  70             {}
  71
  72             Map_InsDelFind&  getTest()
  73             {
  74                 return reinterpret_cast<Map_InsDelFind&>( m_Pool.m_Test );
  75             }
  76
  77             virtual void init() { cds::threading::Manager::attachThread()   ; }
  78             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  79
  80             typedef std::pair< key_type const, value_type > map_value_type;
  81
  82             struct update_functor {
  83                 template <typename Q>
  84                 void operator()( bool /*bNew*/, map_value_type& /*cur*/, Q const& /*val*/ )
  85                 {}
  86
  87                 // MultiLevelHashMap
  88                 void operator()( map_value_type& /*cur*/, map_value_type * /*old*/)
  89                 {}
  90
  91                 // MichaelMap
  92                 void operator()( bool /*bNew*/, map_value_type& /*cur*/ )
  93                 {}
  94
  95                 // BronsonAVLTreeMap
  96                 void operator()( bool /*bNew*/, key_type /*key*/, value_type& /*val*/ )
  97                 {}
  98             };
  99
 100             virtual void test()
 101             {
 102                 Map& rMap = m_Map;
 103
 104                 m_nInsertSuccess =
 105                     m_nInsertFailed =
 106                     m_nDeleteSuccess =
 107                     m_nDeleteFailed =
 108                     m_nFindSuccess =
 109                     m_nFindFailed = 0;
 110
 111                 actions * pAct = getTest().m_arrShuffle;
 112                 unsigned int i = 0;
 113                 size_t const nNormalize = size_t(-1) / (getTest().c_nMapSize * 2);
 114
 115                 size_t nRand = 0;
 116                 while ( !time_elapsed() ) {
 117                     nRand = cds::bitop::RandXorShift(nRand);
 118                     size_t n = nRand / nNormalize;
 119                     switch ( pAct[i] ) {
 120                     case do_find:
 121                         if ( rMap.contains( n ))
 122                             ++m_nFindSuccess;
 123                         else
 124                             ++m_nFindFailed;
 125                         break;
 126                     case do_insert:
 127                         if ( n % 2 ) {
 128                             if ( rMap.insert( n, n ))
 129                                 ++m_nInsertSuccess;
 130                             else
 131                                 ++m_nInsertFailed;
 132                         }
 133                         else {
 134                             if ( rMap.update(n, update_functor(), true ).first )
 135                                 ++m_nInsertSuccess;
 136                             else
 137                                 ++m_nInsertFailed;
 138                         }
 139                         break;
 140                     case do_delete:
 141                         if ( rMap.erase( n ))
 142                             ++m_nDeleteSuccess;
 143                         else
 144                             ++m_nDeleteFailed;
 145                         break;
 146                     }
 147
 148                     if ( ++i >= c_nShuffleSize )
 149                         i = 0;
 150                 }
 151             }
 152         };
 153
 154     protected:
 155         template <class Map>
 156         void do_test( Map& testMap )
 157         {
 158             typedef WorkThread<Map> work_thread;
 159             cds::OS::Timer    timer;
 160
 161             // fill map - only odd number
 162             {
 163                 std::vector<size_t> arr;
 164                 arr.reserve( c_nMapSize );
 165                 for ( size_t i = 0; i < c_nMapSize; ++i )
 166                     arr.push_back( i * 2 + 1);
 167                 shuffle( arr.begin(), arr.end() );
 168                 for ( size_t i = 0; i < c_nMapSize; ++i )
 169                     testMap.insert( arr[i], arr[i] );
 170             }
 171             CPPUNIT_MSG( "   Insert " << c_nMapSize << " items time (single-threaded)=" << timer.duration() );
 172
 173             timer.reset();
 174             CppUnitMini::ThreadPool pool( *this );
 175             pool.add( new work_thread( pool, testMap ), c_nThreadCount );
 176             pool.run( c_nDuration );
 177             //CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 178
 179             size_t nInsertSuccess = 0;
 180             size_t nInsertFailed = 0;
 181             size_t nDeleteSuccess = 0;
 182             size_t nDeleteFailed = 0;
 183             size_t nFindSuccess = 0;
 184             size_t nFindFailed = 0;
 185             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 186                 work_thread * pThread = static_cast<work_thread *>( *it );
 187                 assert( pThread != nullptr );
 188                 nInsertSuccess += pThread->m_nInsertSuccess;
 189                 nInsertFailed += pThread->m_nInsertFailed;
 190                 nDeleteSuccess += pThread->m_nDeleteSuccess;
 191                 nDeleteFailed += pThread->m_nDeleteFailed;
 192                 nFindSuccess += pThread->m_nFindSuccess;
 193                 nFindFailed += pThread->m_nFindFailed;
 194             }
 195
 196             size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 197
 198             CPPUNIT_MSG( "  Totals (success/failed): \n\t"
 199                       << "      Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
 200                       << "      Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
 201                       << "        Find=" << nFindSuccess   << '/' << nFindFailed   << "\n\t"
 202                       << "       Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
 203                       << "             " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
 204                       << "   Total ops=" << nTotalOps << "\n\t"
 205                       << "       speed=" << nTotalOps / c_nDuration << " ops/sec\n\t"
 206                       << "      Map size=" << testMap.size()
 207                 );
 208
 209
 210             check_before_cleanup( testMap );
 211
 212             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 213             timer.reset();
 214             testMap.clear();
 215             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 216             CPPUNIT_ASSERT_EX( testMap.empty(), ((long long) testMap.size()) );
 217
 218             additional_check( testMap );
 219             print_stat( testMap );
 220             additional_cleanup( testMap );
 221         }
 222
 223         template <class Map>
 224         void run_test()
 225         {
 226             CPPUNIT_MSG( "Thread count=" << c_nThreadCount
 227                 << " initial map size=" << c_nMapSize
 228                 << " insert=" << c_nInsertPercentage << '%'
 229                 << " delete=" << c_nDeletePercentage << '%'
 230                 << " duration=" << c_nDuration << "s"
 231                 );
 232
 233             if ( Map::c_bLoadFactorDepended ) {
 234                 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
 235                     CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
 236                     Map  testMap( *this );
 237                     do_test( testMap );
 238                     if ( c_bPrintGCState )
 239                         print_gc_state();
 240                 }
 241             }
 242             else {
 243                 Map testMap( *this );
 244                 do_test( testMap );
 245                 if ( c_bPrintGCState )
 246                     print_gc_state();
 247             }
 248         }
 249
 250         void setUpParams( const CppUnitMini::TestCfg& cfg );
 251
 252 #   include "map2/map_defs.h"
 253         CDSUNIT_DECLARE_MichaelMap
 254         CDSUNIT_DECLARE_SplitList
 255         CDSUNIT_DECLARE_SkipListMap
 256         CDSUNIT_DECLARE_EllenBinTreeMap
 257         CDSUNIT_DECLARE_BronsonAVLTreeMap
 258         CDSUNIT_DECLARE_MultiLevelHashMap
 259         CDSUNIT_DECLARE_StripedMap
 260         CDSUNIT_DECLARE_RefinableMap
 261         CDSUNIT_DECLARE_CuckooMap
 262         CDSUNIT_DECLARE_StdMap
 263
 264         CPPUNIT_TEST_SUITE(Map_InsDelFind)
 265             CDSUNIT_TEST_MichaelMap
 266             CDSUNIT_TEST_SplitList
 267             CDSUNIT_TEST_SkipListMap
 268             CDSUNIT_TEST_EllenBinTreeMap
 269             CDSUNIT_TEST_BronsonAVLTreeMap
 270             CDSUNIT_TEST_MultiLevelHashMap
 271             CDSUNIT_TEST_CuckooMap
 272             CDSUNIT_TEST_StripedMap
 273             CDSUNIT_TEST_RefinableMap
 274             CDSUNIT_TEST_StdMap
 275         CPPUNIT_TEST_SUITE_END();
 276     };
 277 } // namespace map2