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 != NULL );
 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             CPPUNIT_MSG( "  Totals (success/failed): \n\t"
 165                       << "      Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
 166                       << "      Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
 167                       << "        Find=" << nFindSuccess   << '/' << nFindFailed   << "\n\t"
 168                       << "       Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
 169                       << "             " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
 170                       << "      Map size=" << testMap.size()
 171                 );
 172
 173
 174             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 175             timer.reset();
 176             testMap.clear();
 177             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 178             CPPUNIT_ASSERT_EX( testMap.empty(), ((long long) testMap.size()) );
 179
 180             additional_check( testMap );
 181             print_stat( testMap );
 182             additional_cleanup( testMap );
 183         }
 184
 185         template <class MAP>
 186         void test()
 187         {
 188             CPPUNIT_MSG( "Thread count=" << c_nThreadCount
 189                 << " initial map size=" << c_nInitialMapSize
 190                 << " insert=" << c_nInsertPercentage << '%'
 191                 << " delete=" << c_nDeletePercentage << '%'
 192                 << " duration=" << c_nDuration << "s"
 193                 );
 194
 195             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 196                 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 197                 MAP  testMap( c_nInitialMapSize, nLoadFactor );
 198                 do_test( testMap );
 199                 if ( c_bPrintGCState )
 200                     print_gc_state();
 201             }
 202
 203         }
 204
 205         template <class MAP>
 206         void test_nolf()
 207         {
 208             CPPUNIT_MSG( "Thread count=" << c_nThreadCount
 209                 << " initial map size=" << c_nInitialMapSize
 210                 << " insert=" << c_nInsertPercentage << '%'
 211                 << " delete=" << c_nDeletePercentage << '%'
 212                 << " duration=" << c_nDuration << "s"
 213                 );
 214
 215             MAP testMap;
 216             do_test( testMap );
 217             if ( c_bPrintGCState )
 218                 print_gc_state();
 219         }
 220
 221         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 222             c_nInitialMapSize = cfg.getULong("InitialMapSize", 500000 );
 223             c_nThreadCount = cfg.getULong("ThreadCount", 8 );
 224             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 225             c_nInsertPercentage = cfg.getUInt("InsertPercentage", 5 );
 226             c_nDeletePercentage = cfg.getUInt("DeletePercentage", 5 );
 227             c_nDuration = cfg.getUInt("Duration", 30 );
 228             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 229
 230             if ( c_nThreadCount == 0 )
 231                 c_nThreadCount = cds::OS::topology::processor_count() * 2;
 232
 233             CPPUNIT_ASSERT( c_nInsertPercentage + c_nDeletePercentage <= 100 );
 234
 235             actions * pFirst = m_arrShuffle;
 236             actions * pLast = m_arrShuffle + c_nInsertPercentage;
 237             std::fill( pFirst, pLast, do_insert );
 238             pFirst = pLast;
 239             pLast += c_nDeletePercentage;
 240             std::fill( pFirst, pLast, do_delete );
 241             pFirst = pLast;
 242             pLast = m_arrShuffle + sizeof(m_arrShuffle)/sizeof(m_arrShuffle[0]);
 243             std::fill( pFirst, pLast, do_find );
 244             std::random_shuffle( m_arrShuffle, pLast );
 245         }
 246
 247 #   include "map2/map_defs.h"
 248         CDSUNIT_DECLARE_MichaelMap
 249         CDSUNIT_DECLARE_SplitList
 250         CDSUNIT_DECLARE_SkipListMap
 251         CDSUNIT_DECLARE_EllenBinTreeMap
 252         CDSUNIT_DECLARE_StripedMap
 253         CDSUNIT_DECLARE_RefinableMap
 254         CDSUNIT_DECLARE_CuckooMap
 255         CDSUNIT_DECLARE_StdMap
 256
 257         CPPUNIT_TEST_SUITE( Map_InsDelFind )
 258             CDSUNIT_TEST_MichaelMap
 259             CDSUNIT_TEST_SplitList
 260             CDSUNIT_TEST_SkipListMap
 261             CDSUNIT_TEST_EllenBinTreeMap
 262             CDSUNIT_TEST_StripedMap
 263             CDSUNIT_TEST_RefinableMap
 264             CDSUNIT_TEST_CuckooMap
 265             CDSUNIT_TEST_StdMap
 266         CPPUNIT_TEST_SUITE_END()
 267     };
 268
 269     CPPUNIT_TEST_SUITE_REGISTRATION( Map_InsDelFind );
 270 } // namespace map2