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 != nullptr );
 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             size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 173
 174             CPPUNIT_MSG( "  Totals (success/failed): \n\t"
 175                       << "      Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
 176                       << "      Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
 177                       << "        Find=" << nFindSuccess   << '/' << nFindFailed   << "\n\t"
 178                       << "       Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
 179                       << "             " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
 180                       << "   Total ops=" << nTotalOps << "\n\t"
 181                       << "       speed=" << nTotalOps / c_nDuration << " ops/sec\n\t"
 182                       << "      Set size=" << testSet.size()
 183                 );
 184
 185
 186             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 187             timer.reset();
 188             testSet.clear();
 189             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 190             CPPUNIT_CHECK_EX( testSet.empty(), ((long long) testSet.size()) );
 191
 192             additional_check( testSet );
 193             print_stat( testSet );
 194             additional_cleanup( testSet );
 195         }
 196
 197         template <class Set>
 198         void test()
 199         {
 200             CPPUNIT_MSG( "Thread count=" << c_nThreadCount
 201                 << " initial map size=" << c_nInitialMapSize
 202                 << " insert=" << c_nInsertPercentage << '%'
 203                 << " delete=" << c_nDeletePercentage << '%'
 204                 << " duration=" << c_nDuration << "s"
 205                 );
 206
 207             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 208                 do_test<Set>( nLoadFactor );
 209                 if ( c_bPrintGCState )
 210                     print_gc_state();
 211             }
 212         }
 213
 214         template <class Set>
 215         void test_nolf()
 216         {
 217             CPPUNIT_MSG( "Thread count=" << c_nThreadCount
 218                 << " initial map size=" << c_nInitialMapSize
 219                 << " insert=" << c_nInsertPercentage << '%'
 220                 << " delete=" << c_nDeletePercentage << '%'
 221                 << " duration=" << c_nDuration << "s"
 222                 );
 223
 224             Set s;
 225             do_test_with( s );
 226             //CPPUNIT_MSG( s.statistics() );
 227             if ( c_bPrintGCState )
 228                 print_gc_state();
 229         }
 230
 231         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 232             c_nInitialMapSize = cfg.getULong("InitialMapSize", 500000 );
 233             c_nThreadCount = cfg.getULong("ThreadCount", 8 );
 234             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 235             c_nInsertPercentage = cfg.getUInt("InsertPercentage", 5 );
 236             c_nDeletePercentage = cfg.getUInt("DeletePercentage", 5 );
 237             c_nDuration = cfg.getUInt("Duration", 30 );
 238             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 239
 240             if ( c_nThreadCount == 0 )
 241                 c_nThreadCount = cds::OS::topology::processor_count() * 2;
 242
 243             CPPUNIT_ASSERT( c_nInsertPercentage + c_nDeletePercentage <= 100 );
 244
 245             actions * pFirst = m_arrShuffle;
 246             actions * pLast = m_arrShuffle + c_nInsertPercentage;
 247             std::fill( pFirst, pLast, do_insert );
 248             pFirst = pLast;
 249             pLast += c_nDeletePercentage;
 250             std::fill( pFirst, pLast, do_delete );
 251             pFirst = pLast;
 252             pLast = m_arrShuffle + sizeof(m_arrShuffle)/sizeof(m_arrShuffle[0]);
 253             std::fill( pFirst, pLast, do_find );
 254             std::random_shuffle( m_arrShuffle, pLast );
 255         }
 256
 257 #   include "set2/set_defs.h"
 258         CDSUNIT_DECLARE_MichaelSet
 259         CDSUNIT_DECLARE_SplitList
 260         CDSUNIT_DECLARE_StripedSet
 261         CDSUNIT_DECLARE_RefinableSet
 262         CDSUNIT_DECLARE_CuckooSet
 263         CDSUNIT_DECLARE_SkipListSet
 264         CDSUNIT_DECLARE_EllenBinTreeSet
 265         CDSUNIT_DECLARE_StdSet
 266
 267         CPPUNIT_TEST_SUITE_( Set_InsDelFind, "Map_InsDelFind" )
 268             CDSUNIT_TEST_MichaelSet
 269             CDSUNIT_TEST_SplitList
 270             CDSUNIT_TEST_SkipListSet
 271             CDSUNIT_TEST_EllenBinTreeSet
 272             CDSUNIT_TEST_StripedSet
 273             CDSUNIT_TEST_RefinableSet
 274             CDSUNIT_TEST_CuckooSet
 275             CDSUNIT_TEST_StdSet
 276         CPPUNIT_TEST_SUITE_END()
 277     };
 278
 279     CPPUNIT_TEST_SUITE_REGISTRATION( Set_InsDelFind );
 280 } // namespace set2