3 #include "cppunit/thread.h"
4 #include "set2/set_types.h"
5 #include <algorithm> // random_shuffle
9 # define TEST_SET(X) void X() { test<SetTypes<key_type, value_type>::X >() ; }
10 # define TEST_SET_EXTRACT(X) void X() { test_extract<SetTypes<key_type, value_type>::X >() ; }
11 # define TEST_SET_NOLF(X) void X() { test_nolf<SetTypes<key_type, value_type>::X >() ; }
12 # define TEST_SET_NOLF_EXTRACT(X) void X() { test_nolf_extract<SetTypes<key_type, value_type>::X >() ; }
15 static size_t c_nSetSize = 1000000 ; // max set size
16 static size_t c_nInsThreadCount = 4 ; // insert thread count
17 static size_t c_nDelThreadCount = 4 ; // delete thread count
18 static size_t c_nExtractThreadCount = 4 ; // extract thread count
19 static size_t c_nMaxLoadFactor = 8 ; // maximum load factor
20 static bool c_bPrintGCState = true;
29 key_thread( size_t key, size_t threadNo )
38 typedef SetTypes<key_thread, size_t>::key_val key_value_pair;
42 struct cmp<key_thread> {
43 int operator ()(key_thread const& k1, key_thread const& k2) const
45 if ( k1.nKey < k2.nKey )
47 if ( k1.nKey > k2.nKey )
49 if ( k1.nThread < k2.nThread )
51 if ( k1.nThread > k2.nThread )
55 int operator ()(key_thread const& k1, size_t k2) const
63 int operator ()(size_t k1, key_thread const& k2) const
77 struct less<set2::key_thread>
79 bool operator()(set2::key_thread const& k1, set2::key_thread const& k2) const
81 if ( k1.nKey <= k2.nKey )
82 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
88 struct hash<set2::key_thread>
90 typedef size_t result_type;
91 typedef set2::key_thread argument_type;
93 size_t operator()( set2::key_thread const& k ) const
95 return std::hash<size_t>()(k.nKey);
97 size_t operator()( size_t k ) const
99 return std::hash<size_t>()(k);
106 inline size_t hash_value( set2::key_thread const& k )
108 return std::hash<size_t>()( k.nKey );
112 struct hash<set2::key_thread>
114 typedef size_t result_type;
115 typedef set2::key_thread argument_type;
117 size_t operator()(set2::key_thread const& k) const
119 return boost::hash<size_t>()( k.nKey );
121 size_t operator()(size_t k) const
123 return boost::hash<size_t>()( k );
130 template <typename Set>
131 static inline void check_before_clear( Set& s )
134 template <typename GC, typename Key, typename T, typename Traits>
135 static inline void check_before_clear( cds::container::EllenBinTreeSet<GC, Key, T, Traits>& s )
137 CPPUNIT_CHECK_CURRENT( s.check_consistency() );
140 class Set_DelOdd: public CppUnitMini::TestCase
142 std::vector<size_t> m_arrData;
145 typedef key_thread key_type;
146 typedef size_t value_type;
148 atomics::atomic<size_t> m_nInsThreadCount;
150 // Inserts keys from [0..N)
152 class InsertThread: public CppUnitMini::TestThread
156 virtual InsertThread * clone()
158 return new InsertThread( *this );
163 template <typename Q>
164 void operator()( bool bNew, key_value_pair const&, Q const& )
168 size_t m_nInsertSuccess;
169 size_t m_nInsertFailed;
172 InsertThread( CppUnitMini::ThreadPool& pool, Set& rMap )
173 : CppUnitMini::TestThread( pool )
176 InsertThread( InsertThread& src )
177 : CppUnitMini::TestThread( src )
181 Set_DelOdd& getTest()
183 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
186 virtual void init() { cds::threading::Manager::attachThread() ; }
187 virtual void fini() { cds::threading::Manager::detachThread() ; }
196 std::vector<size_t>& arrData = getTest().m_arrData;
197 for ( size_t i = 0; i < arrData.size(); ++i ) {
198 if ( rSet.insert( key_type( arrData[i], m_nThreadNo )))
205 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
206 if ( arrData[i] & 1 ) {
207 rSet.ensure( key_type( arrData[i], m_nThreadNo ), f );
211 getTest().m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
216 bool operator()( key_type const& k1, key_type const& k2 ) const
218 return k1.nKey == k2.nKey;
220 bool operator()( size_t k1, key_type const& k2 ) const
222 return k1 == k2.nKey;
224 bool operator()( key_type const& k1, size_t k2 ) const
226 return k1.nKey == k2;
228 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
230 return operator()( k1.key, k2.key );
232 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
234 return operator()( k1.key, k2 );
236 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
238 return operator()( k1, k2.key );
240 bool operator ()( key_value_pair const& k1, size_t k2 ) const
242 return operator()( k1.key, k2 );
244 bool operator ()( size_t k1, key_value_pair const& k2 ) const
246 return operator()( k1, k2.key );
251 bool operator()( key_type const& k1, key_type const& k2 ) const
253 return k1.nKey < k2.nKey;
255 bool operator()( size_t k1, key_type const& k2 ) const
259 bool operator()( key_type const& k1, size_t k2 ) const
263 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
265 return operator()( k1.key, k2.key );
267 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
269 return operator()( k1.key, k2 );
271 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
273 return operator()( k1, k2.key );
275 bool operator ()( key_value_pair const& k1, size_t k2 ) const
277 return operator()( k1.key, k2 );
279 bool operator ()( size_t k1, key_value_pair const& k2 ) const
281 return operator()( k1, k2.key );
284 typedef key_equal equal_to;
287 // Deletes odd keys from [0..N)
289 class DeleteThread: public CppUnitMini::TestThread
293 virtual DeleteThread * clone()
295 return new DeleteThread( *this );
298 size_t m_nDeleteSuccess;
299 size_t m_nDeleteFailed;
302 DeleteThread( CppUnitMini::ThreadPool& pool, Set& rMap )
303 : CppUnitMini::TestThread( pool )
306 DeleteThread( DeleteThread& src )
307 : CppUnitMini::TestThread( src )
311 Set_DelOdd& getTest()
313 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
316 virtual void init() { cds::threading::Manager::attachThread() ; }
317 virtual void fini() { cds::threading::Manager::detachThread() ; }
326 std::vector<size_t>& arrData = getTest().m_arrData;
327 if ( m_nThreadNo & 1 ) {
328 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
329 for ( size_t i = 0; i < arrData.size(); ++i ) {
330 if ( arrData[i] & 1 ) {
331 if ( rSet.erase_with( arrData[i], key_less() ))
337 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
342 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
343 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
344 if ( arrData[i] & 1 ) {
345 if ( rSet.erase_with( arrData[i], key_less() ))
351 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
358 // Extracts odd keys from [0..N)
359 template <typename GC, class Set>
360 class ExtractThread: public CppUnitMini::TestThread
364 virtual ExtractThread * clone()
366 return new ExtractThread( *this );
369 size_t m_nExtractSuccess;
370 size_t m_nExtractFailed;
373 ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap )
374 : CppUnitMini::TestThread( pool )
377 ExtractThread( ExtractThread& src )
378 : CppUnitMini::TestThread( src )
382 Set_DelOdd& getTest()
384 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
387 virtual void init() { cds::threading::Manager::attachThread() ; }
388 virtual void fini() { cds::threading::Manager::detachThread() ; }
395 m_nExtractFailed = 0;
397 typename Set::guarded_ptr gp;
399 std::vector<size_t>& arrData = getTest().m_arrData;
400 if ( m_nThreadNo & 1 ) {
401 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
402 for ( size_t i = 0; i < arrData.size(); ++i ) {
403 if ( arrData[i] & 1 ) {
404 if ( rSet.extract_with( gp, arrData[i], key_less() ))
410 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
415 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
416 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
417 if ( arrData[i] & 1 ) {
418 if ( rSet.extract_with( gp, arrData[i], key_less() ))
424 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
431 template <typename RCU, class Set>
432 class ExtractThread< cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
436 virtual ExtractThread * clone()
438 return new ExtractThread( *this );
441 size_t m_nExtractSuccess;
442 size_t m_nExtractFailed;
445 ExtractThread( CppUnitMini::ThreadPool& pool, Set& rMap )
446 : CppUnitMini::TestThread( pool )
449 ExtractThread( ExtractThread& src )
450 : CppUnitMini::TestThread( src )
454 Set_DelOdd& getTest()
456 return reinterpret_cast<Set_DelOdd&>( m_Pool.m_Test );
459 virtual void init() { cds::threading::Manager::attachThread() ; }
460 virtual void fini() { cds::threading::Manager::detachThread() ; }
467 m_nExtractFailed = 0;
469 typename Set::exempt_ptr xp;
471 std::vector<size_t>& arrData = getTest().m_arrData;
472 if ( m_nThreadNo & 1 ) {
473 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
474 for ( size_t i = 0; i < arrData.size(); ++i ) {
475 if ( arrData[i] & 1 ) {
476 if ( Set::c_bExtractLockExternal ) {
477 typename Set::rcu_lock l;
478 if ( rSet.extract_with( xp, arrData[i], key_less() ))
484 if ( rSet.extract_with( xp, arrData[i], key_less() ))
492 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
497 for ( size_t k = 0; k < c_nInsThreadCount; ++k ) {
498 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
499 if ( arrData[i] & 1 ) {
500 if ( Set::c_bExtractLockExternal ) {
501 typename Set::rcu_lock l;
502 if ( rSet.extract_with( xp, arrData[i], key_less() ))
508 if ( rSet.extract_with( xp, arrData[i], key_less() ))
516 if ( getTest().m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
525 void do_test( size_t nLoadFactor )
527 Set testSet( c_nSetSize, nLoadFactor );
528 do_test_with( testSet );
533 void do_test_extract( size_t nLoadFactor )
535 Set testSet( c_nSetSize, nLoadFactor );
536 do_test_extract_with( testSet );
541 void do_test_with( Set& testSet )
543 typedef InsertThread<Set> insert_thread;
544 typedef DeleteThread<Set> delete_thread;
546 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
548 CppUnitMini::ThreadPool pool( *this );
549 pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount );
550 pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount ? c_nDelThreadCount : cds::OS::topology::processor_count());
552 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
554 size_t nInsertSuccess = 0;
555 size_t nInsertFailed = 0;
556 size_t nDeleteSuccess = 0;
557 size_t nDeleteFailed = 0;
558 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
559 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
561 nInsertSuccess += pThread->m_nInsertSuccess;
562 nInsertFailed += pThread->m_nInsertFailed;
565 delete_thread * p = static_cast<delete_thread *>( *it );
566 nDeleteSuccess += p->m_nDeleteSuccess;
567 nDeleteFailed += p->m_nDeleteFailed;
571 CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount );
572 CPPUNIT_CHECK( nInsertFailed == 0 );
574 CPPUNIT_MSG( " Totals (success/failed): \n\t"
575 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
576 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
581 void do_test_extract_with( Set& testSet )
583 typedef InsertThread<Set> insert_thread;
584 typedef DeleteThread<Set> delete_thread;
585 typedef ExtractThread< typename Set::gc, Set > extract_thread;
587 m_nInsThreadCount.store( c_nInsThreadCount, atomics::memory_order_release );
589 CppUnitMini::ThreadPool pool( *this );
590 pool.add( new insert_thread( pool, testSet ), c_nInsThreadCount );
591 if ( c_nDelThreadCount )
592 pool.add( new delete_thread( pool, testSet ), c_nDelThreadCount );
593 if ( c_nExtractThreadCount )
594 pool.add( new extract_thread( pool, testSet ), c_nExtractThreadCount );
596 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
598 size_t nInsertSuccess = 0;
599 size_t nInsertFailed = 0;
600 size_t nDeleteSuccess = 0;
601 size_t nDeleteFailed = 0;
602 size_t nExtractSuccess = 0;
603 size_t nExtractFailed = 0;
604 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
605 insert_thread * pThread = dynamic_cast<insert_thread *>( *it );
607 nInsertSuccess += pThread->m_nInsertSuccess;
608 nInsertFailed += pThread->m_nInsertFailed;
611 delete_thread * p = dynamic_cast<delete_thread *>( *it );
613 nDeleteSuccess += p->m_nDeleteSuccess;
614 nDeleteFailed += p->m_nDeleteFailed;
617 extract_thread * pExt = dynamic_cast<extract_thread *>( *it );
619 nExtractSuccess += pExt->m_nExtractSuccess;
620 nExtractFailed += pExt->m_nExtractFailed;
625 CPPUNIT_CHECK( nInsertSuccess == c_nSetSize * c_nInsThreadCount );
626 CPPUNIT_CHECK( nInsertFailed == 0 );
628 CPPUNIT_MSG( " Totals (success/failed): \n\t"
629 << " Insert=" << nInsertSuccess << '/' << nInsertFailed << "\n\t"
630 << " Delete=" << nDeleteSuccess << '/' << nDeleteFailed << "\n\t"
631 << " Extract=" << nExtractSuccess << '/' << nExtractFailed << "\n\t"
635 template <typename Set>
636 void analyze( Set& testSet )
638 // All even keys must be in the set
640 CPPUNIT_MSG( " Check even keys..." );
641 size_t nErrorCount = 0;
642 for ( size_t n = 0; n < c_nSetSize; n +=2 ) {
643 for ( size_t i = 0; i < c_nInsThreadCount; ++i ) {
644 if ( !testSet.find( key_type(n, i) ) ) {
645 if ( ++nErrorCount < 10 ) {
646 CPPUNIT_MSG( "key " << n << "-" << i << " is not found!");
651 CPPUNIT_CHECK_EX( nErrorCount == 0, "Totals: " << nErrorCount << " keys is not found");
654 check_before_clear( testSet );
656 CPPUNIT_MSG( " Clear map (single-threaded)..." );
657 cds::OS::Timer timer;
659 CPPUNIT_MSG( " Duration=" << timer.duration() );
660 CPPUNIT_CHECK_EX( testSet.empty(), ((long long) testSet.size()) );
662 additional_check( testSet );
663 print_stat( testSet );
664 additional_cleanup( testSet );
670 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
671 << " delete thread count=" << c_nDelThreadCount
672 << " set size=" << c_nSetSize
675 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
676 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
677 do_test<Set>( nLoadFactor );
678 if ( c_bPrintGCState )
686 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
687 << " delete thread count=" << c_nDelThreadCount
688 << " extract thread count=" << c_nExtractThreadCount
689 << " set size=" << c_nSetSize
692 for ( size_t nLoadFactor = 1; nLoadFactor <= c_nMaxLoadFactor; nLoadFactor *= 2 ) {
693 CPPUNIT_MSG( "Load factor=" << nLoadFactor );
694 do_test_extract<Set>( nLoadFactor );
695 if ( c_bPrintGCState )
703 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
704 << " delete thread count=" << c_nDelThreadCount
705 << " set size=" << c_nSetSize
714 if ( c_bPrintGCState )
719 void test_nolf_extract()
721 CPPUNIT_MSG( "Insert thread count=" << c_nInsThreadCount
722 << " delete thread count=" << c_nDelThreadCount
723 << " extract thread count=" << c_nExtractThreadCount
724 << " set size=" << c_nSetSize
729 do_test_extract_with( s );
733 if ( c_bPrintGCState )
737 void setUpParams( const CppUnitMini::TestCfg& cfg ) {
738 c_nSetSize = cfg.getULong("MapSize", static_cast<unsigned long>(c_nSetSize) );
739 c_nInsThreadCount = cfg.getULong("InsThreadCount", static_cast<unsigned long>(c_nInsThreadCount) );
740 c_nDelThreadCount = cfg.getULong("DelThreadCount", static_cast<unsigned long>(c_nDelThreadCount) );
741 c_nExtractThreadCount = cfg.getULong("ExtractThreadCount", static_cast<unsigned long>(c_nExtractThreadCount) );
742 c_nMaxLoadFactor = cfg.getULong("MaxLoadFactor", static_cast<unsigned long>(c_nMaxLoadFactor) );
743 c_bPrintGCState = cfg.getBool("PrintGCStateFlag", true );
745 if ( c_nInsThreadCount == 0 )
746 c_nInsThreadCount = cds::OS::topology::processor_count();
747 if ( c_nDelThreadCount == 0 && c_nExtractThreadCount == 0 ) {
748 c_nExtractThreadCount = cds::OS::topology::processor_count() / 2;
749 c_nDelThreadCount = cds::OS::topology::processor_count() - c_nExtractThreadCount;
752 m_arrData.resize( c_nSetSize );
753 for ( size_t i = 0; i < c_nSetSize; ++i )
755 std::random_shuffle( m_arrData.begin(), m_arrData.end() );
758 # include "set2/set_defs.h"
759 CDSUNIT_DECLARE_MichaelSet
760 CDSUNIT_DECLARE_SplitList
761 //CDSUNIT_DECLARE_StripedSet
762 //CDSUNIT_DECLARE_RefinableSet
763 CDSUNIT_DECLARE_CuckooSet
764 CDSUNIT_DECLARE_SkipListSet
765 CDSUNIT_DECLARE_EllenBinTreeSet
766 //CDSUNIT_DECLARE_StdSet
768 CPPUNIT_TEST_SUITE_( Set_DelOdd, "Map_DelOdd" )
769 CDSUNIT_TEST_MichaelSet
770 CDSUNIT_TEST_SplitList
771 CDSUNIT_TEST_SkipListSet
772 CDSUNIT_TEST_EllenBinTreeSet
773 //CDSUNIT_TEST_StripedSet
774 //CDSUNIT_TEST_RefinableSet
775 CDSUNIT_TEST_CuckooSet
776 //CDSUNIT_TEST_StdSet
777 CPPUNIT_TEST_SUITE_END()
780 CPPUNIT_TEST_SUITE_REGISTRATION( Set_DelOdd );