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