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 <class Map>
  63         class TestThread: public CppUnitMini::TestThread
  64         {
  65             Map&     m_Map;
  66
  67             virtual TestThread *    clone()
  68             {
  69                 return new TestThread( *this );
  70             }
  71         public:
  72             struct Stat {
  73                 size_t      nSuccess;
  74                 size_t      nFailed;
  75
  76                 Stat()
  77                     : nSuccess(0)
  78                     , nFailed(0)
  79                 {}
  80             };
  81
  82             Stat    m_KeyExists;
  83             Stat    m_KeyNotExists;
  84
  85         public:
  86             TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
  87                 : CppUnitMini::TestThread( pool )
  88                 , m_Map( rMap )
  89             {}
  90             TestThread( TestThread& src )
  91                 : CppUnitMini::TestThread( src )
  92                 , m_Map( src.m_Map )
  93             {}
  94
  95             Map_find_int&  getTest()
  96             {
  97                 return reinterpret_cast<Map_find_int&>( m_Pool.m_Test );
  98             }
  99
 100             virtual void init() { cds::threading::Manager::attachThread()   ; }
 101             virtual void fini() { cds::threading::Manager::detachThread()   ; }
 102
 103             virtual void test()
 104             {
 105                 ValueVector& arr = getTest().m_Arr;
 106                 //size_t nSize = arr.size();
 107
 108                 Map& rMap = m_Map;
 109                 for ( size_t nPass = 0; nPass < c_nPassCount; ++nPass ) {
 110                     if ( m_nThreadNo & 1 ) {
 111                         ValueVector::const_iterator itEnd = arr.end();
 112                         for ( ValueVector::const_iterator it = arr.begin(); it != itEnd; ++it ) {
 113                             bool bFound = rMap.find( it->nKey );
 114                             if ( it->bExists ) {
 115                                 if ( bFound )
 116                                     ++m_KeyExists.nSuccess;
 117                                 else {
 118                                     //rMap.find( it->nKey );
 119                                     ++m_KeyExists.nFailed;
 120                                 }
 121                             }
 122                             else {
 123                                 if ( bFound ) {
 124                                     //rMap.find( it->nKey );
 125                                     ++m_KeyNotExists.nFailed;
 126                                 }
 127                                 else
 128                                     ++m_KeyNotExists.nSuccess;
 129                             }
 130                         }
 131                     }
 132                     else {
 133                         ValueVector::const_reverse_iterator itEnd = arr.rend();
 134                         for ( ValueVector::const_reverse_iterator it = arr.rbegin(); it != itEnd; ++it ) {
 135                             bool bFound = rMap.find( it->nKey );
 136                             if ( it->bExists ) {
 137                                 if ( bFound )
 138                                     ++m_KeyExists.nSuccess;
 139                                 else {
 140                                     //rMap.find( it->nKey );
 141                                     ++m_KeyExists.nFailed;
 142                                 }
 143                             }
 144                             else {
 145                                 if ( bFound ) {
 146                                     //rMap.find( it->nKey );
 147                                     ++m_KeyNotExists.nFailed;
 148                                 }
 149                                 else
 150                                     ++m_KeyNotExists.nSuccess;
 151                             }
 152                         }
 153                     }
 154                 }
 155             }
 156         };
 157
 158     protected:
 159
 160         template <class Map>
 161         void find_int_test( Map& testMap )
 162         {
 163             typedef TestThread<Map>     Thread;
 164             cds::OS::Timer    timer;
 165
 166             // Fill the map
 167             CPPUNIT_MSG( "  Fill map with " << m_Arr.size() << " items...");
 168             timer.reset();
 169             for ( size_t i = 0; i < m_Arr.size(); ++i ) {
 170                 if ( m_Arr[i].bExists ) {
 171                     CPPUNIT_ASSERT( testMap.insert( m_Arr[i].nKey, m_Arr[i] ) );
 172                 }
 173             }
 174             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 175
 176             CPPUNIT_MSG( "  Searching...");
 177             CppUnitMini::ThreadPool pool( *this );
 178             pool.add( new Thread( pool, testMap ), c_nThreadCount );
 179             pool.run();
 180             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 181
 182             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 183                 Thread * pThread = static_cast<Thread *>( *it );
 184                 CPPUNIT_ASSERT( pThread->m_KeyExists.nFailed == 0 );
 185                 CPPUNIT_ASSERT( pThread->m_KeyExists.nSuccess == m_nRealMapSize * c_nPassCount );
 186                 CPPUNIT_ASSERT( pThread->m_KeyNotExists.nFailed == 0 );
 187                 CPPUNIT_ASSERT( pThread->m_KeyNotExists.nSuccess == (m_Arr.size() - m_nRealMapSize) * c_nPassCount );
 188             }
 189
 190             testMap.clear();
 191             additional_check( testMap );
 192             print_stat( testMap );
 193             additional_cleanup( testMap );
 194         }
 195
 196         void initTestSequence()
 197         {
 198             CPPUNIT_MSG( "Generating test data...");
 199             cds::OS::Timer    timer;
 200             generateSequence();
 201             CPPUNIT_MSG( "   Duration=" << timer.duration() );
 202             CPPUNIT_MSG( "Map size=" << m_nRealMapSize << " find key loop=" << m_Arr.size() << " (" << c_nPercentExists << "% success)" );
 203             CPPUNIT_MSG( "Thread count=" << c_nThreadCount << " Pass count=" << c_nPassCount );
 204
 205             m_bSequenceInitialized = true;
 206         }
 207
 208         template <class Map>
 209         void test()
 210         {
 211             if ( !m_bSequenceInitialized )
 212                 initTestSequence();
 213
 214             for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
 215                 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
 216                 Map  testMap( c_nMapSize, nLoadFactor );
 217                 find_int_test( testMap );
 218                 if ( c_bPrintGCState )
 219                     print_gc_state();
 220             }
 221         }
 222
 223         template <class Map>
 224         void test_nolf()
 225         {
 226             if ( !m_bSequenceInitialized )
 227                 initTestSequence();
 228
 229             Map testMap;
 230             find_int_test( testMap );
 231             if ( c_bPrintGCState )
 232                 print_gc_state();
 233         }
 234
 235         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 236             c_nThreadCount = cfg.getULong("ThreadCount", 8 )        ; // thread count
 237             c_nMapSize = cfg.getULong("MapSize", 20000000 )         ;  // map size (count of searching item)
 238             c_nPercentExists = cfg.getULong("PercentExists", 50 )   ;  // percent of existing keys in searching sequence
 239             c_nPassCount = cfg.getULong("PassCount", 2 );
 240             c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
 241             c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
 242         }
 243
 244
 245     public:
 246         Map_find_int()
 247             : m_bSequenceInitialized( false )
 248         {}
 249
 250 #   include "map2/map_defs.h"
 251         CDSUNIT_DECLARE_MichaelMap
 252         CDSUNIT_DECLARE_MichaelMap_nogc
 253         CDSUNIT_DECLARE_SplitList
 254         CDSUNIT_DECLARE_SplitList_nogc
 255         CDSUNIT_DECLARE_SkipListMap
 256         CDSUNIT_DECLARE_SkipListMap_nogc
 257         CDSUNIT_DECLARE_EllenBinTreeMap
 258         CDSUNIT_DECLARE_StripedMap
 259         CDSUNIT_DECLARE_RefinableMap
 260         CDSUNIT_DECLARE_CuckooMap
 261         CDSUNIT_DECLARE_StdMap
 262
 263         CPPUNIT_TEST_SUITE( Map_find_int )
 264             CDSUNIT_TEST_MichaelMap
 265             CDSUNIT_TEST_MichaelMap_nogc
 266             CDSUNIT_TEST_SplitList
 267             CDSUNIT_TEST_SplitList_nogc
 268             CDSUNIT_TEST_SkipListMap
 269             CDSUNIT_TEST_SkipListMap_nogc
 270             CDSUNIT_TEST_EllenBinTreeMap
 271             CDSUNIT_TEST_StripedMap
 272             CDSUNIT_TEST_RefinableMap
 273             CDSUNIT_TEST_CuckooMap
 274             CDSUNIT_TEST_StdMap
 275         CPPUNIT_TEST_SUITE_END()
 276     };
 277
 278     CPPUNIT_TEST_SUITE_REGISTRATION( Map_find_int );
 279 } // namespace map