X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=test%2Fstress%2Fset%2Fdelodd%2Fset_delodd.h;h=4f77e07782ba245faf3309522a62c29af0f59565;hp=5d8df8aab5dac16c70349a12005421b92b4e5450;hb=907e8f3e384f7161e35dc41ddc3a78c2bb86013b;hpb=2cf8e8bb9dc140e6b6e313d2f754e3d14dfa900c diff --git a/test/stress/set/delodd/set_delodd.h b/test/stress/set/delodd/set_delodd.h index 5d8df8aa..4f77e077 100644 --- a/test/stress/set/delodd/set_delodd.h +++ b/test/stress/set/delodd/set_delodd.h @@ -1,11 +1,11 @@ /* This file is a part of libcds - Concurrent Data Structures library - (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 Source code repo: http://github.com/khizmax/libcds/ Download: http://sourceforge.net/projects/libcds/files/ - + Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: @@ -29,6 +29,8 @@ */ #include "set_type.h" +#include "../../misc/common.h" +#include namespace set { @@ -36,21 +38,20 @@ namespace set { { uint32_t nKey; uint16_t nThread; - uint16_t pad_; key_thread( size_t key, size_t threadNo ) : nKey( static_cast(key)) , nThread( static_cast(threadNo)) - , pad_(0) {} key_thread() : nKey() , nThread() - , pad_( 0 ) {} }; + static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch"); + typedef set_type_base::key_val key_value_pair; template <> @@ -122,6 +123,8 @@ namespace set { static size_t s_nDelThreadCount; // delete thread count static size_t s_nExtractThreadCount; // extract thread count static size_t s_nMaxLoadFactor; // maximum load factor + static size_t s_nInsertPassCount; + static size_t s_nFindThreadCount; // find thread count static size_t s_nCuckooInitialSize; // initial size for CuckooSet static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset) @@ -137,6 +140,18 @@ namespace set { static void SetUpTestCase(); static void TearDownTestCase(); + template + static void prepare_array( std::vector& arr, Pred pred ) + { + arr.reserve( m_arrData.size()); + for ( auto el : m_arrData ) { + if ( pred( el )) + arr.push_back( el ); + } + arr.resize( arr.size()); + shuffle( arr.begin(), arr.end()); + } + protected: typedef key_thread key_type; typedef size_t value_type; @@ -147,6 +162,7 @@ namespace set { inserter_thread, deleter_thread, extractor_thread, + find_thread }; @@ -166,20 +182,40 @@ namespace set { void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const {} }; + + void init_data() + { + prepare_array( m_arr, []( size_t ) -> bool { return true; } ); + for ( size_t i = 0; i < m_arr.size(); ++i ) { + if ( m_Set.insert( key_type( m_arr[i], id()))) + ++m_nInsertInitSuccess; + else + ++m_nInsertInitFailed; + } + } + public: size_t m_nInsertSuccess = 0; size_t m_nInsertFailed = 0; + size_t m_nInsertInitSuccess = 0; + size_t m_nInsertInitFailed = 0; + + std::vector m_arr; public: Inserter( cds_test::thread_pool& pool, Set& set ) : base_class( pool, inserter_thread ) , m_Set( set ) - {} + { + init_data(); + } Inserter( Inserter& src ) : base_class( src ) , m_Set( src.m_Set ) - {} + { + init_data(); + } virtual thread * clone() { @@ -191,21 +227,36 @@ namespace set { Set& rSet = m_Set; Set_DelOdd& fixture = pool().template fixture(); - std::vector& arrData = fixture.m_arrData; - for ( size_t i = 0; i < arrData.size(); ++i ) { - if ( rSet.insert( key_type( arrData[i], id() ))) - ++m_nInsertSuccess; - else - ++m_nInsertFailed; - } - - update_functor f; - for ( size_t i = arrData.size() - 1; i > 0; --i ) { - if ( arrData[i] & 1 ) - rSet.update( key_type( arrData[i], id() ), f, true ); + for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) { + if ( nPass & 1 ) { + // insert pass + for ( auto el : m_arr ) { + if ( el & 1 ) { + if ( rSet.insert( key_type( el, id()))) + ++m_nInsertSuccess; + else + ++m_nInsertFailed; + } + } + } + else { + // update pass + for ( auto el : m_arr ) { + if ( el & 1 ) { + bool success; + bool inserted; + std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor()); + if ( success && inserted ) + ++m_nInsertSuccess; + else + ++m_nInsertFailed; + } + } + } } fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release ); + m_arr.resize( 0 ); } }; @@ -288,19 +339,30 @@ namespace set { typedef cds_test::thread base_class; Set& m_Set; + void init_data() + { + prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } ); + } + public: size_t m_nDeleteSuccess = 0; size_t m_nDeleteFailed = 0; + std::vector m_arr; + public: Deleter( cds_test::thread_pool& pool, Set& set ) : base_class( pool, deleter_thread ) , m_Set( set ) - {} + { + init_data(); + } Deleter( Deleter& src ) : base_class( src ) , m_Set( src.m_Set ) - {} + { + init_data(); + } virtual thread * clone() { @@ -311,7 +373,7 @@ namespace set { struct eraser { static bool erase( SetType& s, size_t key, size_t /*thread*/) { - return s.erase_with( key, key_less() ); + return s.erase_with( key, key_less()); } }; @@ -329,36 +391,31 @@ namespace set { size_t const nInsThreadCount = s_nInsThreadCount; Set_DelOdd& fixture = pool().template fixture(); - std::vector& arrData = fixture.m_arrData; - if ( id() & 1 ) { - for (size_t i = 0; i < arrData.size(); ++i) { - if ( arrData[i] & 1 ) { + do { + if ( id() & 1 ) { + for ( auto el : m_arr ) { for ( size_t k = 0; k < nInsThreadCount; ++k ) { - if ( eraser::erase( rSet, arrData[i], k )) + if ( rSet.erase( key_type( el, k ))) ++m_nDeleteSuccess; else ++m_nDeleteFailed; } } - if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; } - } - else { - for ( size_t i = arrData.size() - 1; i > 0; --i ) { - if ( arrData[i] & 1 ) { - for ( size_t k = 0; k < nInsThreadCount; ++k ) { - if (eraser::erase(rSet, arrData[i], k)) + else { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { + for ( auto el : m_arr ) { + if ( rSet.erase( key_type( el, k ))) ++m_nDeleteSuccess; else ++m_nDeleteFailed; } } - if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; } - } + } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 ); + + m_arr.resize( 0 ); } }; @@ -369,6 +426,13 @@ namespace set { typedef cds_test::thread base_class; Set& m_Set; + std::vector m_arr; + + void init_data() + { + prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } ); + } + public: size_t m_nExtractSuccess = 0; size_t m_nExtractFailed = 0; @@ -377,49 +441,35 @@ namespace set { Extractor( cds_test::thread_pool& pool, Set& set ) : base_class( pool, extractor_thread ) , m_Set( set ) - {} + { + init_data(); + } Extractor( Extractor& src ) : base_class( src ) , m_Set( src.m_Set ) - {} + { + init_data(); + } virtual thread * clone() { return new Extractor( *this ); } - template - struct extractor { - static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t /*thread*/) - { - return s.extract_with( key, key_less()); - } - }; - - template - struct extractor { - static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t thread) - { - return s.extract( key_type(key, thread)); - } - }; - virtual void test() { Set& rSet = m_Set; - typename Set::guarded_ptr gp; Set_DelOdd& fixture = pool().template fixture(); - std::vector& arrData = fixture.m_arrData; size_t const nInsThreadCount = s_nInsThreadCount; - if ( id() & 1 ) { - for ( size_t i = 0; i < arrData.size(); ++i ) { - if ( arrData[i] & 1 ) { + do { + if ( id() & 1 ) { + for ( auto el : m_arr ) { for ( size_t k = 0; k < nInsThreadCount; ++k ) { - gp = extractor::extract( rSet, arrData[i], k ); + gp = rSet.extract( key_type( el, k )); if ( gp ) ++m_nExtractSuccess; else @@ -427,15 +477,11 @@ namespace set { gp.release(); } } - if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; } - } - else { - for ( size_t i = arrData.size() - 1; i > 0; --i ) { - if ( arrData[i] & 1 ) { - for ( size_t k = 0; k < nInsThreadCount; ++k ) { - gp = extractor::extract( rSet, arrData[i], k); + else { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { + for ( auto el : m_arr ) { + gp = rSet.extract( key_type( el, k )); if ( gp ) ++m_nExtractSuccess; else @@ -443,10 +489,10 @@ namespace set { gp.release(); } } - if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; } - } + } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 ); + + m_arr.resize( 0 ); } }; @@ -455,6 +501,12 @@ namespace set { { typedef cds_test::thread base_class; Set& m_Set; + std::vector m_arr; + + void init_data() + { + prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } ); + } public: size_t m_nExtractSuccess = 0; @@ -464,58 +516,44 @@ namespace set { Extractor( cds_test::thread_pool& pool, Set& set ) : base_class( pool, extractor_thread ) , m_Set( set ) - {} + { + init_data(); + } Extractor( Extractor& src ) : base_class( src ) , m_Set( src.m_Set ) - {} + { + init_data(); + } virtual thread * clone() { return new Extractor( *this ); } - template - struct extractor { - static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t /*thread*/) - { - return s.extract_with(key, key_less()); - } - }; - - template - struct extractor { - static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t thread) - { - return s.extract(key_type(key, thread)); - } - }; - virtual void test() { Set& rSet = m_Set; - typename Set::exempt_ptr xp; Set_DelOdd& fixture = pool().template fixture(); - std::vector& arrData = fixture.m_arrData; size_t const nInsThreadCount = fixture.s_nInsThreadCount; - if ( id() & 1 ) { - for ( size_t i = 0; i < arrData.size(); ++i ) { - if ( arrData[i] & 1 ) { - for ( size_t k = 0; k < nInsThreadCount; ++k ) { + do { + if ( id() & 1 ) { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { + for ( auto el : m_arr ) { if ( Set::c_bExtractLockExternal ) { typename Set::rcu_lock l; - xp = extractor::extract( rSet, arrData[i], k); + xp = rSet.extract( key_type( el, k )); if ( xp ) ++m_nExtractSuccess; else ++m_nExtractFailed; } else { - xp = extractor::extract(rSet, arrData[i], k); + xp = rSet.extract( key_type( el, k )); if ( xp ) ++m_nExtractSuccess; else @@ -524,24 +562,20 @@ namespace set { xp.release(); } } - if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; } - } - else { - for ( size_t i = arrData.size() - 1; i > 0; --i ) { - if ( arrData[i] & 1 ) { + else { + for ( auto el : m_arr ) { for ( size_t k = 0; k < nInsThreadCount; ++k ) { if ( Set::c_bExtractLockExternal ) { typename Set::rcu_lock l; - xp = extractor::extract(rSet, arrData[i], k); + xp = rSet.extract( key_type( el, k )); if ( xp ) ++m_nExtractSuccess; else ++m_nExtractFailed; } else { - xp = extractor::extract(rSet, arrData[i], k); + xp = rSet.extract( key_type( el, k )); if ( xp ) ++m_nExtractSuccess; else @@ -550,10 +584,70 @@ namespace set { xp.release(); } } - if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 ) - break; } - } + } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 ); + + m_arr.resize( 0 ); + } + }; + + // Finds keys + template + class Observer: public cds_test::thread + { + typedef cds_test::thread base_class; + Set& m_Set; + + public: + size_t m_nFindEvenSuccess = 0; + size_t m_nFindEvenFailed = 0; + size_t m_nFindOddSuccess = 0; + size_t m_nFindOddFailed = 0; + + public: + Observer( cds_test::thread_pool& pool, Set& set ) + : base_class( pool, find_thread ) + , m_Set( set ) + {} + + Observer( Observer& src ) + : base_class( src ) + , m_Set( src.m_Set ) + {} + + virtual thread * clone() + { + return new Observer( *this ); + } + + virtual void test() + { + Set& set = m_Set; + Set_DelOdd& fixture = pool().template fixture(); + std::vector const& arr = m_arrData; + size_t const nInsThreadCount = s_nInsThreadCount; + + do { + for ( size_t key : arr ) { + if ( key & 1 ) { + for ( size_t k = 0; k < nInsThreadCount; ++k ) { + if ( set.contains( key_thread( key, k ))) + ++m_nFindOddSuccess; + else + ++m_nFindOddFailed; + } + } + else { + // even keys MUST be in the map + for ( size_t k = 0; k < nInsThreadCount; ++k ) { + if ( set.contains( key_thread( key, k ))) + ++m_nFindEvenSuccess; + else + ++m_nFindEvenFailed; + } + } + } + } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 ); } }; @@ -563,49 +657,90 @@ namespace set { { typedef Inserter insert_thread; typedef Deleter delete_thread; + typedef Observer observer_thread; m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release ); cds_test::thread_pool& pool = get_pool(); pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount ); pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count()); + if ( s_nFindThreadCount ) + pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount ); propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount ) << std::make_pair( "delete_thread_count", s_nDelThreadCount ) - << std::make_pair( "set_size", s_nSetSize ); + << std::make_pair( "find_thread_count", s_nFindThreadCount ) + << std::make_pair( "set_size", s_nSetSize ) + << std::make_pair( "pass_count", s_nInsertPassCount ); std::chrono::milliseconds duration = pool.run(); propout() << std::make_pair( "duration", duration ); + size_t nInsertInitFailed = 0; + size_t nInsertInitSuccess = 0; size_t nInsertSuccess = 0; size_t nInsertFailed = 0; size_t nDeleteSuccess = 0; size_t nDeleteFailed = 0; + size_t nFindEvenSuccess = 0; + size_t nFindEvenFailed = 0; + size_t nFindOddSuccess = 0; + size_t nFindOddFailed = 0; + for ( size_t i = 0; i < pool.size(); ++i ) { cds_test::thread& thr = pool.get( i ); - if ( thr.type() == inserter_thread ) { - insert_thread& inserter = static_cast(thr); - nInsertSuccess += inserter.m_nInsertSuccess; - nInsertFailed += inserter.m_nInsertFailed; - } - else { - assert( thr.type() == deleter_thread ); - delete_thread& deleter = static_cast(thr); - nDeleteSuccess += deleter.m_nDeleteSuccess; - nDeleteFailed += deleter.m_nDeleteFailed; + switch ( thr.type()) { + case inserter_thread: + { + insert_thread& inserter = static_cast(thr); + nInsertSuccess += inserter.m_nInsertSuccess; + nInsertFailed += inserter.m_nInsertFailed; + nInsertInitSuccess += inserter.m_nInsertInitSuccess; + nInsertInitFailed += inserter.m_nInsertInitFailed; + } + break; + case deleter_thread: + { + delete_thread& deleter = static_cast(thr); + nDeleteSuccess += deleter.m_nDeleteSuccess; + nDeleteFailed += deleter.m_nDeleteFailed; + } + break; + case find_thread: + { + observer_thread& observer = static_cast( thr ); + nFindEvenSuccess = observer.m_nFindEvenSuccess; + nFindEvenFailed = observer.m_nFindEvenFailed; + nFindOddSuccess = observer.m_nFindOddSuccess; + nFindOddFailed = observer.m_nFindOddFailed; + } + break; + default: + assert( false ); } } - EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount ); - EXPECT_EQ( nInsertFailed, 0 ); + size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2; + + EXPECT_EQ( nInsertInitFailed, 0u ); + EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount ); + EXPECT_EQ( nFindEvenFailed, 0u ); + EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess ); + EXPECT_LE( nInsertSuccess, nDeleteSuccess ); propout() + << std::make_pair( "insert_init_success", nInsertInitSuccess ) + << std::make_pair( "insert_init_failed", nInsertInitFailed ) << 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( "delete_failed", nDeleteFailed ) + << std::make_pair( "find_even_success", nFindEvenSuccess ) + << std::make_pair( "find_even_failed", nFindEvenFailed ) + << std::make_pair( "find_odd_success", nFindOddSuccess ) + << std::make_pair( "find_odd_failed", nFindOddFailed ); } template @@ -614,6 +749,7 @@ namespace set { typedef Inserter insert_thread; typedef Deleter delete_thread; typedef Extractor< typename Set::gc, Set > extract_thread; + typedef Observer observer_thread; m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release ); @@ -623,30 +759,44 @@ namespace set { pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ); if ( s_nExtractThreadCount ) pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount ); + if ( s_nFindThreadCount ) + pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount ); propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount ) << std::make_pair( "delete_thread_count", s_nDelThreadCount ) << std::make_pair( "extract_thread_count", s_nExtractThreadCount ) - << std::make_pair( "set_size", s_nSetSize ); + << std::make_pair( "find_thread_count", s_nFindThreadCount ) + << std::make_pair( "set_size", s_nSetSize ) + << std::make_pair( "pass_count", s_nInsertPassCount ); std::chrono::milliseconds duration = pool.run(); propout() << std::make_pair( "duration", duration ); + size_t nInsertInitFailed = 0; + size_t nInsertInitSuccess = 0; size_t nInsertSuccess = 0; size_t nInsertFailed = 0; size_t nDeleteSuccess = 0; size_t nDeleteFailed = 0; size_t nExtractSuccess = 0; size_t nExtractFailed = 0; + + size_t nFindEvenSuccess = 0; + size_t nFindEvenFailed = 0; + size_t nFindOddSuccess = 0; + size_t nFindOddFailed = 0; + for ( size_t i = 0; i < pool.size(); ++i ) { cds_test::thread& thr = pool.get( i ); - switch ( thr.type() ) { + switch ( thr.type()) { case inserter_thread: { insert_thread& inserter = static_cast( thr ); nInsertSuccess += inserter.m_nInsertSuccess; nInsertFailed += inserter.m_nInsertFailed; + nInsertInitSuccess += inserter.m_nInsertInitSuccess; + nInsertInitFailed += inserter.m_nInsertInitFailed; } break; case deleter_thread: @@ -663,21 +813,41 @@ namespace set { nExtractFailed += extractor.m_nExtractFailed; } break; + case find_thread: + { + observer_thread& observer = static_cast( thr ); + nFindEvenSuccess = observer.m_nFindEvenSuccess; + nFindEvenFailed = observer.m_nFindEvenFailed; + nFindOddSuccess = observer.m_nFindOddSuccess; + nFindOddFailed = observer.m_nFindOddFailed; + } + break; default: assert( false ); } } - EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount ); - EXPECT_EQ( nInsertFailed, 0 ); + size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2; + + EXPECT_EQ( nInsertInitFailed, 0u ); + EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount ); + EXPECT_EQ( nFindEvenFailed, 0u ); + EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess ); + EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess ); propout() + << std::make_pair( "insert_init_success", nInsertInitSuccess ) + << std::make_pair( "insert_init_failed", nInsertInitFailed ) << 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( "extract_success", nExtractSuccess ) - << std::make_pair( "extract_failed", nExtractFailed ); + << std::make_pair( "extract_failed", nExtractFailed ) + << std::make_pair( "find_even_success", nFindEvenSuccess ) + << std::make_pair( "find_even_failed", nFindEvenFailed ) + << std::make_pair( "find_odd_success", nFindOddSuccess ) + << std::make_pair( "find_odd_failed", nFindOddFailed ); } template @@ -695,7 +865,7 @@ namespace set { check_before_clear( testSet ); testSet.clear(); - EXPECT_TRUE( testSet.empty() ) << "set.size=" << testSet.size(); + EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size(); additional_check( testSet ); print_stat( propout(), testSet ); @@ -709,7 +879,7 @@ namespace set { Set testSet( *this ); do_test_with( testSet ); - analyze( testSet ); + DEBUG(analyze( testSet )); } template @@ -719,8 +889,11 @@ namespace set { Set testSet( *this ); do_test_extract_with( testSet ); - analyze( testSet ); + DEBUG(analyze( testSet )); } + + template + void run_feldman(); }; class Set_DelOdd_LF: public Set_DelOdd