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.
31 #include "../../../misc/common.h"
33 #include <cds/os/topology.h>
43 key_thread( size_t key, size_t threadNo )
44 : nKey( static_cast<uint32_t>(key))
45 , nThread( static_cast<uint16_t>(threadNo))
54 static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
56 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
59 struct cmp<key_thread> {
60 int operator ()(key_thread const& k1, key_thread const& k2) const
62 if ( k1.nKey < k2.nKey )
64 if ( k1.nKey > k2.nKey )
66 if ( k1.nThread < k2.nThread )
68 if ( k1.nThread > k2.nThread )
72 int operator ()(key_thread const& k1, size_t k2) const
80 int operator ()(size_t k1, key_thread const& k2) const
91 struct less<set::key_thread>
93 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
95 if ( k1.nKey <= k2.nKey )
96 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
102 struct hash<set::key_thread>
104 typedef size_t result_type;
105 typedef set::key_thread argument_type;
107 size_t operator()( set::key_thread const& k ) const
109 return std::hash<size_t>()(k.nKey);
112 size_t operator()( size_t k ) const
114 return std::hash<size_t>()(k);
119 class Set_Del3: public cds_test::stress_fixture
122 static size_t s_nSetSize; // max set size
123 static size_t s_nInsThreadCount; // insert thread count
124 static size_t s_nDelThreadCount; // delete thread count
125 static size_t s_nExtractThreadCount; // extract thread count
126 static size_t s_nMaxLoadFactor; // maximum load factor
127 static size_t s_nPassCount;
128 static size_t s_nFeldmanPassCount;
130 static size_t s_nInsertPassCount;
131 static size_t s_nDeletePassCount;
132 static size_t s_nFindPassCount;
133 static size_t s_nFindThreadCount; // find thread count
135 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
136 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
137 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
139 static size_t s_nFeldmanSet_HeadBits;
140 static size_t s_nFeldmanSet_ArrayBits;
142 static size_t s_nLoadFactor;
144 static std::vector<size_t> m_arrData;
146 static void SetUpTestCase();
147 static void TearDownTestCase();
149 template <typename Pred>
150 static void prepare_array( std::vector<size_t>& arr, Pred pred )
152 arr.reserve( m_arrData.size());
153 for ( auto el : m_arrData ) {
157 arr.resize( arr.size());
158 shuffle( arr.begin(), arr.end());
162 typedef key_thread key_type;
163 typedef size_t value_type;
173 // Inserts keys from [0..N)
175 class Inserter: public cds_test::thread
177 typedef cds_test::thread base_class;
180 struct update_functor
182 template <typename Q>
183 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
186 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
192 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
196 size_t m_nInsertSuccess = 0;
197 size_t m_nInsertFailed = 0;
198 size_t m_nInsertInitSuccess = 0;
199 size_t m_nInsertInitFailed = 0;
201 std::vector<size_t> m_arr;
204 Inserter(cds_test::thread_pool &pool, Set &set)
205 : base_class(pool, inserter_thread), m_Set(set) {
209 Inserter(Inserter &src) : base_class(src), m_Set(src.m_Set) {
213 virtual thread * clone()
215 return new Inserter( *this );
221 for (size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass) {
224 for (auto el : m_arrData) {
225 if (rSet.insert(key_type(el, 0)))
232 for (auto el : m_arrData) {
235 std::tie(success, inserted) =
236 rSet.update(key_type(el, 0), update_functor());
237 if (success && inserted)
248 bool operator()( key_type const& k1, key_type const& k2 ) const
250 return k1.nKey == k2.nKey;
252 bool operator()( size_t k1, key_type const& k2 ) const
254 return k1 == k2.nKey;
256 bool operator()( key_type const& k1, size_t k2 ) const
258 return k1.nKey == k2;
260 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
262 return operator()( k1.key, k2.key );
264 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
266 return operator()( k1.key, k2 );
268 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
270 return operator()( k1, k2.key );
272 bool operator ()( key_value_pair const& k1, size_t k2 ) const
274 return operator()( k1.key, k2 );
276 bool operator ()( size_t k1, key_value_pair const& k2 ) const
278 return operator()( k1, k2.key );
283 bool operator()( key_type const& k1, key_type const& k2 ) const
285 return k1.nKey < k2.nKey;
287 bool operator()( size_t k1, key_type const& k2 ) const
291 bool operator()( key_type const& k1, size_t k2 ) const
295 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
297 return operator()( k1.key, k2.key );
299 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
301 return operator()( k1.key, k2 );
303 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
305 return operator()( k1, k2.key );
307 bool operator ()( key_value_pair const& k1, size_t k2 ) const
309 return operator()( k1.key, k2 );
311 bool operator ()( size_t k1, key_value_pair const& k2 ) const
313 return operator()( k1, k2.key );
316 typedef key_equal equal_to;
319 // Deletes odd keys from [0..N)
321 class Deleter: public cds_test::thread
323 typedef cds_test::thread base_class;
328 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
332 size_t m_nDeleteSuccess = 0;
333 size_t m_nDeleteFailed = 0;
335 std::vector<size_t> m_arr;
338 Deleter( cds_test::thread_pool& pool, Set& set )
339 : base_class( pool, deleter_thread )
343 Deleter( Deleter& src )
348 virtual thread * clone()
350 return new Deleter( *this );
353 template <typename SetType, bool>
355 static bool erase( SetType& s, size_t key, size_t /*thread*/)
357 return s.erase_with( key, key_less());
361 template <typename SetType>
362 struct eraser<SetType, true> {
363 static bool erase(SetType& s, size_t key, size_t thread)
365 return s.erase( key_type(key, thread));
369 virtual void test() {
371 for (auto el : m_arrData) {
373 if (rSet.erase(key_type(el, 0)))
382 // Extracts odd 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 )
407 Extractor( Extractor& src )
413 virtual thread * clone()
415 return new Extractor( *this );
418 virtual void test() {
420 typename Set::guarded_ptr gp;
422 for (auto el : m_arrData) {
424 gp = rSet.extract(key_type(el, 0));
435 template <typename RCU, class Set>
436 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
438 typedef cds_test::thread base_class;
440 std::vector<size_t> m_arr;
444 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
448 size_t m_nExtractSuccess = 0;
449 size_t m_nExtractFailed = 0;
452 Extractor( cds_test::thread_pool& pool, Set& set )
453 : base_class( pool, extractor_thread )
457 Extractor( Extractor& src )
462 virtual thread * clone()
464 return new Extractor( *this );
470 typename Set::exempt_ptr xp;
472 Set_Del3& fixture = pool().template fixture<Set_Del3>();
473 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
477 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
478 for ( auto el : m_arr ) {
479 if ( Set::c_bExtractLockExternal ) {
480 typename Set::rcu_lock l;
481 xp = rSet.extract( key_type( el, k ));
488 xp = rSet.extract( key_type( el, k ));
499 for ( auto el : m_arr ) {
500 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
501 if ( Set::c_bExtractLockExternal ) {
502 typename Set::rcu_lock l;
503 xp = rSet.extract( key_type( el, k ));
510 xp = rSet.extract( key_type( el, k ));
528 class Observer: public cds_test::thread
530 typedef cds_test::thread base_class;
534 size_t m_nFindEvenSuccess = 0;
535 size_t m_nFindEvenFailed = 0;
536 size_t m_nFindOddSuccess = 0;
537 size_t m_nFindOddFailed = 0;
540 Observer( cds_test::thread_pool& pool, Set& set )
541 : base_class( pool, find_thread )
545 Observer( Observer& src )
550 virtual thread * clone()
552 return new Observer( *this );
555 virtual void test() {
557 std::vector<size_t> const &arr = m_arrData;
559 for (size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass) {
560 for (size_t key : arr) {
562 if (set.contains(key_thread(key, 0)))
567 // even keys MUST be in the map
568 if (set.contains(key_thread(key, 0)))
569 ++m_nFindEvenSuccess;
580 void do_test_with( Set& testSet )
582 typedef Inserter<Set> insert_thread;
583 typedef Deleter<Set> delete_thread;
584 typedef Observer<Set> observer_thread;
586 cds_test::thread_pool& pool = get_pool();
587 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
588 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
589 if ( s_nFindThreadCount )
590 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
592 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
593 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
594 << std::make_pair( "find_thread_count", s_nFindThreadCount )
595 << std::make_pair( "set_size", s_nSetSize )
596 << std::make_pair( "pass_count", s_nInsertPassCount );
600 size_t nInsertInitFailed = 0;
601 size_t nInsertInitSuccess = 0;
602 size_t nInsertSuccess = 0;
603 size_t nInsertFailed = 0;
604 size_t nDeleteSuccess = 0;
605 size_t nDeleteFailed = 0;
607 size_t nFindEvenSuccess = 0;
608 size_t nFindEvenFailed = 0;
609 size_t nFindOddSuccess = 0;
610 size_t nFindOddFailed = 0;
612 for ( size_t i = 0; i < pool.size(); ++i ) {
613 cds_test::thread& thr = pool.get( i );
614 switch ( thr.type()) {
615 case inserter_thread:
617 insert_thread& inserter = static_cast<insert_thread&>(thr);
618 nInsertSuccess += inserter.m_nInsertSuccess;
619 nInsertFailed += inserter.m_nInsertFailed;
620 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
621 nInsertInitFailed += inserter.m_nInsertInitFailed;
626 delete_thread& deleter = static_cast<delete_thread&>(thr);
627 nDeleteSuccess += deleter.m_nDeleteSuccess;
628 nDeleteFailed += deleter.m_nDeleteFailed;
633 observer_thread& observer = static_cast<observer_thread&>( thr );
634 nFindEvenSuccess = observer.m_nFindEvenSuccess;
635 nFindEvenFailed = observer.m_nFindEvenFailed;
636 nFindOddSuccess = observer.m_nFindOddSuccess;
637 nFindOddFailed = observer.m_nFindOddFailed;
645 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
647 EXPECT_EQ( nInsertInitFailed, 0u );
648 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
649 EXPECT_EQ( nFindEvenFailed, 0u );
650 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
651 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
654 << std::make_pair( "insert_init_success", nInsertInitSuccess )
655 << std::make_pair( "insert_init_failed", nInsertInitFailed )
656 << std::make_pair( "insert_success", nInsertSuccess )
657 << std::make_pair( "insert_failed", nInsertFailed )
658 << std::make_pair( "delete_success", nDeleteSuccess )
659 << std::make_pair( "delete_failed", nDeleteFailed )
660 << std::make_pair( "find_even_success", nFindEvenSuccess )
661 << std::make_pair( "find_even_failed", nFindEvenFailed )
662 << std::make_pair( "find_odd_success", nFindOddSuccess )
663 << std::make_pair( "find_odd_failed", nFindOddFailed );
667 void do_test_extract_with(Set &testSet, size_t pass_count) {
668 typedef Inserter<Set> insert_thread;
669 typedef Deleter<Set> delete_thread;
670 typedef Extractor<typename Set::gc, Set> extract_thread;
671 typedef Observer<Set> observer_thread;
673 size_t nInsertSuccess = 0;
674 size_t nInsertFailed = 0;
675 size_t nDeleteSuccess = 0;
676 size_t nDeleteFailed = 0;
677 size_t nExtractSuccess = 0;
678 size_t nExtractFailed = 0;
679 size_t nFindEvenSuccess = 0;
680 size_t nFindEvenFailed = 0;
681 size_t nFindOddSuccess = 0;
682 size_t nFindOddFailed = 0;
684 auto reset_stat = [&]() {
691 nFindEvenSuccess = 0;
697 auto insert_func = [&]() {
698 for (auto el : m_arrData) {
699 if (testSet.insert(key_type(el, 0)))
706 auto delete_func = [&]() {
707 for (auto el : m_arrData) {
709 if (testSet.erase(key_type(el, 0)))
717 auto extract_func = [&]() {
718 for (auto el : m_arrData) {
720 auto gp = testSet.extract(key_type(el, 0));
730 auto find_func = [&]() {
731 for (size_t el : m_arrData) {
733 if (testSet.contains(key_thread(el, 0)))
738 // even keys MUST be in the map
739 if (testSet.contains(key_thread(el, 0)))
747 auto test_func = [&](size_t count, std::function<void()> func) {
748 for (size_t i = 0; i < count; ++i) {
753 size_t const nInitialOddKeys = s_nSetSize * 3 / 4;
754 size_t const nInitialEvenKeys = s_nSetSize / 4;
755 for (size_t nPass = 0; nPass < pass_count; ++nPass) {
756 // Start with an empty set.
760 test_func(s_nInsertPassCount, insert_func);
761 EXPECT_EQ(nInsertSuccess, s_nSetSize);
764 test_func(s_nFindPassCount, find_func);
765 EXPECT_EQ(nFindEvenFailed, 0u);
766 EXPECT_EQ(nFindOddFailed, 0u);
769 test_func(s_nDeletePassCount, delete_func);
770 EXPECT_EQ(nDeleteSuccess, nInitialOddKeys);
773 test_func(s_nInsertPassCount, insert_func);
774 EXPECT_EQ(nInsertSuccess, nInitialOddKeys);
777 test_func(s_nDeletePassCount, extract_func);
778 EXPECT_EQ(nExtractSuccess, nInitialOddKeys);
781 test_func(s_nFindPassCount, find_func);
782 EXPECT_EQ(nFindEvenFailed, 0u);
783 EXPECT_EQ(nFindOddSuccess, 0u);
786 // std::chrono::duration<double> time_elapsed;
787 // std::chrono::duration<double> time_diff;
788 // std::chrono::time_point<std::chrono::steady_clock>
790 // std::chrono::time_point<std::chrono::steady_clock>
792 // time_start = std::chrono::steady_clock::now();
793 // time_end = std::chrono::steady_clock::now();
794 // time_diff = time_end - time_start;
795 // time_elapsed = time_diff;
796 // std::cout << "Time elapsed: " << time_elapsed.count() <<
800 template <typename Set>
801 void analyze( Set& testSet )
803 // All even keys must be in the set
805 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
806 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
807 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
812 check_before_clear( testSet );
815 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
817 additional_check( testSet );
818 print_stat( propout(), testSet );
819 additional_cleanup( testSet );
825 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
827 Set testSet( *this );
828 do_test_with( testSet );
833 void run_test_extract(size_t pass_count = s_nPassCount)
835 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
837 Set testSet( *this );
838 do_test_extract_with( testSet, pass_count);
845 class Set_Del3_LF: public Set_Del3
846 , public ::testing::WithParamInterface<size_t>
852 s_nLoadFactor = GetParam();
853 propout() << std::make_pair( "load_factor", s_nLoadFactor );
854 Set_Del3::run_test<Set>();
858 void run_test_extract(size_t pass_count = s_nPassCount)
860 s_nLoadFactor = GetParam();
861 propout() << std::make_pair( "load_factor", s_nLoadFactor );
862 Set_Del3::run_test_extract<Set>(pass_count);
865 static std::vector<size_t> get_load_factors();