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