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_DelOdd: 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
126 static size_t s_nPassCount;
127 static size_t s_nFeldmanPassCount;
128 static size_t s_nInsertPassCount;
129 static size_t s_nDeletePassCount;
130 static size_t s_nFindPassCount;
132 static size_t s_nFindThreadCount; // find thread count
134 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
135 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
136 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
138 static size_t s_nFeldmanSet_HeadBits;
139 static size_t s_nFeldmanSet_ArrayBits;
141 static size_t s_nLoadFactor;
143 static std::vector<size_t> m_arrData;
145 static void SetUpTestCase();
146 static void TearDownTestCase();
148 template <typename Pred>
149 static void prepare_array( std::vector<size_t>& arr, Pred pred )
151 arr.reserve( m_arrData.size());
152 for ( auto el : m_arrData ) {
156 arr.resize( arr.size());
157 shuffle( arr.begin(), arr.end());
161 typedef key_thread key_type;
162 typedef size_t value_type;
164 atomics::atomic<size_t> m_nInsThreadCount;
174 // Inserts keys from [0..N)
176 class Inserter: public cds_test::thread
178 typedef cds_test::thread base_class;
181 struct update_functor
183 template <typename Q>
184 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
187 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
193 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
194 for ( size_t i = 0; i < m_arr.size(); ++i ) {
195 if ( m_Set.insert( key_type( m_arr[i], id())))
196 ++m_nInsertInitSuccess;
198 ++m_nInsertInitFailed;
203 size_t m_nInsertSuccess = 0;
204 size_t m_nInsertFailed = 0;
205 size_t m_nInsertInitSuccess = 0;
206 size_t m_nInsertInitFailed = 0;
208 std::vector<size_t> m_arr;
211 Inserter( cds_test::thread_pool& pool, Set& set )
212 : base_class( pool, inserter_thread )
218 Inserter( Inserter& src )
225 virtual thread * clone()
227 return new Inserter( *this );
233 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
235 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
238 for ( auto el : m_arr ) {
240 if ( rSet.insert( key_type( el, id())))
249 for ( auto el : m_arr ) {
253 std::tie( success, inserted ) = rSet.update( key_type( el, id()), update_functor());
254 if ( success && inserted )
263 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
269 bool operator()( key_type const& k1, key_type const& k2 ) const
271 return k1.nKey == k2.nKey;
273 bool operator()( size_t k1, key_type const& k2 ) const
275 return k1 == k2.nKey;
277 bool operator()( key_type const& k1, size_t k2 ) const
279 return k1.nKey == k2;
281 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
283 return operator()( k1.key, k2.key );
285 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
287 return operator()( k1.key, k2 );
289 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
291 return operator()( k1, k2.key );
293 bool operator ()( key_value_pair const& k1, size_t k2 ) const
295 return operator()( k1.key, k2 );
297 bool operator ()( size_t k1, key_value_pair const& k2 ) const
299 return operator()( k1, k2.key );
304 bool operator()( key_type const& k1, key_type const& k2 ) const
306 return k1.nKey < k2.nKey;
308 bool operator()( size_t k1, key_type const& k2 ) const
312 bool operator()( key_type const& k1, size_t k2 ) const
316 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
318 return operator()( k1.key, k2.key );
320 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
322 return operator()( k1.key, k2 );
324 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
326 return operator()( k1, k2.key );
328 bool operator ()( key_value_pair const& k1, size_t k2 ) const
330 return operator()( k1.key, k2 );
332 bool operator ()( size_t k1, key_value_pair const& k2 ) const
334 return operator()( k1, k2.key );
337 typedef key_equal equal_to;
340 // Deletes odd keys from [0..N)
342 class Deleter: public cds_test::thread
344 typedef cds_test::thread base_class;
349 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
353 size_t m_nDeleteSuccess = 0;
354 size_t m_nDeleteFailed = 0;
356 std::vector<size_t> m_arr;
359 Deleter( cds_test::thread_pool& pool, Set& set )
360 : base_class( pool, deleter_thread )
365 Deleter( Deleter& src )
372 virtual thread * clone()
374 return new Deleter( *this );
377 template <typename SetType, bool>
379 static bool erase( SetType& s, size_t key, size_t /*thread*/)
381 return s.erase_with( key, key_less());
385 template <typename SetType>
386 struct eraser<SetType, true> {
387 static bool erase(SetType& s, size_t key, size_t thread)
389 return s.erase( key_type(key, thread));
397 size_t const nInsThreadCount = s_nInsThreadCount;
398 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
402 for ( auto el : m_arr ) {
403 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
404 if ( rSet.erase( key_type( el, k )))
412 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
413 for ( auto el : m_arr ) {
414 if ( rSet.erase( key_type( el, k )))
421 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
427 // Extracts odd keys from [0..N)
428 template <typename GC, class Set>
429 class Extractor: public cds_test::thread
431 typedef cds_test::thread base_class;
434 std::vector<size_t> m_arr;
438 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
442 size_t m_nExtractSuccess = 0;
443 size_t m_nExtractFailed = 0;
446 Extractor( cds_test::thread_pool& pool, Set& set )
447 : base_class( pool, extractor_thread )
453 Extractor( Extractor& src )
460 virtual thread * clone()
462 return new Extractor( *this );
468 typename Set::guarded_ptr gp;
470 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
471 size_t const nInsThreadCount = s_nInsThreadCount;
475 for ( auto el : m_arr ) {
476 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
477 gp = rSet.extract( key_type( el, k ));
487 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
488 for ( auto el : m_arr ) {
489 gp = rSet.extract( key_type( el, k ));
498 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
504 template <typename RCU, class Set>
505 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
507 typedef cds_test::thread base_class;
509 std::vector<size_t> m_arr;
513 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
517 size_t m_nExtractSuccess = 0;
518 size_t m_nExtractFailed = 0;
521 Extractor( cds_test::thread_pool& pool, Set& set )
522 : base_class( pool, extractor_thread )
528 Extractor( Extractor& src )
535 virtual thread * clone()
537 return new Extractor( *this );
543 typename Set::exempt_ptr xp;
545 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
546 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
550 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
551 for ( auto el : m_arr ) {
552 if ( Set::c_bExtractLockExternal ) {
553 typename Set::rcu_lock l;
554 xp = rSet.extract( key_type( el, k ));
561 xp = rSet.extract( key_type( el, k ));
572 for ( auto el : m_arr ) {
573 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
574 if ( Set::c_bExtractLockExternal ) {
575 typename Set::rcu_lock l;
576 xp = rSet.extract( key_type( el, k ));
583 xp = rSet.extract( key_type( el, k ));
593 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
601 class Observer: public cds_test::thread
603 typedef cds_test::thread base_class;
607 size_t m_nFindEvenSuccess = 0;
608 size_t m_nFindEvenFailed = 0;
609 size_t m_nFindOddSuccess = 0;
610 size_t m_nFindOddFailed = 0;
613 Observer( cds_test::thread_pool& pool, Set& set )
614 : base_class( pool, find_thread )
618 Observer( Observer& src )
623 virtual thread * clone()
625 return new Observer( *this );
631 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
632 std::vector<size_t> const& arr = m_arrData;
633 size_t const nInsThreadCount = s_nInsThreadCount;
636 for ( size_t key : arr ) {
638 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
639 if ( set.contains( key_thread( key, k )))
646 // even keys MUST be in the map
647 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
648 if ( set.contains( key_thread( key, k )))
649 ++m_nFindEvenSuccess;
655 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
661 void do_test_with( Set& testSet )
663 typedef Inserter<Set> insert_thread;
664 typedef Deleter<Set> delete_thread;
665 typedef Observer<Set> observer_thread;
667 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
669 cds_test::thread_pool& pool = get_pool();
670 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
671 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
672 if ( s_nFindThreadCount )
673 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
675 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
676 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
677 << std::make_pair( "find_thread_count", s_nFindThreadCount )
678 << std::make_pair( "set_size", s_nSetSize )
679 << std::make_pair( "pass_count", s_nInsertPassCount );
681 std::chrono::milliseconds duration = pool.run();
683 propout() << std::make_pair( "duration", duration );
685 size_t nInsertInitFailed = 0;
686 size_t nInsertInitSuccess = 0;
687 size_t nInsertSuccess = 0;
688 size_t nInsertFailed = 0;
689 size_t nDeleteSuccess = 0;
690 size_t nDeleteFailed = 0;
692 size_t nFindEvenSuccess = 0;
693 size_t nFindEvenFailed = 0;
694 size_t nFindOddSuccess = 0;
695 size_t nFindOddFailed = 0;
697 for ( size_t i = 0; i < pool.size(); ++i ) {
698 cds_test::thread& thr = pool.get( i );
699 switch ( thr.type()) {
700 case inserter_thread:
702 insert_thread& inserter = static_cast<insert_thread&>(thr);
703 nInsertSuccess += inserter.m_nInsertSuccess;
704 nInsertFailed += inserter.m_nInsertFailed;
705 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
706 nInsertInitFailed += inserter.m_nInsertInitFailed;
711 delete_thread& deleter = static_cast<delete_thread&>(thr);
712 nDeleteSuccess += deleter.m_nDeleteSuccess;
713 nDeleteFailed += deleter.m_nDeleteFailed;
718 observer_thread& observer = static_cast<observer_thread&>( thr );
719 nFindEvenSuccess = observer.m_nFindEvenSuccess;
720 nFindEvenFailed = observer.m_nFindEvenFailed;
721 nFindOddSuccess = observer.m_nFindOddSuccess;
722 nFindOddFailed = observer.m_nFindOddFailed;
730 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
732 EXPECT_EQ( nInsertInitFailed, 0u );
733 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
734 EXPECT_EQ( nFindEvenFailed, 0u );
735 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
736 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
739 << std::make_pair( "insert_init_success", nInsertInitSuccess )
740 << std::make_pair( "insert_init_failed", nInsertInitFailed )
741 << std::make_pair( "insert_success", nInsertSuccess )
742 << std::make_pair( "insert_failed", nInsertFailed )
743 << std::make_pair( "delete_success", nDeleteSuccess )
744 << std::make_pair( "delete_failed", nDeleteFailed )
745 << std::make_pair( "find_even_success", nFindEvenSuccess )
746 << std::make_pair( "find_even_failed", nFindEvenFailed )
747 << std::make_pair( "find_odd_success", nFindOddSuccess )
748 << std::make_pair( "find_odd_failed", nFindOddFailed );
752 void do_test_extract_with(Set &testSet, size_t pass_count) {
753 typedef Inserter<Set> insert_thread;
754 typedef Deleter<Set> delete_thread;
755 typedef Extractor<typename Set::gc, Set> extract_thread;
756 typedef Observer<Set> observer_thread;
758 size_t nInsertSuccess = 0;
759 size_t nInsertFailed = 0;
760 size_t nDeleteSuccess = 0;
761 size_t nDeleteFailed = 0;
762 size_t nExtractSuccess = 0;
763 size_t nExtractFailed = 0;
764 size_t nFindEvenSuccess = 0;
765 size_t nFindEvenFailed = 0;
766 size_t nFindOddSuccess = 0;
767 size_t nFindOddFailed = 0;
769 auto reset_stat = [&]() {
776 nFindEvenSuccess = 0;
782 auto insert_func = [&]() {
783 for (auto el : m_arrData) {
784 if (testSet.insert(key_type(el, 0)))
791 auto delete_func = [&]() {
792 for (auto el : m_arrData) {
794 if (testSet.erase(key_type(el, 0)))
802 auto extract_func = [&]() {
803 for (auto el : m_arrData) {
805 auto gp = testSet.extract(key_type(el, 0));
815 auto find_func = [&]() {
816 for (size_t el : m_arrData) {
818 if (testSet.contains(key_thread(el, 0)))
823 // even keys MUST be in the map
824 if (testSet.contains(key_thread(el, 0)))
832 auto test_func = [&](size_t count, std::function<void()> func) {
833 for (size_t i = 0; i < count; ++i) {
838 size_t const nInitialOddKeys = s_nSetSize / 2;
839 size_t const nInitialEvenKeys = s_nSetSize / 2;
840 for (size_t nPass = 0; nPass < pass_count; ++nPass) {
841 // Start with an empty set.
845 test_func(s_nInsertPassCount, insert_func);
846 EXPECT_EQ(nInsertSuccess, s_nSetSize);
849 test_func(s_nFindPassCount, find_func);
850 EXPECT_EQ(nFindEvenFailed, 0u);
851 EXPECT_EQ(nFindOddFailed, 0u);
854 test_func(s_nDeletePassCount, delete_func);
855 EXPECT_EQ(nDeleteSuccess, nInitialOddKeys);
858 test_func(s_nInsertPassCount, insert_func);
859 EXPECT_EQ(nInsertSuccess, nInitialOddKeys);
862 test_func(s_nDeletePassCount, extract_func);
863 EXPECT_EQ(nExtractSuccess, nInitialOddKeys);
866 test_func(s_nFindPassCount, find_func);
867 EXPECT_EQ(nFindEvenFailed, 0u);
868 EXPECT_EQ(nFindOddSuccess, 0u);
871 // std::chrono::duration<double> time_elapsed;
872 // std::chrono::duration<double> time_diff;
873 // std::chrono::time_point<std::chrono::steady_clock>
875 // std::chrono::time_point<std::chrono::steady_clock>
877 // time_start = std::chrono::steady_clock::now();
878 // time_end = std::chrono::steady_clock::now();
879 // time_diff = time_end - time_start;
880 // time_elapsed = time_diff;
881 // std::cout << "Time elapsed: " << time_elapsed.count() <<
885 template <typename Set>
886 void analyze( Set& testSet )
888 // All even keys must be in the set
890 for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
891 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
892 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
897 check_before_clear( testSet );
900 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
902 additional_check( testSet );
903 print_stat( propout(), testSet );
904 additional_cleanup( testSet );
910 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
912 Set testSet( *this );
913 do_test_with( testSet );
918 void run_test_extract(size_t pass_count = s_nPassCount)
920 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
922 Set testSet( *this );
923 do_test_extract_with( testSet, pass_count);
930 class Set_DelOdd_LF: public Set_DelOdd
931 , public ::testing::WithParamInterface<size_t>
937 s_nLoadFactor = GetParam();
938 propout() << std::make_pair( "load_factor", s_nLoadFactor );
939 Set_DelOdd::run_test<Set>();
943 void run_test_extract(size_t pass_count = s_nPassCount)
945 s_nLoadFactor = GetParam();
946 propout() << std::make_pair( "load_factor", s_nLoadFactor );
947 Set_DelOdd::run_test_extract<Set>(pass_count);
950 static std::vector<size_t> get_load_factors();