tests/unit/map2/map_insdel_item_int.cpp

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