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