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_DelOdd: 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_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
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 odd keys from [0..N)
336 class Deleter: public cds_test::thread
338 typedef cds_test::thread base_class;
343 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
347 size_t m_nDeleteSuccess = 0;
348 size_t m_nDeleteFailed = 0;
350 std::vector<size_t> m_arr;
353 Deleter( cds_test::thread_pool& pool, Set& set )
354 : base_class( pool, deleter_thread )
359 Deleter( Deleter& src )
366 virtual thread * clone()
368 return new Deleter( *this );
371 template <typename SetType, bool>
373 static bool erase( SetType& s, size_t key, size_t /*thread*/)
375 return s.erase_with( key, key_less());
379 template <typename SetType>
380 struct eraser<SetType, true> {
381 static bool erase(SetType& s, size_t key, size_t thread)
383 return s.erase( key_type(key, thread));
391 size_t const nInsThreadCount = s_nInsThreadCount;
392 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
396 for ( auto el : m_arr ) {
397 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
398 if ( rSet.erase( key_type( el, k ) ) )
406 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
407 for ( auto el : m_arr ) {
408 if ( rSet.erase( key_type( el, k ) ) )
415 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
421 // Extracts odd keys from [0..N)
422 template <typename GC, class Set>
423 class Extractor: public cds_test::thread
425 typedef cds_test::thread base_class;
428 std::vector<size_t> m_arr;
432 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
436 size_t m_nExtractSuccess = 0;
437 size_t m_nExtractFailed = 0;
440 Extractor( cds_test::thread_pool& pool, Set& set )
441 : base_class( pool, extractor_thread )
447 Extractor( Extractor& src )
454 virtual thread * clone()
456 return new Extractor( *this );
462 typename Set::guarded_ptr gp;
464 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
465 size_t const nInsThreadCount = s_nInsThreadCount;
469 for ( auto el : m_arr ) {
470 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
471 gp = rSet.extract( key_type( el, k ) );
481 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
482 for ( auto el : m_arr ) {
483 gp = rSet.extract( key_type( el, k ) );
492 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
498 template <typename RCU, class Set>
499 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
501 typedef cds_test::thread base_class;
503 std::vector<size_t> m_arr;
507 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
511 size_t m_nExtractSuccess = 0;
512 size_t m_nExtractFailed = 0;
515 Extractor( cds_test::thread_pool& pool, Set& set )
516 : base_class( pool, extractor_thread )
522 Extractor( Extractor& src )
529 virtual thread * clone()
531 return new Extractor( *this );
537 typename Set::exempt_ptr xp;
539 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
540 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
544 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
545 for ( auto el : m_arr ) {
546 if ( Set::c_bExtractLockExternal ) {
547 typename Set::rcu_lock l;
548 xp = rSet.extract( key_type( el, k ) );
555 xp = rSet.extract( key_type( el, k ) );
566 for ( auto el : m_arr ) {
567 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
568 if ( Set::c_bExtractLockExternal ) {
569 typename Set::rcu_lock l;
570 xp = rSet.extract( key_type( el, k ) );
577 xp = rSet.extract( key_type( el, k ) );
587 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
595 class Observer: public cds_test::thread
597 typedef cds_test::thread base_class;
601 size_t m_nFindEvenSuccess = 0;
602 size_t m_nFindEvenFailed = 0;
603 size_t m_nFindOddSuccess = 0;
604 size_t m_nFindOddFailed = 0;
607 Observer( cds_test::thread_pool& pool, Set& set )
608 : base_class( pool, find_thread )
612 Observer( Observer& src )
617 virtual thread * clone()
619 return new Observer( *this );
625 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
626 std::vector<size_t> const& arr = m_arrData;
627 size_t const nInsThreadCount = s_nInsThreadCount;
630 for ( size_t key : arr ) {
632 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
633 if ( set.contains( key_thread( key, k ) ) )
640 // even keys MUST be in the map
641 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
642 if ( set.contains( key_thread( key, k ) ) )
643 ++m_nFindEvenSuccess;
649 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
655 void do_test_with( Set& testSet )
657 typedef Inserter<Set> insert_thread;
658 typedef Deleter<Set> delete_thread;
659 typedef Observer<Set> observer_thread;
661 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
663 cds_test::thread_pool& pool = get_pool();
664 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
665 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
666 if ( s_nFindThreadCount )
667 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
669 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
670 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
671 << std::make_pair( "find_thread_count", s_nFindThreadCount )
672 << std::make_pair( "set_size", s_nSetSize )
673 << std::make_pair( "pass_count", s_nInsertPassCount );
675 std::chrono::milliseconds duration = pool.run();
677 propout() << std::make_pair( "duration", duration );
679 size_t nInsertInitFailed = 0;
680 size_t nInsertInitSuccess = 0;
681 size_t nInsertSuccess = 0;
682 size_t nInsertFailed = 0;
683 size_t nDeleteSuccess = 0;
684 size_t nDeleteFailed = 0;
686 size_t nFindEvenSuccess = 0;
687 size_t nFindEvenFailed = 0;
688 size_t nFindOddSuccess = 0;
689 size_t nFindOddFailed = 0;
691 for ( size_t i = 0; i < pool.size(); ++i ) {
692 cds_test::thread& thr = pool.get( i );
693 switch ( thr.type()) {
694 case inserter_thread:
696 insert_thread& inserter = static_cast<insert_thread&>(thr);
697 nInsertSuccess += inserter.m_nInsertSuccess;
698 nInsertFailed += inserter.m_nInsertFailed;
699 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
700 nInsertInitFailed += inserter.m_nInsertInitFailed;
705 delete_thread& deleter = static_cast<delete_thread&>(thr);
706 nDeleteSuccess += deleter.m_nDeleteSuccess;
707 nDeleteFailed += deleter.m_nDeleteFailed;
712 observer_thread& observer = static_cast<observer_thread&>( thr );
713 nFindEvenSuccess = observer.m_nFindEvenSuccess;
714 nFindEvenFailed = observer.m_nFindEvenFailed;
715 nFindOddSuccess = observer.m_nFindOddSuccess;
716 nFindOddFailed = observer.m_nFindOddFailed;
724 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
726 EXPECT_EQ( nInsertInitFailed, 0u );
727 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
728 EXPECT_EQ( nFindEvenFailed, 0u );
729 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
730 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
733 << std::make_pair( "insert_init_success", nInsertInitSuccess )
734 << std::make_pair( "insert_init_failed", nInsertInitFailed )
735 << std::make_pair( "insert_success", nInsertSuccess )
736 << std::make_pair( "insert_failed", nInsertFailed )
737 << std::make_pair( "delete_success", nDeleteSuccess )
738 << std::make_pair( "delete_failed", nDeleteFailed )
739 << std::make_pair( "find_even_success", nFindEvenSuccess )
740 << std::make_pair( "find_even_failed", nFindEvenFailed )
741 << std::make_pair( "find_odd_success", nFindOddSuccess )
742 << std::make_pair( "find_odd_failed", nFindOddFailed );
746 void do_test_extract_with( Set& testSet )
748 typedef Inserter<Set> insert_thread;
749 typedef Deleter<Set> delete_thread;
750 typedef Extractor< typename Set::gc, Set > extract_thread;
751 typedef Observer<Set> observer_thread;
753 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
755 cds_test::thread_pool& pool = get_pool();
756 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
757 if ( s_nDelThreadCount )
758 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
759 if ( s_nExtractThreadCount )
760 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
761 if ( s_nFindThreadCount )
762 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
764 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
765 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
766 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
767 << std::make_pair( "find_thread_count", s_nFindThreadCount )
768 << std::make_pair( "set_size", s_nSetSize )
769 << std::make_pair( "pass_count", s_nInsertPassCount );
771 std::chrono::milliseconds duration = pool.run();
773 propout() << std::make_pair( "duration", duration );
775 size_t nInsertInitFailed = 0;
776 size_t nInsertInitSuccess = 0;
777 size_t nInsertSuccess = 0;
778 size_t nInsertFailed = 0;
779 size_t nDeleteSuccess = 0;
780 size_t nDeleteFailed = 0;
781 size_t nExtractSuccess = 0;
782 size_t nExtractFailed = 0;
784 size_t nFindEvenSuccess = 0;
785 size_t nFindEvenFailed = 0;
786 size_t nFindOddSuccess = 0;
787 size_t nFindOddFailed = 0;
789 for ( size_t i = 0; i < pool.size(); ++i ) {
790 cds_test::thread& thr = pool.get( i );
791 switch ( thr.type()) {
792 case inserter_thread:
794 insert_thread& inserter = static_cast<insert_thread&>( thr );
795 nInsertSuccess += inserter.m_nInsertSuccess;
796 nInsertFailed += inserter.m_nInsertFailed;
797 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
798 nInsertInitFailed += inserter.m_nInsertInitFailed;
803 delete_thread& deleter = static_cast<delete_thread&>(thr);
804 nDeleteSuccess += deleter.m_nDeleteSuccess;
805 nDeleteFailed += deleter.m_nDeleteFailed;
808 case extractor_thread:
810 extract_thread& extractor = static_cast<extract_thread&>(thr);
811 nExtractSuccess += extractor.m_nExtractSuccess;
812 nExtractFailed += extractor.m_nExtractFailed;
817 observer_thread& observer = static_cast<observer_thread&>( thr );
818 nFindEvenSuccess = observer.m_nFindEvenSuccess;
819 nFindEvenFailed = observer.m_nFindEvenFailed;
820 nFindOddSuccess = observer.m_nFindOddSuccess;
821 nFindOddFailed = observer.m_nFindOddFailed;
829 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
831 EXPECT_EQ( nInsertInitFailed, 0u );
832 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
833 EXPECT_EQ( nFindEvenFailed, 0u );
834 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
835 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
838 << std::make_pair( "insert_init_success", nInsertInitSuccess )
839 << std::make_pair( "insert_init_failed", nInsertInitFailed )
840 << std::make_pair( "insert_success", nInsertSuccess )
841 << std::make_pair( "insert_failed", nInsertFailed )
842 << std::make_pair( "delete_success", nDeleteSuccess )
843 << std::make_pair( "delete_failed", nDeleteFailed )
844 << std::make_pair( "extract_success", nExtractSuccess )
845 << std::make_pair( "extract_failed", nExtractFailed )
846 << std::make_pair( "find_even_success", nFindEvenSuccess )
847 << std::make_pair( "find_even_failed", nFindEvenFailed )
848 << std::make_pair( "find_odd_success", nFindOddSuccess )
849 << std::make_pair( "find_odd_failed", nFindOddFailed );
852 template <typename Set>
853 void analyze( Set& testSet )
855 // All even keys must be in the set
857 for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
858 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
859 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
864 check_before_clear( testSet );
867 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
869 additional_check( testSet );
870 print_stat( propout(), testSet );
871 additional_cleanup( testSet );
877 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
879 Set testSet( *this );
880 do_test_with( testSet );
885 void run_test_extract()
887 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
889 Set testSet( *this );
890 do_test_extract_with( testSet );
898 class Set_DelOdd_LF: public Set_DelOdd
899 , public ::testing::WithParamInterface<size_t>
905 s_nLoadFactor = GetParam();
906 propout() << std::make_pair( "load_factor", s_nLoadFactor );
907 Set_DelOdd::run_test<Set>();
911 void run_test_extract()
913 s_nLoadFactor = GetParam();
914 propout() << std::make_pair( "load_factor", s_nLoadFactor );
915 Set_DelOdd::run_test_extract<Set>();
918 static std::vector<size_t> get_load_factors();