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>
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 size mismatch!!!");
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<key_thread>
92 bool operator()( key_thread const& k1, key_thread const& k2 ) const
94 if ( k1.nKey <= k2.nKey )
95 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
101 struct hash<key_thread>
103 typedef size_t result_type;
104 typedef key_thread argument_type;
106 size_t operator()( key_thread const& k ) const
108 return std::hash<size_t>()(k.nKey);
110 size_t operator()( size_t k ) const
112 return std::hash<size_t>()(k);
116 class Map_Del3: public cds_test::stress_fixture
119 static size_t s_nInsThreadCount; // insert thread count
120 static size_t s_nDelThreadCount; // delete thread count
121 static size_t s_nExtractThreadCount; // extract thread count
122 static size_t s_nMapSize; // max map size
123 static size_t s_nMaxLoadFactor; // maximum load factor
124 static size_t s_nInsertPassCount;
125 static size_t s_nFindThreadCount; // find thread count
127 static size_t s_nCuckooInitialSize; // initial size for CuckooMap
128 static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
129 static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
131 static size_t s_nFeldmanMap_HeadBits;
132 static size_t s_nFeldmanMap_ArrayBits;
134 static size_t s_nLoadFactor; // current load factor
136 static std::vector<size_t> m_arrElements;
138 static void SetUpTestCase();
139 static void TearDownTestCase();
141 template <typename Pred>
142 static void prepare_array( std::vector<size_t>& arr, Pred pred )
144 arr.reserve( m_arrElements.size());
145 for ( auto el : m_arrElements ) {
149 arr.resize( arr.size());
150 shuffle( arr.begin(), arr.end());
154 typedef key_thread key_type;
155 typedef size_t value_type;
156 typedef std::pair<key_type const, value_type> pair_type;
158 atomics::atomic<size_t> m_nInsThreadCount;
167 // Inserts keys from [0..N)
169 class Inserter: public cds_test::thread
171 typedef cds_test::thread base_class;
176 template <typename Q>
177 void operator()( bool /*bNew*/, Q const& ) const
180 template <typename Q, typename V>
181 void operator()( bool /*bNew*/, Q const&, V& ) const
185 template <typename Q>
186 void operator()( Q&, Q*) const
192 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
193 for ( size_t i = 0; i < m_arr.size(); ++i ) {
194 if ( m_Map.insert( key_type( m_arr[i], id())))
195 ++m_nInsertInitSuccess;
197 ++m_nInsertInitFailed;
202 size_t m_nInsertSuccess = 0;
203 size_t m_nInsertFailed = 0;
204 size_t m_nInsertInitSuccess = 0;
205 size_t m_nInsertInitFailed = 0;
207 std::vector<size_t> m_arr;
210 Inserter( cds_test::thread_pool& pool, Map& map )
211 : base_class( pool, inserter_thread )
217 Inserter( Inserter& src )
224 virtual thread * clone()
226 return new Inserter( *this );
232 Map_Del3& fixture = pool().template fixture<Map_Del3>();
236 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
239 for ( auto el : m_arr ) {
241 if ( rMap.insert( key_type( el, id())))
250 for ( auto el : m_arr ) {
254 std::tie( success, inserted ) = rMap.update( key_type( el, id()), f );
255 if ( success && inserted )
264 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
270 bool operator()( key_type const& k1, key_type const& k2 ) const
272 return k1.nKey == k2.nKey;
274 bool operator()( size_t k1, key_type const& k2 ) const
276 return k1 == k2.nKey;
278 bool operator()( key_type const& k1, size_t k2 ) const
280 return k1.nKey == k2;
285 bool operator()( key_type const& k1, key_type const& k2 ) const
287 return k1.nKey < k2.nKey;
289 bool operator()( size_t k1, key_type const& k2 ) const
293 bool operator()( key_type const& k1, size_t k2 ) const
298 typedef key_equal equal_to;
301 // Deletes odd keys from [0..N)
303 class Deleter: public cds_test::thread
305 typedef cds_test::thread base_class;
310 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
314 size_t m_nDeleteSuccess = 0;
315 size_t m_nDeleteFailed = 0;
317 std::vector<size_t> m_arr;
320 Deleter( cds_test::thread_pool& pool, Map& map )
321 : base_class( pool, deleter_thread )
327 Deleter( Deleter& src )
334 virtual thread * clone()
336 return new Deleter( *this );
343 Map_Del3& fixture = pool().template fixture<Map_Del3>();
344 size_t const nInsThreadCount = s_nInsThreadCount;
348 for ( auto el: m_arr ) {
349 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
350 if ( rMap.erase( key_type( el, k )))
358 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
359 for ( auto el: m_arr ) {
360 if ( rMap.erase( key_type( el, k )))
367 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
373 // Deletes odd keys from [0..N)
374 template <class GC, class Map >
375 class Extractor: public cds_test::thread
377 typedef cds_test::thread base_class;
382 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
386 size_t m_nDeleteSuccess = 0;
387 size_t m_nDeleteFailed = 0;
389 std::vector<size_t> m_arr;
392 Extractor( cds_test::thread_pool& pool, Map& map )
393 : base_class( pool, extractor_thread )
399 Extractor( Extractor& src )
406 virtual thread * clone()
408 return new Extractor( *this );
415 typename Map::guarded_ptr gp;
416 Map_Del3& fixture = pool().template fixture<Map_Del3>();
417 size_t const nInsThreadCount = s_nInsThreadCount;
421 for ( auto el : m_arr ) {
422 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
423 gp = rMap.extract( key_type( el, k ));
433 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
434 for ( auto el: m_arr ) {
435 gp = rMap.extract( key_type( el, k ));
444 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
450 template <class RCU, class Map >
451 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
453 typedef cds_test::thread base_class;
458 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
462 size_t m_nDeleteSuccess = 0;
463 size_t m_nDeleteFailed = 0;
465 std::vector<size_t> m_arr;
468 Extractor( cds_test::thread_pool& pool, Map& map )
469 : base_class( pool, extractor_thread )
475 Extractor( Extractor& src )
482 virtual thread * clone()
484 return new Extractor( *this );
490 Map_Del3& fixture = pool().template fixture<Map_Del3>();
492 typename Map::exempt_ptr xp;
493 size_t const nInsThreadCount = s_nInsThreadCount;
497 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
498 for ( auto el: m_arr ) {
499 if ( Map::c_bExtractLockExternal ) {
500 typename Map::rcu_lock l;
501 xp = rMap.extract( key_type( el, k ));
508 xp = rMap.extract( key_type( el, k ));
519 for ( auto el : m_arr ) {
520 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
521 if ( Map::c_bExtractLockExternal ) {
522 typename Map::rcu_lock l;
523 xp = rMap.extract( key_type( el, k ));
530 xp = rMap.extract( key_type( el, k ));
540 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
548 class Observer: public cds_test::thread
550 typedef cds_test::thread base_class;
554 size_t m_nFindEvenSuccess = 0;
555 size_t m_nFindEvenFailed = 0;
556 size_t m_nFindOddSuccess = 0;
557 size_t m_nFindOddFailed = 0;
560 Observer( cds_test::thread_pool& pool, Map& map )
561 : base_class( pool, find_thread )
565 Observer( Observer& src )
570 virtual thread * clone()
572 return new Observer( *this );
578 Map_Del3& fixture = pool().template fixture<Map_Del3>();
579 std::vector<size_t> const& arr = m_arrElements;
580 size_t const nInsThreadCount = s_nInsThreadCount;
583 for ( size_t key : arr ) {
585 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
586 if ( map.contains( key_thread( key, k )))
593 // even keys MUST be in the map
594 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
595 if ( map.contains( key_thread( key, k )))
596 ++m_nFindEvenSuccess;
602 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
608 void do_test( Map& testMap )
610 typedef Inserter<Map> insert_thread;
611 typedef Deleter<Map> delete_thread;
612 typedef Observer<Map> observer_thread;
614 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
616 cds_test::thread_pool& pool = get_pool();
617 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
618 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
619 if ( s_nFindThreadCount )
620 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
622 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
623 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
624 << std::make_pair( "find_thread_count", s_nFindThreadCount )
625 << std::make_pair( "map_size", s_nMapSize )
626 << std::make_pair( "pass_count", s_nInsertPassCount );
628 std::chrono::milliseconds duration = pool.run();
630 propout() << std::make_pair( "duration", duration );
632 size_t nInsertInitFailed = 0;
633 size_t nInsertInitSuccess = 0;
634 size_t nInsertSuccess = 0;
635 size_t nInsertFailed = 0;
636 size_t nDeleteSuccess = 0;
637 size_t nDeleteFailed = 0;
639 size_t nFindEvenSuccess = 0;
640 size_t nFindEvenFailed = 0;
641 size_t nFindOddSuccess = 0;
642 size_t nFindOddFailed = 0;
644 for ( size_t i = 0; i < pool.size(); ++i ) {
645 cds_test::thread& thr = pool.get( i );
646 switch ( thr.type()) {
647 case inserter_thread:
649 insert_thread& inserter = static_cast<insert_thread&>( thr );
650 nInsertSuccess += inserter.m_nInsertSuccess;
651 nInsertFailed += inserter.m_nInsertFailed;
652 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
653 nInsertInitFailed += inserter.m_nInsertInitFailed;
658 delete_thread& deleter = static_cast<delete_thread&>( thr );
659 nDeleteSuccess += deleter.m_nDeleteSuccess;
660 nDeleteFailed += deleter.m_nDeleteFailed;
665 observer_thread& observer = static_cast<observer_thread&>( thr );
666 nFindEvenSuccess = observer.m_nFindEvenSuccess;
667 nFindEvenFailed = observer.m_nFindEvenFailed;
668 nFindOddSuccess = observer.m_nFindOddSuccess;
669 nFindOddFailed = observer.m_nFindOddFailed;
675 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
677 EXPECT_EQ( nInsertInitFailed, 0u );
678 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
679 EXPECT_EQ( nFindEvenFailed, 0u );
680 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
681 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
684 << std::make_pair( "insert_init_success", nInsertInitSuccess )
685 << std::make_pair( "insert_init_failed", nInsertInitFailed )
686 << std::make_pair( "insert_success", nInsertSuccess )
687 << std::make_pair( "insert_failed", nInsertFailed )
688 << std::make_pair( "delete_success", nDeleteSuccess )
689 << std::make_pair( "delete_failed", nDeleteFailed )
690 << std::make_pair( "find_even_success", nFindEvenSuccess )
691 << std::make_pair( "find_even_failed", nFindEvenFailed )
692 << std::make_pair( "find_odd_success", nFindOddSuccess )
693 << std::make_pair( "find_odd_failed", nFindOddFailed );
695 DEBUG(analyze( testMap ));
699 void do_test_extract( Map& testMap )
701 typedef Inserter<Map> insert_thread;
702 typedef Deleter<Map> delete_thread;
703 typedef Extractor< typename Map::gc, Map > extract_thread;
704 typedef Observer<Map> observer_thread;
706 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
708 cds_test::thread_pool& pool = get_pool();
709 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
710 if ( s_nDelThreadCount )
711 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
712 if ( s_nExtractThreadCount )
713 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
714 if ( s_nFindThreadCount )
715 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
717 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
718 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
719 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
720 << std::make_pair( "find_thread_count", s_nFindThreadCount )
721 << std::make_pair( "map_size", s_nMapSize )
722 << std::make_pair( "pass_count", s_nInsertPassCount );
724 std::chrono::milliseconds duration = pool.run();
726 propout() << std::make_pair( "duration", duration );
728 size_t nInsertInitFailed = 0;
729 size_t nInsertInitSuccess = 0;
730 size_t nInsertSuccess = 0;
731 size_t nInsertFailed = 0;
732 size_t nDeleteSuccess = 0;
733 size_t nDeleteFailed = 0;
734 size_t nExtractSuccess = 0;
735 size_t nExtractFailed = 0;
737 size_t nFindEvenSuccess = 0;
738 size_t nFindEvenFailed = 0;
739 size_t nFindOddSuccess = 0;
740 size_t nFindOddFailed = 0;
742 for ( size_t i = 0; i < pool.size(); ++i ) {
743 cds_test::thread& thr = pool.get( i );
744 switch ( thr.type()) {
745 case inserter_thread:
747 insert_thread& inserter = static_cast<insert_thread&>(thr);
748 nInsertSuccess += inserter.m_nInsertSuccess;
749 nInsertFailed += inserter.m_nInsertFailed;
750 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
751 nInsertInitFailed += inserter.m_nInsertInitFailed;
756 delete_thread& deleter = static_cast<delete_thread&>(thr);
757 nDeleteSuccess += deleter.m_nDeleteSuccess;
758 nDeleteFailed += deleter.m_nDeleteFailed;
761 case extractor_thread:
763 extract_thread& extractor = static_cast<extract_thread&>(thr);
764 nExtractSuccess += extractor.m_nDeleteSuccess;
765 nExtractFailed += extractor.m_nDeleteFailed;
770 observer_thread& observer = static_cast<observer_thread&>( thr );
771 nFindEvenSuccess = observer.m_nFindEvenSuccess;
772 nFindEvenFailed = observer.m_nFindEvenFailed;
773 nFindOddSuccess = observer.m_nFindOddSuccess;
774 nFindOddFailed = observer.m_nFindOddFailed;
782 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
784 EXPECT_EQ( nInsertInitFailed, 0u );
785 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
786 EXPECT_EQ( nFindEvenFailed, 0u );
787 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
788 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
791 << std::make_pair( "insert_init_success", nInsertInitSuccess )
792 << std::make_pair( "insert_init_failed", nInsertInitFailed )
793 << std::make_pair( "insert_success", nInsertSuccess )
794 << std::make_pair( "insert_failed", nInsertFailed )
795 << std::make_pair( "delete_success", nDeleteSuccess )
796 << std::make_pair( "delete_failed", nDeleteFailed )
797 << std::make_pair( "extract_success", nExtractSuccess )
798 << std::make_pair( "extract_failed", nExtractFailed )
799 << std::make_pair( "find_even_success", nFindEvenSuccess )
800 << std::make_pair( "find_even_failed", nFindEvenFailed )
801 << std::make_pair( "find_odd_success", nFindOddSuccess )
802 << std::make_pair( "find_odd_failed", nFindOddFailed );
804 DEBUG(analyze( testMap ));
808 void analyze( Map& testMap )
810 // All even keys must be in the map
812 for ( size_t n = 0; n < s_nMapSize; n +=4 ) {
813 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
814 EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
819 print_stat( propout(), testMap );
821 check_before_cleanup( testMap );
823 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
825 additional_check( testMap );
826 additional_cleanup( testMap );
830 void run_test_extract()
832 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
834 size_t nMapSize = s_nMapSize;
835 s_nMapSize *= s_nInsThreadCount;
837 Map testMap( *this );
839 s_nMapSize = nMapSize;
840 do_test_extract( testMap );
846 size_t nMapSize = s_nMapSize;
847 s_nMapSize *= s_nInsThreadCount;
849 Map testMap( *this );
851 s_nMapSize = nMapSize;
859 class Map_Del3_LF: public Map_Del3
860 , public ::testing::WithParamInterface<size_t>
866 s_nLoadFactor = GetParam();
867 propout() << std::make_pair( "load_factor", s_nLoadFactor );
868 Map_Del3::run_test<Map>();
872 void run_test_extract()
874 s_nLoadFactor = GetParam();
875 propout() << std::make_pair( "load_factor", s_nLoadFactor );
876 Map_Del3::run_test_extract<Map>();
879 static std::vector<size_t> get_load_factors();