From ded4ac486f04a6ffdcd776adefd4db3e8efee38e Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 16 Mar 2015 22:36:50 +0300 Subject: [PATCH] Splitted map_insdel_func test for reducing compiler memory requirements --- projects/Win/vc12/unit-map-insdel.vcxproj | 10 + projects/source.unit.map.mk | 7 + tests/unit/map2/map_insdel_func.cpp | 603 ++-------------------- tests/unit/map2/map_insdel_func.h | 560 ++++++++++++++++++++ tests/unit/map2/map_insdel_func2.cpp | 10 + tests/unit/map2/map_insdel_func3.cpp | 10 + tests/unit/map2/map_insdel_func4.cpp | 10 + tests/unit/map2/map_insdel_func5.cpp | 9 + tests/unit/map2/map_insdel_func6.cpp | 9 + tests/unit/map2/map_insdel_func7.cpp | 9 + tests/unit/map2/map_insdel_func8.cpp | 9 + 11 files changed, 685 insertions(+), 561 deletions(-) create mode 100644 tests/unit/map2/map_insdel_func.h create mode 100644 tests/unit/map2/map_insdel_func2.cpp create mode 100644 tests/unit/map2/map_insdel_func3.cpp create mode 100644 tests/unit/map2/map_insdel_func4.cpp create mode 100644 tests/unit/map2/map_insdel_func5.cpp create mode 100644 tests/unit/map2/map_insdel_func6.cpp create mode 100644 tests/unit/map2/map_insdel_func7.cpp create mode 100644 tests/unit/map2/map_insdel_func8.cpp diff --git a/projects/Win/vc12/unit-map-insdel.vcxproj b/projects/Win/vc12/unit-map-insdel.vcxproj index cef34fd5..9a504f1d 100644 --- a/projects/Win/vc12/unit-map-insdel.vcxproj +++ b/projects/Win/vc12/unit-map-insdel.vcxproj @@ -45,11 +45,21 @@ + + + + + + + + + + {CA25BDBF-B354-4597-B6D2-220ABBB0D2F4} unitmap diff --git a/projects/source.unit.map.mk b/projects/source.unit.map.mk index 5d8f4bf4..f66e4a40 100644 --- a/projects/source.unit.map.mk +++ b/projects/source.unit.map.mk @@ -3,6 +3,13 @@ CDSUNIT_MAP_SOURCES := \ tests/unit/map2/map_find_int.cpp \ tests/unit/map2/map_find_string.cpp \ tests/unit/map2/map_insdel_func.cpp \ + tests/unit/map2/map_insdel_func2.cpp \ + tests/unit/map2/map_insdel_func3.cpp \ + tests/unit/map2/map_insdel_func4.cpp \ + tests/unit/map2/map_insdel_func5.cpp \ + tests/unit/map2/map_insdel_func6.cpp \ + tests/unit/map2/map_insdel_func7.cpp \ + tests/unit/map2/map_insdel_func8.cpp \ tests/unit/map2/map_insdel_int.cpp \ tests/unit/map2/map_insdel_item_int.cpp \ tests/unit/map2/map_insdel_string.cpp \ diff --git a/tests/unit/map2/map_insdel_func.cpp b/tests/unit/map2/map_insdel_func.cpp index 65b970b7..6232125a 100644 --- a/tests/unit/map2/map_insdel_func.cpp +++ b/tests/unit/map2/map_insdel_func.cpp @@ -1,572 +1,53 @@ //$$CDS-header$$ -#include -#include //unique_lock -#include "map2/map_types.h" -#include "cppunit/thread.h" - -#include -#include -#include // random_shuffle +#include "map2/map_insdel_func.h" namespace map2 { + CPPUNIT_TEST_SUITE_REGISTRATION( Map_InsDel_func ); -# define TEST_MAP(X) void X() { test::X >() ; } -# define TEST_MAP_EXTRACT(X) TEST_MAP(X) -# define TEST_MAP_NOLF(X) void X() { test_nolf::X >() ; } -# define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X) - - namespace { - static size_t c_nMapSize = 1000000 ; // map size - static size_t c_nInsertThreadCount = 4; // count of insertion thread - static size_t c_nDeleteThreadCount = 4; // count of deletion thread - static size_t c_nEnsureThreadCount = 4; // count of ensure thread - static size_t c_nThreadPassCount = 4 ; // pass count for each thread - static size_t c_nMaxLoadFactor = 8 ; // maximum load factor - static bool c_bPrintGCState = true; + static const size_t def_nMapSize = 1000000; + static const size_t def_nInsertThreadCount = 4; + static const size_t def_nDeleteThreadCount = 4; + static const size_t def_nEnsureThreadCount = 4; + static const size_t def_nThreadPassCount = 4; + static const size_t def_nMaxLoadFactor = 8; + + size_t Map_InsDel_func::c_nMapSize = def_nMapSize ; // map size + size_t Map_InsDel_func::c_nInsertThreadCount = def_nInsertThreadCount; // count of insertion thread + size_t Map_InsDel_func::c_nDeleteThreadCount = def_nDeleteThreadCount; // count of deletion thread + size_t Map_InsDel_func::c_nEnsureThreadCount = def_nEnsureThreadCount; // count of ensure thread + size_t Map_InsDel_func::c_nThreadPassCount = def_nThreadPassCount; // pass count for each thread + size_t Map_InsDel_func::c_nMaxLoadFactor = def_nMaxLoadFactor; // maximum load factor + bool Map_InsDel_func::c_bPrintGCState = true; + + void Map_InsDel_func::setUpParams( const CppUnitMini::TestCfg& cfg ) + { + c_nInsertThreadCount = cfg.getULong("InsertThreadCount", def_nInsertThreadCount ); + c_nDeleteThreadCount = cfg.getULong("DeleteThreadCount", def_nDeleteThreadCount ); + c_nEnsureThreadCount = cfg.getULong("EnsureThreadCount", def_nEnsureThreadCount ); + c_nThreadPassCount = cfg.getULong("ThreadPassCount", def_nThreadPassCount ); + c_nMapSize = cfg.getULong("MapSize", def_nMapSize ); + c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", def_nMaxLoadFactor ); + c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true ); } - class Map_InsDel_func: public CppUnitMini::TestCase + void Map_InsDel_func::myRun(const char *in_name, bool invert /*= false*/) { - typedef size_t key_type; - struct value_type { - size_t nKey; - size_t nData; - atomics::atomic nEnsureCall; - atomics::atomic bInitialized; - cds::OS::ThreadId threadId ; // insert thread id - - typedef cds::sync::spin_lock< cds::backoff::pause > lock_type; - mutable lock_type m_access; - - value_type() - : nKey(0) - , nData(0) - , nEnsureCall(0) - , bInitialized( false ) - , threadId( cds::OS::get_current_thread_id() ) - {} - - value_type( value_type const& s ) - : nKey(s.nKey) - , nData(s.nData) - , nEnsureCall(s.nEnsureCall.load(atomics::memory_order_relaxed)) - , bInitialized( s.bInitialized.load(atomics::memory_order_relaxed) ) - , threadId( cds::OS::get_current_thread_id() ) - {} - - // boost::container::flat_map requires operator = - value_type& operator=( value_type const& v ) - { - nKey = v.nKey; - nData = v.nData; - nEnsureCall.store( v.nEnsureCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed ); - bInitialized.store(v.bInitialized.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed); - - return *this; - } - }; - - typedef std::vector key_array; - key_array m_arrValues; - - template - class Inserter: public CppUnitMini::TestThread - { - Map& m_Map; - - virtual Inserter * clone() - { - return new Inserter( *this ); - } - - struct insert_functor { - size_t nTestFunctorRef; - - insert_functor() - : nTestFunctorRef(0) - {} - - template - void operator()( Pair& val ) - { - operator()( val.first, val.second ); - } - - template - void operator()( Key const& key, Val& v ) - { - std::unique_lock< typename value_type::lock_type> ac( v.m_access ); - - v.nKey = key; - v.nData = key * 8; - - ++nTestFunctorRef; - v.bInitialized.store( true, atomics::memory_order_relaxed); - } - }; - - public: - size_t m_nInsertSuccess; - size_t m_nInsertFailed; - - size_t m_nTestFunctorRef; - - public: - Inserter( CppUnitMini::ThreadPool& pool, Map& rMap ) - : CppUnitMini::TestThread( pool ) - , m_Map( rMap ) - {} - Inserter( Inserter& src ) - : CppUnitMini::TestThread( src ) - , m_Map( src.m_Map ) - {} - - Map_InsDel_func& getTest() - { - return reinterpret_cast( m_Pool.m_Test ); - } - - virtual void init() { cds::threading::Manager::attachThread() ; } - virtual void fini() { cds::threading::Manager::detachThread() ; } - - virtual void test() - { - Map& rMap = m_Map; - - m_nInsertSuccess = - m_nInsertFailed = - m_nTestFunctorRef = 0; - - // func is passed by reference - insert_functor func; - key_array const& arr = getTest().m_arrValues; - - if ( m_nThreadNo & 1 ) { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { - for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { - if ( rMap.insert_with( *it, std::ref(func) ) ) - ++m_nInsertSuccess; - else - ++m_nInsertFailed; - } - } - } - else { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { - for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { - if ( rMap.insert_with( *it, std::ref(func) ) ) - ++m_nInsertSuccess; - else - ++m_nInsertFailed; - } - } - } - - m_nTestFunctorRef = func.nTestFunctorRef; - } - }; - - template - class Ensurer: public CppUnitMini::TestThread - { - Map& m_Map; - - virtual Ensurer * clone() - { - return new Ensurer( *this ); - } - - struct ensure_functor { - size_t nCreated; - size_t nModified; - - ensure_functor() - : nCreated(0) - , nModified(0) - {} - - template - void operator()( bool bNew, Key const& key, Val& v ) - { - std::unique_lock ac( v.m_access ); - if ( bNew ) { - ++nCreated; - v.nKey = key; - v.nData = key * 8; - v.bInitialized.store( true, atomics::memory_order_relaxed); - } - else { - v.nEnsureCall.fetch_add( 1, atomics::memory_order_relaxed ); - ++nModified; - } - } - - template - void operator()( bool bNew, Pair& val ) - { - operator()( bNew, val.first, val.second ); - } - private: - ensure_functor(const ensure_functor& ); - }; - - public: - size_t m_nEnsureFailed; - size_t m_nEnsureCreated; - size_t m_nEnsureExisted; - size_t m_nFunctorCreated; - size_t m_nFunctorModified; - - public: - Ensurer( CppUnitMini::ThreadPool& pool, Map& rMap ) - : CppUnitMini::TestThread( pool ) - , m_Map( rMap ) - {} - Ensurer( Ensurer& src ) - : CppUnitMini::TestThread( src ) - , m_Map( src.m_Map ) - {} - - Map_InsDel_func& getTest() - { - return reinterpret_cast( m_Pool.m_Test ); - } - - virtual void init() { cds::threading::Manager::attachThread() ; } - virtual void fini() { cds::threading::Manager::detachThread() ; } - - virtual void test() - { - Map& rMap = m_Map; - - m_nEnsureCreated = - m_nEnsureExisted = - m_nEnsureFailed = 0; - - ensure_functor func; - - key_array const& arr = getTest().m_arrValues; - - if ( m_nThreadNo & 1 ) { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { - for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { - //for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) { - std::pair ret = rMap.ensure( *it, std::ref( func ) ); - if ( ret.first ) { - if ( ret.second ) - ++m_nEnsureCreated; - else - ++m_nEnsureExisted; - } - else - ++m_nEnsureFailed; - } - } - } - else { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { - for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { - std::pair ret = rMap.ensure( *it, std::ref( func ) ); - if ( ret.first ) { - if ( ret.second ) - ++m_nEnsureCreated; - else - ++m_nEnsureExisted; - } - else - ++m_nEnsureFailed; - } - } - } - - m_nFunctorCreated = func.nCreated; - m_nFunctorModified = func.nModified; - } - }; - - template - class Deleter: public CppUnitMini::TestThread - { - Map& m_Map; - typedef typename Map::mapped_type value_type; - - virtual Deleter * clone() - { - return new Deleter( *this ); - } - - struct value_container - { - size_t nKeyExpected; - - size_t nSuccessItem; - size_t nFailedItem; - - value_container() - : nSuccessItem(0) - , nFailedItem(0) - {} - }; - - struct erase_functor { - value_container m_cnt; - - template - void operator()( Key const& /*key*/, Val& v ) - { - while ( true ) { - if ( v.bInitialized.load( atomics::memory_order_relaxed )) { - std::unique_lock< typename value_type::lock_type> ac( v.m_access ); - - if ( m_cnt.nKeyExpected == v.nKey && m_cnt.nKeyExpected * 8 == v.nData ) - ++m_cnt.nSuccessItem; - else - ++m_cnt.nFailedItem; - v.nData++; - v.nKey = 0; - break; - } - else - cds::backoff::yield()(); - } - } - - template - void operator ()( Pair& item ) - { - operator()( item.first, item.second ); - } - }; - - public: - size_t m_nDeleteSuccess; - size_t m_nDeleteFailed; - - size_t m_nValueSuccess; - size_t m_nValueFailed; - - public: - Deleter( CppUnitMini::ThreadPool& pool, Map& rMap ) - : CppUnitMini::TestThread( pool ) - , m_Map( rMap ) - {} - Deleter( Deleter& src ) - : CppUnitMini::TestThread( src ) - , m_Map( src.m_Map ) - {} - - Map_InsDel_func& getTest() - { - return reinterpret_cast( m_Pool.m_Test ); - } - - virtual void init() { cds::threading::Manager::attachThread() ; } - virtual void fini() { cds::threading::Manager::detachThread() ; } - - virtual void test() - { - Map& rMap = m_Map; - - m_nDeleteSuccess = - m_nDeleteFailed = 0; - - erase_functor func; - key_array const& arr = getTest().m_arrValues; - - if ( m_nThreadNo & 1 ) { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { - for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { - func.m_cnt.nKeyExpected = *it; - if ( rMap.erase( *it, std::ref(func) )) - ++m_nDeleteSuccess; - else - ++m_nDeleteFailed; - } - } - } - else { - for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { - for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { - func.m_cnt.nKeyExpected = *it; - if ( rMap.erase( *it, std::ref(func) )) - ++m_nDeleteSuccess; - else - ++m_nDeleteFailed; - } - } - } - - m_nValueSuccess = func.m_cnt.nSuccessItem; - m_nValueFailed = func.m_cnt.nFailedItem; - } - }; - - protected: - - template - void do_test( Map& testMap ) - { - typedef Inserter InserterThread; - typedef Deleter DeleterThread; - typedef Ensurer EnsurerThread; - cds::OS::Timer timer; - - m_arrValues.clear(); - m_arrValues.reserve( c_nMapSize ); - for ( size_t i = 0; i < c_nMapSize; ++i ) - m_arrValues.push_back( i ); - std::random_shuffle( m_arrValues.begin(), m_arrValues.end() ); - - CppUnitMini::ThreadPool pool( *this ); - pool.add( new InserterThread( pool, testMap ), c_nInsertThreadCount ); - pool.add( new DeleterThread( pool, testMap ), c_nDeleteThreadCount ); - pool.add( new EnsurerThread( pool, testMap ), c_nEnsureThreadCount ); - pool.run(); - CPPUNIT_MSG( " Duration=" << pool.avgDuration() ); - - size_t nInsertSuccess = 0; - size_t nInsertFailed = 0; - size_t nDeleteSuccess = 0; - size_t nDeleteFailed = 0; - size_t nDelValueSuccess = 0; - size_t nDelValueFailed = 0; - size_t nEnsureFailed = 0; - size_t nEnsureCreated = 0; - size_t nEnsureModified = 0; - size_t nEnsFuncCreated = 0; - size_t nEnsFuncModified = 0; - size_t nTestFunctorRef = 0; - - for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) { - InserterThread * pThread = dynamic_cast( *it ); - if ( pThread ) { - nInsertSuccess += pThread->m_nInsertSuccess; - nInsertFailed += pThread->m_nInsertFailed; - nTestFunctorRef += pThread->m_nTestFunctorRef; - } - else { - DeleterThread * p = dynamic_cast( *it ); - if ( p ) { - nDeleteSuccess += p->m_nDeleteSuccess; - nDeleteFailed += p->m_nDeleteFailed; - nDelValueSuccess += p->m_nValueSuccess; - nDelValueFailed += p->m_nValueFailed; - } - else { - EnsurerThread * pEns = static_cast( *it ); - nEnsureCreated += pEns->m_nEnsureCreated; - nEnsureModified += pEns->m_nEnsureExisted; - nEnsureFailed += pEns->m_nEnsureFailed; - nEnsFuncCreated += pEns->m_nFunctorCreated; - nEnsFuncModified += pEns->m_nFunctorModified; - } - } - } - - CPPUNIT_MSG( " Totals: Ins succ=" << nInsertSuccess - << " Del succ=" << nDeleteSuccess << "\n" - << " : Ins fail=" << nInsertFailed - << " Del fail=" << nDeleteFailed << "\n" - << " : Ensure succ=" << (nEnsureCreated + nEnsureModified) << " fail=" << nEnsureFailed - << " create=" << nEnsureCreated << " modify=" << nEnsureModified << "\n" - << " Map size=" << testMap.size() - ); - - CPPUNIT_CHECK_EX( nDelValueFailed == 0, "Functor del failed=" << nDelValueFailed ); - CPPUNIT_CHECK_EX( nDelValueSuccess == nDeleteSuccess, "Delete success=" << nDeleteSuccess << " functor=" << nDelValueSuccess ); - - CPPUNIT_CHECK( nEnsureFailed == 0 ); - - CPPUNIT_CHECK_EX( nEnsureCreated == nEnsFuncCreated, "Ensure created=" << nEnsureCreated << " functor=" << nEnsFuncCreated ); - CPPUNIT_CHECK_EX( nEnsureModified == nEnsFuncModified, "Ensure modified=" << nEnsureModified << " functor=" << nEnsFuncModified ); - - // nTestFunctorRef is call count of insert functor - CPPUNIT_CHECK_EX( nTestFunctorRef == nInsertSuccess, "nInsertSuccess=" << nInsertSuccess << " functor nTestFunctorRef=" << nTestFunctorRef ); - - check_before_cleanup( testMap ); - - CPPUNIT_MSG( " Clear map (single-threaded)..." ); - timer.reset(); - for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) { - testMap.erase( nItem ); - } - CPPUNIT_MSG( " Duration=" << timer.duration() ); - CPPUNIT_CHECK( testMap.empty() ); - - additional_check( testMap ); - print_stat( testMap ); - additional_cleanup( testMap ); - } - - template - void test() - { - CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount - << " delete=" << c_nDeleteThreadCount - << " ensure=" << c_nEnsureThreadCount - << " pass count=" << c_nThreadPassCount - << " map size=" << c_nMapSize - ); - - for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { - CPPUNIT_MSG( "Load factor=" << nLoadFactor ); - Map testMap( c_nMapSize, nLoadFactor ); - do_test( testMap ); - if ( c_bPrintGCState ) - print_gc_state(); - } - - } - - template - void test_nolf() - { - CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount - << " delete=" << c_nDeleteThreadCount - << " ensure=" << c_nEnsureThreadCount - << " pass count=" << c_nThreadPassCount - << " map size=" << c_nMapSize - ); - - Map testMap; - do_test( testMap ); - if ( c_bPrintGCState ) - print_gc_state(); - } - - void setUpParams( const CppUnitMini::TestCfg& cfg ) { - c_nInsertThreadCount = cfg.getULong("InsertThreadCount", 4 ); - c_nDeleteThreadCount = cfg.getULong("DeleteThreadCount", 4 ); - c_nEnsureThreadCount = cfg.getULong("EnsureThreadCount", 4 ); - c_nThreadPassCount = cfg.getULong("ThreadPassCount", 4 ); - c_nMapSize = cfg.getULong("MapSize", 1000000 ); - c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", 8 ); - c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true ); - } - -# include "map2/map_defs.h" - CDSUNIT_DECLARE_MichaelMap - CDSUNIT_DECLARE_SplitList - CDSUNIT_DECLARE_SkipListMap - CDSUNIT_DECLARE_EllenBinTreeMap - CDSUNIT_DECLARE_BronsonAVLTreeMap - CDSUNIT_DECLARE_StripedMap - CDSUNIT_DECLARE_RefinableMap - CDSUNIT_DECLARE_CuckooMap + setUpParams( m_Cfg.get( "Map_InsDel_func" )); + + run_MichaelMap(in_name, invert); + run_SplitList(in_name, invert); + run_SkipListMap(in_name, invert); + run_EllenBinTreeMap(in_name, invert); + run_BronsonAVLTreeMap(in_name, invert); + run_StripedMap(in_name, invert); + run_RefinableMap(in_name, invert); + run_CuckooMap(in_name, invert); + + endTestCase(); + } - CPPUNIT_TEST_SUITE( Map_InsDel_func ) + CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_MichaelMap ) CDSUNIT_TEST_MichaelMap - CDSUNIT_TEST_SplitList - CDSUNIT_TEST_SkipListMap - CDSUNIT_TEST_EllenBinTreeMap - CDSUNIT_TEST_BronsonAVLTreeMap - CDSUNIT_TEST_StripedMap - CDSUNIT_TEST_RefinableMap - CDSUNIT_TEST_CuckooMap - CPPUNIT_TEST_SUITE_END() - - }; - - CPPUNIT_TEST_SUITE_REGISTRATION( Map_InsDel_func ); + CPPUNIT_TEST_SUITE_END_PART() } // namespace map2 diff --git a/tests/unit/map2/map_insdel_func.h b/tests/unit/map2/map_insdel_func.h new file mode 100644 index 00000000..9621e06a --- /dev/null +++ b/tests/unit/map2/map_insdel_func.h @@ -0,0 +1,560 @@ +//$$CDS-header$$ + +#include +#include //unique_lock +#include "map2/map_types.h" +#include "cppunit/thread.h" + +#include +#include +#include // random_shuffle + +namespace map2 { + +# define TEST_MAP(X) void X() { test::X >() ; } +# define TEST_MAP_EXTRACT(X) TEST_MAP(X) +# define TEST_MAP_NOLF(X) void X() { test_nolf::X >() ; } +# define TEST_MAP_NOLF_EXTRACT(X) TEST_MAP_NOLF(X) + + class Map_InsDel_func: public CppUnitMini::TestCase + { + static size_t c_nMapSize; // map size + static size_t c_nInsertThreadCount; // count of insertion thread + static size_t c_nDeleteThreadCount; // count of deletion thread + static size_t c_nEnsureThreadCount; // count of ensure thread + static size_t c_nThreadPassCount; // pass count for each thread + static size_t c_nMaxLoadFactor; // maximum load factor + static bool c_bPrintGCState; + + typedef size_t key_type; + struct value_type { + size_t nKey; + size_t nData; + atomics::atomic nEnsureCall; + atomics::atomic bInitialized; + cds::OS::ThreadId threadId ; // insert thread id + + typedef cds::sync::spin_lock< cds::backoff::pause > lock_type; + mutable lock_type m_access; + + value_type() + : nKey(0) + , nData(0) + , nEnsureCall(0) + , bInitialized( false ) + , threadId( cds::OS::get_current_thread_id() ) + {} + + value_type( value_type const& s ) + : nKey(s.nKey) + , nData(s.nData) + , nEnsureCall(s.nEnsureCall.load(atomics::memory_order_relaxed)) + , bInitialized( s.bInitialized.load(atomics::memory_order_relaxed) ) + , threadId( cds::OS::get_current_thread_id() ) + {} + + // boost::container::flat_map requires operator = + value_type& operator=( value_type const& v ) + { + nKey = v.nKey; + nData = v.nData; + nEnsureCall.store( v.nEnsureCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed ); + bInitialized.store(v.bInitialized.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed); + + return *this; + } + }; + + typedef std::vector key_array; + key_array m_arrValues; + + template + class Inserter: public CppUnitMini::TestThread + { + Map& m_Map; + + virtual Inserter * clone() + { + return new Inserter( *this ); + } + + struct insert_functor { + size_t nTestFunctorRef; + + insert_functor() + : nTestFunctorRef(0) + {} + + template + void operator()( Pair& val ) + { + operator()( val.first, val.second ); + } + + template + void operator()( Key const& key, Val& v ) + { + std::unique_lock< typename value_type::lock_type> ac( v.m_access ); + + v.nKey = key; + v.nData = key * 8; + + ++nTestFunctorRef; + v.bInitialized.store( true, atomics::memory_order_relaxed); + } + }; + + public: + size_t m_nInsertSuccess; + size_t m_nInsertFailed; + + size_t m_nTestFunctorRef; + + public: + Inserter( CppUnitMini::ThreadPool& pool, Map& rMap ) + : CppUnitMini::TestThread( pool ) + , m_Map( rMap ) + {} + Inserter( Inserter& src ) + : CppUnitMini::TestThread( src ) + , m_Map( src.m_Map ) + {} + + Map_InsDel_func& getTest() + { + return reinterpret_cast( m_Pool.m_Test ); + } + + virtual void init() { cds::threading::Manager::attachThread() ; } + virtual void fini() { cds::threading::Manager::detachThread() ; } + + virtual void test() + { + Map& rMap = m_Map; + + m_nInsertSuccess = + m_nInsertFailed = + m_nTestFunctorRef = 0; + + // func is passed by reference + insert_functor func; + key_array const& arr = getTest().m_arrValues; + + if ( m_nThreadNo & 1 ) { + for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { + if ( rMap.insert_with( *it, std::ref(func) ) ) + ++m_nInsertSuccess; + else + ++m_nInsertFailed; + } + } + } + else { + for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { + if ( rMap.insert_with( *it, std::ref(func) ) ) + ++m_nInsertSuccess; + else + ++m_nInsertFailed; + } + } + } + + m_nTestFunctorRef = func.nTestFunctorRef; + } + }; + + template + class Ensurer: public CppUnitMini::TestThread + { + Map& m_Map; + + virtual Ensurer * clone() + { + return new Ensurer( *this ); + } + + struct ensure_functor { + size_t nCreated; + size_t nModified; + + ensure_functor() + : nCreated(0) + , nModified(0) + {} + + template + void operator()( bool bNew, Key const& key, Val& v ) + { + std::unique_lock ac( v.m_access ); + if ( bNew ) { + ++nCreated; + v.nKey = key; + v.nData = key * 8; + v.bInitialized.store( true, atomics::memory_order_relaxed); + } + else { + v.nEnsureCall.fetch_add( 1, atomics::memory_order_relaxed ); + ++nModified; + } + } + + template + void operator()( bool bNew, Pair& val ) + { + operator()( bNew, val.first, val.second ); + } + private: + ensure_functor(const ensure_functor& ); + }; + + public: + size_t m_nEnsureFailed; + size_t m_nEnsureCreated; + size_t m_nEnsureExisted; + size_t m_nFunctorCreated; + size_t m_nFunctorModified; + + public: + Ensurer( CppUnitMini::ThreadPool& pool, Map& rMap ) + : CppUnitMini::TestThread( pool ) + , m_Map( rMap ) + {} + Ensurer( Ensurer& src ) + : CppUnitMini::TestThread( src ) + , m_Map( src.m_Map ) + {} + + Map_InsDel_func& getTest() + { + return reinterpret_cast( m_Pool.m_Test ); + } + + virtual void init() { cds::threading::Manager::attachThread() ; } + virtual void fini() { cds::threading::Manager::detachThread() ; } + + virtual void test() + { + Map& rMap = m_Map; + + m_nEnsureCreated = + m_nEnsureExisted = + m_nEnsureFailed = 0; + + ensure_functor func; + + key_array const& arr = getTest().m_arrValues; + + if ( m_nThreadNo & 1 ) { + for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { + //for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) { + std::pair ret = rMap.ensure( *it, std::ref( func ) ); + if ( ret.first ) { + if ( ret.second ) + ++m_nEnsureCreated; + else + ++m_nEnsureExisted; + } + else + ++m_nEnsureFailed; + } + } + } + else { + for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { + std::pair ret = rMap.ensure( *it, std::ref( func ) ); + if ( ret.first ) { + if ( ret.second ) + ++m_nEnsureCreated; + else + ++m_nEnsureExisted; + } + else + ++m_nEnsureFailed; + } + } + } + + m_nFunctorCreated = func.nCreated; + m_nFunctorModified = func.nModified; + } + }; + + template + class Deleter: public CppUnitMini::TestThread + { + Map& m_Map; + typedef typename Map::mapped_type value_type; + + virtual Deleter * clone() + { + return new Deleter( *this ); + } + + struct value_container + { + size_t nKeyExpected; + + size_t nSuccessItem; + size_t nFailedItem; + + value_container() + : nSuccessItem(0) + , nFailedItem(0) + {} + }; + + struct erase_functor { + value_container m_cnt; + + template + void operator()( Key const& /*key*/, Val& v ) + { + while ( true ) { + if ( v.bInitialized.load( atomics::memory_order_relaxed )) { + std::unique_lock< typename value_type::lock_type> ac( v.m_access ); + + if ( m_cnt.nKeyExpected == v.nKey && m_cnt.nKeyExpected * 8 == v.nData ) + ++m_cnt.nSuccessItem; + else + ++m_cnt.nFailedItem; + v.nData++; + v.nKey = 0; + break; + } + else + cds::backoff::yield()(); + } + } + + template + void operator ()( Pair& item ) + { + operator()( item.first, item.second ); + } + }; + + public: + size_t m_nDeleteSuccess; + size_t m_nDeleteFailed; + + size_t m_nValueSuccess; + size_t m_nValueFailed; + + public: + Deleter( CppUnitMini::ThreadPool& pool, Map& rMap ) + : CppUnitMini::TestThread( pool ) + , m_Map( rMap ) + {} + Deleter( Deleter& src ) + : CppUnitMini::TestThread( src ) + , m_Map( src.m_Map ) + {} + + Map_InsDel_func& getTest() + { + return reinterpret_cast( m_Pool.m_Test ); + } + + virtual void init() { cds::threading::Manager::attachThread() ; } + virtual void fini() { cds::threading::Manager::detachThread() ; } + + virtual void test() + { + Map& rMap = m_Map; + + m_nDeleteSuccess = + m_nDeleteFailed = 0; + + erase_functor func; + key_array const& arr = getTest().m_arrValues; + + if ( m_nThreadNo & 1 ) { + for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( key_array::const_iterator it = arr.begin(), itEnd = arr.end(); it != itEnd; ++it ) { + func.m_cnt.nKeyExpected = *it; + if ( rMap.erase( *it, std::ref(func) )) + ++m_nDeleteSuccess; + else + ++m_nDeleteFailed; + } + } + } + else { + for ( size_t nPass = 0; nPass < c_nThreadPassCount; ++nPass ) { + for ( key_array::const_reverse_iterator it = arr.rbegin(), itEnd = arr.rend(); it != itEnd; ++it ) { + func.m_cnt.nKeyExpected = *it; + if ( rMap.erase( *it, std::ref(func) )) + ++m_nDeleteSuccess; + else + ++m_nDeleteFailed; + } + } + } + + m_nValueSuccess = func.m_cnt.nSuccessItem; + m_nValueFailed = func.m_cnt.nFailedItem; + } + }; + + protected: + + template + void do_test( Map& testMap ) + { + typedef Inserter InserterThread; + typedef Deleter DeleterThread; + typedef Ensurer EnsurerThread; + cds::OS::Timer timer; + + m_arrValues.clear(); + m_arrValues.reserve( c_nMapSize ); + for ( size_t i = 0; i < c_nMapSize; ++i ) + m_arrValues.push_back( i ); + std::random_shuffle( m_arrValues.begin(), m_arrValues.end() ); + + CppUnitMini::ThreadPool pool( *this ); + pool.add( new InserterThread( pool, testMap ), c_nInsertThreadCount ); + pool.add( new DeleterThread( pool, testMap ), c_nDeleteThreadCount ); + pool.add( new EnsurerThread( pool, testMap ), c_nEnsureThreadCount ); + pool.run(); + CPPUNIT_MSG( " Duration=" << pool.avgDuration() ); + + size_t nInsertSuccess = 0; + size_t nInsertFailed = 0; + size_t nDeleteSuccess = 0; + size_t nDeleteFailed = 0; + size_t nDelValueSuccess = 0; + size_t nDelValueFailed = 0; + size_t nEnsureFailed = 0; + size_t nEnsureCreated = 0; + size_t nEnsureModified = 0; + size_t nEnsFuncCreated = 0; + size_t nEnsFuncModified = 0; + size_t nTestFunctorRef = 0; + + for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) { + InserterThread * pThread = dynamic_cast( *it ); + if ( pThread ) { + nInsertSuccess += pThread->m_nInsertSuccess; + nInsertFailed += pThread->m_nInsertFailed; + nTestFunctorRef += pThread->m_nTestFunctorRef; + } + else { + DeleterThread * p = dynamic_cast( *it ); + if ( p ) { + nDeleteSuccess += p->m_nDeleteSuccess; + nDeleteFailed += p->m_nDeleteFailed; + nDelValueSuccess += p->m_nValueSuccess; + nDelValueFailed += p->m_nValueFailed; + } + else { + EnsurerThread * pEns = static_cast( *it ); + nEnsureCreated += pEns->m_nEnsureCreated; + nEnsureModified += pEns->m_nEnsureExisted; + nEnsureFailed += pEns->m_nEnsureFailed; + nEnsFuncCreated += pEns->m_nFunctorCreated; + nEnsFuncModified += pEns->m_nFunctorModified; + } + } + } + + CPPUNIT_MSG( " Totals: Ins succ=" << nInsertSuccess + << " Del succ=" << nDeleteSuccess << "\n" + << " : Ins fail=" << nInsertFailed + << " Del fail=" << nDeleteFailed << "\n" + << " : Ensure succ=" << (nEnsureCreated + nEnsureModified) << " fail=" << nEnsureFailed + << " create=" << nEnsureCreated << " modify=" << nEnsureModified << "\n" + << " Map size=" << testMap.size() + ); + + CPPUNIT_CHECK_EX( nDelValueFailed == 0, "Functor del failed=" << nDelValueFailed ); + CPPUNIT_CHECK_EX( nDelValueSuccess == nDeleteSuccess, "Delete success=" << nDeleteSuccess << " functor=" << nDelValueSuccess ); + + CPPUNIT_CHECK( nEnsureFailed == 0 ); + + CPPUNIT_CHECK_EX( nEnsureCreated == nEnsFuncCreated, "Ensure created=" << nEnsureCreated << " functor=" << nEnsFuncCreated ); + CPPUNIT_CHECK_EX( nEnsureModified == nEnsFuncModified, "Ensure modified=" << nEnsureModified << " functor=" << nEnsFuncModified ); + + // nTestFunctorRef is call count of insert functor + CPPUNIT_CHECK_EX( nTestFunctorRef == nInsertSuccess, "nInsertSuccess=" << nInsertSuccess << " functor nTestFunctorRef=" << nTestFunctorRef ); + + check_before_cleanup( testMap ); + + CPPUNIT_MSG( " Clear map (single-threaded)..." ); + timer.reset(); + for ( size_t nItem = 0; nItem < c_nMapSize; ++nItem ) { + testMap.erase( nItem ); + } + CPPUNIT_MSG( " Duration=" << timer.duration() ); + CPPUNIT_CHECK( testMap.empty() ); + + additional_check( testMap ); + print_stat( testMap ); + additional_cleanup( testMap ); + } + + template + void test() + { + CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount + << " delete=" << c_nDeleteThreadCount + << " ensure=" << c_nEnsureThreadCount + << " pass count=" << c_nThreadPassCount + << " map size=" << c_nMapSize + ); + + for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) { + CPPUNIT_MSG( "Load factor=" << nLoadFactor ); + Map testMap( c_nMapSize, nLoadFactor ); + do_test( testMap ); + if ( c_bPrintGCState ) + print_gc_state(); + } + + } + + template + void test_nolf() + { + CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount + << " delete=" << c_nDeleteThreadCount + << " ensure=" << c_nEnsureThreadCount + << " pass count=" << c_nThreadPassCount + << " map size=" << c_nMapSize + ); + + Map testMap; + do_test( testMap ); + if ( c_bPrintGCState ) + print_gc_state(); + } + + typedef CppUnitMini::TestCase Base; + void setUpParams( const CppUnitMini::TestCfg& cfg ); + + void run_MichaelMap(const char *in_name, bool invert = false); + void run_SplitList(const char *in_name, bool invert = false); + void run_StripedMap(const char *in_name, bool invert = false); + void run_RefinableMap(const char *in_name, bool invert = false); + void run_CuckooMap(const char *in_name, bool invert = false); + void run_SkipListMap(const char *in_name, bool invert = false); + void run_EllenBinTreeMap(const char *in_name, bool invert = false); + void run_BronsonAVLTreeMap(const char *in_name, bool invert = false); + + virtual void myRun(const char *in_name, bool invert = false); + +# include "map2/map_defs.h" + CDSUNIT_DECLARE_MichaelMap + CDSUNIT_DECLARE_SplitList + CDSUNIT_DECLARE_SkipListMap + CDSUNIT_DECLARE_EllenBinTreeMap + CDSUNIT_DECLARE_BronsonAVLTreeMap + CDSUNIT_DECLARE_StripedMap + CDSUNIT_DECLARE_RefinableMap + CDSUNIT_DECLARE_CuckooMap + }; +} // namespace map2 diff --git a/tests/unit/map2/map_insdel_func2.cpp b/tests/unit/map2/map_insdel_func2.cpp new file mode 100644 index 00000000..da1c3fac --- /dev/null +++ b/tests/unit/map2/map_insdel_func2.cpp @@ -0,0 +1,10 @@ +//$$CDS-header$$ + +#include "map2/map_insdel_func.h" + +namespace map2 { + CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_SplitList ) + CDSUNIT_TEST_SplitList + CPPUNIT_TEST_SUITE_END_PART() +} // namespace map2 + diff --git a/tests/unit/map2/map_insdel_func3.cpp b/tests/unit/map2/map_insdel_func3.cpp new file mode 100644 index 00000000..9cec610e --- /dev/null +++ b/tests/unit/map2/map_insdel_func3.cpp @@ -0,0 +1,10 @@ +//$$CDS-header$$ + +#include "map2/map_insdel_func.h" + +namespace map2 { + CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_SkipListMap ) + CDSUNIT_TEST_SkipListMap + CPPUNIT_TEST_SUITE_END_PART() +} // namespace map2 + diff --git a/tests/unit/map2/map_insdel_func4.cpp b/tests/unit/map2/map_insdel_func4.cpp new file mode 100644 index 00000000..1533d352 --- /dev/null +++ b/tests/unit/map2/map_insdel_func4.cpp @@ -0,0 +1,10 @@ +//$$CDS-header$$ + +#include "map2/map_insdel_func.h" + +namespace map2 { + CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_EllenBinTreeMap ) + CDSUNIT_TEST_EllenBinTreeMap + CPPUNIT_TEST_SUITE_END_PART() +} // namespace map2 + diff --git a/tests/unit/map2/map_insdel_func5.cpp b/tests/unit/map2/map_insdel_func5.cpp new file mode 100644 index 00000000..30d277d3 --- /dev/null +++ b/tests/unit/map2/map_insdel_func5.cpp @@ -0,0 +1,9 @@ +//$$CDS-header$$ + +#include "map2/map_insdel_func.h" + +namespace map2 { + CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_BronsonAVLTreeMap ) + CDSUNIT_TEST_BronsonAVLTreeMap + CPPUNIT_TEST_SUITE_END_PART() +} // namespace map2 diff --git a/tests/unit/map2/map_insdel_func6.cpp b/tests/unit/map2/map_insdel_func6.cpp new file mode 100644 index 00000000..f6841183 --- /dev/null +++ b/tests/unit/map2/map_insdel_func6.cpp @@ -0,0 +1,9 @@ +//$$CDS-header$$ + +#include "map2/map_insdel_func.h" + +namespace map2 { + CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_StripedMap ) + CDSUNIT_TEST_StripedMap + CPPUNIT_TEST_SUITE_END_PART() +} // namespace map2 diff --git a/tests/unit/map2/map_insdel_func7.cpp b/tests/unit/map2/map_insdel_func7.cpp new file mode 100644 index 00000000..10fdfad6 --- /dev/null +++ b/tests/unit/map2/map_insdel_func7.cpp @@ -0,0 +1,9 @@ +//$$CDS-header$$ + +#include "map2/map_insdel_func.h" + +namespace map2 { + CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_RefinableMap ) + CDSUNIT_TEST_RefinableMap + CPPUNIT_TEST_SUITE_END_PART() +} // namespace map2 diff --git a/tests/unit/map2/map_insdel_func8.cpp b/tests/unit/map2/map_insdel_func8.cpp new file mode 100644 index 00000000..b8901950 --- /dev/null +++ b/tests/unit/map2/map_insdel_func8.cpp @@ -0,0 +1,9 @@ +//$$CDS-header$$ + +#include "map2/map_insdel_func.h" + +namespace map2 { + CPPUNIT_TEST_SUITE_PART( Map_InsDel_func, run_CuckooMap ) + CDSUNIT_TEST_CuckooMap + CPPUNIT_TEST_SUITE_END_PART() +} // namespace map2 -- 2.34.1