tests/unit/map2/map_insdelfind.h

   1 //$$CDS-header$$
   2
   3 #include "map2/map_type.h"
   4 #include "cppunit/thread.h"
   5 #include <vector>
   6
   7 namespace map2 {
   8
   9 #   define TEST_MAP(IMPL, C, X)         void C::X() { test<map_type<IMPL, key_type, value_type>::X >(); }
  10 #   define TEST_MAP_NOLF(IMPL, C, X)    void C::X() { test_nolf<map_type<IMPL, key_type, value_type>::X >(); }
  11 #   define TEST_MAP_EXTRACT(IMPL, C, X)  TEST_MAP(IMPL, C, X)
  12 #   define TEST_MAP_NOLF_EXTRACT(IMPL, C, X) TEST_MAP_NOLF(IMPL, C, X)
  13
  14     class Map_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 MAP>
  40         class WorkThread: public CppUnitMini::TestThread
  41         {
  42             MAP&     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, MAP& 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             Map_InsDelFind&  getTest()
  67             {
  68                 return reinterpret_cast<Map_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                 MAP& 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, 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 MAP>
 122         void do_test( MAP& testMap )
 123         {
 124             typedef WorkThread<MAP> work_thread;
 125             cds::OS::Timer    timer;
 126
 127             // fill map - only odd number
 128             {
 129                 std::vector<size_t> arr;
 130                 arr.reserve( c_nInitialMapSize );
 131                 for ( size_t i = 0; i < c_nInitialMapSize; ++i )
 132                     arr.push_back( i * 2 + 1);
 133                 shuffle( arr.begin(), arr.end() );
 134                 for ( size_t i = 0; i < c_nInitialMapSize; ++i )
 135                     testMap.insert( arr[i], arr[i] );
 136             }
 137             CPPUNIT_MSG( "   Insert " << c_nInitialMapSize << " items time (single-threaded)=" << timer.duration() );
 138
 139             timer.reset();
 140             CppUnitMini::ThreadPool pool( *this );
 141             pool.add( new work_thread( pool, testMap ), c_nThreadCount );
 142             pool.run( c_nDuration );
 143             //CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 144
 145             size_t nInsertSuccess = 0;
 146             size_t nInsertFailed = 0;
 147             size_t nDeleteSuccess = 0;
 148             size_t nDeleteFailed = 0;
 149             size_t nFindSuccess = 0;
 150             size_t nFindFailed = 0;
 151             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 152                 work_thread * pThread = static_cast<work_thread *>( *it );
 153                 assert( pThread != nullptr );
 154                 nInsertSuccess += pThread->m_nInsertSuccess;
 155                 nInsertFailed += pThread->m_nInsertFailed;
 156                 nDeleteSuccess += pThread->m_nDeleteSuccess;
 157                 nDeleteFailed += pThread->m_nDeleteFailed;
 158                 nFindSuccess += pThread->m_nFindSuccess;
 159                 nFindFailed += pThread->m_nFindFailed;
 160             }
 161
 162             size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 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                       << "   Total ops=" << nTotalOps << "\n\t"
 171                       << "       speed=" << nTotalOps / c_nDuration << " ops/sec\n\t"
 172                       << "      Map size=" << testMap.size()
 173                 );
 174
 175
 176             check_before_cleanup( testMap );
 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
 227         void run_MichaelMap(const char *in_name, bool invert = false);
 228         void run_SplitList(const char *in_name, bool invert = false);
 229         void run_StripedMap(const char *in_name, bool invert = false);
 230         void run_RefinableMap(const char *in_name, bool invert = false);
 231         void run_CuckooMap(const char *in_name, bool invert = false);
 232         void run_SkipListMap(const char *in_name, bool invert = false);
 233         void run_EllenBinTreeMap(const char *in_name, bool invert = false);
 234         void run_BronsonAVLTreeMap(const char *in_name, bool invert = false);
 235         void run_StdMap(const char *in_name, bool invert = false);
 236
 237         virtual void myRun(const char *in_name, bool invert = false);
 238
 239 #   include "map2/map_defs.h"
 240         CDSUNIT_DECLARE_MichaelMap
 241         CDSUNIT_DECLARE_SplitList
 242         CDSUNIT_DECLARE_SkipListMap
 243         CDSUNIT_DECLARE_EllenBinTreeMap
 244         CDSUNIT_DECLARE_BronsonAVLTreeMap
 245         CDSUNIT_DECLARE_StripedMap
 246         CDSUNIT_DECLARE_RefinableMap
 247         CDSUNIT_DECLARE_CuckooMap
 248         CDSUNIT_DECLARE_StdMap
 249     };
 250 } // namespace map2