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
128 static size_t s_nPassCount;
129 static size_t s_nFeldmanPassCount;
130 static size_t s_nInsertPassCount;
131 static size_t s_nDeletePassCount;
132 static size_t s_nFindPassCount;
134 static size_t s_nFindThreadCount; // find thread count
136 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
137 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
138 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
140 static size_t s_nFeldmanSet_HeadBits;
141 static size_t s_nFeldmanSet_ArrayBits;
143 static size_t s_nLoadFactor;
145 static std::vector<size_t> m_arrData;
147 static void SetUpTestCase();
148 static void TearDownTestCase();
150 template <typename Pred>
151 static void prepare_array( std::vector<size_t>& arr, Pred pred )
153 arr.reserve( m_arrData.size());
154 for ( auto el : m_arrData ) {
158 arr.resize( arr.size());
159 shuffle( arr.begin(), arr.end());
163 typedef key_thread key_type;
164 typedef size_t value_type;
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; } );
197 size_t m_nInsertSuccess = 0;
198 size_t m_nInsertFailed = 0;
199 size_t m_nInsertInitSuccess = 0;
200 size_t m_nInsertInitFailed = 0;
202 std::vector<size_t> m_arr;
205 Inserter(cds_test::thread_pool &pool, Set &set)
206 : base_class(pool, inserter_thread), m_Set(set) {
210 Inserter(Inserter &src) : base_class(src), m_Set(src.m_Set) {
214 virtual thread * clone()
216 return new Inserter( *this );
222 for (size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass) {
225 for (auto el : m_arrData) {
226 if (rSet.insert(key_type(el, 0)))
233 for (auto el : m_arrData) {
236 std::tie(success, inserted) =
237 rSet.update(key_type(el, 0), update_functor());
238 if (success && inserted)
249 bool operator()( key_type const& k1, key_type const& k2 ) const
251 return k1.nKey == k2.nKey;
253 bool operator()( size_t k1, key_type const& k2 ) const
255 return k1 == k2.nKey;
257 bool operator()( key_type const& k1, size_t k2 ) const
259 return k1.nKey == k2;
261 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
263 return operator()( k1.key, k2.key );
265 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
267 return operator()( k1.key, k2 );
269 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
271 return operator()( k1, k2.key );
273 bool operator ()( key_value_pair const& k1, size_t k2 ) const
275 return operator()( k1.key, k2 );
277 bool operator ()( size_t k1, key_value_pair const& k2 ) const
279 return operator()( k1, k2.key );
284 bool operator()( key_type const& k1, key_type const& k2 ) const
286 return k1.nKey < k2.nKey;
288 bool operator()( size_t k1, key_type const& k2 ) const
292 bool operator()( key_type const& k1, size_t k2 ) const
296 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
298 return operator()( k1.key, k2.key );
300 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
302 return operator()( k1.key, k2 );
304 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
306 return operator()( k1, k2.key );
308 bool operator ()( key_value_pair const& k1, size_t k2 ) const
310 return operator()( k1.key, k2 );
312 bool operator ()( size_t k1, key_value_pair const& k2 ) const
314 return operator()( k1, k2.key );
317 typedef key_equal equal_to;
320 // Deletes odd keys from [0..N)
322 class Deleter: public cds_test::thread
324 typedef cds_test::thread base_class;
329 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
333 size_t m_nDeleteSuccess = 0;
334 size_t m_nDeleteFailed = 0;
336 std::vector<size_t> m_arr;
339 Deleter( cds_test::thread_pool& pool, Set& set )
340 : base_class( pool, deleter_thread )
344 Deleter( Deleter& src )
349 virtual thread * clone()
351 return new Deleter( *this );
354 template <typename SetType, bool>
356 static bool erase( SetType& s, size_t key, size_t /*thread*/)
358 return s.erase_with( key, key_less());
362 template <typename SetType>
363 struct eraser<SetType, true> {
364 static bool erase(SetType& s, size_t key, size_t thread)
366 return s.erase( key_type(key, thread));
370 virtual void test() {
372 for (auto el : m_arrData) {
374 if (rSet.erase(key_type(el, 0)))
383 // Extracts odd keys from [0..N)
384 template <typename GC, class Set>
385 class Extractor: public cds_test::thread
387 typedef cds_test::thread base_class;
390 std::vector<size_t> m_arr;
394 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
398 size_t m_nExtractSuccess = 0;
399 size_t m_nExtractFailed = 0;
402 Extractor( cds_test::thread_pool& pool, Set& set )
403 : base_class( pool, extractor_thread )
408 Extractor( Extractor& src )
414 virtual thread * clone()
416 return new Extractor( *this );
419 virtual void test() {
421 typename Set::guarded_ptr gp;
423 for (auto el : m_arrData) {
425 gp = rSet.extract(key_type(el, 0));
436 template <typename RCU, class Set>
437 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
439 typedef cds_test::thread base_class;
441 std::vector<size_t> m_arr;
445 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
449 size_t m_nExtractSuccess = 0;
450 size_t m_nExtractFailed = 0;
453 Extractor( cds_test::thread_pool& pool, Set& set )
454 : base_class( pool, extractor_thread )
458 Extractor( Extractor& src )
463 virtual thread * clone()
465 return new Extractor( *this );
471 typename Set::exempt_ptr xp;
473 Set_Del3& fixture = pool().template fixture<Set_Del3>();
474 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
478 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
479 for ( auto el : m_arr ) {
480 if ( Set::c_bExtractLockExternal ) {
481 typename Set::rcu_lock l;
482 xp = rSet.extract( key_type( el, k ));
489 xp = rSet.extract( key_type( el, k ));
500 for ( auto el : m_arr ) {
501 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
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 ));
529 class Observer: public cds_test::thread
531 typedef cds_test::thread base_class;
535 size_t m_nFindEvenSuccess = 0;
536 size_t m_nFindEvenFailed = 0;
537 size_t m_nFindOddSuccess = 0;
538 size_t m_nFindOddFailed = 0;
541 Observer( cds_test::thread_pool& pool, Set& set )
542 : base_class( pool, find_thread )
546 Observer( Observer& src )
551 virtual thread * clone()
553 return new Observer( *this );
556 virtual void test() {
558 std::vector<size_t> const &arr = m_arrData;
560 for (size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass) {
561 for (size_t key : arr) {
563 if (set.contains(key_thread(key, 0)))
568 // even keys MUST be in the map
569 if (set.contains(key_thread(key, 0)))
570 ++m_nFindEvenSuccess;
581 void do_test_with( Set& testSet )
583 typedef Inserter<Set> insert_thread;
584 typedef Deleter<Set> delete_thread;
585 typedef Observer<Set> observer_thread;
587 cds_test::thread_pool& pool = get_pool();
588 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
589 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
590 if ( s_nFindThreadCount )
591 pool.add( new observer_thread( pool, testSet ), s_nFindThreadCount );
593 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
594 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
595 << std::make_pair( "find_thread_count", s_nFindThreadCount )
596 << std::make_pair( "set_size", s_nSetSize )
597 << std::make_pair( "pass_count", s_nInsertPassCount );
601 size_t nInsertInitFailed = 0;
602 size_t nInsertInitSuccess = 0;
603 size_t nInsertSuccess = 0;
604 size_t nInsertFailed = 0;
605 size_t nDeleteSuccess = 0;
606 size_t nDeleteFailed = 0;
608 size_t nFindEvenSuccess = 0;
609 size_t nFindEvenFailed = 0;
610 size_t nFindOddSuccess = 0;
611 size_t nFindOddFailed = 0;
613 for ( size_t i = 0; i < pool.size(); ++i ) {
614 cds_test::thread& thr = pool.get( i );
615 switch ( thr.type()) {
616 case inserter_thread:
618 insert_thread& inserter = static_cast<insert_thread&>(thr);
619 nInsertSuccess += inserter.m_nInsertSuccess;
620 nInsertFailed += inserter.m_nInsertFailed;
621 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
622 nInsertInitFailed += inserter.m_nInsertInitFailed;
627 delete_thread& deleter = static_cast<delete_thread&>(thr);
628 nDeleteSuccess += deleter.m_nDeleteSuccess;
629 nDeleteFailed += deleter.m_nDeleteFailed;
634 observer_thread& observer = static_cast<observer_thread&>( thr );
635 nFindEvenSuccess = observer.m_nFindEvenSuccess;
636 nFindEvenFailed = observer.m_nFindEvenFailed;
637 nFindOddSuccess = observer.m_nFindOddSuccess;
638 nFindOddFailed = observer.m_nFindOddFailed;
646 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) * 3 / 4;
648 EXPECT_EQ( nInsertInitFailed, 0u );
649 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
650 EXPECT_EQ( nFindEvenFailed, 0u );
651 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
652 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
655 << std::make_pair( "insert_init_success", nInsertInitSuccess )
656 << std::make_pair( "insert_init_failed", nInsertInitFailed )
657 << std::make_pair( "insert_success", nInsertSuccess )
658 << std::make_pair( "insert_failed", nInsertFailed )
659 << std::make_pair( "delete_success", nDeleteSuccess )
660 << std::make_pair( "delete_failed", nDeleteFailed )
661 << std::make_pair( "find_even_success", nFindEvenSuccess )
662 << std::make_pair( "find_even_failed", nFindEvenFailed )
663 << std::make_pair( "find_odd_success", nFindOddSuccess )
664 << std::make_pair( "find_odd_failed", nFindOddFailed );
668 void do_test_extract_with(Set &testSet, size_t pass_count) {
669 typedef Inserter<Set> insert_thread;
670 typedef Deleter<Set> delete_thread;
671 typedef Extractor<typename Set::gc, Set> extract_thread;
672 typedef Observer<Set> observer_thread;
674 size_t nInsertSuccess = 0;
675 size_t nInsertFailed = 0;
676 size_t nDeleteSuccess = 0;
677 size_t nDeleteFailed = 0;
678 size_t nExtractSuccess = 0;
679 size_t nExtractFailed = 0;
680 size_t nFindEvenSuccess = 0;
681 size_t nFindEvenFailed = 0;
682 size_t nFindOddSuccess = 0;
683 size_t nFindOddFailed = 0;
685 auto reset_stat = [&]() {
692 nFindEvenSuccess = 0;
698 auto insert_func = [&]() {
699 for (auto el : m_arrData) {
700 if (testSet.insert(key_type(el, 0)))
707 auto delete_func = [&]() {
708 for (auto el : m_arrData) {
710 if (testSet.erase(key_type(el, 0)))
718 auto extract_func = [&]() {
719 for (auto el : m_arrData) {
721 auto gp = testSet.extract(key_type(el, 0));
731 auto find_func = [&]() {
732 for (size_t el : m_arrData) {
734 if (testSet.contains(key_thread(el, 0)))
739 // even keys MUST be in the map
740 if (testSet.contains(key_thread(el, 0)))
748 auto test_func = [&](size_t count, std::function<void()> func) {
749 for (size_t i = 0; i < count; ++i) {
754 size_t const nInitialOddKeys = s_nSetSize * 3 / 4;
755 size_t const nInitialEvenKeys = s_nSetSize / 4;
756 for (size_t nPass = 0; nPass < pass_count; ++nPass) {
757 // Start with an empty set.
761 test_func(s_nInsertPassCount, insert_func);
762 EXPECT_EQ(nInsertSuccess, s_nSetSize);
765 test_func(s_nFindPassCount, find_func);
766 EXPECT_EQ(nFindEvenFailed, 0u);
767 EXPECT_EQ(nFindOddFailed, 0u);
770 test_func(s_nDeletePassCount, delete_func);
771 EXPECT_EQ(nDeleteSuccess, nInitialOddKeys);
774 test_func(s_nInsertPassCount, insert_func);
775 EXPECT_EQ(nInsertSuccess, nInitialOddKeys);
778 test_func(s_nDeletePassCount, extract_func);
779 EXPECT_EQ(nExtractSuccess, nInitialOddKeys);
782 test_func(s_nFindPassCount, find_func);
783 EXPECT_EQ(nFindEvenFailed, 0u);
784 EXPECT_EQ(nFindOddSuccess, 0u);
787 // std::chrono::duration<double> time_elapsed;
788 // std::chrono::duration<double> time_diff;
789 // std::chrono::time_point<std::chrono::steady_clock>
791 // std::chrono::time_point<std::chrono::steady_clock>
793 // time_start = std::chrono::steady_clock::now();
794 // time_end = std::chrono::steady_clock::now();
795 // time_diff = time_end - time_start;
796 // time_elapsed = time_diff;
797 // std::cout << "Time elapsed: " << time_elapsed.count() <<
801 template <typename Set>
802 void analyze( Set& testSet )
804 // All even keys must be in the set
806 for ( size_t n = 0; n < s_nSetSize; n +=4 ) {
807 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
808 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
813 check_before_clear( testSet );
816 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
818 additional_check( testSet );
819 print_stat( propout(), testSet );
820 additional_cleanup( testSet );
826 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
828 Set testSet( *this );
829 do_test_with( testSet );
834 void run_test_extract(size_t pass_count = s_nPassCount)
836 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
838 Set testSet( *this );
839 do_test_extract_with( testSet, pass_count);
846 class Set_Del3_LF: public Set_Del3
847 , public ::testing::WithParamInterface<size_t>
853 s_nLoadFactor = GetParam();
854 propout() << std::make_pair( "load_factor", s_nLoadFactor );
855 Set_Del3::run_test<Set>();
859 void run_test_extract(size_t pass_count = s_nPassCount)
861 s_nLoadFactor = GetParam();
862 propout() << std::make_pair( "load_factor", s_nLoadFactor );
863 Set_Del3::run_test_extract<Set>(pass_count);
866 static std::vector<size_t> get_load_factors();