2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 #include <cds/os/topology.h>
41 key_thread( size_t key, size_t threadNo )
42 : nKey( static_cast<uint32_t>(key))
43 , nThread( static_cast<uint16_t>(threadNo))
52 static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
54 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
57 struct cmp<key_thread> {
58 int operator ()(key_thread const& k1, key_thread const& k2) const
60 if ( k1.nKey < k2.nKey )
62 if ( k1.nKey > k2.nKey )
64 if ( k1.nThread < k2.nThread )
66 if ( k1.nThread > k2.nThread )
70 int operator ()(key_thread const& k1, size_t k2) const
78 int operator ()(size_t k1, key_thread const& k2) const
89 struct less<set::key_thread>
91 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
93 if ( k1.nKey <= k2.nKey )
94 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
100 struct hash<set::key_thread>
102 typedef size_t result_type;
103 typedef set::key_thread argument_type;
105 size_t operator()( set::key_thread const& k ) const
107 return std::hash<size_t>()(k.nKey);
110 size_t operator()( size_t k ) const
112 return std::hash<size_t>()(k);
117 class Set_Iter_Del3: public cds_test::stress_fixture
120 static size_t s_nSetSize; // max set size
121 static size_t s_nInsThreadCount; // insert thread count
122 static size_t s_nDelThreadCount; // delete thread count
123 static size_t s_nExtractThreadCount; // extract thread count
124 static size_t s_nMaxLoadFactor; // maximum load factor
125 static size_t s_nInsertPassCount;
126 static size_t s_nFindThreadCount; // find thread count
128 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
129 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
130 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
132 static size_t s_nFeldmanSet_HeadBits;
133 static size_t s_nFeldmanSet_ArrayBits;
135 static size_t s_nLoadFactor;
137 static std::vector<size_t> m_arrData;
139 static void SetUpTestCase();
140 static void TearDownTestCase();
142 template <typename Pred>
143 static void prepare_array( std::vector<size_t>& arr, Pred pred )
145 arr.reserve( m_arrData.size());
146 for ( auto el : m_arrData ) {
150 arr.resize( arr.size());
151 shuffle( arr.begin(), arr.end());
155 typedef key_thread key_type;
156 typedef size_t value_type;
158 atomics::atomic<size_t> m_nInsThreadCount;
168 // Inserts keys from [0..N)
170 class Inserter: public cds_test::thread
172 typedef cds_test::thread base_class;
175 struct update_functor
177 template <typename Q>
178 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
181 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
187 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
188 for ( size_t i = 0; i < m_arr.size(); ++i ) {
189 if ( m_Set.insert( key_type( m_arr[i], id())))
190 ++m_nInsertInitSuccess;
192 ++m_nInsertInitFailed;
197 size_t m_nInsertSuccess = 0;
198 size_t m_nInsertFailed = 0;
199 size_t m_nInsertInitSuccess = 0;
200 size_t m_nInsertInitFailed = 0;
202 std::vector<size_t> m_arr;
205 Inserter( cds_test::thread_pool& pool, Set& set )
206 : base_class( pool, inserter_thread )
212 Inserter( Inserter& src )
219 virtual thread * clone()
221 return new Inserter( *this );
227 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
229 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
232 for ( auto el : m_arr ) {
234 if ( rSet.insert( key_type( el, id())))
243 for ( auto el : m_arr ) {
247 std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
248 if ( success && inserted )
257 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
263 bool operator()( key_type const& k1, key_type const& k2 ) const
265 return k1.nKey == k2.nKey;
267 bool operator()( size_t k1, key_type const& k2 ) const
269 return k1 == k2.nKey;
271 bool operator()( key_type const& k1, size_t k2 ) const
273 return k1.nKey == k2;
275 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
277 return operator()( k1.key, k2.key );
279 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
281 return operator()( k1.key, k2 );
283 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
285 return operator()( k1, k2.key );
287 bool operator ()( key_value_pair const& k1, size_t k2 ) const
289 return operator()( k1.key, k2 );
291 bool operator ()( size_t k1, key_value_pair const& k2 ) const
293 return operator()( k1, k2.key );
298 bool operator()( key_type const& k1, key_type const& k2 ) const
300 return k1.nKey < k2.nKey;
302 bool operator()( size_t k1, key_type const& k2 ) const
306 bool operator()( key_type const& k1, size_t k2 ) const
310 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
312 return operator()( k1.key, k2.key );
314 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
316 return operator()( k1.key, k2 );
318 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
320 return operator()( k1, k2.key );
322 bool operator ()( key_value_pair const& k1, size_t k2 ) const
324 return operator()( k1.key, k2 );
326 bool operator ()( size_t k1, key_value_pair const& k2 ) const
328 return operator()( k1, k2.key );
331 typedef key_equal equal_to;
334 // Deletes keys from [0..N)
335 template <class Set, typename Iterator>
336 class Deleter: public cds_test::thread
338 typedef cds_test::thread base_class;
342 size_t m_nDeleteSuccess = 0;
343 size_t m_nDeleteFailed = 0;
346 Deleter( cds_test::thread_pool& pool, Set& set )
347 : base_class( pool, deleter_thread )
351 Deleter( Deleter& src )
356 virtual thread * clone()
358 return new Deleter( *this );
365 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
368 auto itEnd = rSet.template get_end<Iterator>();
369 for ( auto it = rSet.template get_begin<Iterator>(); it != itEnd; ++it ) {
370 if ( it->key.nKey & 3 ) {
371 if ( rSet.erase_at( it ))
377 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
381 // Extracts keys from [0..N)
382 template <typename GC, class Set>
383 class Extractor: public cds_test::thread
385 typedef cds_test::thread base_class;
388 std::vector<size_t> m_arr;
392 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
396 size_t m_nExtractSuccess = 0;
397 size_t m_nExtractFailed = 0;
400 Extractor( cds_test::thread_pool& pool, Set& set )
401 : base_class( pool, extractor_thread )
407 Extractor( Extractor& src )
414 virtual thread * clone()
416 return new Extractor( *this );
422 typename Set::guarded_ptr gp;
424 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
425 size_t const nInsThreadCount = s_nInsThreadCount;
429 for ( auto el : m_arr ) {
430 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
431 gp = rSet.extract( key_type( el, k ));
441 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
442 for ( auto el : m_arr ) {
443 gp = rSet.extract( key_type( el, k ));
452 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
458 template <typename RCU, class Set>
459 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
461 typedef cds_test::thread base_class;
463 std::vector<size_t> m_arr;
467 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
471 size_t m_nExtractSuccess = 0;
472 size_t m_nExtractFailed = 0;
475 Extractor( cds_test::thread_pool& pool, Set& set )
476 : base_class( pool, extractor_thread )
482 Extractor( Extractor& src )
489 virtual thread * clone()
491 return new Extractor( *this );
497 typename Set::exempt_ptr xp;
499 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
500 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
504 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
505 for ( auto el : m_arr ) {
506 if ( Set::c_bExtractLockExternal ) {
507 typename Set::rcu_lock l;
508 xp = rSet.extract( key_type( el, k ));
515 xp = rSet.extract( key_type( el, k ));
526 for ( auto el : m_arr ) {
527 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
528 if ( Set::c_bExtractLockExternal ) {
529 typename Set::rcu_lock l;
530 xp = rSet.extract( key_type( el, k ));
537 xp = rSet.extract( key_type( el, k ));
547 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
555 class Observer: public cds_test::thread
557 typedef cds_test::thread base_class;
561 size_t m_nFindEvenSuccess = 0;
562 size_t m_nFindEvenFailed = 0;
563 size_t m_nFindOddSuccess = 0;
564 size_t m_nFindOddFailed = 0;
567 Observer( cds_test::thread_pool& pool, Set& set )
568 : base_class( pool, find_thread )
572 Observer( Observer& src )
577 virtual thread * clone()
579 return new Observer( *this );
585 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
586 std::vector<size_t> const& arr = m_arrData;
587 size_t const nInsThreadCount = s_nInsThreadCount;
590 for ( size_t key : arr ) {
592 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
593 if ( set.contains( key_thread( key, k )))
600 // that keys MUST be in the map
601 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
602 if ( set.contains( key_thread( key, k )))
603 ++m_nFindEvenSuccess;
609 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
614 template <typename Iterator, class Set>
615 void do_test_with( Set& testSet )
617 typedef Inserter<Set> insert_thread;
618 typedef Deleter<Set, Iterator> delete_thread;
619 typedef Observer<Set> observer_thread;
621 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
623 cds_test::thread_pool& pool = get_pool();
624 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
625 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
626 if ( s_nFindThreadCount )
627 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
629 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
630 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
631 << std::make_pair( "find_thread_count", s_nFindThreadCount )
632 << std::make_pair( "set_size", s_nSetSize )
633 << std::make_pair( "pass_count", s_nInsertPassCount );
635 std::chrono::milliseconds duration = pool.run();
637 propout() << std::make_pair( "duration", duration );
639 size_t nInsertInitFailed = 0;
640 size_t nInsertInitSuccess = 0;
641 size_t nInsertSuccess = 0;
642 size_t nInsertFailed = 0;
643 size_t nDeleteSuccess = 0;
644 size_t nDeleteFailed = 0;
646 size_t nFindEvenSuccess = 0;
647 size_t nFindEvenFailed = 0;
648 size_t nFindOddSuccess = 0;
649 size_t nFindOddFailed = 0;
651 for ( size_t i = 0; i < pool.size(); ++i ) {
652 cds_test::thread& thr = pool.get( i );
653 switch ( thr.type()) {
654 case inserter_thread:
656 insert_thread& inserter = static_cast<insert_thread&>(thr);
657 nInsertSuccess += inserter.m_nInsertSuccess;
658 nInsertFailed += inserter.m_nInsertFailed;
659 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
660 nInsertInitFailed += inserter.m_nInsertInitFailed;
665 delete_thread& deleter = static_cast<delete_thread&>(thr);
666 nDeleteSuccess += deleter.m_nDeleteSuccess;
667 nDeleteFailed += deleter.m_nDeleteFailed;
672 observer_thread& observer = static_cast<observer_thread&>( thr );
673 nFindEvenSuccess = observer.m_nFindEvenSuccess;
674 nFindEvenFailed = observer.m_nFindEvenFailed;
675 nFindOddSuccess = observer.m_nFindOddSuccess;
676 nFindOddFailed = observer.m_nFindOddFailed;
684 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
686 EXPECT_EQ( nInsertInitFailed, 0u );
687 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
688 EXPECT_EQ( nFindEvenFailed, 0u );
689 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
690 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
693 << std::make_pair( "insert_init_success", nInsertInitSuccess )
694 << std::make_pair( "insert_init_failed", nInsertInitFailed )
695 << std::make_pair( "insert_success", nInsertSuccess )
696 << std::make_pair( "insert_failed", nInsertFailed )
697 << std::make_pair( "delete_success", nDeleteSuccess )
698 << std::make_pair( "delete_failed", nDeleteFailed )
699 << std::make_pair( "find_even_success", nFindEvenSuccess )
700 << std::make_pair( "find_even_failed", nFindEvenFailed )
701 << std::make_pair( "find_odd_success", nFindOddSuccess )
702 << std::make_pair( "find_odd_failed", nFindOddFailed );
705 template <typename Iterator, class Set>
706 void do_test_extract_with( Set& testSet )
708 typedef Inserter<Set> insert_thread;
709 typedef Deleter<Set, Iterator> delete_thread;
710 typedef Extractor< typename Set::gc, Set > extract_thread;
711 typedef Observer<Set> observer_thread;
713 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
715 cds_test::thread_pool& pool = get_pool();
716 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
717 if ( s_nDelThreadCount )
718 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
719 if ( s_nExtractThreadCount )
720 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
721 if ( s_nFindThreadCount )
722 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
724 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
725 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
726 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
727 << std::make_pair( "find_thread_count", s_nFindThreadCount )
728 << std::make_pair( "set_size", s_nSetSize )
729 << std::make_pair( "pass_count", s_nInsertPassCount );
731 std::chrono::milliseconds duration = pool.run();
733 propout() << std::make_pair( "duration", duration );
735 size_t nInsertInitFailed = 0;
736 size_t nInsertInitSuccess = 0;
737 size_t nInsertSuccess = 0;
738 size_t nInsertFailed = 0;
739 size_t nDeleteSuccess = 0;
740 size_t nDeleteFailed = 0;
741 size_t nExtractSuccess = 0;
742 size_t nExtractFailed = 0;
744 size_t nFindEvenSuccess = 0;
745 size_t nFindEvenFailed = 0;
746 size_t nFindOddSuccess = 0;
747 size_t nFindOddFailed = 0;
749 for ( size_t i = 0; i < pool.size(); ++i ) {
750 cds_test::thread& thr = pool.get( i );
751 switch ( thr.type()) {
752 case inserter_thread:
754 insert_thread& inserter = static_cast<insert_thread&>( thr );
755 nInsertSuccess += inserter.m_nInsertSuccess;
756 nInsertFailed += inserter.m_nInsertFailed;
757 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
758 nInsertInitFailed += inserter.m_nInsertInitFailed;
763 delete_thread& deleter = static_cast<delete_thread&>(thr);
764 nDeleteSuccess += deleter.m_nDeleteSuccess;
765 nDeleteFailed += deleter.m_nDeleteFailed;
768 case extractor_thread:
770 extract_thread& extractor = static_cast<extract_thread&>(thr);
771 nExtractSuccess += extractor.m_nExtractSuccess;
772 nExtractFailed += extractor.m_nExtractFailed;
777 observer_thread& observer = static_cast<observer_thread&>( thr );
778 nFindEvenSuccess = observer.m_nFindEvenSuccess;
779 nFindEvenFailed = observer.m_nFindEvenFailed;
780 nFindOddSuccess = observer.m_nFindOddSuccess;
781 nFindOddFailed = observer.m_nFindOddFailed;
789 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
791 EXPECT_EQ( nInsertInitFailed, 0u );
792 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
793 EXPECT_EQ( nFindEvenFailed, 0u );
794 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
795 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
798 << std::make_pair( "insert_init_success", nInsertInitSuccess )
799 << std::make_pair( "insert_init_failed", nInsertInitFailed )
800 << std::make_pair( "insert_success", nInsertSuccess )
801 << std::make_pair( "insert_failed", nInsertFailed )
802 << std::make_pair( "delete_success", nDeleteSuccess )
803 << std::make_pair( "delete_failed", nDeleteFailed )
804 << std::make_pair( "extract_success", nExtractSuccess )
805 << std::make_pair( "extract_failed", nExtractFailed )
806 << std::make_pair( "find_even_success", nFindEvenSuccess )
807 << std::make_pair( "find_even_failed", nFindEvenFailed )
808 << std::make_pair( "find_odd_success", nFindOddSuccess )
809 << std::make_pair( "find_odd_failed", nFindOddFailed );
812 template <typename Set>
813 void analyze( Set& testSet )
815 // All even keys must be in the set
817 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
818 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
819 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
824 check_before_clear( testSet );
827 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
829 additional_check( testSet );
830 print_stat( propout(), testSet );
831 additional_cleanup( testSet );
834 template <class Set, typename Iterator=typename Set::iterator>
837 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
839 Set testSet( *this );
840 do_test_with<Iterator>( testSet );
844 template <class Set, typename Iterator=typename Set::iterator>
845 void run_test_extract()
847 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
849 Set testSet( *this );
850 do_test_extract_with<Iterator>( testSet );
858 void run_feldman_reverse();
861 class Set_Iter_Del3_reverse: public Set_Iter_Del3
869 class Set_Iter_Del3_LF: public Set_Iter_Del3
870 , public ::testing::WithParamInterface<size_t>
876 s_nLoadFactor = GetParam();
877 propout() << std::make_pair( "load_factor", s_nLoadFactor );
878 Set_Iter_Del3::run_test<Set>();
882 void run_test_extract()
884 s_nLoadFactor = GetParam();
885 propout() << std::make_pair( "load_factor", s_nLoadFactor );
886 Set_Iter_Del3::run_test_extract<Set>();
889 static std::vector<size_t> get_load_factors();