3 #include "map2/map_types.h"
4 #include "cppunit/thread.h"
5 #include <algorithm> // random_shuffle
10 # define TEST_MAP(X) void X() { test<MapTypes<key_type, value_type>::X >() ; }
11 # define TEST_MAP_NOLF(X) void X() { test_nolf<MapTypes<key_type, value_type>::X >() ; }
12 # define TEST_MAP_EXTRACT(X) TEST_MAP(X)
13 # define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X)
16 static size_t c_nInitialMapSize = 500000 ; // initial map size
17 static size_t c_nThreadCount = 8 ; // thread count
18 static size_t c_nMaxLoadFactor = 8 ; // maximum load factor
19 static unsigned int c_nInsertPercentage = 5;
20 static unsigned int c_nDeletePercentage = 5;
21 static unsigned int c_nDuration = 30 ; // test duration, seconds
22 static bool c_bPrintGCState = true;
25 class Map_InsDelFind: public CppUnitMini::TestCase
34 static const unsigned int c_nShuffleSize = 100;
35 actions m_arrShuffle[c_nShuffleSize];
38 typedef size_t key_type;
39 typedef size_t value_type;
42 class WorkThread: public CppUnitMini::TestThread
46 virtual WorkThread * clone()
48 return new WorkThread( *this );
51 size_t m_nInsertSuccess;
52 size_t m_nInsertFailed;
53 size_t m_nDeleteSuccess;
54 size_t m_nDeleteFailed;
55 size_t m_nFindSuccess;
59 WorkThread( CppUnitMini::ThreadPool& pool, MAP& rMap )
60 : CppUnitMini::TestThread( pool )
63 WorkThread( WorkThread& src )
64 : CppUnitMini::TestThread( src )
68 Map_InsDelFind& getTest()
70 return reinterpret_cast<Map_InsDelFind&>( m_Pool.m_Test );
73 virtual void init() { cds::threading::Manager::attachThread() ; }
74 virtual void fini() { cds::threading::Manager::detachThread() ; }
87 actions * pAct = getTest().m_arrShuffle;
89 size_t const nNormalize = size_t(-1) / (c_nInitialMapSize * 2);
92 while ( !time_elapsed() ) {
93 nRand = cds::bitop::RandXorShift(nRand);
94 size_t n = nRand / nNormalize;
103 if ( rMap.insert( n, n ))
109 if ( rMap.erase( n ))
116 if ( ++i >= c_nShuffleSize )
124 void do_test( MAP& testMap )
126 typedef WorkThread<MAP> work_thread;
127 cds::OS::Timer timer;
129 // fill map - only odd number
131 std::vector<size_t> arr;
132 arr.reserve( c_nInitialMapSize );
133 for ( size_t i = 0; i < c_nInitialMapSize; ++i )
134 arr.push_back( i * 2 + 1);
135 std::random_shuffle( arr.begin(), arr.end() );
136 for ( size_t i = 0; i < c_nInitialMapSize; ++i )
137 testMap.insert( arr[i], arr[i] );
139 CPPUNIT_MSG( " Insert " << c_nInitialMapSize << " items time (single-threaded)=" << timer.duration() );
142 CppUnitMini::ThreadPool pool( *this );
143 pool.add( new work_thread( pool, testMap ), c_nThreadCount );
144 pool.run( c_nDuration );
145 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
147 size_t nInsertSuccess = 0;
148 size_t nInsertFailed = 0;
149 size_t nDeleteSuccess = 0;
150 size_t nDeleteFailed = 0;
151 size_t nFindSuccess = 0;
152 size_t nFindFailed = 0;
153 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
154 work_thread * pThread = static_cast<work_thread *>( *it );
155 assert( pThread != NULL );
156 nInsertSuccess += pThread->m_nInsertSuccess;
157 nInsertFailed += pThread->m_nInsertFailed;
158 nDeleteSuccess += pThread->m_nDeleteSuccess;
159 nDeleteFailed += pThread->m_nDeleteFailed;
160 nFindSuccess += pThread->m_nFindSuccess;
161 nFindFailed += pThread->m_nFindFailed;
164 CPPUNIT_MSG( " Totals (success/failed): \n\t"
165 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
166 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
167 << " Find=" << nFindSuccess << '/' << nFindFailed << "\n\t"
168 << " Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
169 << " " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
170 << " Map size=" << testMap.size()
174 CPPUNIT_MSG( " Clear map (single-threaded)..." );
177 CPPUNIT_MSG( " Duration=" << timer.duration() );
178 CPPUNIT_ASSERT_EX( testMap.empty(), ((long long) testMap.size()) );
180 additional_check( testMap );
181 print_stat( testMap );
182 additional_cleanup( testMap );
188 CPPUNIT_MSG( "Thread count=" << c_nThreadCount
189 << " initial map size=" << c_nInitialMapSize
190 << " insert=" << c_nInsertPercentage << '%'
191 << " delete=" << c_nDeletePercentage << '%'
192 << " duration=" << c_nDuration << "s"
195 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
196 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
197 MAP testMap( c_nInitialMapSize, nLoadFactor );
199 if ( c_bPrintGCState )
208 CPPUNIT_MSG( "Thread count=" << c_nThreadCount
209 << " initial map size=" << c_nInitialMapSize
210 << " insert=" << c_nInsertPercentage << '%'
211 << " delete=" << c_nDeletePercentage << '%'
212 << " duration=" << c_nDuration << "s"
217 if ( c_bPrintGCState )
221 void setUpParams( const CppUnitMini::TestCfg& cfg ) {
222 c_nInitialMapSize = cfg.getULong("InitialMapSize", 500000 );
223 c_nThreadCount = cfg.getULong("ThreadCount", 8 );
224 c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 );
225 c_nInsertPercentage = cfg.getUInt("InsertPercentage", 5 );
226 c_nDeletePercentage = cfg.getUInt("DeletePercentage", 5 );
227 c_nDuration = cfg.getUInt("Duration", 30 );
228 c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
230 if ( c_nThreadCount == 0 )
231 c_nThreadCount = cds::OS::topology::processor_count() * 2;
233 CPPUNIT_ASSERT( c_nInsertPercentage + c_nDeletePercentage <= 100 );
235 actions * pFirst = m_arrShuffle;
236 actions * pLast = m_arrShuffle + c_nInsertPercentage;
237 std::fill( pFirst, pLast, do_insert );
239 pLast += c_nDeletePercentage;
240 std::fill( pFirst, pLast, do_delete );
242 pLast = m_arrShuffle + sizeof(m_arrShuffle)/sizeof(m_arrShuffle[0]);
243 std::fill( pFirst, pLast, do_find );
244 std::random_shuffle( m_arrShuffle, pLast );
247 # include "map2/map_defs.h"
248 CDSUNIT_DECLARE_MichaelMap
249 CDSUNIT_DECLARE_SplitList
250 CDSUNIT_DECLARE_SkipListMap
251 CDSUNIT_DECLARE_EllenBinTreeMap
252 CDSUNIT_DECLARE_StripedMap
253 CDSUNIT_DECLARE_RefinableMap
254 CDSUNIT_DECLARE_CuckooMap
255 CDSUNIT_DECLARE_StdMap
257 CPPUNIT_TEST_SUITE( Map_InsDelFind )
258 CDSUNIT_TEST_MichaelMap
259 CDSUNIT_TEST_SplitList
260 CDSUNIT_TEST_SkipListMap
261 CDSUNIT_TEST_EllenBinTreeMap
262 CDSUNIT_TEST_StripedMap
263 CDSUNIT_TEST_RefinableMap
264 CDSUNIT_TEST_CuckooMap
266 CPPUNIT_TEST_SUITE_END()
269 CPPUNIT_TEST_SUITE_REGISTRATION( Map_InsDelFind );