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.
40 key_thread( size_t key, size_t threadNo )
41 : nKey( static_cast<uint32_t>(key))
42 , nThread( static_cast<uint16_t>(threadNo))
51 static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
53 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
56 struct cmp<key_thread> {
57 int operator ()(key_thread const& k1, key_thread const& k2) const
59 if ( k1.nKey < k2.nKey )
61 if ( k1.nKey > k2.nKey )
63 if ( k1.nThread < k2.nThread )
65 if ( k1.nThread > k2.nThread )
69 int operator ()(key_thread const& k1, size_t k2) const
77 int operator ()(size_t k1, key_thread const& k2) const
88 struct less<set::key_thread>
90 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
92 if ( k1.nKey <= k2.nKey )
93 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
99 struct hash<set::key_thread>
101 typedef size_t result_type;
102 typedef set::key_thread argument_type;
104 size_t operator()( set::key_thread const& k ) const
106 return std::hash<size_t>()(k.nKey);
109 size_t operator()( size_t k ) const
111 return std::hash<size_t>()(k);
116 class Set_DelOdd: public cds_test::stress_fixture
119 static size_t s_nSetSize; // max set size
120 static size_t s_nInsThreadCount; // insert thread count
121 static size_t s_nDelThreadCount; // delete thread count
122 static size_t s_nExtractThreadCount; // extract thread count
123 static size_t s_nMaxLoadFactor; // maximum load factor
124 static size_t s_nInsertPassCount;
125 static size_t s_nFindThreadCount; // find thread count
127 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
128 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
129 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
131 static size_t s_nFeldmanSet_HeadBits;
132 static size_t s_nFeldmanSet_ArrayBits;
134 static size_t s_nLoadFactor;
136 static std::vector<size_t> m_arrData;
138 static void SetUpTestCase();
139 static void TearDownTestCase();
141 template <typename Pred>
142 static void prepare_array( std::vector<size_t>& arr, Pred pred )
144 arr.reserve( m_arrData.size() );
145 for ( auto el : m_arrData ) {
149 arr.resize( arr.size() );
150 shuffle( arr.begin(), arr.end() );
154 typedef key_thread key_type;
155 typedef size_t value_type;
157 atomics::atomic<size_t> m_nInsThreadCount;
167 // Inserts keys from [0..N)
169 class Inserter: public cds_test::thread
171 typedef cds_test::thread base_class;
174 struct update_functor
176 template <typename Q>
177 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
180 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
186 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
187 for ( size_t i = 0; i < m_arr.size(); ++i ) {
188 if ( m_Set.insert( key_type( m_arr[i], id() ) ) )
189 ++m_nInsertInitSuccess;
191 ++m_nInsertInitFailed;
196 size_t m_nInsertSuccess = 0;
197 size_t m_nInsertFailed = 0;
198 size_t m_nInsertInitSuccess = 0;
199 size_t m_nInsertInitFailed = 0;
201 std::vector<size_t> m_arr;
204 Inserter( cds_test::thread_pool& pool, Set& set )
205 : base_class( pool, inserter_thread )
211 Inserter( Inserter& src )
218 virtual thread * clone()
220 return new Inserter( *this );
226 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
228 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
231 for ( auto el : m_arr ) {
233 if ( rSet.insert( key_type( el, id() ) ) )
242 for ( auto el : m_arr ) {
246 std::tie( success, inserted ) = rSet.update( key_type( el, id() ), update_functor() );
247 if ( success && inserted )
256 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
262 bool operator()( key_type const& k1, key_type const& k2 ) const
264 return k1.nKey == k2.nKey;
266 bool operator()( size_t k1, key_type const& k2 ) const
268 return k1 == k2.nKey;
270 bool operator()( key_type const& k1, size_t k2 ) const
272 return k1.nKey == k2;
274 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
276 return operator()( k1.key, k2.key );
278 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
280 return operator()( k1.key, k2 );
282 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
284 return operator()( k1, k2.key );
286 bool operator ()( key_value_pair const& k1, size_t k2 ) const
288 return operator()( k1.key, k2 );
290 bool operator ()( size_t k1, key_value_pair const& k2 ) const
292 return operator()( k1, k2.key );
297 bool operator()( key_type const& k1, key_type const& k2 ) const
299 return k1.nKey < k2.nKey;
301 bool operator()( size_t k1, key_type const& k2 ) const
305 bool operator()( key_type const& k1, size_t k2 ) const
309 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
311 return operator()( k1.key, k2.key );
313 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
315 return operator()( k1.key, k2 );
317 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
319 return operator()( k1, k2.key );
321 bool operator ()( key_value_pair const& k1, size_t k2 ) const
323 return operator()( k1.key, k2 );
325 bool operator ()( size_t k1, key_value_pair const& k2 ) const
327 return operator()( k1, k2.key );
330 typedef key_equal equal_to;
333 // Deletes odd keys from [0..N)
335 class Deleter: public cds_test::thread
337 typedef cds_test::thread base_class;
342 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
346 size_t m_nDeleteSuccess = 0;
347 size_t m_nDeleteFailed = 0;
349 std::vector<size_t> m_arr;
352 Deleter( cds_test::thread_pool& pool, Set& set )
353 : base_class( pool, deleter_thread )
358 Deleter( Deleter& src )
365 virtual thread * clone()
367 return new Deleter( *this );
370 template <typename SetType, bool>
372 static bool erase( SetType& s, size_t key, size_t /*thread*/)
374 return s.erase_with( key, key_less());
378 template <typename SetType>
379 struct eraser<SetType, true> {
380 static bool erase(SetType& s, size_t key, size_t thread)
382 return s.erase( key_type(key, thread));
390 size_t const nInsThreadCount = s_nInsThreadCount;
391 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
395 for ( auto el : m_arr ) {
396 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
397 if ( rSet.erase( key_type( el, k ) ) )
405 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
406 for ( auto el : m_arr ) {
407 if ( rSet.erase( key_type( el, k ) ) )
414 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
420 // Extracts odd keys from [0..N)
421 template <typename GC, class Set>
422 class Extractor: public cds_test::thread
424 typedef cds_test::thread base_class;
427 std::vector<size_t> m_arr;
431 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
435 size_t m_nExtractSuccess = 0;
436 size_t m_nExtractFailed = 0;
439 Extractor( cds_test::thread_pool& pool, Set& set )
440 : base_class( pool, extractor_thread )
446 Extractor( Extractor& src )
453 virtual thread * clone()
455 return new Extractor( *this );
461 typename Set::guarded_ptr gp;
463 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
464 size_t const nInsThreadCount = s_nInsThreadCount;
468 for ( auto el : m_arr ) {
469 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
470 gp = rSet.extract( key_type( el, k ) );
480 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
481 for ( auto el : m_arr ) {
482 gp = rSet.extract( key_type( el, k ) );
491 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
497 template <typename RCU, class Set>
498 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
500 typedef cds_test::thread base_class;
502 std::vector<size_t> m_arr;
506 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
510 size_t m_nExtractSuccess = 0;
511 size_t m_nExtractFailed = 0;
514 Extractor( cds_test::thread_pool& pool, Set& set )
515 : base_class( pool, extractor_thread )
521 Extractor( Extractor& src )
528 virtual thread * clone()
530 return new Extractor( *this );
536 typename Set::exempt_ptr xp;
538 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
539 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
543 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
544 for ( auto el : m_arr ) {
545 if ( Set::c_bExtractLockExternal ) {
546 typename Set::rcu_lock l;
547 xp = rSet.extract( key_type( el, k ) );
554 xp = rSet.extract( key_type( el, k ) );
565 for ( auto el : m_arr ) {
566 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
567 if ( Set::c_bExtractLockExternal ) {
568 typename Set::rcu_lock l;
569 xp = rSet.extract( key_type( el, k ) );
576 xp = rSet.extract( key_type( el, k ) );
586 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
594 class Observer: public cds_test::thread
596 typedef cds_test::thread base_class;
600 size_t m_nFindEvenSuccess = 0;
601 size_t m_nFindEvenFailed = 0;
602 size_t m_nFindOddSuccess = 0;
603 size_t m_nFindOddFailed = 0;
606 Observer( cds_test::thread_pool& pool, Set& set )
607 : base_class( pool, find_thread )
611 Observer( Observer& src )
616 virtual thread * clone()
618 return new Observer( *this );
624 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
625 std::vector<size_t> const& arr = m_arrData;
626 size_t const nInsThreadCount = s_nInsThreadCount;
629 for ( size_t key : arr ) {
631 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
632 if ( set.contains( key_thread( key, k ) ) )
639 // even keys MUST be in the map
640 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
641 if ( set.contains( key_thread( key, k ) ) )
642 ++m_nFindEvenSuccess;
648 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
654 void do_test_with( Set& testSet )
656 typedef Inserter<Set> insert_thread;
657 typedef Deleter<Set> delete_thread;
658 typedef Observer<Set> observer_thread;
660 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
662 cds_test::thread_pool& pool = get_pool();
663 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
664 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
665 if ( s_nFindThreadCount )
666 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
668 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
669 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
670 << std::make_pair( "find_thread_count", s_nFindThreadCount )
671 << std::make_pair( "set_size", s_nSetSize )
672 << std::make_pair( "pass_count", s_nInsertPassCount );
674 std::chrono::milliseconds duration = pool.run();
676 propout() << std::make_pair( "duration", duration );
678 size_t nInsertInitFailed = 0;
679 size_t nInsertInitSuccess = 0;
680 size_t nInsertSuccess = 0;
681 size_t nInsertFailed = 0;
682 size_t nDeleteSuccess = 0;
683 size_t nDeleteFailed = 0;
685 size_t nFindEvenSuccess = 0;
686 size_t nFindEvenFailed = 0;
687 size_t nFindOddSuccess = 0;
688 size_t nFindOddFailed = 0;
690 for ( size_t i = 0; i < pool.size(); ++i ) {
691 cds_test::thread& thr = pool.get( i );
692 switch ( thr.type()) {
693 case inserter_thread:
695 insert_thread& inserter = static_cast<insert_thread&>(thr);
696 nInsertSuccess += inserter.m_nInsertSuccess;
697 nInsertFailed += inserter.m_nInsertFailed;
698 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
699 nInsertInitFailed += inserter.m_nInsertInitFailed;
704 delete_thread& deleter = static_cast<delete_thread&>(thr);
705 nDeleteSuccess += deleter.m_nDeleteSuccess;
706 nDeleteFailed += deleter.m_nDeleteFailed;
711 observer_thread& observer = static_cast<observer_thread&>( thr );
712 nFindEvenSuccess = observer.m_nFindEvenSuccess;
713 nFindEvenFailed = observer.m_nFindEvenFailed;
714 nFindOddSuccess = observer.m_nFindOddSuccess;
715 nFindOddFailed = observer.m_nFindOddFailed;
723 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
725 EXPECT_EQ( nInsertInitFailed, 0u );
726 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
727 EXPECT_EQ( nFindEvenFailed, 0u );
728 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
729 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
732 << std::make_pair( "insert_init_success", nInsertInitSuccess )
733 << std::make_pair( "insert_init_failed", nInsertInitFailed )
734 << std::make_pair( "insert_success", nInsertSuccess )
735 << std::make_pair( "insert_failed", nInsertFailed )
736 << std::make_pair( "delete_success", nDeleteSuccess )
737 << std::make_pair( "delete_failed", nDeleteFailed )
738 << std::make_pair( "find_even_success", nFindEvenSuccess )
739 << std::make_pair( "find_even_failed", nFindEvenFailed )
740 << std::make_pair( "find_odd_success", nFindOddSuccess )
741 << std::make_pair( "find_odd_failed", nFindOddFailed );
745 void do_test_extract_with( Set& testSet )
747 typedef Inserter<Set> insert_thread;
748 typedef Deleter<Set> delete_thread;
749 typedef Extractor< typename Set::gc, Set > extract_thread;
750 typedef Observer<Set> observer_thread;
752 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
754 cds_test::thread_pool& pool = get_pool();
755 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
756 if ( s_nDelThreadCount )
757 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
758 if ( s_nExtractThreadCount )
759 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
760 if ( s_nFindThreadCount )
761 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
763 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
764 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
765 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
766 << std::make_pair( "find_thread_count", s_nFindThreadCount )
767 << std::make_pair( "set_size", s_nSetSize )
768 << std::make_pair( "pass_count", s_nInsertPassCount );
770 std::chrono::milliseconds duration = pool.run();
772 propout() << std::make_pair( "duration", duration );
774 size_t nInsertInitFailed = 0;
775 size_t nInsertInitSuccess = 0;
776 size_t nInsertSuccess = 0;
777 size_t nInsertFailed = 0;
778 size_t nDeleteSuccess = 0;
779 size_t nDeleteFailed = 0;
780 size_t nExtractSuccess = 0;
781 size_t nExtractFailed = 0;
783 size_t nFindEvenSuccess = 0;
784 size_t nFindEvenFailed = 0;
785 size_t nFindOddSuccess = 0;
786 size_t nFindOddFailed = 0;
788 for ( size_t i = 0; i < pool.size(); ++i ) {
789 cds_test::thread& thr = pool.get( i );
790 switch ( thr.type()) {
791 case inserter_thread:
793 insert_thread& inserter = static_cast<insert_thread&>( thr );
794 nInsertSuccess += inserter.m_nInsertSuccess;
795 nInsertFailed += inserter.m_nInsertFailed;
796 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
797 nInsertInitFailed += inserter.m_nInsertInitFailed;
802 delete_thread& deleter = static_cast<delete_thread&>(thr);
803 nDeleteSuccess += deleter.m_nDeleteSuccess;
804 nDeleteFailed += deleter.m_nDeleteFailed;
807 case extractor_thread:
809 extract_thread& extractor = static_cast<extract_thread&>(thr);
810 nExtractSuccess += extractor.m_nExtractSuccess;
811 nExtractFailed += extractor.m_nExtractFailed;
816 observer_thread& observer = static_cast<observer_thread&>( thr );
817 nFindEvenSuccess = observer.m_nFindEvenSuccess;
818 nFindEvenFailed = observer.m_nFindEvenFailed;
819 nFindOddSuccess = observer.m_nFindOddSuccess;
820 nFindOddFailed = observer.m_nFindOddFailed;
828 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
830 EXPECT_EQ( nInsertInitFailed, 0u );
831 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
832 EXPECT_EQ( nFindEvenFailed, 0u );
833 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
834 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
837 << std::make_pair( "insert_init_success", nInsertInitSuccess )
838 << std::make_pair( "insert_init_failed", nInsertInitFailed )
839 << std::make_pair( "insert_success", nInsertSuccess )
840 << std::make_pair( "insert_failed", nInsertFailed )
841 << std::make_pair( "delete_success", nDeleteSuccess )
842 << std::make_pair( "delete_failed", nDeleteFailed )
843 << std::make_pair( "extract_success", nExtractSuccess )
844 << std::make_pair( "extract_failed", nExtractFailed )
845 << std::make_pair( "find_even_success", nFindEvenSuccess )
846 << std::make_pair( "find_even_failed", nFindEvenFailed )
847 << std::make_pair( "find_odd_success", nFindOddSuccess )
848 << std::make_pair( "find_odd_failed", nFindOddFailed );
851 template <typename Set>
852 void analyze( Set& testSet )
854 // All even keys must be in the set
856 for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
857 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
858 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
863 check_before_clear( testSet );
866 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
868 additional_check( testSet );
869 print_stat( propout(), testSet );
870 additional_cleanup( testSet );
876 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
878 Set testSet( *this );
879 do_test_with( testSet );
884 void run_test_extract()
886 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
888 Set testSet( *this );
889 do_test_extract_with( testSet );
897 class Set_DelOdd_LF: public Set_DelOdd
898 , public ::testing::WithParamInterface<size_t>
904 s_nLoadFactor = GetParam();
905 propout() << std::make_pair( "load_factor", s_nLoadFactor );
906 Set_DelOdd::run_test<Set>();
910 void run_test_extract()
912 s_nLoadFactor = GetParam();
913 propout() << std::make_pair( "load_factor", s_nLoadFactor );
914 Set_DelOdd::run_test_extract<Set>();
917 static std::vector<size_t> get_load_factors();