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