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>
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 size mismatch!!!");
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<key_thread>
91 bool operator()( key_thread const& k1, key_thread const& k2 ) const
93 if ( k1.nKey <= k2.nKey )
94 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
100 struct hash<key_thread>
102 typedef size_t result_type;
103 typedef key_thread argument_type;
105 size_t operator()( key_thread const& k ) const
107 return std::hash<size_t>()(k.nKey);
109 size_t operator()( size_t k ) const
111 return std::hash<size_t>()(k);
115 class Map_DelOdd: public cds_test::stress_fixture
118 static size_t s_nInsThreadCount; // insert thread count
119 static size_t s_nDelThreadCount; // delete thread count
120 static size_t s_nExtractThreadCount; // extract thread count
121 static size_t s_nMapSize; // max map size
122 static size_t s_nMaxLoadFactor; // maximum load factor
123 static size_t s_nInsertPassCount;
124 static size_t s_nFindThreadCount; // find thread count
126 static size_t s_nCuckooInitialSize; // initial size for CuckooMap
127 static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
128 static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
130 static size_t s_nFeldmanMap_HeadBits;
131 static size_t s_nFeldmanMap_ArrayBits;
133 static size_t s_nLoadFactor; // current load factor
135 static std::vector<size_t> m_arrElements;
137 static void SetUpTestCase();
138 static void TearDownTestCase();
140 template <typename Pred>
141 static void prepare_array( std::vector<size_t>& arr, Pred pred )
143 arr.reserve( m_arrElements.size());
144 for ( auto el : m_arrElements ) {
148 arr.resize( arr.size());
149 shuffle( arr.begin(), arr.end());
153 typedef key_thread key_type;
154 typedef size_t value_type;
155 typedef std::pair<key_type const, value_type> pair_type;
157 atomics::atomic<size_t> m_nInsThreadCount;
166 // Inserts keys from [0..N)
168 class Inserter: public cds_test::thread
170 typedef cds_test::thread base_class;
175 template <typename Q>
176 void operator()( bool /*bNew*/, Q const& ) const
179 template <typename Q, typename V>
180 void operator()( bool /*bNew*/, Q const&, V& ) const
184 template <typename Q>
185 void operator()( Q&, Q*) const
191 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
192 for ( size_t i = 0; i < m_arr.size(); ++i ) {
193 if ( m_Map.insert( key_type( m_arr[i], id())))
194 ++m_nInsertInitSuccess;
196 ++m_nInsertInitFailed;
201 size_t m_nInsertSuccess = 0;
202 size_t m_nInsertFailed = 0;
203 size_t m_nInsertInitSuccess = 0;
204 size_t m_nInsertInitFailed = 0;
206 std::vector<size_t> m_arr;
209 Inserter( cds_test::thread_pool& pool, Map& map )
210 : base_class( pool, inserter_thread )
216 Inserter( Inserter& src )
223 virtual thread * clone()
225 return new Inserter( *this );
231 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
235 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
238 for ( auto el : m_arr ) {
240 if ( rMap.insert( key_type( el, id())))
249 for ( auto el : m_arr ) {
253 std::tie( success, inserted ) = rMap.update( key_type( el, id()), f );
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;
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
297 typedef key_equal equal_to;
300 // Deletes odd keys from [0..N)
302 class Deleter: public cds_test::thread
304 typedef cds_test::thread base_class;
309 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
313 size_t m_nDeleteSuccess = 0;
314 size_t m_nDeleteFailed = 0;
316 std::vector<size_t> m_arr;
319 Deleter( cds_test::thread_pool& pool, Map& map )
320 : base_class( pool, deleter_thread )
326 Deleter( Deleter& src )
333 virtual thread * clone()
335 return new Deleter( *this );
342 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
343 size_t const nInsThreadCount = s_nInsThreadCount;
347 for ( auto el: m_arr ) {
348 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
349 if ( rMap.erase( key_type( el, k )))
357 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
358 for ( auto el: m_arr ) {
359 if ( rMap.erase( key_type( el, k )))
366 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
372 // Deletes odd keys from [0..N)
373 template <class GC, class Map >
374 class Extractor: public cds_test::thread
376 typedef cds_test::thread base_class;
381 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
385 size_t m_nDeleteSuccess = 0;
386 size_t m_nDeleteFailed = 0;
388 std::vector<size_t> m_arr;
391 Extractor( cds_test::thread_pool& pool, Map& map )
392 : base_class( pool, extractor_thread )
398 Extractor( Extractor& src )
405 virtual thread * clone()
407 return new Extractor( *this );
414 typename Map::guarded_ptr gp;
415 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
416 size_t const nInsThreadCount = s_nInsThreadCount;
420 for ( auto el : m_arr ) {
421 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
422 gp = rMap.extract( key_type( el, k ));
432 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
433 for ( auto el: m_arr ) {
434 gp = rMap.extract( key_type( el, k ));
443 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
449 template <class RCU, class Map >
450 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
452 typedef cds_test::thread base_class;
457 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
461 size_t m_nDeleteSuccess = 0;
462 size_t m_nDeleteFailed = 0;
464 std::vector<size_t> m_arr;
467 Extractor( cds_test::thread_pool& pool, Map& map )
468 : base_class( pool, extractor_thread )
474 Extractor( Extractor& src )
481 virtual thread * clone()
483 return new Extractor( *this );
489 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
491 typename Map::exempt_ptr xp;
492 size_t const nInsThreadCount = s_nInsThreadCount;
496 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
497 for ( auto el: m_arr ) {
498 if ( Map::c_bExtractLockExternal ) {
499 typename Map::rcu_lock l;
500 xp = rMap.extract( key_type( el, k ));
507 xp = rMap.extract( key_type( el, k ));
518 for ( auto el : m_arr ) {
519 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
520 if ( Map::c_bExtractLockExternal ) {
521 typename Map::rcu_lock l;
522 xp = rMap.extract( key_type( el, k ));
529 xp = rMap.extract( key_type( el, k ));
539 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
547 class Observer: public cds_test::thread
549 typedef cds_test::thread base_class;
553 size_t m_nFindEvenSuccess = 0;
554 size_t m_nFindEvenFailed = 0;
555 size_t m_nFindOddSuccess = 0;
556 size_t m_nFindOddFailed = 0;
559 Observer( cds_test::thread_pool& pool, Map& map )
560 : base_class( pool, find_thread )
564 Observer( Observer& src )
569 virtual thread * clone()
571 return new Observer( *this );
577 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
578 std::vector<size_t> const& arr = m_arrElements;
579 size_t const nInsThreadCount = s_nInsThreadCount;
582 for ( size_t key : arr ) {
584 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
585 if ( map.contains( key_thread( key, k )))
592 // even keys MUST be in the map
593 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
594 if ( map.contains( key_thread( key, k )))
595 ++m_nFindEvenSuccess;
601 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
607 void do_test( Map& testMap )
609 typedef Inserter<Map> insert_thread;
610 typedef Deleter<Map> delete_thread;
611 typedef Observer<Map> observer_thread;
613 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
615 cds_test::thread_pool& pool = get_pool();
616 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
617 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
618 if ( s_nFindThreadCount )
619 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
621 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
622 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
623 << std::make_pair( "find_thread_count", s_nFindThreadCount )
624 << std::make_pair( "map_size", s_nMapSize )
625 << std::make_pair( "pass_count", s_nInsertPassCount );
627 std::chrono::milliseconds duration = pool.run();
629 propout() << std::make_pair( "duration", duration );
631 size_t nInsertInitFailed = 0;
632 size_t nInsertInitSuccess = 0;
633 size_t nInsertSuccess = 0;
634 size_t nInsertFailed = 0;
635 size_t nDeleteSuccess = 0;
636 size_t nDeleteFailed = 0;
638 size_t nFindEvenSuccess = 0;
639 size_t nFindEvenFailed = 0;
640 size_t nFindOddSuccess = 0;
641 size_t nFindOddFailed = 0;
643 for ( size_t i = 0; i < pool.size(); ++i ) {
644 cds_test::thread& thr = pool.get( i );
645 switch ( thr.type()) {
646 case inserter_thread:
648 insert_thread& inserter = static_cast<insert_thread&>( thr );
649 nInsertSuccess += inserter.m_nInsertSuccess;
650 nInsertFailed += inserter.m_nInsertFailed;
651 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
652 nInsertInitFailed += inserter.m_nInsertInitFailed;
657 delete_thread& deleter = static_cast<delete_thread&>( thr );
658 nDeleteSuccess += deleter.m_nDeleteSuccess;
659 nDeleteFailed += deleter.m_nDeleteFailed;
664 observer_thread& observer = static_cast<observer_thread&>( thr );
665 nFindEvenSuccess = observer.m_nFindEvenSuccess;
666 nFindEvenFailed = observer.m_nFindEvenFailed;
667 nFindOddSuccess = observer.m_nFindOddSuccess;
668 nFindOddFailed = observer.m_nFindOddFailed;
674 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
676 EXPECT_EQ( nInsertInitFailed, 0u );
677 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
678 EXPECT_EQ( nFindEvenFailed, 0u );
679 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
680 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
683 << std::make_pair( "insert_init_success", nInsertInitSuccess )
684 << std::make_pair( "insert_init_failed", nInsertInitFailed )
685 << std::make_pair( "insert_success", nInsertSuccess )
686 << std::make_pair( "insert_failed", nInsertFailed )
687 << std::make_pair( "delete_success", nDeleteSuccess )
688 << std::make_pair( "delete_failed", nDeleteFailed )
689 << std::make_pair( "find_even_success", nFindEvenSuccess )
690 << std::make_pair( "find_even_failed", nFindEvenFailed )
691 << std::make_pair( "find_odd_success", nFindOddSuccess )
692 << std::make_pair( "find_odd_failed", nFindOddFailed );
698 void do_test_extract( Map& testMap )
700 typedef Inserter<Map> insert_thread;
701 typedef Deleter<Map> delete_thread;
702 typedef Extractor< typename Map::gc, Map > extract_thread;
703 typedef Observer<Map> observer_thread;
705 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
707 cds_test::thread_pool& pool = get_pool();
708 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
709 if ( s_nDelThreadCount )
710 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
711 if ( s_nExtractThreadCount )
712 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
713 if ( s_nFindThreadCount )
714 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
716 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
717 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
718 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
719 << std::make_pair( "find_thread_count", s_nFindThreadCount )
720 << std::make_pair( "map_size", s_nMapSize )
721 << std::make_pair( "pass_count", s_nInsertPassCount );
723 std::chrono::milliseconds duration = pool.run();
725 propout() << std::make_pair( "duration", duration );
727 size_t nInsertInitFailed = 0;
728 size_t nInsertInitSuccess = 0;
729 size_t nInsertSuccess = 0;
730 size_t nInsertFailed = 0;
731 size_t nDeleteSuccess = 0;
732 size_t nDeleteFailed = 0;
733 size_t nExtractSuccess = 0;
734 size_t nExtractFailed = 0;
736 size_t nFindEvenSuccess = 0;
737 size_t nFindEvenFailed = 0;
738 size_t nFindOddSuccess = 0;
739 size_t nFindOddFailed = 0;
741 for ( size_t i = 0; i < pool.size(); ++i ) {
742 cds_test::thread& thr = pool.get( i );
743 switch ( thr.type()) {
744 case inserter_thread:
746 insert_thread& inserter = static_cast<insert_thread&>(thr);
747 nInsertSuccess += inserter.m_nInsertSuccess;
748 nInsertFailed += inserter.m_nInsertFailed;
749 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
750 nInsertInitFailed += inserter.m_nInsertInitFailed;
755 delete_thread& deleter = static_cast<delete_thread&>(thr);
756 nDeleteSuccess += deleter.m_nDeleteSuccess;
757 nDeleteFailed += deleter.m_nDeleteFailed;
760 case extractor_thread:
762 extract_thread& extractor = static_cast<extract_thread&>(thr);
763 nExtractSuccess += extractor.m_nDeleteSuccess;
764 nExtractFailed += extractor.m_nDeleteFailed;
769 observer_thread& observer = static_cast<observer_thread&>( thr );
770 nFindEvenSuccess = observer.m_nFindEvenSuccess;
771 nFindEvenFailed = observer.m_nFindEvenFailed;
772 nFindOddSuccess = observer.m_nFindOddSuccess;
773 nFindOddFailed = observer.m_nFindOddFailed;
781 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
783 EXPECT_EQ( nInsertInitFailed, 0u );
784 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
785 EXPECT_EQ( nFindEvenFailed, 0u );
786 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
787 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
790 << std::make_pair( "insert_init_success", nInsertInitSuccess )
791 << std::make_pair( "insert_init_failed", nInsertInitFailed )
792 << std::make_pair( "insert_success", nInsertSuccess )
793 << std::make_pair( "insert_failed", nInsertFailed )
794 << std::make_pair( "delete_success", nDeleteSuccess )
795 << std::make_pair( "delete_failed", nDeleteFailed )
796 << std::make_pair( "extract_success", nExtractSuccess )
797 << std::make_pair( "extract_failed", nExtractFailed )
798 << std::make_pair( "find_even_success", nFindEvenSuccess )
799 << std::make_pair( "find_even_failed", nFindEvenFailed )
800 << std::make_pair( "find_odd_success", nFindOddSuccess )
801 << std::make_pair( "find_odd_failed", nFindOddFailed );
807 void analyze( Map& testMap )
809 // All even keys must be in the map
811 for ( size_t n = 0; n < s_nMapSize; n +=2 ) {
812 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
813 EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
818 print_stat( propout(), testMap );
820 check_before_cleanup( testMap );
822 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
824 additional_check( testMap );
825 additional_cleanup( testMap );
829 void run_test_extract()
831 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
833 size_t nMapSize = s_nMapSize;
834 s_nMapSize *= s_nInsThreadCount;
836 Map testMap( *this );
838 s_nMapSize = nMapSize;
839 do_test_extract( testMap );
845 size_t nMapSize = s_nMapSize;
846 s_nMapSize *= s_nInsThreadCount;
848 Map testMap( *this );
850 s_nMapSize = nMapSize;
858 class Map_DelOdd_LF: public Map_DelOdd
859 , public ::testing::WithParamInterface<size_t>
865 s_nLoadFactor = GetParam();
866 propout() << std::make_pair( "load_factor", s_nLoadFactor );
867 Map_DelOdd::run_test<Map>();
871 void run_test_extract()
873 s_nLoadFactor = GetParam();
874 propout() << std::make_pair( "load_factor", s_nLoadFactor );
875 Map_DelOdd::run_test_extract<Map>();
878 static std::vector<size_t> get_load_factors();