3 #include "map2/map_type.h"
4 #include "cppunit/thread.h"
9 #define TEST_CASE(TAG, X) void X();
11 class Map_InsDelFind: public CppUnitMini::TestCase
14 size_t c_nMapSize = 500000; // initial map size
15 size_t c_nThreadCount = 8; // thread count
16 size_t c_nMaxLoadFactor = 8; // maximum load factor
17 unsigned int c_nInsertPercentage = 5;
18 unsigned int c_nDeletePercentage = 5;
19 unsigned int c_nDuration = 30; // test duration, seconds
20 bool c_bPrintGCState = true;
22 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooMap
23 size_t c_nCuckooProbesetSize = 16; // CuckooMap probeset size (only for list-based probeset)
24 size_t c_nCuckooProbesetThreshold = 0; // CUckooMap probeset threshold (o - use default)
26 size_t c_nFeldmanMap_HeadBits = 10;
27 size_t c_nFeldmanMap_ArrayBits = 4;
29 size_t c_nLoadFactor = 2; // current load factor
38 static const unsigned int c_nShuffleSize = 100;
39 actions m_arrShuffle[c_nShuffleSize];
42 typedef size_t key_type;
43 typedef size_t value_type;
46 class WorkThread: public CppUnitMini::TestThread
50 virtual WorkThread * clone()
52 return new WorkThread( *this );
55 size_t m_nInsertSuccess;
56 size_t m_nInsertFailed;
57 size_t m_nDeleteSuccess;
58 size_t m_nDeleteFailed;
59 size_t m_nFindSuccess;
63 WorkThread( CppUnitMini::ThreadPool& pool, Map& rMap )
64 : CppUnitMini::TestThread( pool )
67 WorkThread( WorkThread& src )
68 : CppUnitMini::TestThread( src )
72 Map_InsDelFind& getTest()
74 return reinterpret_cast<Map_InsDelFind&>( m_Pool.m_Test );
77 virtual void init() { cds::threading::Manager::attachThread() ; }
78 virtual void fini() { cds::threading::Manager::detachThread() ; }
80 typedef std::pair< key_type const, value_type > map_value_type;
82 struct update_functor {
84 void operator()( bool /*bNew*/, map_value_type& /*cur*/, Q const& /*val*/ )
88 void operator()( map_value_type& /*cur*/, map_value_type * /*old*/)
92 void operator()( bool /*bNew*/, map_value_type& /*cur*/ )
96 void operator()( bool /*bNew*/, key_type /*key*/, value_type& /*val*/ )
111 actions * pAct = getTest().m_arrShuffle;
113 size_t const nNormalize = size_t(-1) / (getTest().c_nMapSize * 2);
116 while ( !time_elapsed() ) {
117 nRand = cds::bitop::RandXorShift(nRand);
118 size_t n = nRand / nNormalize;
121 if ( rMap.contains( n ))
128 if ( rMap.insert( n, n ))
134 if ( rMap.update(n, update_functor(), true ).first )
141 if ( rMap.erase( n ))
148 if ( ++i >= c_nShuffleSize )
156 void do_test( Map& testMap )
158 typedef WorkThread<Map> work_thread;
159 cds::OS::Timer timer;
161 // fill map - only odd number
163 std::vector<size_t> arr;
164 arr.reserve( c_nMapSize );
165 for ( size_t i = 0; i < c_nMapSize; ++i )
166 arr.push_back( i * 2 + 1);
167 shuffle( arr.begin(), arr.end() );
168 for ( size_t i = 0; i < c_nMapSize; ++i )
169 testMap.insert( arr[i], arr[i] );
171 CPPUNIT_MSG( " Insert " << c_nMapSize << " items time (single-threaded)=" << timer.duration() );
174 CppUnitMini::ThreadPool pool( *this );
175 pool.add( new work_thread( pool, testMap ), c_nThreadCount );
176 pool.run( c_nDuration );
177 //CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
179 size_t nInsertSuccess = 0;
180 size_t nInsertFailed = 0;
181 size_t nDeleteSuccess = 0;
182 size_t nDeleteFailed = 0;
183 size_t nFindSuccess = 0;
184 size_t nFindFailed = 0;
185 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
186 work_thread * pThread = static_cast<work_thread *>( *it );
187 assert( pThread != nullptr );
188 nInsertSuccess += pThread->m_nInsertSuccess;
189 nInsertFailed += pThread->m_nInsertFailed;
190 nDeleteSuccess += pThread->m_nDeleteSuccess;
191 nDeleteFailed += pThread->m_nDeleteFailed;
192 nFindSuccess += pThread->m_nFindSuccess;
193 nFindFailed += pThread->m_nFindFailed;
196 size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
198 CPPUNIT_MSG( " Totals (success/failed): \n\t"
199 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
200 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
201 << " Find=" << nFindSuccess << '/' << nFindFailed << "\n\t"
202 << " Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
203 << " " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
204 << " Total ops=" << nTotalOps << "\n\t"
205 << " speed=" << nTotalOps / c_nDuration << " ops/sec\n\t"
206 << " Map size=" << testMap.size()
210 check_before_cleanup( testMap );
212 CPPUNIT_MSG( " Clear map (single-threaded)..." );
215 CPPUNIT_MSG( " Duration=" << timer.duration() );
216 CPPUNIT_ASSERT_EX( testMap.empty(), ((long long) testMap.size()) );
218 additional_check( testMap );
219 print_stat( testMap );
220 additional_cleanup( testMap );
226 CPPUNIT_MSG( "Thread count=" << c_nThreadCount
227 << " initial map size=" << c_nMapSize
228 << " insert=" << c_nInsertPercentage << '%'
229 << " delete=" << c_nDeletePercentage << '%'
230 << " duration=" << c_nDuration << "s"
233 if ( Map::c_bLoadFactorDepended ) {
234 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
235 CPPUNIT_MSG( "Load factor=" << c_nLoadFactor );
236 Map testMap( *this );
238 if ( c_bPrintGCState )
243 Map testMap( *this );
245 if ( c_bPrintGCState )
250 void setUpParams( const CppUnitMini::TestCfg& cfg );
252 # include "map2/map_defs.h"
253 CDSUNIT_DECLARE_MichaelMap
254 CDSUNIT_DECLARE_SplitList
255 CDSUNIT_DECLARE_SkipListMap
256 CDSUNIT_DECLARE_EllenBinTreeMap
257 CDSUNIT_DECLARE_BronsonAVLTreeMap
258 CDSUNIT_DECLARE_FeldmanHashMap_fixed
259 CDSUNIT_DECLARE_FeldmanHashMap_city
260 CDSUNIT_DECLARE_StripedMap
261 CDSUNIT_DECLARE_RefinableMap
262 CDSUNIT_DECLARE_CuckooMap
263 CDSUNIT_DECLARE_StdMap
265 CPPUNIT_TEST_SUITE(Map_InsDelFind)
266 CDSUNIT_TEST_MichaelMap
267 CDSUNIT_TEST_SplitList
268 CDSUNIT_TEST_SkipListMap
269 CDSUNIT_TEST_EllenBinTreeMap
270 CDSUNIT_TEST_BronsonAVLTreeMap
271 CDSUNIT_TEST_FeldmanHashMap_fixed
272 CDSUNIT_TEST_FeldmanHashMap_city
273 CDSUNIT_TEST_CuckooMap
274 CDSUNIT_TEST_StripedMap
275 CDSUNIT_TEST_RefinableMap
277 CPPUNIT_TEST_SUITE_END();