tests/unit/set2/set_insdelfind.cpp

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