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 size_t const nInsThreadCount = s_nInsThreadCount;
366 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
369 auto itEnd = rSet.get_end<Iterator>();
370 for ( auto it = rSet.get_begin<Iterator>(); it != itEnd; ++it ) {
371 if ( it->key.nKey & 3 ) {
372 if ( rSet.erase_at( it ))
378 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
382 // Extracts keys from [0..N)
383 template <typename GC, class Set>
384 class Extractor: public cds_test::thread
386 typedef cds_test::thread base_class;
389 std::vector<size_t> m_arr;
393 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
397 size_t m_nExtractSuccess = 0;
398 size_t m_nExtractFailed = 0;
401 Extractor( cds_test::thread_pool& pool, Set& set )
402 : base_class( pool, extractor_thread )
408 Extractor( Extractor& src )
415 virtual thread * clone()
417 return new Extractor( *this );
423 typename Set::guarded_ptr gp;
425 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
426 size_t const nInsThreadCount = s_nInsThreadCount;
430 for ( auto el : m_arr ) {
431 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
432 gp = rSet.extract( key_type( el, k ));
442 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
443 for ( auto el : m_arr ) {
444 gp = rSet.extract( key_type( el, k ));
453 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
459 template <typename RCU, class Set>
460 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
462 typedef cds_test::thread base_class;
464 std::vector<size_t> m_arr;
468 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
472 size_t m_nExtractSuccess = 0;
473 size_t m_nExtractFailed = 0;
476 Extractor( cds_test::thread_pool& pool, Set& set )
477 : base_class( pool, extractor_thread )
483 Extractor( Extractor& src )
490 virtual thread * clone()
492 return new Extractor( *this );
498 typename Set::exempt_ptr xp;
500 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
501 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
505 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
506 for ( auto el : m_arr ) {
507 if ( Set::c_bExtractLockExternal ) {
508 typename Set::rcu_lock l;
509 xp = rSet.extract( key_type( el, k ));
516 xp = rSet.extract( key_type( el, k ));
527 for ( auto el : m_arr ) {
528 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
529 if ( Set::c_bExtractLockExternal ) {
530 typename Set::rcu_lock l;
531 xp = rSet.extract( key_type( el, k ));
538 xp = rSet.extract( key_type( el, k ));
548 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
556 class Observer: public cds_test::thread
558 typedef cds_test::thread base_class;
562 size_t m_nFindEvenSuccess = 0;
563 size_t m_nFindEvenFailed = 0;
564 size_t m_nFindOddSuccess = 0;
565 size_t m_nFindOddFailed = 0;
568 Observer( cds_test::thread_pool& pool, Set& set )
569 : base_class( pool, find_thread )
573 Observer( Observer& src )
578 virtual thread * clone()
580 return new Observer( *this );
586 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
587 std::vector<size_t> const& arr = m_arrData;
588 size_t const nInsThreadCount = s_nInsThreadCount;
591 for ( size_t key : arr ) {
593 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
594 if ( set.contains( key_thread( key, k )))
601 // that keys MUST be in the map
602 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
603 if ( set.contains( key_thread( key, k )))
604 ++m_nFindEvenSuccess;
610 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
615 template <typename Iterator, class Set>
616 void do_test_with( Set& testSet )
618 typedef Inserter<Set> insert_thread;
619 typedef Deleter<Set, Iterator> delete_thread;
620 typedef Observer<Set> observer_thread;
622 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
624 cds_test::thread_pool& pool = get_pool();
625 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
626 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
627 if ( s_nFindThreadCount )
628 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
630 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
631 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
632 << std::make_pair( "find_thread_count", s_nFindThreadCount )
633 << std::make_pair( "set_size", s_nSetSize )
634 << std::make_pair( "pass_count", s_nInsertPassCount );
636 std::chrono::milliseconds duration = pool.run();
638 propout() << std::make_pair( "duration", duration );
640 size_t nInsertInitFailed = 0;
641 size_t nInsertInitSuccess = 0;
642 size_t nInsertSuccess = 0;
643 size_t nInsertFailed = 0;
644 size_t nDeleteSuccess = 0;
645 size_t nDeleteFailed = 0;
647 size_t nFindEvenSuccess = 0;
648 size_t nFindEvenFailed = 0;
649 size_t nFindOddSuccess = 0;
650 size_t nFindOddFailed = 0;
652 for ( size_t i = 0; i < pool.size(); ++i ) {
653 cds_test::thread& thr = pool.get( i );
654 switch ( thr.type()) {
655 case inserter_thread:
657 insert_thread& inserter = static_cast<insert_thread&>(thr);
658 nInsertSuccess += inserter.m_nInsertSuccess;
659 nInsertFailed += inserter.m_nInsertFailed;
660 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
661 nInsertInitFailed += inserter.m_nInsertInitFailed;
666 delete_thread& deleter = static_cast<delete_thread&>(thr);
667 nDeleteSuccess += deleter.m_nDeleteSuccess;
668 nDeleteFailed += deleter.m_nDeleteFailed;
673 observer_thread& observer = static_cast<observer_thread&>( thr );
674 nFindEvenSuccess = observer.m_nFindEvenSuccess;
675 nFindEvenFailed = observer.m_nFindEvenFailed;
676 nFindOddSuccess = observer.m_nFindOddSuccess;
677 nFindOddFailed = observer.m_nFindOddFailed;
685 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
687 EXPECT_EQ( nInsertInitFailed, 0u );
688 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
689 EXPECT_EQ( nFindEvenFailed, 0u );
690 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
691 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
694 << std::make_pair( "insert_init_success", nInsertInitSuccess )
695 << std::make_pair( "insert_init_failed", nInsertInitFailed )
696 << std::make_pair( "insert_success", nInsertSuccess )
697 << std::make_pair( "insert_failed", nInsertFailed )
698 << std::make_pair( "delete_success", nDeleteSuccess )
699 << std::make_pair( "delete_failed", nDeleteFailed )
700 << std::make_pair( "find_even_success", nFindEvenSuccess )
701 << std::make_pair( "find_even_failed", nFindEvenFailed )
702 << std::make_pair( "find_odd_success", nFindOddSuccess )
703 << std::make_pair( "find_odd_failed", nFindOddFailed );
706 template <typename Iterator, class Set>
707 void do_test_extract_with( Set& testSet )
709 typedef Inserter<Set> insert_thread;
710 typedef Deleter<Set, Iterator> delete_thread;
711 typedef Extractor< typename Set::gc, Set > extract_thread;
712 typedef Observer<Set> observer_thread;
714 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
716 cds_test::thread_pool& pool = get_pool();
717 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
718 if ( s_nDelThreadCount )
719 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
720 if ( s_nExtractThreadCount )
721 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
722 if ( s_nFindThreadCount )
723 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
725 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
726 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
727 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
728 << std::make_pair( "find_thread_count", s_nFindThreadCount )
729 << std::make_pair( "set_size", s_nSetSize )
730 << std::make_pair( "pass_count", s_nInsertPassCount );
732 std::chrono::milliseconds duration = pool.run();
734 propout() << std::make_pair( "duration", duration );
736 size_t nInsertInitFailed = 0;
737 size_t nInsertInitSuccess = 0;
738 size_t nInsertSuccess = 0;
739 size_t nInsertFailed = 0;
740 size_t nDeleteSuccess = 0;
741 size_t nDeleteFailed = 0;
742 size_t nExtractSuccess = 0;
743 size_t nExtractFailed = 0;
745 size_t nFindEvenSuccess = 0;
746 size_t nFindEvenFailed = 0;
747 size_t nFindOddSuccess = 0;
748 size_t nFindOddFailed = 0;
750 for ( size_t i = 0; i < pool.size(); ++i ) {
751 cds_test::thread& thr = pool.get( i );
752 switch ( thr.type()) {
753 case inserter_thread:
755 insert_thread& inserter = static_cast<insert_thread&>( thr );
756 nInsertSuccess += inserter.m_nInsertSuccess;
757 nInsertFailed += inserter.m_nInsertFailed;
758 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
759 nInsertInitFailed += inserter.m_nInsertInitFailed;
764 delete_thread& deleter = static_cast<delete_thread&>(thr);
765 nDeleteSuccess += deleter.m_nDeleteSuccess;
766 nDeleteFailed += deleter.m_nDeleteFailed;
769 case extractor_thread:
771 extract_thread& extractor = static_cast<extract_thread&>(thr);
772 nExtractSuccess += extractor.m_nExtractSuccess;
773 nExtractFailed += extractor.m_nExtractFailed;
778 observer_thread& observer = static_cast<observer_thread&>( thr );
779 nFindEvenSuccess = observer.m_nFindEvenSuccess;
780 nFindEvenFailed = observer.m_nFindEvenFailed;
781 nFindOddSuccess = observer.m_nFindOddSuccess;
782 nFindOddFailed = observer.m_nFindOddFailed;
790 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
792 EXPECT_EQ( nInsertInitFailed, 0u );
793 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
794 EXPECT_EQ( nFindEvenFailed, 0u );
795 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
796 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
799 << std::make_pair( "insert_init_success", nInsertInitSuccess )
800 << std::make_pair( "insert_init_failed", nInsertInitFailed )
801 << std::make_pair( "insert_success", nInsertSuccess )
802 << std::make_pair( "insert_failed", nInsertFailed )
803 << std::make_pair( "delete_success", nDeleteSuccess )
804 << std::make_pair( "delete_failed", nDeleteFailed )
805 << std::make_pair( "extract_success", nExtractSuccess )
806 << std::make_pair( "extract_failed", nExtractFailed )
807 << std::make_pair( "find_even_success", nFindEvenSuccess )
808 << std::make_pair( "find_even_failed", nFindEvenFailed )
809 << std::make_pair( "find_odd_success", nFindOddSuccess )
810 << std::make_pair( "find_odd_failed", nFindOddFailed );
813 template <typename Set>
814 void analyze( Set& testSet )
816 // All even keys must be in the set
818 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
819 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
820 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
825 check_before_clear( testSet );
828 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
830 additional_check( testSet );
831 print_stat( propout(), testSet );
832 additional_cleanup( testSet );
835 template <class Set, typename Iterator=typename Set::iterator>
838 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
840 Set testSet( *this );
841 do_test_with<Iterator>( testSet );
845 template <class Set, typename Iterator=typename Set::iterator>
846 void run_test_extract()
848 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
850 Set testSet( *this );
851 do_test_extract_with<Iterator>( testSet );
859 void run_feldman_reverse();
862 class Set_Iter_Del3_reverse: public Set_Iter_Del3
870 class Set_Iter_Del3_LF: public Set_Iter_Del3
871 , public ::testing::WithParamInterface<size_t>
877 s_nLoadFactor = GetParam();
878 propout() << std::make_pair( "load_factor", s_nLoadFactor );
879 Set_Iter_Del3::run_test<Set>();
883 void run_test_extract()
885 s_nLoadFactor = GetParam();
886 propout() << std::make_pair( "load_factor", s_nLoadFactor );
887 Set_Iter_Del3::run_test_extract<Set>();
890 static std::vector<size_t> get_load_factors();