tests/unit/set2/set_insdelfind.h

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