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 "../../misc/common.h"
33 #include <cds/os/topology.h>
42 key_thread( size_t key, size_t threadNo )
43 : nKey( static_cast<uint32_t>(key))
44 , nThread( static_cast<uint16_t>(threadNo))
53 static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
55 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
58 struct cmp<key_thread> {
59 int operator ()(key_thread const& k1, key_thread const& k2) const
61 if ( k1.nKey < k2.nKey )
63 if ( k1.nKey > k2.nKey )
65 if ( k1.nThread < k2.nThread )
67 if ( k1.nThread > k2.nThread )
71 int operator ()(key_thread const& k1, size_t k2) const
79 int operator ()(size_t k1, key_thread const& k2) const
90 struct less<set::key_thread>
92 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
94 if ( k1.nKey <= k2.nKey )
95 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
101 struct hash<set::key_thread>
103 typedef size_t result_type;
104 typedef set::key_thread argument_type;
106 size_t operator()( set::key_thread const& k ) const
108 return std::hash<size_t>()(k.nKey);
111 size_t operator()( size_t k ) const
113 return std::hash<size_t>()(k);
118 class Set_Iter_Del3: public cds_test::stress_fixture
121 static size_t s_nSetSize; // max set size
122 static size_t s_nInsThreadCount; // insert thread count
123 static size_t s_nDelThreadCount; // delete thread count
124 static size_t s_nExtractThreadCount; // extract thread count
125 static size_t s_nMaxLoadFactor; // maximum load factor
126 static size_t s_nInsertPassCount;
127 static size_t s_nFindThreadCount; // find thread count
129 static size_t s_nFeldmanSet_HeadBits;
130 static size_t s_nFeldmanSet_ArrayBits;
132 static size_t s_nLoadFactor;
134 static std::vector<size_t> m_arrData;
136 static void SetUpTestCase();
137 static void TearDownTestCase();
139 template <typename Pred>
140 static void prepare_array( std::vector<size_t>& arr, Pred pred )
142 arr.reserve( m_arrData.size());
143 for ( auto el : m_arrData ) {
147 arr.resize( arr.size());
148 shuffle( arr.begin(), arr.end());
152 typedef key_thread key_type;
153 typedef size_t value_type;
155 atomics::atomic<size_t> m_nInsThreadCount;
165 // Inserts keys from [0..N)
167 class Inserter: public cds_test::thread
169 typedef cds_test::thread base_class;
172 struct update_functor
174 template <typename Q>
175 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
178 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
184 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
185 for ( size_t i = 0; i < m_arr.size(); ++i ) {
186 if ( m_Set.insert( key_type( m_arr[i], id())))
187 ++m_nInsertInitSuccess;
189 ++m_nInsertInitFailed;
194 size_t m_nInsertSuccess = 0;
195 size_t m_nInsertFailed = 0;
196 size_t m_nInsertInitSuccess = 0;
197 size_t m_nInsertInitFailed = 0;
199 std::vector<size_t> m_arr;
202 Inserter( cds_test::thread_pool& pool, Set& set )
203 : base_class( pool, inserter_thread )
209 Inserter( Inserter& src )
216 virtual thread * clone()
218 return new Inserter( *this );
224 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
226 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
229 for ( auto el : m_arr ) {
231 if ( rSet.insert( key_type( el, id())))
240 for ( auto el : m_arr ) {
244 std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
245 if ( success && inserted )
254 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
260 bool operator()( key_type const& k1, key_type const& k2 ) const
262 return k1.nKey == k2.nKey;
264 bool operator()( size_t k1, key_type const& k2 ) const
266 return k1 == k2.nKey;
268 bool operator()( key_type const& k1, size_t k2 ) const
270 return k1.nKey == k2;
272 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
274 return operator()( k1.key, k2.key );
276 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
278 return operator()( k1.key, k2 );
280 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
282 return operator()( k1, k2.key );
284 bool operator ()( key_value_pair const& k1, size_t k2 ) const
286 return operator()( k1.key, k2 );
288 bool operator ()( size_t k1, key_value_pair const& k2 ) const
290 return operator()( k1, k2.key );
295 bool operator()( key_type const& k1, key_type const& k2 ) const
297 return k1.nKey < k2.nKey;
299 bool operator()( size_t k1, key_type const& k2 ) const
303 bool operator()( key_type const& k1, size_t k2 ) const
307 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
309 return operator()( k1.key, k2.key );
311 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
313 return operator()( k1.key, k2 );
315 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
317 return operator()( k1, k2.key );
319 bool operator ()( key_value_pair const& k1, size_t k2 ) const
321 return operator()( k1.key, k2 );
323 bool operator ()( size_t k1, key_value_pair const& k2 ) const
325 return operator()( k1, k2.key );
328 typedef key_equal equal_to;
331 // Deletes keys from [0..N)
332 template <class Set, typename Iterator>
333 class Deleter: public cds_test::thread
335 typedef cds_test::thread base_class;
339 size_t m_nDeleteSuccess = 0;
340 size_t m_nDeleteFailed = 0;
343 Deleter( cds_test::thread_pool& pool, Set& set )
344 : base_class( pool, deleter_thread )
348 Deleter( Deleter& src )
353 virtual thread * clone()
355 return new Deleter( *this );
362 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
365 auto itEnd = rSet.template get_end<Iterator>();
366 for ( auto it = rSet.template get_begin<Iterator>(); it != itEnd; ++it ) {
367 if ( it->key.nKey & 3 ) {
368 if ( rSet.erase_at( it ))
374 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
378 // Extracts keys from [0..N)
379 template <typename GC, class Set>
380 class Extractor: public cds_test::thread
382 typedef cds_test::thread base_class;
385 std::vector<size_t> m_arr;
389 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
393 size_t m_nExtractSuccess = 0;
394 size_t m_nExtractFailed = 0;
397 Extractor( cds_test::thread_pool& pool, Set& set )
398 : base_class( pool, extractor_thread )
404 Extractor( Extractor& src )
411 virtual thread * clone()
413 return new Extractor( *this );
419 typename Set::guarded_ptr gp;
421 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
422 size_t const nInsThreadCount = s_nInsThreadCount;
426 for ( auto el : m_arr ) {
427 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
428 gp = rSet.extract( key_type( el, k ));
438 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
439 for ( auto el : m_arr ) {
440 gp = rSet.extract( key_type( el, k ));
449 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
455 template <typename RCU, class Set>
456 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
458 typedef cds_test::thread base_class;
460 std::vector<size_t> m_arr;
464 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
468 size_t m_nExtractSuccess = 0;
469 size_t m_nExtractFailed = 0;
472 Extractor( cds_test::thread_pool& pool, Set& set )
473 : base_class( pool, extractor_thread )
479 Extractor( Extractor& src )
486 virtual thread * clone()
488 return new Extractor( *this );
494 typename Set::exempt_ptr xp;
496 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
497 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
501 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
502 for ( auto el : m_arr ) {
503 if ( Set::c_bExtractLockExternal ) {
504 typename Set::rcu_lock l;
505 xp = rSet.extract( key_type( el, k ));
512 xp = rSet.extract( key_type( el, k ));
523 for ( auto el : m_arr ) {
524 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
525 if ( Set::c_bExtractLockExternal ) {
526 typename Set::rcu_lock l;
527 xp = rSet.extract( key_type( el, k ));
534 xp = rSet.extract( key_type( el, k ));
544 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
552 class Observer: public cds_test::thread
554 typedef cds_test::thread base_class;
558 size_t m_nFindEvenSuccess = 0;
559 size_t m_nFindEvenFailed = 0;
560 size_t m_nFindOddSuccess = 0;
561 size_t m_nFindOddFailed = 0;
564 Observer( cds_test::thread_pool& pool, Set& set )
565 : base_class( pool, find_thread )
569 Observer( Observer& src )
574 virtual thread * clone()
576 return new Observer( *this );
582 Set_Iter_Del3& fixture = pool().template fixture<Set_Iter_Del3>();
583 std::vector<size_t> const& arr = m_arrData;
584 size_t const nInsThreadCount = s_nInsThreadCount;
587 for ( size_t key : arr ) {
589 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
590 if ( set.contains( key_thread( key, k )))
597 // that keys MUST be in the map
598 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
599 if ( set.contains( key_thread( key, k )))
600 ++m_nFindEvenSuccess;
606 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
611 template <typename Iterator, class Set>
612 void do_test_with( Set& testSet )
614 typedef Inserter<Set> insert_thread;
615 typedef Deleter<Set, Iterator> delete_thread;
616 typedef Observer<Set> observer_thread;
618 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
620 cds_test::thread_pool& pool = get_pool();
621 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
622 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
623 if ( s_nFindThreadCount )
624 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
626 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
627 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
628 << std::make_pair( "find_thread_count", s_nFindThreadCount )
629 << std::make_pair( "set_size", s_nSetSize )
630 << std::make_pair( "pass_count", s_nInsertPassCount );
632 std::chrono::milliseconds duration = pool.run();
634 propout() << std::make_pair( "duration", duration );
636 size_t nInsertInitFailed = 0;
637 size_t nInsertInitSuccess = 0;
638 size_t nInsertSuccess = 0;
639 size_t nInsertFailed = 0;
640 size_t nDeleteSuccess = 0;
641 size_t nDeleteFailed = 0;
643 size_t nFindEvenSuccess = 0;
644 size_t nFindEvenFailed = 0;
645 size_t nFindOddSuccess = 0;
646 size_t nFindOddFailed = 0;
648 for ( size_t i = 0; i < pool.size(); ++i ) {
649 cds_test::thread& thr = pool.get( i );
650 switch ( thr.type()) {
651 case inserter_thread:
653 insert_thread& inserter = static_cast<insert_thread&>(thr);
654 nInsertSuccess += inserter.m_nInsertSuccess;
655 nInsertFailed += inserter.m_nInsertFailed;
656 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
657 nInsertInitFailed += inserter.m_nInsertInitFailed;
662 delete_thread& deleter = static_cast<delete_thread&>(thr);
663 nDeleteSuccess += deleter.m_nDeleteSuccess;
664 nDeleteFailed += deleter.m_nDeleteFailed;
669 observer_thread& observer = static_cast<observer_thread&>( thr );
670 nFindEvenSuccess = observer.m_nFindEvenSuccess;
671 nFindEvenFailed = observer.m_nFindEvenFailed;
672 nFindOddSuccess = observer.m_nFindOddSuccess;
673 nFindOddFailed = observer.m_nFindOddFailed;
681 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
683 EXPECT_EQ( nInsertInitFailed, 0u );
684 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
685 EXPECT_EQ( nFindEvenFailed, 0u );
686 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
687 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
690 << std::make_pair( "insert_init_success", nInsertInitSuccess )
691 << std::make_pair( "insert_init_failed", nInsertInitFailed )
692 << std::make_pair( "insert_success", nInsertSuccess )
693 << std::make_pair( "insert_failed", nInsertFailed )
694 << std::make_pair( "delete_success", nDeleteSuccess )
695 << std::make_pair( "delete_failed", nDeleteFailed )
696 << std::make_pair( "find_even_success", nFindEvenSuccess )
697 << std::make_pair( "find_even_failed", nFindEvenFailed )
698 << std::make_pair( "find_odd_success", nFindOddSuccess )
699 << std::make_pair( "find_odd_failed", nFindOddFailed );
702 template <typename Iterator, class Set>
703 void do_test_extract_with( Set& testSet )
705 typedef Inserter<Set> insert_thread;
706 typedef Deleter<Set, Iterator> delete_thread;
707 typedef Extractor< typename Set::gc, Set > extract_thread;
708 typedef Observer<Set> observer_thread;
710 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
712 cds_test::thread_pool& pool = get_pool();
713 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
714 if ( s_nDelThreadCount )
715 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
716 if ( s_nExtractThreadCount )
717 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
718 if ( s_nFindThreadCount )
719 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
721 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
722 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
723 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
724 << std::make_pair( "find_thread_count", s_nFindThreadCount )
725 << std::make_pair( "set_size", s_nSetSize )
726 << std::make_pair( "pass_count", s_nInsertPassCount );
728 std::chrono::milliseconds duration = pool.run();
730 propout() << std::make_pair( "duration", duration );
732 size_t nInsertInitFailed = 0;
733 size_t nInsertInitSuccess = 0;
734 size_t nInsertSuccess = 0;
735 size_t nInsertFailed = 0;
736 size_t nDeleteSuccess = 0;
737 size_t nDeleteFailed = 0;
738 size_t nExtractSuccess = 0;
739 size_t nExtractFailed = 0;
741 size_t nFindEvenSuccess = 0;
742 size_t nFindEvenFailed = 0;
743 size_t nFindOddSuccess = 0;
744 size_t nFindOddFailed = 0;
746 for ( size_t i = 0; i < pool.size(); ++i ) {
747 cds_test::thread& thr = pool.get( i );
748 switch ( thr.type()) {
749 case inserter_thread:
751 insert_thread& inserter = static_cast<insert_thread&>( thr );
752 nInsertSuccess += inserter.m_nInsertSuccess;
753 nInsertFailed += inserter.m_nInsertFailed;
754 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
755 nInsertInitFailed += inserter.m_nInsertInitFailed;
760 delete_thread& deleter = static_cast<delete_thread&>(thr);
761 nDeleteSuccess += deleter.m_nDeleteSuccess;
762 nDeleteFailed += deleter.m_nDeleteFailed;
765 case extractor_thread:
767 extract_thread& extractor = static_cast<extract_thread&>(thr);
768 nExtractSuccess += extractor.m_nExtractSuccess;
769 nExtractFailed += extractor.m_nExtractFailed;
774 observer_thread& observer = static_cast<observer_thread&>( thr );
775 nFindEvenSuccess = observer.m_nFindEvenSuccess;
776 nFindEvenFailed = observer.m_nFindEvenFailed;
777 nFindOddSuccess = observer.m_nFindOddSuccess;
778 nFindOddFailed = observer.m_nFindOddFailed;
786 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
788 EXPECT_EQ( nInsertInitFailed, 0u );
789 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
790 EXPECT_EQ( nFindEvenFailed, 0u );
791 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
792 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
795 << std::make_pair( "insert_init_success", nInsertInitSuccess )
796 << std::make_pair( "insert_init_failed", nInsertInitFailed )
797 << std::make_pair( "insert_success", nInsertSuccess )
798 << std::make_pair( "insert_failed", nInsertFailed )
799 << std::make_pair( "delete_success", nDeleteSuccess )
800 << std::make_pair( "delete_failed", nDeleteFailed )
801 << std::make_pair( "extract_success", nExtractSuccess )
802 << std::make_pair( "extract_failed", nExtractFailed )
803 << std::make_pair( "find_even_success", nFindEvenSuccess )
804 << std::make_pair( "find_even_failed", nFindEvenFailed )
805 << std::make_pair( "find_odd_success", nFindOddSuccess )
806 << std::make_pair( "find_odd_failed", nFindOddFailed );
809 template <typename Set>
810 void analyze( Set& testSet )
812 // All even keys must be in the set
814 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
815 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
816 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
821 check_before_clear( testSet );
824 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
826 additional_check( testSet );
827 print_stat( propout(), testSet );
828 additional_cleanup( testSet );
831 template <class Set, typename Iterator=typename Set::iterator>
834 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
836 Set testSet( *this );
837 do_test_with<Iterator>( testSet );
838 DEBUG(analyze( testSet ));
841 template <class Set, typename Iterator=typename Set::iterator>
842 void run_test_extract()
844 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
846 Set testSet( *this );
847 do_test_extract_with<Iterator>( testSet );
848 DEBUG(analyze( testSet ));
855 class Set_Iter_Del3_reverse: public Set_Iter_Del3
863 class Set_Iter_Del3_LF: public Set_Iter_Del3
864 , public ::testing::WithParamInterface<size_t>
870 s_nLoadFactor = GetParam();
871 propout() << std::make_pair( "load_factor", s_nLoadFactor );
872 Set_Iter_Del3::run_test<Set>();
876 void run_test_extract()
878 s_nLoadFactor = GetParam();
879 propout() << std::make_pair( "load_factor", s_nLoadFactor );
880 Set_Iter_Del3::run_test_extract<Set>();
883 static std::vector<size_t> get_load_factors();