tests/unit/map2/map_insdelfind.cpp

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