{
public:
static size_t s_nMapSize; // initial map size
+
+ static size_t s_nPassCount;
+ static size_t s_nBronsonAVLTreeMapPassCount;
+ static size_t s_nEllenBinTreeMapPassCount;
+ static size_t s_nFeldmanPassCount;
+ static size_t s_nMichaelMapPassCount;
+ static size_t s_nSkipListMapPassCount;
+ static size_t s_nSplitListMapPassCount;
+
static size_t s_nThreadCount; // thread count
static size_t s_nMaxLoadFactor; // maximum load factor
static unsigned int s_nInsertPercentage;
virtual void test()
{
Map& rMap = m_Map;
-
- unsigned int i = 0;
- size_t const nNormalize = size_t(-1) / ( s_nMapSize * 2 );
-
- size_t nRand = 0;
- while ( !time_elapsed()) {
- nRand = cds::bitop::RandXorShift( nRand );
- size_t n = nRand / nNormalize;
- switch ( s_arrShuffle[i] ) {
- case do_find:
- if ( rMap.contains( n ))
- ++m_nFindSuccess;
+ size_t pass_count = Map_InsDelFind::s_nPassCount;
+
+ for (size_t count = 0; count < pass_count; count++) {
+ bool shouldUpdate = true;
+ for (size_t i = 0; i < s_nMapSize; ++i) {
+ // The number to operate on the map.
+ size_t n = i;
+ // Insert
+ if (i % s_nInsertPercentage == 1) {
+ if (!shouldUpdate) {
+ if (rMap.insert(n, n))
+ ++m_nInsertSuccess;
else
- ++m_nFindFailed;
- break;
- case do_insert:
- if ( n % 2 ) {
- if ( rMap.insert( n, n ))
- ++m_nInsertSuccess;
- else
- ++m_nInsertFailed;
- }
- else {
- if ( rMap.update( n, update_functor(), true ).first )
- ++m_nInsertSuccess;
- else
- ++m_nInsertFailed;
- }
- break;
- case do_delete:
- if ( rMap.erase( n ))
- ++m_nDeleteSuccess;
+ ++m_nInsertFailed;
+ shouldUpdate = true;
+ } else {
+ if (rMap.update(n, update_functor(), true).first)
+ ++m_nInsertSuccess;
else
- ++m_nDeleteFailed;
- break;
+ ++m_nInsertFailed;
+ shouldUpdate = false;
+ }
}
-
- if ( ++i >= c_nShuffleSize )
- i = 0;
+ // Find
+ if (rMap.contains(n))
+ ++m_nFindSuccess;
+ else
+ ++m_nFindFailed;
+ // Delete
+ if (i % s_nInsertPercentage == 1) {
+
+ if (rMap.erase(n))
+ ++m_nDeleteSuccess;
+ else
+ ++m_nDeleteFailed;
+ break;
+ }
+ }
}
}
};
void do_test( Map& testMap )
{
typedef Worker<Map> worker;
-
- // fill map - only odd number
- {
- std::vector<size_t> arr;
- arr.reserve( s_nMapSize );
- for ( size_t i = 0; i < s_nMapSize; ++i )
- arr.push_back( i * 2 + 1);
- shuffle( arr.begin(), arr.end());
- for ( size_t i = 0; i < s_nMapSize; ++i )
- testMap.insert( arr[i], arr[i] );
- }
-
cds_test::thread_pool& pool = get_pool();
- pool.add( new worker( pool, testMap ), s_nThreadCount );
-
- propout() << std::make_pair( "thread_count", s_nThreadCount )
- << std::make_pair( "insert_percentage", s_nInsertPercentage )
- << std::make_pair( "delete_percentage", s_nDeletePercentage )
- << std::make_pair( "map_size", s_nMapSize );
-
- std::chrono::milliseconds duration = pool.run( std::chrono::seconds( s_nDuration ));
-
- propout() << std::make_pair( "duration", duration );
-
- size_t nInsertSuccess = 0;
- size_t nInsertFailed = 0;
- size_t nDeleteSuccess = 0;
- size_t nDeleteFailed = 0;
- size_t nFindSuccess = 0;
- size_t nFindFailed = 0;
- for ( size_t i = 0; i < pool.size(); ++i ) {
- worker& thr = static_cast<worker&>( pool.get( i ));
-
- nInsertSuccess += thr.m_nInsertSuccess;
- nInsertFailed += thr.m_nInsertFailed;
- nDeleteSuccess += thr.m_nDeleteSuccess;
- nDeleteFailed += thr.m_nDeleteFailed;
- nFindSuccess += thr.m_nFindSuccess;
- nFindFailed += thr.m_nFindFailed;
- }
-
- propout()
- << std::make_pair( "insert_success", nInsertSuccess )
- << std::make_pair( "insert_failed", nInsertFailed )
- << std::make_pair( "delete_success", nDeleteSuccess )
- << std::make_pair( "delete_failed", nDeleteFailed )
- << std::make_pair( "find_success", nFindSuccess )
- << std::make_pair( "find_failed", nFindFailed )
- << std::make_pair( "finish_map_size", testMap.size());
-
- {
- ASSERT_TRUE( std::chrono::duration_cast<std::chrono::seconds>(duration).count() > 0 );
- size_t nTotalOps = nInsertSuccess + nInsertFailed + nDeleteSuccess + nDeleteFailed + nFindSuccess + nFindFailed;
- propout() << std::make_pair( "avg_speed", nTotalOps / std::chrono::duration_cast<std::chrono::seconds>( duration ).count());
- }
-
- check_before_cleanup( testMap );
+ std::unique_ptr<worker> worker_thrd(new worker(pool, testMap));
+ worker_thrd->test();
testMap.clear();
EXPECT_TRUE( testMap.empty());
-
- additional_check( testMap );
- print_stat( propout(), testMap );
additional_cleanup( testMap );
}
Map testMap( *this );
do_test( testMap );
}
+
+ template <class Map>
+ void run_bronson_avl_tree() {
+ Map_InsDelFind::s_nPassCount =
+ Map_InsDelFind::s_nBronsonAVLTreeMapPassCount;
+ run_test<Map>();
+ }
+
+ template <class Map>
+ void run_ellen_bin_tree() {
+ Map_InsDelFind::s_nPassCount =
+ Map_InsDelFind::s_nEllenBinTreeMapPassCount;
+ run_test<Map>();
+ }
+
+ template <class Map>
+ void run_skip_list() {
+ Map_InsDelFind::s_nPassCount =
+ Map_InsDelFind::s_nSkipListMapPassCount;
+ run_test<Map>();
+ }
+
+ template <class Map>
+ void run_feldman() {
+ Map_InsDelFind::s_nPassCount =
+ Map_InsDelFind::s_nFeldmanPassCount;
+ run_test<Map>();
+ }
};
class Map_InsDelFind_LF: public Map_InsDelFind
Map_InsDelFind::run_test<Map>();
}
+ template <class Map>
+ void run_michael() {
+ Map_InsDelFind::s_nPassCount =
+ Map_InsDelFind::s_nMichaelMapPassCount;
+ Map_InsDelFind_LF::run_test<Map>();
+ }
+
+ template <class Map>
+ void run_split_list() {
+ Map_InsDelFind::s_nPassCount =
+ Map_InsDelFind::s_nSplitListMapPassCount;
+ Map_InsDelFind_LF::run_test<Map>();
+ }
+
static std::vector<size_t> get_load_factors();
};
projects / libcds.git / blobdiff