tests/unit/map2/map_find_int.cpp

   1 //$$CDS-header$$
   2
   3 // defines concurrent access to map::nonconcurrent_iterator::Sequence::TValue::nAccess field
   4
   5 #include "map2/map_types.h"
   6 #include "cppunit/thread.h"
   7
   8 #include <vector>
   9 #include <algorithm> // random_shuffle
  10
  11 // find int test in map<int> in mutithreaded mode
  12 namespace map2 {
  13
  14 #   define TEST_MAP(X)         void X() { test<MapTypes<key_type, value_type>::X >()    ; }
  15 #   define TEST_MAP_NOLF(X)    void X() { test_nolf<MapTypes<key_type, value_type>::X >()    ; }
  16 #   define TEST_MAP_EXTRACT(X)  TEST_MAP(X)
  17 #   define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
  18
  19     namespace {
  20         static size_t  c_nThreadCount = 8      ;  // thread count
  21         static size_t  c_nMapSize = 20000000   ;  // map size (count of searching item)
  22         static size_t  c_nPercentExists = 50   ;  // percent of existing keys in searching sequence
  23         static size_t  c_nPassCount = 2;
  24         static size_t  c_nMaxLoadFactor = 8    ;  // maximum load factor
  25         static bool    c_bPrintGCState = true;
  26     }
  27
  28     class Map_find_int: public CppUnitMini::TestCase
  29     {
  30         typedef size_t   key_type;
  31         struct value_type {
  32             key_type    nKey    ;   // key
  33             bool        bExists ;   // true - key in map, false - key not in map
  34         };
  35
  36         typedef std::vector<value_type> ValueVector;
  37         ValueVector             m_Arr;
  38         size_t                  m_nRealMapSize;
  39         bool                    m_bSequenceInitialized;
  40
  41         void generateSequence()
  42         {
  43             size_t nPercent = c_nPercentExists;
  44
  45             if ( nPercent > 100 )
  46                 nPercent = 100;
  47             else if ( nPercent < 1 )
  48                 nPercent = 1;
  49
  50             m_nRealMapSize = 0;
  51
  52             m_Arr.resize( c_nMapSize );
  53             for ( size_t i = 0; i < c_nMapSize; ++i ) {
  54                 m_Arr[i].nKey = i * 13;
  55                 m_Arr[i].bExists = CppUnitMini::Rand( 100 ) <= nPercent;
  56                 if ( m_Arr[i].bExists )
  57                     ++m_nRealMapSize;
  58             }
  59             std::random_shuffle( m_Arr.begin(), m_Arr.end() );
  60         }
  61
  62         template <typename Iterator, typename Map>
  63         static bool check_result( Iterator const& it, Map const& map )
  64         {
  65             return it != map.end();
  66         }
  67         template <typename Map>
  68         static bool check_result( bool b, Map const& )
  69         {
  70             return b;
  71         }
  72
  73         template <class Map>
  74         class TestThread: public CppUnitMini::TestThread
  75         {
  76             Map&     m_Map;
  77
  78             virtual TestThread *    clone()
  79             {
  80                 return new TestThread( *this );
  81             }
  82         public:
  83             struct Stat {
  84                 size_t      nSuccess;
  85                 size_t      nFailed;
  86
  87                 Stat()
  88                     : nSuccess(0)
  89                     , nFailed(0)
  90                 {}
  91             };
  92
  93             Stat    m_KeyExists;
  94             Stat    m_KeyNotExists;
  95
  96         public:
  97             TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
  98                 : CppUnitMini::TestThread( pool )
  99                 , m_Map( rMap )
 100             {}
 101             TestThread( TestThread& src )
 102                 : CppUnitMini::TestThread( src )
 103                 , m_Map( src.m_Map )
 104             {}
 105
 106             Map_find_int&  getTest()
 107             {
 108                 return reinterpret_cast<Map_find_int&>( m_Pool.m_Test );
 109             }
 110
 111             virtual void init() { cds::threading::Manager::attachThread()   ; }
 112             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 113
 114             virtual void test()
 115             {
 116                 ValueVector& arr = getTest().m_Arr;
 117                 //size_t nSize = arr.size();
 118
 119                 Map& rMap = m_Map;
 120                 for ( size_t nPass = 0; nPass < c_nPassCount; ++nPass ) {
 121                     if ( m_nThreadNo & 1 ) {
 122                         ValueVector::const_iterator itEnd = arr.end();
 123                         for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
 124                             auto bFound = rMap.find( it->nKey );
 125                             if ( it->bExists ) {
 126                                 if ( check_result( bFound, rMap ))
 127                                     ++m_KeyExists.nSuccess;
 128                                 else {
 129                                     //rMap.find( it->nKey );
 130                                     ++m_KeyExists.nFailed;
 131                                 }
 132                             }
 133                             else {
 134                                 if ( check_result( bFound, rMap )) {
 135                                     //rMap.find( it->nKey );
 136                                     ++m_KeyNotExists.nFailed;
 137                                 }
 138                                 else
 139                                     ++m_KeyNotExists.nSuccess;
 140                             }
 141                         }
 142                     }
 143                     else {
 144                         ValueVector::const_reverse_iterator itEnd = arr.rend();
 145                         for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
 146                             auto bFound = rMap.find( it->nKey );
 147                             if ( it->bExists ) {
 148                                 if ( check_result( bFound, rMap ))
 149                                     ++m_KeyExists.nSuccess;
 150                                 else {
 151                                     //rMap.find( it->nKey );
 152                                     ++m_KeyExists.nFailed;
 153                                 }
 154                             }
 155                             else {
 156                                 if ( check_result( bFound, rMap )) {
 157                                     //rMap.find( it->nKey );
 158                                     ++m_KeyNotExists.nFailed;
 159                                 }
 160                                 else
 161                                     ++m_KeyNotExists.nSuccess;
 162                             }
 163                         }
 164                     }
 165                 }
 166             }
 167         };
 168
 169     protected:
 170
 171         template <class Map>
 172         void find_int_test( Map& testMap )
 173         {
 174             typedef TestThread<Map>     Thread;
 175             cds::OS::Timer    timer;
 176
 177             // Fill the map
 178             CPPUNIT_MSG( "  Fill map with " << m_Arr.size() << " items...");
 179             timer.reset();
 180             for ( size_t i = 0; i < m_Arr.size(); ++i ) {
 181                 if ( m_Arr[i].bExists ) {
 182                     CPPUNIT_ASSERT( check_result( testMap.insert( m_Arr[i].nKey, m_Arr[i] ), testMap ));
 183                 }
 184             }
 185             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 186
 187             CPPUNIT_MSG( "  Searching...");
 188             CppUnitMini::ThreadPool pool( *this );
 189             pool.add( new Thread( pool, testMap ), c_nThreadCount );
 190             pool.run();
 191             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 192
 193             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 194                 Thread * pThread = static_cast<Thread *>( *it );
 195                 CPPUNIT_ASSERT( pThread->m_KeyExists.nFailed == 0 );
 196                 CPPUNIT_ASSERT( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
 197                 CPPUNIT_ASSERT( pThread->m_KeyNotExists.nFailed == 0 );
 198                 CPPUNIT_ASSERT( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
 199             }
 200
 201             testMap.clear();
 202             additional_check( testMap );
 203             print_stat( testMap );
 204             additional_cleanup( testMap );
 205         }
 206
 207         void initTestSequence()
 208         {
 209             CPPUNIT_MSG( "Generating test data...");
 210             cds::OS::Timer    timer;
 211             generateSequence();
 212             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 213             CPPUNIT_MSG( "Map size=" << m_nRealMapSize << " find key loop=" << m_Arr.size() << " (" << c_nPercentExists << "% success)" );
 214             CPPUNIT_MSG( "Thread count=" << c_nThreadCount << " Pass count=" << c_nPassCount );
 215
 216             m_bSequenceInitialized = true;
 217         }
 218
 219         template <class Map>
 220         void test()
 221         {
 222             if ( !m_bSequenceInitialized )
 223                 initTestSequence();
 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                 find_int_test( testMap );
 229                 if ( c_bPrintGCState )
 230                     print_gc_state();
 231             }
 232         }
 233
 234         template <class Map>
 235         void test_nolf()
 236         {
 237             if ( !m_bSequenceInitialized )
 238                 initTestSequence();
 239
 240             Map testMap;
 241             find_int_test( testMap );
 242             if ( c_bPrintGCState )
 243                 print_gc_state();
 244         }
 245
 246         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 247             c_nThreadCount = cfg.getULong("ThreadCount", 8 )        ; // thread count
 248             c_nMapSize = cfg.getULong("MapSize", 20000000 )         ;  // map size (count of searching item)
 249             c_nPercentExists = cfg.getULong("PercentExists", 50 )   ;  // percent of existing keys in searching sequence
 250             c_nPassCount = cfg.getULong("PassCount", 2 );
 251             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 252             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 253         }
 254
 255
 256     public:
 257         Map_find_int()
 258             : m_bSequenceInitialized( false )
 259         {}
 260
 261 #   include "map2/map_defs.h"
 262         CDSUNIT_DECLARE_MichaelMap
 263         CDSUNIT_DECLARE_MichaelMap_nogc
 264         CDSUNIT_DECLARE_SplitList
 265         CDSUNIT_DECLARE_SplitList_nogc
 266         CDSUNIT_DECLARE_SkipListMap
 267         CDSUNIT_DECLARE_SkipListMap_nogc
 268         CDSUNIT_DECLARE_EllenBinTreeMap
 269         CDSUNIT_DECLARE_StripedMap
 270         CDSUNIT_DECLARE_RefinableMap
 271         CDSUNIT_DECLARE_CuckooMap
 272         CDSUNIT_DECLARE_StdMap
 273
 274         CPPUNIT_TEST_SUITE( Map_find_int )
 275             CDSUNIT_TEST_MichaelMap
 276             CDSUNIT_TEST_MichaelMap_nogc
 277             CDSUNIT_TEST_SplitList
 278             CDSUNIT_TEST_SplitList_nogc
 279             CDSUNIT_TEST_SkipListMap
 280             CDSUNIT_TEST_SkipListMap_nogc
 281             CDSUNIT_TEST_EllenBinTreeMap
 282             CDSUNIT_TEST_StripedMap
 283             CDSUNIT_TEST_RefinableMap
 284             CDSUNIT_TEST_CuckooMap
 285             CDSUNIT_TEST_StdMap
 286         CPPUNIT_TEST_SUITE_END()
 287     };
 288
 289     CPPUNIT_TEST_SUITE_REGISTRATION( Map_find_int );
 290 } // namespace map