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)
15 class Map_InsDelFind: public CppUnitMini::TestCase
17 static size_t c_nInitialMapSize; // initial map size
18 static size_t c_nThreadCount; // thread count
19 static size_t c_nMaxLoadFactor; // maximum load factor
20 static unsigned int c_nInsertPercentage;
21 static unsigned int c_nDeletePercentage;
22 static unsigned int c_nDuration; // test duration, seconds
23 static bool c_bPrintGCState;
32 static const unsigned int c_nShuffleSize = 100;
33 actions m_arrShuffle[c_nShuffleSize];
36 typedef CppUnitMini::TestCase Base;
37 typedef size_t key_type;
38 typedef size_t value_type;
41 class WorkThread: public CppUnitMini::TestThread
45 virtual WorkThread * clone()
47 return new WorkThread( *this );
50 size_t m_nInsertSuccess;
51 size_t m_nInsertFailed;
52 size_t m_nDeleteSuccess;
53 size_t m_nDeleteFailed;
54 size_t m_nFindSuccess;
58 WorkThread( CppUnitMini::ThreadPool& pool, MAP& rMap )
59 : CppUnitMini::TestThread( pool )
62 WorkThread( WorkThread& src )
63 : CppUnitMini::TestThread( src )
67 Map_InsDelFind& getTest()
69 return reinterpret_cast<Map_InsDelFind&>( m_Pool.m_Test );
72 virtual void init() { cds::threading::Manager::attachThread() ; }
73 virtual void fini() { cds::threading::Manager::detachThread() ; }
86 actions * pAct = getTest().m_arrShuffle;
88 size_t const nNormalize = size_t(-1) / (c_nInitialMapSize * 2);
91 while ( !time_elapsed() ) {
92 nRand = cds::bitop::RandXorShift(nRand);
93 size_t n = nRand / nNormalize;
102 if ( rMap.insert( n, n ))
108 if ( rMap.erase( n ))
115 if ( ++i >= c_nShuffleSize )
123 void do_test( MAP& testMap )
125 typedef WorkThread<MAP> work_thread;
126 cds::OS::Timer timer;
128 // fill map - only odd number
130 std::vector<size_t> arr;
131 arr.reserve( c_nInitialMapSize );
132 for ( size_t i = 0; i < c_nInitialMapSize; ++i )
133 arr.push_back( i * 2 + 1);
134 std::random_shuffle( arr.begin(), arr.end() );
135 for ( size_t i = 0; i < c_nInitialMapSize; ++i )
136 testMap.insert( arr[i], arr[i] );
138 CPPUNIT_MSG( " Insert " << c_nInitialMapSize << " items time (single-threaded)=" << timer.duration() );
141 CppUnitMini::ThreadPool pool( *this );
142 pool.add( new work_thread( pool, testMap ), c_nThreadCount );
143 pool.run( c_nDuration );
144 //CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
146 size_t nInsertSuccess = 0;
147 size_t nInsertFailed = 0;
148 size_t nDeleteSuccess = 0;
149 size_t nDeleteFailed = 0;
150 size_t nFindSuccess = 0;
151 size_t nFindFailed = 0;
152 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
153 work_thread * pThread = static_cast<work_thread *>( *it );
154 assert( pThread != nullptr );
155 nInsertSuccess += pThread->m_nInsertSuccess;
156 nInsertFailed += pThread->m_nInsertFailed;
157 nDeleteSuccess += pThread->m_nDeleteSuccess;
158 nDeleteFailed += pThread->m_nDeleteFailed;
159 nFindSuccess += pThread->m_nFindSuccess;
160 nFindFailed += pThread->m_nFindFailed;
163 size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
165 CPPUNIT_MSG( " Totals (success/failed): \n\t"
166 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
167 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
168 << " Find=" << nFindSuccess << '/' << nFindFailed << "\n\t"
169 << " Speed=" << (nFindSuccess + nFindFailed) / c_nDuration << " find/sec\n\t"
170 << " " << (nInsertSuccess + nDeleteSuccess) / c_nDuration << " modify/sec\n\t"
171 << " Total ops=" << nTotalOps << "\n\t"
172 << " speed=" << nTotalOps / c_nDuration << " ops/sec\n\t"
173 << " Map size=" << testMap.size()
177 check_before_cleanup( testMap );
179 CPPUNIT_MSG( " Clear map (single-threaded)..." );
182 CPPUNIT_MSG( " Duration=" << timer.duration() );
183 CPPUNIT_ASSERT_EX( testMap.empty(), ((long long) testMap.size()) );
185 additional_check( testMap );
186 print_stat( testMap );
187 additional_cleanup( testMap );
193 CPPUNIT_MSG( "Thread count=" << c_nThreadCount
194 << " initial map size=" << c_nInitialMapSize
195 << " insert=" << c_nInsertPercentage << '%'
196 << " delete=" << c_nDeletePercentage << '%'
197 << " duration=" << c_nDuration << "s"
200 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
201 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
202 MAP testMap( c_nInitialMapSize, nLoadFactor );
204 if ( c_bPrintGCState )
213 CPPUNIT_MSG( "Thread count=" << c_nThreadCount
214 << " initial map size=" << c_nInitialMapSize
215 << " insert=" << c_nInsertPercentage << '%'
216 << " delete=" << c_nDeletePercentage << '%'
217 << " duration=" << c_nDuration << "s"
222 if ( c_bPrintGCState )
226 void setUpParams( const CppUnitMini::TestCfg& cfg );
228 void run_MichaelMap(const char *in_name, bool invert = false);
229 void run_SplitList(const char *in_name, bool invert = false);
230 void run_StripedMap(const char *in_name, bool invert = false);
231 void run_RefinableMap(const char *in_name, bool invert = false);
232 void run_CuckooMap(const char *in_name, bool invert = false);
233 void run_SkipListMap(const char *in_name, bool invert = false);
234 void run_EllenBinTreeMap(const char *in_name, bool invert = false);
235 void run_BronsonAVLTreeMap(const char *in_name, bool invert = false);
236 void run_StdMap(const char *in_name, bool invert = false);
238 virtual void myRun(const char *in_name, bool invert = false);
240 # include "map2/map_defs.h"
241 CDSUNIT_DECLARE_MichaelMap
242 CDSUNIT_DECLARE_SplitList
243 CDSUNIT_DECLARE_SkipListMap
244 CDSUNIT_DECLARE_EllenBinTreeMap
245 CDSUNIT_DECLARE_BronsonAVLTreeMap
246 CDSUNIT_DECLARE_StripedMap
247 CDSUNIT_DECLARE_RefinableMap
248 CDSUNIT_DECLARE_CuckooMap
249 CDSUNIT_DECLARE_StdMap