3 // defines concurrent access to map::nonconcurrent_iterator::Sequence::TValue::nAccess field
5 #include "map2/map_types.h"
6 #include "cppunit/thread.h"
9 #include <algorithm> // random_shuffle
11 // find int test in map<int> in mutithreaded mode
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)
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;
28 class Map_find_int: public CppUnitMini::TestCase
30 typedef size_t key_type;
32 key_type nKey ; // key
33 bool bExists ; // true - key in map, false - key not in map
36 typedef std::vector<value_type> ValueVector;
38 size_t m_nRealMapSize;
39 bool m_bSequenceInitialized;
41 void generateSequence()
43 size_t nPercent = c_nPercentExists;
47 else if ( nPercent < 1 )
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 )
59 std::random_shuffle( m_Arr.begin(), m_Arr.end() );
62 template <typename Iterator, typename Map>
63 static bool check_result( Iterator const& it, Map const& map )
65 return it != map.end();
67 template <typename Map>
68 static bool check_result( bool b, Map const& )
74 class TestThread: public CppUnitMini::TestThread
78 virtual TestThread * clone()
80 return new TestThread( *this );
97 TestThread( CppUnitMini::ThreadPool& pool, Map& rMap )
98 : CppUnitMini::TestThread( pool )
101 TestThread( TestThread& src )
102 : CppUnitMini::TestThread( src )
106 Map_find_int& getTest()
108 return reinterpret_cast<Map_find_int&>( m_Pool.m_Test );
111 virtual void init() { cds::threading::Manager::attachThread() ; }
112 virtual void fini() { cds::threading::Manager::detachThread() ; }
116 ValueVector& arr = getTest().m_Arr;
117 //size_t nSize = arr.size();
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 );
126 if ( check_result( bFound, rMap ))
127 ++m_KeyExists.nSuccess;
129 //rMap.find( it->nKey );
130 ++m_KeyExists.nFailed;
134 if ( check_result( bFound, rMap )) {
135 //rMap.find( it->nKey );
136 ++m_KeyNotExists.nFailed;
139 ++m_KeyNotExists.nSuccess;
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 );
148 if ( check_result( bFound, rMap ))
149 ++m_KeyExists.nSuccess;
151 //rMap.find( it->nKey );
152 ++m_KeyExists.nFailed;
156 if ( check_result( bFound, rMap )) {
157 //rMap.find( it->nKey );
158 ++m_KeyNotExists.nFailed;
161 ++m_KeyNotExists.nSuccess;
172 void find_int_test( Map& testMap )
174 typedef TestThread<Map> Thread;
175 cds::OS::Timer timer;
178 CPPUNIT_MSG( " Fill map with " << m_Arr.size() << " items...");
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 ));
185 CPPUNIT_MSG( " Duration=" << timer.duration() );
187 CPPUNIT_MSG( " Searching...");
188 CppUnitMini::ThreadPool pool( *this );
189 pool.add( new Thread( pool, testMap ), c_nThreadCount );
191 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
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 );
202 additional_check( testMap );
203 print_stat( testMap );
204 additional_cleanup( testMap );
207 void initTestSequence()
209 CPPUNIT_MSG( "Generating test data...");
210 cds::OS::Timer timer;
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 );
216 m_bSequenceInitialized = true;
222 if ( !m_bSequenceInitialized )
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 )
237 if ( !m_bSequenceInitialized )
241 find_int_test( testMap );
242 if ( c_bPrintGCState )
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 );
258 : m_bSequenceInitialized( false )
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
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
286 CPPUNIT_TEST_SUITE_END()
289 CPPUNIT_TEST_SUITE_REGISTRATION( Map_find_int );