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_nFeldmanSet_HeadBits;
129 static size_t s_nFeldmanSet_ArrayBits;
131 static size_t s_nLoadFactor;
133 static std::vector<size_t> m_arrData;
135 static void SetUpTestCase();
136 static void TearDownTestCase();
138 template <typename Pred>
139 static void prepare_array( std::vector<size_t>& arr, Pred pred )
141 arr.reserve( m_arrData.size());
142 for ( auto el : m_arrData ) {
146 arr.resize( arr.size());
147 shuffle( arr.begin(), arr.end());
151 typedef key_thread key_type;
152 typedef size_t value_type;
154 atomics::atomic<size_t> m_nInsThreadCount;
164 // Inserts keys from [0..N)
166 class Inserter: public cds_test::thread
168 typedef cds_test::thread base_class;
171 struct update_functor
173 template <typename Q>
174 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
177 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
183 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
184 for ( size_t i = 0; i < m_arr.size(); ++i ) {
185 if ( m_Set.insert( key_type( m_arr[i], id())))
186 ++m_nInsertInitSuccess;
188 ++m_nInsertInitFailed;
193 size_t m_nInsertSuccess = 0;
194 size_t m_nInsertFailed = 0;
195 size_t m_nInsertInitSuccess = 0;
196 size_t m_nInsertInitFailed = 0;
198 std::vector<size_t> m_arr;
201 Inserter( cds_test::thread_pool& pool, Set& set )
202 : base_class( pool, inserter_thread )
208 Inserter( Inserter& src )
215 virtual thread * clone()
217 return new Inserter( *this );
223 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
225 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
228 for ( auto el : m_arr ) {
230 if ( rSet.insert( key_type( el, id())))
239 for ( auto el : m_arr ) {
243 std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
244 if ( success && inserted )
253 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
259 bool operator()( key_type const& k1, key_type const& k2 ) const
261 return k1.nKey == k2.nKey;
263 bool operator()( size_t k1, key_type const& k2 ) const
265 return k1 == k2.nKey;
267 bool operator()( key_type const& k1, size_t k2 ) const
269 return k1.nKey == k2;
271 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
273 return operator()( k1.key, k2.key );
275 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
277 return operator()( k1.key, k2 );
279 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
281 return operator()( k1, k2.key );
283 bool operator ()( key_value_pair const& k1, size_t k2 ) const
285 return operator()( k1.key, k2 );
287 bool operator ()( size_t k1, key_value_pair const& k2 ) const
289 return operator()( k1, k2.key );
294 bool operator()( key_type const& k1, key_type const& k2 ) const
296 return k1.nKey < k2.nKey;
298 bool operator()( size_t k1, key_type const& k2 ) const
302 bool operator()( key_type const& k1, size_t k2 ) const
306 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
308 return operator()( k1.key, k2.key );
310 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
312 return operator()( k1.key, k2 );
314 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
316 return operator()( k1, k2.key );
318 bool operator ()( key_value_pair const& k1, size_t k2 ) const
320 return operator()( k1.key, k2 );
322 bool operator ()( size_t k1, key_value_pair const& k2 ) const
324 return operator()( k1, k2.key );
327 typedef key_equal equal_to;
330 // Deletes keys from [0..N)
331 template <class Set, typename Iterator>
332 class Deleter: public cds_test::thread
334 typedef cds_test::thread base_class;
338 size_t m_nDeleteSuccess = 0;
339 size_t m_nDeleteFailed = 0;
342 Deleter( cds_test::thread_pool& pool, Set& set )
343 : base_class( pool, deleter_thread )
347 Deleter( Deleter& src )
352 virtual thread * clone()
354 return new Deleter( *this );
361 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
364 auto itEnd = rSet.template get_end<Iterator>();
365 for ( auto it = rSet.template get_begin<Iterator>(); it != itEnd; ++it ) {
366 if ( it->key.nKey & 3 ) {
367 if ( rSet.erase_at( it ))
373 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
377 // Extracts keys from [0..N)
378 template <typename GC, class Set>
379 class Extractor: public cds_test::thread
381 typedef cds_test::thread base_class;
384 std::vector<size_t> m_arr;
388 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
392 size_t m_nExtractSuccess = 0;
393 size_t m_nExtractFailed = 0;
396 Extractor( cds_test::thread_pool& pool, Set& set )
397 : base_class( pool, extractor_thread )
403 Extractor( Extractor& src )
410 virtual thread * clone()
412 return new Extractor( *this );
418 typename Set::guarded_ptr gp;
420 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
421 size_t const nInsThreadCount = s_nInsThreadCount;
425 for ( auto el : m_arr ) {
426 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
427 gp = rSet.extract( key_type( el, k ));
437 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
438 for ( auto el : m_arr ) {
439 gp = rSet.extract( key_type( el, k ));
448 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
454 template <typename RCU, class Set>
455 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
457 typedef cds_test::thread base_class;
459 std::vector<size_t> m_arr;
463 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
467 size_t m_nExtractSuccess = 0;
468 size_t m_nExtractFailed = 0;
471 Extractor( cds_test::thread_pool& pool, Set& set )
472 : base_class( pool, extractor_thread )
478 Extractor( Extractor& src )
485 virtual thread * clone()
487 return new Extractor( *this );
493 typename Set::exempt_ptr xp;
495 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
496 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
500 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
501 for ( auto el : m_arr ) {
502 if ( Set::c_bExtractLockExternal ) {
503 typename Set::rcu_lock l;
504 xp = rSet.extract( key_type( el, k ));
511 xp = rSet.extract( key_type( el, k ));
522 for ( auto el : m_arr ) {
523 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
524 if ( Set::c_bExtractLockExternal ) {
525 typename Set::rcu_lock l;
526 xp = rSet.extract( key_type( el, k ));
533 xp = rSet.extract( key_type( el, k ));
543 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
551 class Observer: public cds_test::thread
553 typedef cds_test::thread base_class;
557 size_t m_nFindEvenSuccess = 0;
558 size_t m_nFindEvenFailed = 0;
559 size_t m_nFindOddSuccess = 0;
560 size_t m_nFindOddFailed = 0;
563 Observer( cds_test::thread_pool& pool, Set& set )
564 : base_class( pool, find_thread )
568 Observer( Observer& src )
573 virtual thread * clone()
575 return new Observer( *this );
581 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
582 std::vector<size_t> const& arr = m_arrData;
583 size_t const nInsThreadCount = s_nInsThreadCount;
586 for ( size_t key : arr ) {
588 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
589 if ( set.contains( key_thread( key, k )))
596 // that keys MUST be in the map
597 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
598 if ( set.contains( key_thread( key, k )))
599 ++m_nFindEvenSuccess;
605 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
610 template <typename Iterator, class Set>
611 void do_test_with( Set& testSet )
613 typedef Inserter<Set> insert_thread;
614 typedef Deleter<Set, Iterator> delete_thread;
615 typedef Observer<Set> observer_thread;
617 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
619 cds_test::thread_pool& pool = get_pool();
620 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
621 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
622 if ( s_nFindThreadCount )
623 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
625 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
626 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
627 << std::make_pair( "find_thread_count", s_nFindThreadCount )
628 << std::make_pair( "set_size", s_nSetSize )
629 << std::make_pair( "pass_count", s_nInsertPassCount );
631 std::chrono::milliseconds duration = pool.run();
633 propout() << std::make_pair( "duration", duration );
635 size_t nInsertInitFailed = 0;
636 size_t nInsertInitSuccess = 0;
637 size_t nInsertSuccess = 0;
638 size_t nInsertFailed = 0;
639 size_t nDeleteSuccess = 0;
640 size_t nDeleteFailed = 0;
642 size_t nFindEvenSuccess = 0;
643 size_t nFindEvenFailed = 0;
644 size_t nFindOddSuccess = 0;
645 size_t nFindOddFailed = 0;
647 for ( size_t i = 0; i < pool.size(); ++i ) {
648 cds_test::thread& thr = pool.get( i );
649 switch ( thr.type()) {
650 case inserter_thread:
652 insert_thread& inserter = static_cast<insert_thread&>(thr);
653 nInsertSuccess += inserter.m_nInsertSuccess;
654 nInsertFailed += inserter.m_nInsertFailed;
655 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
656 nInsertInitFailed += inserter.m_nInsertInitFailed;
661 delete_thread& deleter = static_cast<delete_thread&>(thr);
662 nDeleteSuccess += deleter.m_nDeleteSuccess;
663 nDeleteFailed += deleter.m_nDeleteFailed;
668 observer_thread& observer = static_cast<observer_thread&>( thr );
669 nFindEvenSuccess = observer.m_nFindEvenSuccess;
670 nFindEvenFailed = observer.m_nFindEvenFailed;
671 nFindOddSuccess = observer.m_nFindOddSuccess;
672 nFindOddFailed = observer.m_nFindOddFailed;
680 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
682 EXPECT_EQ( nInsertInitFailed, 0u );
683 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
684 EXPECT_EQ( nFindEvenFailed, 0u );
685 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
686 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
689 << std::make_pair( "insert_init_success", nInsertInitSuccess )
690 << std::make_pair( "insert_init_failed", nInsertInitFailed )
691 << std::make_pair( "insert_success", nInsertSuccess )
692 << std::make_pair( "insert_failed", nInsertFailed )
693 << std::make_pair( "delete_success", nDeleteSuccess )
694 << std::make_pair( "delete_failed", nDeleteFailed )
695 << std::make_pair( "find_even_success", nFindEvenSuccess )
696 << std::make_pair( "find_even_failed", nFindEvenFailed )
697 << std::make_pair( "find_odd_success", nFindOddSuccess )
698 << std::make_pair( "find_odd_failed", nFindOddFailed );
701 template <typename Iterator, class Set>
702 void do_test_extract_with( Set& testSet )
704 typedef Inserter<Set> insert_thread;
705 typedef Deleter<Set, Iterator> delete_thread;
706 typedef Extractor< typename Set::gc, Set > extract_thread;
707 typedef Observer<Set> observer_thread;
709 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
711 cds_test::thread_pool& pool = get_pool();
712 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
713 if ( s_nDelThreadCount )
714 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
715 if ( s_nExtractThreadCount )
716 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
717 if ( s_nFindThreadCount )
718 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
720 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
721 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
722 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
723 << std::make_pair( "find_thread_count", s_nFindThreadCount )
724 << std::make_pair( "set_size", s_nSetSize )
725 << std::make_pair( "pass_count", s_nInsertPassCount );
727 std::chrono::milliseconds duration = pool.run();
729 propout() << std::make_pair( "duration", duration );
731 size_t nInsertInitFailed = 0;
732 size_t nInsertInitSuccess = 0;
733 size_t nInsertSuccess = 0;
734 size_t nInsertFailed = 0;
735 size_t nDeleteSuccess = 0;
736 size_t nDeleteFailed = 0;
737 size_t nExtractSuccess = 0;
738 size_t nExtractFailed = 0;
740 size_t nFindEvenSuccess = 0;
741 size_t nFindEvenFailed = 0;
742 size_t nFindOddSuccess = 0;
743 size_t nFindOddFailed = 0;
745 for ( size_t i = 0; i < pool.size(); ++i ) {
746 cds_test::thread& thr = pool.get( i );
747 switch ( thr.type()) {
748 case inserter_thread:
750 insert_thread& inserter = static_cast<insert_thread&>( thr );
751 nInsertSuccess += inserter.m_nInsertSuccess;
752 nInsertFailed += inserter.m_nInsertFailed;
753 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
754 nInsertInitFailed += inserter.m_nInsertInitFailed;
759 delete_thread& deleter = static_cast<delete_thread&>(thr);
760 nDeleteSuccess += deleter.m_nDeleteSuccess;
761 nDeleteFailed += deleter.m_nDeleteFailed;
764 case extractor_thread:
766 extract_thread& extractor = static_cast<extract_thread&>(thr);
767 nExtractSuccess += extractor.m_nExtractSuccess;
768 nExtractFailed += extractor.m_nExtractFailed;
773 observer_thread& observer = static_cast<observer_thread&>( thr );
774 nFindEvenSuccess = observer.m_nFindEvenSuccess;
775 nFindEvenFailed = observer.m_nFindEvenFailed;
776 nFindOddSuccess = observer.m_nFindOddSuccess;
777 nFindOddFailed = observer.m_nFindOddFailed;
785 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
787 EXPECT_EQ( nInsertInitFailed, 0u );
788 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
789 EXPECT_EQ( nFindEvenFailed, 0u );
790 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
791 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
794 << std::make_pair( "insert_init_success", nInsertInitSuccess )
795 << std::make_pair( "insert_init_failed", nInsertInitFailed )
796 << std::make_pair( "insert_success", nInsertSuccess )
797 << std::make_pair( "insert_failed", nInsertFailed )
798 << std::make_pair( "delete_success", nDeleteSuccess )
799 << std::make_pair( "delete_failed", nDeleteFailed )
800 << std::make_pair( "extract_success", nExtractSuccess )
801 << std::make_pair( "extract_failed", nExtractFailed )
802 << std::make_pair( "find_even_success", nFindEvenSuccess )
803 << std::make_pair( "find_even_failed", nFindEvenFailed )
804 << std::make_pair( "find_odd_success", nFindOddSuccess )
805 << std::make_pair( "find_odd_failed", nFindOddFailed );
808 template <typename Set>
809 void analyze( Set& testSet )
811 // All even keys must be in the set
813 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
814 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
815 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
820 check_before_clear( testSet );
823 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
825 additional_check( testSet );
826 print_stat( propout(), testSet );
827 additional_cleanup( testSet );
830 template <class Set, typename Iterator=typename Set::iterator>
833 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
835 Set testSet( *this );
836 do_test_with<Iterator>( testSet );
840 template <class Set, typename Iterator=typename Set::iterator>
841 void run_test_extract()
843 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
845 Set testSet( *this );
846 do_test_extract_with<Iterator>( testSet );
854 class Set_Iter_Del3_reverse: public Set_Iter_Del3
862 class Set_Iter_Del3_LF: public Set_Iter_Del3
863 , public ::testing::WithParamInterface<size_t>
869 s_nLoadFactor = GetParam();
870 propout() << std::make_pair( "load_factor", s_nLoadFactor );
871 Set_Iter_Del3::run_test<Set>();
875 void run_test_extract()
877 s_nLoadFactor = GetParam();
878 propout() << std::make_pair( "load_factor", s_nLoadFactor );
879 Set_Iter_Del3::run_test_extract<Set>();
882 static std::vector<size_t> get_load_factors();