tests/unit/map2/map_insdel_item_string.cpp

   1 //$$CDS-header$$
   2
   3 #include "map2/map_types.h"
   4 #include "cppunit/thread.h"
   5
   6 #include <vector>
   7
   8 namespace map2 {
   9
  10 #   define TEST_MAP(X)         void X() { test<MapTypes<key_type, value_type>::X >()    ; }
  11 #   define TEST_MAP_NOLF(X)    void X() { test_nolf<MapTypes<key_type, value_type>::X >()    ; }
  12 #   define TEST_MAP_EXTRACT(X)  TEST_MAP(X)
  13 #   define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
  14
  15     namespace {
  16         static size_t  c_nMapSize = 1000000    ;  // map size
  17         static size_t  c_nThreadCount = 4      ;  // thread count
  18         static size_t  c_nGoalItem = c_nMapSize / 2;
  19         static size_t  c_nAttemptCount = 100000       ;   // count of SUCCESS insert/delete for each thread
  20         static size_t  c_nMaxLoadFactor = 8    ;  // maximum load factor
  21         static bool    c_bPrintGCState = true;
  22     }
  23
  24     class Map_InsDel_Item_string: public CppUnitMini::TestCase
  25     {
  26         typedef std::string  key_type;
  27         typedef size_t  value_type;
  28
  29         const std::vector<std::string> *  m_parrString;
  30
  31         template <class Map>
  32         class Inserter: public CppUnitMini::TestThread
  33         {
  34             Map&     m_Map;
  35
  36             virtual Inserter *    clone()
  37             {
  38                 return new Inserter( *this );
  39             }
  40         public:
  41             size_t  m_nInsertSuccess;
  42             size_t  m_nInsertFailed;
  43
  44         public:
  45             Inserter( CppUnitMini::ThreadPool& pool, Map& rMap )
  46                 : CppUnitMini::TestThread( pool )
  47                 , m_Map( rMap )
  48             {}
  49             Inserter( Inserter& src )
  50                 : CppUnitMini::TestThread( src )
  51                 , m_Map( src.m_Map )
  52             {}
  53
  54             Map_InsDel_Item_string&  getTest()
  55             {
  56                 return reinterpret_cast<Map_InsDel_Item_string&>( m_Pool.m_Test );
  57             }
  58
  59             virtual void init() { cds::threading::Manager::attachThread()   ; }
  60             virtual void fini() { cds::threading::Manager::detachThread()   ; }
  61
  62             virtual void test()
  63             {
  64                 Map& rMap = m_Map;
  65
  66                 m_nInsertSuccess =
  67                     m_nInsertFailed = 0;
  68
  69                 size_t nGoalItem = c_nGoalItem;
  70                 std::string strGoal = (*getTest().m_parrString)[nGoalItem];
  71
  72                 for ( size_t nAttempt = 0; nAttempt < c_nAttemptCount; ) {
  73                     if ( rMap.insert( strGoal, nGoalItem )) {
  74                         ++m_nInsertSuccess;
  75                         ++nAttempt;
  76                     }
  77                     else
  78                         ++m_nInsertFailed;
  79                 }
  80             }
  81         };
  82
  83         template <class Map>
  84         class Deleter: public CppUnitMini::TestThread
  85         {
  86             Map&     m_Map;
  87
  88             struct erase_cleaner {
  89                 void operator ()(std::pair<typename Map::key_type const, typename Map::mapped_type>& val )
  90                 {
  91                     val.second = 0;
  92                 }
  93                 // for boost::container::flat_map
  94                 void operator ()(std::pair< typename std::remove_const< typename Map::key_type >::type, typename Map::mapped_type>& val )
  95                 {
  96                     val.second = 0;
  97                 }
  98                 // for BronsonAVLTreeMap
  99                 void operator()( typename Map::mapped_type& val )
 100                 {
 101                     val = 0;
 102                 }
 103             };
 104
 105             virtual Deleter *    clone()
 106             {
 107                 return new Deleter( *this );
 108             }
 109         public:
 110             size_t  m_nDeleteSuccess;
 111             size_t  m_nDeleteFailed;
 112
 113         public:
 114             Deleter( CppUnitMini::ThreadPool& pool, Map& rMap )
 115                 : CppUnitMini::TestThread( pool )
 116                 , m_Map( rMap )
 117             {}
 118             Deleter( Deleter& src )
 119                 : CppUnitMini::TestThread( src )
 120                 , m_Map( src.m_Map )
 121             {}
 122
 123             Map_InsDel_Item_string&  getTest()
 124             {
 125                 return reinterpret_cast<Map_InsDel_Item_string&>( m_Pool.m_Test );
 126             }
 127
 128             virtual void init() { cds::threading::Manager::attachThread()   ; }
 129             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 130
 131             virtual void test()
 132             {
 133                 Map& rMap = m_Map;
 134
 135                 m_nDeleteSuccess =
 136                     m_nDeleteFailed = 0;
 137
 138                 size_t nGoalItem = c_nGoalItem;
 139                 std::string strGoal = (*getTest().m_parrString)[nGoalItem];
 140
 141                 for ( size_t nAttempt = 0; nAttempt < c_nAttemptCount; ) {
 142                     if ( rMap.erase( strGoal, erase_cleaner() )) {
 143                         ++m_nDeleteSuccess;
 144                         ++nAttempt;
 145                     }
 146                     else
 147                         ++m_nDeleteFailed;
 148                 }
 149             }
 150         };
 151
 152     protected:
 153
 154         template <class Map>
 155         void do_test( Map& testMap )
 156         {
 157             typedef Inserter<Map>       InserterThread;
 158             typedef Deleter<Map>        DeleterThread;
 159             cds::OS::Timer    timer;
 160
 161             // Fill the map
 162             CPPUNIT_MSG( "  Fill map (" << c_nMapSize << " items)...");
 163             timer.reset();
 164             for ( size_t i = 0; i < c_nMapSize; ++i ) {
 165                 CPPUNIT_ASSERT_EX( testMap.insert( (*m_parrString)[i], i ), i );
 166             }
 167             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 168
 169             CPPUNIT_MSG( "  Insert/delete the key " << c_nGoalItem << " (" << c_nAttemptCount << " successful times)...");
 170             CppUnitMini::ThreadPool pool( *this );
 171             pool.add( new InserterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 172             pool.add( new DeleterThread( pool, testMap ), (c_nThreadCount + 1) / 2 );
 173             pool.run();
 174             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 175
 176             size_t nInsertSuccess = 0;
 177             size_t nInsertFailed = 0;
 178             size_t nDeleteSuccess = 0;
 179             size_t nDeleteFailed = 0;
 180             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 181                 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
 182                 if ( pThread ) {
 183                     CPPUNIT_CHECK( pThread->m_nInsertSuccess == c_nAttemptCount );
 184                     nInsertSuccess += pThread->m_nInsertSuccess;
 185                     nInsertFailed += pThread->m_nInsertFailed;
 186                 }
 187                 else {
 188                     DeleterThread * p = static_cast<DeleterThread *>( *it );
 189                     CPPUNIT_CHECK( p->m_nDeleteSuccess == c_nAttemptCount );
 190                     nDeleteSuccess += p->m_nDeleteSuccess;
 191                     nDeleteFailed += p->m_nDeleteFailed;
 192                 }
 193             }
 194             CPPUNIT_CHECK_EX( nInsertSuccess == nDeleteSuccess, "nInsertSuccess=" << nInsertSuccess << ", nDeleteSuccess=" << nDeleteSuccess );
 195             CPPUNIT_MSG( "    Totals: Ins fail=" << nInsertFailed << " Del fail=" << nDeleteFailed );
 196
 197             // Check if the map contains all items
 198             CPPUNIT_MSG( "    Check if the map contains all items" );
 199             timer.reset();
 200             for ( size_t i = 0; i < c_nMapSize; ++i ) {
 201                 CPPUNIT_CHECK_EX( testMap.find( (*m_parrString)[i] ), "Key \"" << (*m_parrString)[i] << "\" not found" );
 202             }
 203             CPPUNIT_MSG( "    Duration=" << timer.duration() );
 204
 205             testMap.clear();
 206             additional_check( testMap );
 207             print_stat( testMap );
 208             additional_cleanup( testMap );
 209         }
 210
 211         template <class Map>
 212         void test()
 213         {
 214             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 215             if ( c_nMapSize > m_parrString->size() )
 216                 c_nMapSize = m_parrString->size();
 217             if ( c_nGoalItem > m_parrString->size() )
 218                 c_nGoalItem = m_parrString->size() / 2;
 219
 220             CPPUNIT_MSG( "Thread count= " << c_nThreadCount
 221                 << " pass count=" << c_nAttemptCount
 222                 << " map size=" << c_nMapSize
 223                 );
 224
 225             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 226                 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 227                 Map  testMap( c_nMapSize, nLoadFactor );
 228                 do_test( testMap );
 229                 if ( c_bPrintGCState )
 230                     print_gc_state();
 231             }
 232         }
 233
 234         template <typename Map>
 235         void test_nolf()
 236         {
 237             m_parrString = &CppUnitMini::TestCase::getTestStrings();
 238             if ( c_nMapSize > m_parrString->size() )
 239                 c_nMapSize = m_parrString->size();
 240             if ( c_nGoalItem > m_parrString->size() )
 241                 c_nGoalItem = m_parrString->size() / 2;
 242
 243             CPPUNIT_MSG( "Thread count= " << c_nThreadCount
 244                 << " pass count=" << c_nAttemptCount
 245                 << " map size=" << c_nMapSize
 246                 );
 247
 248             Map testMap;
 249             do_test( testMap );
 250             if ( c_bPrintGCState )
 251                 print_gc_state();
 252         }
 253
 254         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 255             c_nThreadCount = cfg.getULong("ThreadCount", 8 )        ; // thread count
 256             c_nMapSize = cfg.getULong("MapSize", 1000000 );
 257             c_nGoalItem = cfg.getULong("GoalItemIndex", (unsigned long) (c_nMapSize / 2) );
 258             c_nAttemptCount = cfg.getULong("AttemptCount", 100000 );
 259             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 260             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 261         }
 262
 263 #   include "map2/map_defs.h"
 264         CDSUNIT_DECLARE_MichaelMap
 265         CDSUNIT_DECLARE_SplitList
 266         CDSUNIT_DECLARE_SkipListMap
 267         CDSUNIT_DECLARE_EllenBinTreeMap
 268         CDSUNIT_DECLARE_BronsonAVLTreeMap
 269         CDSUNIT_DECLARE_StripedMap
 270         CDSUNIT_DECLARE_RefinableMap
 271         CDSUNIT_DECLARE_CuckooMap
 272         CDSUNIT_DECLARE_StdMap
 273
 274         CPPUNIT_TEST_SUITE( Map_InsDel_Item_string )
 275             CDSUNIT_TEST_MichaelMap
 276             CDSUNIT_TEST_SplitList
 277             CDSUNIT_TEST_SkipListMap
 278             CDSUNIT_TEST_EllenBinTreeMap
 279             CDSUNIT_TEST_BronsonAVLTreeMap
 280             CDSUNIT_TEST_StripedMap
 281             CDSUNIT_TEST_RefinableMap
 282             CDSUNIT_TEST_CuckooMap
 283             //CDSUNIT_TEST_StdMap       // very slow!!!
 284         CPPUNIT_TEST_SUITE_END()
 285
 286     };
 287
 288     CPPUNIT_TEST_SUITE_REGISTRATION( Map_InsDel_Item_string );
 289 } // namespace map2