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_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_nCuckooInitialSize; // initial size for CuckooSet
130 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
131 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
133 static size_t s_nFeldmanSet_HeadBits;
134 static size_t s_nFeldmanSet_ArrayBits;
136 static size_t s_nLoadFactor;
138 static std::vector<size_t> m_arrData;
140 static void SetUpTestCase();
141 static void TearDownTestCase();
143 template <typename Pred>
144 static void prepare_array( std::vector<size_t>& arr, Pred pred )
146 arr.reserve( m_arrData.size());
147 for ( auto el : m_arrData ) {
151 arr.resize( arr.size());
152 shuffle( arr.begin(), arr.end());
156 typedef key_thread key_type;
157 typedef size_t value_type;
159 atomics::atomic<size_t> m_nInsThreadCount;
169 // Inserts keys from [0..N)
171 class Inserter: public cds_test::thread
173 typedef cds_test::thread base_class;
176 struct update_functor
178 template <typename Q>
179 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
182 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
188 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
189 for ( size_t i = 0; i < m_arr.size(); ++i ) {
190 if ( m_Set.insert( key_type( m_arr[i], id())))
191 ++m_nInsertInitSuccess;
193 ++m_nInsertInitFailed;
198 size_t m_nInsertSuccess = 0;
199 size_t m_nInsertFailed = 0;
200 size_t m_nInsertInitSuccess = 0;
201 size_t m_nInsertInitFailed = 0;
203 std::vector<size_t> m_arr;
206 Inserter( cds_test::thread_pool& pool, Set& set )
207 : base_class( pool, inserter_thread )
213 Inserter( Inserter& src )
220 virtual thread * clone()
222 return new Inserter( *this );
228 Set_Del3& fixture = pool().template fixture<Set_Del3>();
230 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
233 for ( auto el : m_arr ) {
235 if ( rSet.insert( key_type( el, id())))
244 for ( auto el : m_arr ) {
248 std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
249 if ( success && inserted )
258 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
264 bool operator()( key_type const& k1, key_type const& k2 ) const
266 return k1.nKey == k2.nKey;
268 bool operator()( size_t k1, key_type const& k2 ) const
270 return k1 == k2.nKey;
272 bool operator()( key_type const& k1, size_t k2 ) const
274 return k1.nKey == k2;
276 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
278 return operator()( k1.key, k2.key );
280 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
282 return operator()( k1.key, k2 );
284 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
286 return operator()( k1, k2.key );
288 bool operator ()( key_value_pair const& k1, size_t k2 ) const
290 return operator()( k1.key, k2 );
292 bool operator ()( size_t k1, key_value_pair const& k2 ) const
294 return operator()( k1, k2.key );
299 bool operator()( key_type const& k1, key_type const& k2 ) const
301 return k1.nKey < k2.nKey;
303 bool operator()( size_t k1, key_type const& k2 ) const
307 bool operator()( key_type const& k1, size_t k2 ) const
311 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
313 return operator()( k1.key, k2.key );
315 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
317 return operator()( k1.key, k2 );
319 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
321 return operator()( k1, k2.key );
323 bool operator ()( key_value_pair const& k1, size_t k2 ) const
325 return operator()( k1.key, k2 );
327 bool operator ()( size_t k1, key_value_pair const& k2 ) const
329 return operator()( k1, k2.key );
332 typedef key_equal equal_to;
335 // Deletes odd keys from [0..N)
337 class Deleter: public cds_test::thread
339 typedef cds_test::thread base_class;
344 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
348 size_t m_nDeleteSuccess = 0;
349 size_t m_nDeleteFailed = 0;
351 std::vector<size_t> m_arr;
354 Deleter( cds_test::thread_pool& pool, Set& set )
355 : base_class( pool, deleter_thread )
360 Deleter( Deleter& src )
367 virtual thread * clone()
369 return new Deleter( *this );
372 template <typename SetType, bool>
374 static bool erase( SetType& s, size_t key, size_t /*thread*/)
376 return s.erase_with( key, key_less());
380 template <typename SetType>
381 struct eraser<SetType, true> {
382 static bool erase(SetType& s, size_t key, size_t thread)
384 return s.erase( key_type(key, thread));
392 size_t const nInsThreadCount = s_nInsThreadCount;
393 Set_Del3& fixture = pool().template fixture<Set_Del3>();
397 for ( auto el : m_arr ) {
398 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
399 if ( rSet.erase( key_type( el, k )))
407 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
408 for ( auto el : m_arr ) {
409 if ( rSet.erase( key_type( el, k )))
416 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
422 // Extracts odd keys from [0..N)
423 template <typename GC, class Set>
424 class Extractor: public cds_test::thread
426 typedef cds_test::thread base_class;
429 std::vector<size_t> m_arr;
433 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
437 size_t m_nExtractSuccess = 0;
438 size_t m_nExtractFailed = 0;
441 Extractor( cds_test::thread_pool& pool, Set& set )
442 : base_class( pool, extractor_thread )
448 Extractor( Extractor& src )
455 virtual thread * clone()
457 return new Extractor( *this );
463 typename Set::guarded_ptr gp;
465 Set_Del3& fixture = pool().template fixture<Set_Del3>();
466 size_t const nInsThreadCount = s_nInsThreadCount;
470 for ( auto el : m_arr ) {
471 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
472 gp = rSet.extract( key_type( el, k ));
482 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
483 for ( auto el : m_arr ) {
484 gp = rSet.extract( key_type( el, k ));
493 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
499 template <typename RCU, class Set>
500 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
502 typedef cds_test::thread base_class;
504 std::vector<size_t> m_arr;
508 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
512 size_t m_nExtractSuccess = 0;
513 size_t m_nExtractFailed = 0;
516 Extractor( cds_test::thread_pool& pool, Set& set )
517 : base_class( pool, extractor_thread )
523 Extractor( Extractor& src )
530 virtual thread * clone()
532 return new Extractor( *this );
538 typename Set::exempt_ptr xp;
540 Set_Del3& fixture = pool().template fixture<Set_Del3>();
541 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
545 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
546 for ( auto el : m_arr ) {
547 if ( Set::c_bExtractLockExternal ) {
548 typename Set::rcu_lock l;
549 xp = rSet.extract( key_type( el, k ));
556 xp = rSet.extract( key_type( el, k ));
567 for ( auto el : m_arr ) {
568 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
569 if ( Set::c_bExtractLockExternal ) {
570 typename Set::rcu_lock l;
571 xp = rSet.extract( key_type( el, k ));
578 xp = rSet.extract( key_type( el, k ));
588 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
596 class Observer: public cds_test::thread
598 typedef cds_test::thread base_class;
602 size_t m_nFindEvenSuccess = 0;
603 size_t m_nFindEvenFailed = 0;
604 size_t m_nFindOddSuccess = 0;
605 size_t m_nFindOddFailed = 0;
608 Observer( cds_test::thread_pool& pool, Set& set )
609 : base_class( pool, find_thread )
613 Observer( Observer& src )
618 virtual thread * clone()
620 return new Observer( *this );
626 Set_Del3& fixture = pool().template fixture<Set_Del3>();
627 std::vector<size_t> const& arr = m_arrData;
628 size_t const nInsThreadCount = s_nInsThreadCount;
631 for ( size_t key : arr ) {
633 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
634 if ( set.contains( key_thread( key, k )))
641 // even keys MUST be in the map
642 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
643 if ( set.contains( key_thread( key, k )))
644 ++m_nFindEvenSuccess;
650 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
656 void do_test_with( Set& testSet )
658 typedef Inserter<Set> insert_thread;
659 typedef Deleter<Set> delete_thread;
660 typedef Observer<Set> observer_thread;
662 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
664 cds_test::thread_pool& pool = get_pool();
665 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
666 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
667 if ( s_nFindThreadCount )
668 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
670 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
671 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
672 << std::make_pair( "find_thread_count", s_nFindThreadCount )
673 << std::make_pair( "set_size", s_nSetSize )
674 << std::make_pair( "pass_count", s_nInsertPassCount );
676 std::chrono::milliseconds duration = pool.run();
678 propout() << std::make_pair( "duration", duration );
680 size_t nInsertInitFailed = 0;
681 size_t nInsertInitSuccess = 0;
682 size_t nInsertSuccess = 0;
683 size_t nInsertFailed = 0;
684 size_t nDeleteSuccess = 0;
685 size_t nDeleteFailed = 0;
687 size_t nFindEvenSuccess = 0;
688 size_t nFindEvenFailed = 0;
689 size_t nFindOddSuccess = 0;
690 size_t nFindOddFailed = 0;
692 for ( size_t i = 0; i < pool.size(); ++i ) {
693 cds_test::thread& thr = pool.get( i );
694 switch ( thr.type()) {
695 case inserter_thread:
697 insert_thread& inserter = static_cast<insert_thread&>(thr);
698 nInsertSuccess += inserter.m_nInsertSuccess;
699 nInsertFailed += inserter.m_nInsertFailed;
700 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
701 nInsertInitFailed += inserter.m_nInsertInitFailed;
706 delete_thread& deleter = static_cast<delete_thread&>(thr);
707 nDeleteSuccess += deleter.m_nDeleteSuccess;
708 nDeleteFailed += deleter.m_nDeleteFailed;
713 observer_thread& observer = static_cast<observer_thread&>( thr );
714 nFindEvenSuccess = observer.m_nFindEvenSuccess;
715 nFindEvenFailed = observer.m_nFindEvenFailed;
716 nFindOddSuccess = observer.m_nFindOddSuccess;
717 nFindOddFailed = observer.m_nFindOddFailed;
725 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
727 EXPECT_EQ( nInsertInitFailed, 0u );
728 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
729 EXPECT_EQ( nFindEvenFailed, 0u );
730 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
731 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
734 << std::make_pair( "insert_init_success", nInsertInitSuccess )
735 << std::make_pair( "insert_init_failed", nInsertInitFailed )
736 << std::make_pair( "insert_success", nInsertSuccess )
737 << std::make_pair( "insert_failed", nInsertFailed )
738 << std::make_pair( "delete_success", nDeleteSuccess )
739 << std::make_pair( "delete_failed", nDeleteFailed )
740 << std::make_pair( "find_even_success", nFindEvenSuccess )
741 << std::make_pair( "find_even_failed", nFindEvenFailed )
742 << std::make_pair( "find_odd_success", nFindOddSuccess )
743 << std::make_pair( "find_odd_failed", nFindOddFailed );
747 void do_test_extract_with( Set& testSet )
749 typedef Inserter<Set> insert_thread;
750 typedef Deleter<Set> delete_thread;
751 typedef Extractor< typename Set::gc, Set > extract_thread;
752 typedef Observer<Set> observer_thread;
754 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
756 cds_test::thread_pool& pool = get_pool();
757 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
758 if ( s_nDelThreadCount )
759 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
760 if ( s_nExtractThreadCount )
761 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
762 if ( s_nFindThreadCount )
763 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
765 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
766 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
767 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
768 << std::make_pair( "find_thread_count", s_nFindThreadCount )
769 << std::make_pair( "set_size", s_nSetSize )
770 << std::make_pair( "pass_count", s_nInsertPassCount );
772 std::chrono::milliseconds duration = pool.run();
774 propout() << std::make_pair( "duration", duration );
776 size_t nInsertInitFailed = 0;
777 size_t nInsertInitSuccess = 0;
778 size_t nInsertSuccess = 0;
779 size_t nInsertFailed = 0;
780 size_t nDeleteSuccess = 0;
781 size_t nDeleteFailed = 0;
782 size_t nExtractSuccess = 0;
783 size_t nExtractFailed = 0;
785 size_t nFindEvenSuccess = 0;
786 size_t nFindEvenFailed = 0;
787 size_t nFindOddSuccess = 0;
788 size_t nFindOddFailed = 0;
790 for ( size_t i = 0; i < pool.size(); ++i ) {
791 cds_test::thread& thr = pool.get( i );
792 switch ( thr.type()) {
793 case inserter_thread:
795 insert_thread& inserter = static_cast<insert_thread&>( thr );
796 nInsertSuccess += inserter.m_nInsertSuccess;
797 nInsertFailed += inserter.m_nInsertFailed;
798 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
799 nInsertInitFailed += inserter.m_nInsertInitFailed;
804 delete_thread& deleter = static_cast<delete_thread&>(thr);
805 nDeleteSuccess += deleter.m_nDeleteSuccess;
806 nDeleteFailed += deleter.m_nDeleteFailed;
809 case extractor_thread:
811 extract_thread& extractor = static_cast<extract_thread&>(thr);
812 nExtractSuccess += extractor.m_nExtractSuccess;
813 nExtractFailed += extractor.m_nExtractFailed;
818 observer_thread& observer = static_cast<observer_thread&>( thr );
819 nFindEvenSuccess = observer.m_nFindEvenSuccess;
820 nFindEvenFailed = observer.m_nFindEvenFailed;
821 nFindOddSuccess = observer.m_nFindOddSuccess;
822 nFindOddFailed = observer.m_nFindOddFailed;
830 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
832 EXPECT_EQ( nInsertInitFailed, 0u );
833 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
834 EXPECT_EQ( nFindEvenFailed, 0u );
835 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
836 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
839 << std::make_pair( "insert_init_success", nInsertInitSuccess )
840 << std::make_pair( "insert_init_failed", nInsertInitFailed )
841 << std::make_pair( "insert_success", nInsertSuccess )
842 << std::make_pair( "insert_failed", nInsertFailed )
843 << std::make_pair( "delete_success", nDeleteSuccess )
844 << std::make_pair( "delete_failed", nDeleteFailed )
845 << std::make_pair( "extract_success", nExtractSuccess )
846 << std::make_pair( "extract_failed", nExtractFailed )
847 << std::make_pair( "find_even_success", nFindEvenSuccess )
848 << std::make_pair( "find_even_failed", nFindEvenFailed )
849 << std::make_pair( "find_odd_success", nFindOddSuccess )
850 << std::make_pair( "find_odd_failed", nFindOddFailed );
853 template <typename Set>
854 void analyze( Set& testSet )
856 // All even keys must be in the set
858 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
859 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
860 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
865 check_before_clear( testSet );
868 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
870 additional_check( testSet );
871 print_stat( propout(), testSet );
872 additional_cleanup( testSet );
878 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
880 Set testSet( *this );
881 do_test_with( testSet );
882 DEBUG(analyze( testSet ));
886 void run_test_extract()
888 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
890 Set testSet( *this );
891 do_test_extract_with( testSet );
892 DEBUG(analyze( testSet ));
899 class Set_Del3_LF: public Set_Del3
900 , public ::testing::WithParamInterface<size_t>
906 s_nLoadFactor = GetParam();
907 propout() << std::make_pair( "load_factor", s_nLoadFactor );
908 Set_Del3::run_test<Set>();
912 void run_test_extract()
914 s_nLoadFactor = GetParam();
915 propout() << std::make_pair( "load_factor", s_nLoadFactor );
916 Set_Del3::run_test_extract<Set>();
919 static std::vector<size_t> get_load_factors();