tests/unit/map2/map_insdelfind.h

   1 //$$CDS-header$$
   2
   3 #include "map2/map_type.h"
   4 #include "cppunit/thread.h"
   5 #include <algorithm> // random_shuffle
   6 #include <vector>
   7
   8 namespace map2 {
   9
  10 #   define TEST_MAP(IMPL, C, X)         void C::X() { test<map_type<IMPL, key_type, value_type>::X >(); }
  11 #   define TEST_MAP_NOLF(IMPL, C, X)    void C::X() { test_nolf<map_type<IMPL, key_type, value_type>::X >(); }
  12 #   define TEST_MAP_EXTRACT(IMPL, C, X)  TEST_MAP(IMPL, C, X)
  13 #   define TEST_MAP_NOLF_EXTRACT(IMPL, C, X) TEST_MAP_NOLF(IMPL, C, X)
  14
  15     class Map_InsDelFind: public CppUnitMini::TestCase
  16     {
  17         static size_t  c_nInitialMapSize;   // initial map size
  18         static size_t  c_nThreadCount;      // thread count
  19         static size_t  c_nMaxLoadFactor;    // maximum load factor
  20         static unsigned int c_nInsertPercentage;
  21         static unsigned int c_nDeletePercentage;
  22         static unsigned int c_nDuration;    // test duration, seconds
  23         static bool    c_bPrintGCState;
  24
  25     public:
  26         enum actions
  27         {
  28             do_find,
  29             do_insert,
  30             do_delete
  31         };
  32         static const unsigned int c_nShuffleSize = 100;
  33         actions m_arrShuffle[c_nShuffleSize];
  34
  35     protected:
  36         typedef CppUnitMini::TestCase Base;
  37         typedef size_t  key_type;
  38         typedef size_t  value_type;
  39
  40         template <class MAP>
  41         class WorkThread: public CppUnitMini::TestThread
  42         {
  43             MAP&     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, MAP& 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             Map_InsDelFind&  getTest()
  68             {
  69                 return reinterpret_cast<Map_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                 MAP& 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, 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 MAP>
 123         void do_test( MAP& testMap )
 124         {
 125             typedef WorkThread<MAP> work_thread;
 126             cds::OS::Timer    timer;
 127
 128             // fill map - only odd number
 129             {
 130                 std::vector<size_t> arr;
 131                 arr.reserve( c_nInitialMapSize );
 132                 for ( size_t i = 0; i < c_nInitialMapSize; ++i )
 133                     arr.push_back( i * 2 + 1);
 134                 std::random_shuffle( arr.begin(), arr.end() );
 135                 for ( size_t i = 0; i < c_nInitialMapSize; ++i )
 136                     testMap.insert( arr[i], arr[i] );
 137             }
 138             CPPUNIT_MSG( "   Insert " << c_nInitialMapSize << " items time (single-threaded)=" << timer.duration() );
 139
 140             timer.reset();
 141             CppUnitMini::ThreadPool pool( *this );
 142             pool.add( new work_thread( pool, testMap ), c_nThreadCount );
 143             pool.run( c_nDuration );
 144             //CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 145
 146             size_t nInsertSuccess = 0;
 147             size_t nInsertFailed = 0;
 148             size_t nDeleteSuccess = 0;
 149             size_t nDeleteFailed = 0;
 150             size_t nFindSuccess = 0;
 151             size_t nFindFailed = 0;
 152             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 153                 work_thread * pThread = static_cast<work_thread *>( *it );
 154                 assert( pThread != nullptr );
 155                 nInsertSuccess += pThread->m_nInsertSuccess;
 156                 nInsertFailed += pThread->m_nInsertFailed;
 157                 nDeleteSuccess += pThread->m_nDeleteSuccess;
 158                 nDeleteFailed += pThread->m_nDeleteFailed;
 159                 nFindSuccess += pThread->m_nFindSuccess;
 160                 nFindFailed += pThread->m_nFindFailed;
 161             }
 162
 163             size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
 164
 165             CPPUNIT_MSG( "  Totals (success/failed): \n\t"
 166                       << "      Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
 167                       << "      Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
 168                       << "        Find=" << nFindSuccess   << '/' << nFindFailed   << "\n\t"
 169                       << "       Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
 170                       << "             " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
 171                       << "   Total ops=" << nTotalOps << "\n\t"
 172                       << "       speed=" << nTotalOps / c_nDuration << " ops/sec\n\t"
 173                       << "      Map size=" << testMap.size()
 174                 );
 175
 176
 177             check_before_cleanup( testMap );
 178
 179             CPPUNIT_MSG( "  Clear map (single-threaded)..." );
 180             timer.reset();
 181             testMap.clear();
 182             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 183             CPPUNIT_ASSERT_EX( testMap.empty(), ((long long) testMap.size()) );
 184
 185             additional_check( testMap );
 186             print_stat( testMap );
 187             additional_cleanup( testMap );
 188         }
 189
 190         template <class MAP>
 191         void test()
 192         {
 193             CPPUNIT_MSG( "Thread count=" << c_nThreadCount
 194                 << " initial map size=" << c_nInitialMapSize
 195                 << " insert=" << c_nInsertPercentage << '%'
 196                 << " delete=" << c_nDeletePercentage << '%'
 197                 << " duration=" << c_nDuration << "s"
 198                 );
 199
 200             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 201                 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 202                 MAP  testMap( c_nInitialMapSize, nLoadFactor );
 203                 do_test( testMap );
 204                 if ( c_bPrintGCState )
 205                     print_gc_state();
 206             }
 207
 208         }
 209
 210         template <class MAP>
 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             MAP testMap;
 221             do_test( testMap );
 222             if ( c_bPrintGCState )
 223                 print_gc_state();
 224         }
 225
 226         void setUpParams( const CppUnitMini::TestCfg& cfg );
 227
 228         void run_MichaelMap(const char *in_name, bool invert = false);
 229         void run_SplitList(const char *in_name, bool invert = false);
 230         void run_StripedMap(const char *in_name, bool invert = false);
 231         void run_RefinableMap(const char *in_name, bool invert = false);
 232         void run_CuckooMap(const char *in_name, bool invert = false);
 233         void run_SkipListMap(const char *in_name, bool invert = false);
 234         void run_EllenBinTreeMap(const char *in_name, bool invert = false);
 235         void run_BronsonAVLTreeMap(const char *in_name, bool invert = false);
 236         void run_StdMap(const char *in_name, bool invert = false);
 237
 238         virtual void myRun(const char *in_name, bool invert = false);
 239
 240 #   include "map2/map_defs.h"
 241         CDSUNIT_DECLARE_MichaelMap
 242         CDSUNIT_DECLARE_SplitList
 243         CDSUNIT_DECLARE_SkipListMap
 244         CDSUNIT_DECLARE_EllenBinTreeMap
 245         CDSUNIT_DECLARE_BronsonAVLTreeMap
 246         CDSUNIT_DECLARE_StripedMap
 247         CDSUNIT_DECLARE_RefinableMap
 248         CDSUNIT_DECLARE_CuckooMap
 249         CDSUNIT_DECLARE_StdMap
 250     };
 251 } // namespace map2