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_Iter_Del3: 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_nFeldmanMap_HeadBits;
127 static size_t s_nFeldmanMap_ArrayBits;
129 static size_t s_nLoadFactor; // current load factor
131 static std::vector<size_t> m_arrElements;
133 static void SetUpTestCase();
134 static void TearDownTestCase();
136 template <typename Pred>
137 static void prepare_array( std::vector<size_t>& arr, Pred pred )
139 arr.reserve( m_arrElements.size());
140 for ( auto el : m_arrElements ) {
144 arr.resize( arr.size());
145 shuffle( arr.begin(), arr.end());
149 typedef key_thread key_type;
150 typedef size_t value_type;
151 typedef std::pair<key_type const, value_type> pair_type;
153 atomics::atomic<size_t> m_nInsThreadCount;
162 // Inserts keys from [0..N)
164 class Inserter: public cds_test::thread
166 typedef cds_test::thread base_class;
171 template <typename Q>
172 void operator()( bool /*bNew*/, Q const& ) const
175 template <typename Q, typename V>
176 void operator()( bool /*bNew*/, Q const&, V& ) const
180 template <typename Q>
181 void operator()( Q&, Q*) const
187 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
188 for ( size_t i = 0; i < m_arr.size(); ++i ) {
189 if ( m_Map.insert( key_type( m_arr[i], id())))
190 ++m_nInsertInitSuccess;
192 ++m_nInsertInitFailed;
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, Map& map )
206 : base_class( pool, inserter_thread )
212 Inserter( Inserter& src )
219 virtual thread * clone()
221 return new Inserter( *this );
227 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
231 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
234 for ( auto el : m_arr ) {
236 if ( rMap.insert( key_type( el, id())))
245 for ( auto el : m_arr ) {
249 std::tie( success, inserted ) = rMap.update( key_type( el, id()), f );
250 if ( success && inserted )
259 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
265 bool operator()( key_type const& k1, key_type const& k2 ) const
267 return k1.nKey == k2.nKey;
269 bool operator()( size_t k1, key_type const& k2 ) const
271 return k1 == k2.nKey;
273 bool operator()( key_type const& k1, size_t k2 ) const
275 return k1.nKey == k2;
280 bool operator()( key_type const& k1, key_type const& k2 ) const
282 return k1.nKey < k2.nKey;
284 bool operator()( size_t k1, key_type const& k2 ) const
288 bool operator()( key_type const& k1, size_t k2 ) const
293 typedef key_equal equal_to;
296 // Deletes odd keys from [0..N)
297 template <class Map, typename Iterator>
298 class Deleter: public cds_test::thread
300 typedef cds_test::thread base_class;
305 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
309 size_t m_nDeleteSuccess = 0;
310 size_t m_nDeleteFailed = 0;
312 std::vector<size_t> m_arr;
315 Deleter( cds_test::thread_pool& pool, Map& map )
316 : base_class( pool, deleter_thread )
322 Deleter( Deleter& src )
329 virtual thread * clone()
331 return new Deleter( *this );
338 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
341 auto itEnd = rMap.template get_end<Iterator>();
342 for ( auto it = rMap.template get_begin<Iterator>(); it != itEnd; ++it ) {
343 if ( it->first.nKey & 3 ) {
344 if ( rMap.erase_at( it ))
350 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
354 // Deletes odd keys from [0..N)
355 template <class GC, class Map >
356 class Extractor: public cds_test::thread
358 typedef cds_test::thread base_class;
363 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
367 size_t m_nDeleteSuccess = 0;
368 size_t m_nDeleteFailed = 0;
370 std::vector<size_t> m_arr;
373 Extractor( cds_test::thread_pool& pool, Map& map )
374 : base_class( pool, extractor_thread )
380 Extractor( Extractor& src )
387 virtual thread * clone()
389 return new Extractor( *this );
396 typename Map::guarded_ptr gp;
397 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
398 size_t const nInsThreadCount = s_nInsThreadCount;
402 for ( auto el : m_arr ) {
403 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
404 gp = rMap.extract( key_type( el, k ));
414 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
415 for ( auto el: m_arr ) {
416 gp = rMap.extract( key_type( el, k ));
425 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
431 template <class RCU, class Map >
432 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
434 typedef cds_test::thread base_class;
439 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
443 size_t m_nDeleteSuccess = 0;
444 size_t m_nDeleteFailed = 0;
446 std::vector<size_t> m_arr;
449 Extractor( cds_test::thread_pool& pool, Map& map )
450 : base_class( pool, extractor_thread )
456 Extractor( Extractor& src )
463 virtual thread * clone()
465 return new Extractor( *this );
471 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
473 typename Map::exempt_ptr xp;
474 size_t const nInsThreadCount = s_nInsThreadCount;
478 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
479 for ( auto el: m_arr ) {
480 if ( Map::c_bExtractLockExternal ) {
481 typename Map::rcu_lock l;
482 xp = rMap.extract( key_type( el, k ));
489 xp = rMap.extract( key_type( el, k ));
500 for ( auto el : m_arr ) {
501 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
502 if ( Map::c_bExtractLockExternal ) {
503 typename Map::rcu_lock l;
504 xp = rMap.extract( key_type( el, k ));
511 xp = rMap.extract( key_type( el, k ));
521 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
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, Map& map )
542 : base_class( pool, find_thread )
546 Observer( Observer& src )
551 virtual thread * clone()
553 return new Observer( *this );
559 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
560 std::vector<size_t> const& arr = m_arrElements;
561 size_t const nInsThreadCount = s_nInsThreadCount;
564 for ( size_t key : arr ) {
566 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
567 if ( map.contains( key_thread( key, k )))
574 // even keys MUST be in the map
575 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
576 if ( map.contains( key_thread( key, k )))
577 ++m_nFindEvenSuccess;
583 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
588 template <typename Iterator, class Map>
589 void do_test( Map& testMap )
591 typedef Inserter<Map> insert_thread;
592 typedef Deleter<Map, Iterator> delete_thread;
593 typedef Observer<Map> observer_thread;
595 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
597 cds_test::thread_pool& pool = get_pool();
598 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
599 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
600 if ( s_nFindThreadCount )
601 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
603 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
604 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
605 << std::make_pair( "find_thread_count", s_nFindThreadCount )
606 << std::make_pair( "map_size", s_nMapSize )
607 << std::make_pair( "pass_count", s_nInsertPassCount );
609 std::chrono::milliseconds duration = pool.run();
611 propout() << std::make_pair( "duration", duration );
613 size_t nInsertInitFailed = 0;
614 size_t nInsertInitSuccess = 0;
615 size_t nInsertSuccess = 0;
616 size_t nInsertFailed = 0;
617 size_t nDeleteSuccess = 0;
618 size_t nDeleteFailed = 0;
620 size_t nFindEvenSuccess = 0;
621 size_t nFindEvenFailed = 0;
622 size_t nFindOddSuccess = 0;
623 size_t nFindOddFailed = 0;
625 for ( size_t i = 0; i < pool.size(); ++i ) {
626 cds_test::thread& thr = pool.get( i );
627 switch ( thr.type()) {
628 case inserter_thread:
630 insert_thread& inserter = static_cast<insert_thread&>( thr );
631 nInsertSuccess += inserter.m_nInsertSuccess;
632 nInsertFailed += inserter.m_nInsertFailed;
633 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
634 nInsertInitFailed += inserter.m_nInsertInitFailed;
639 delete_thread& deleter = static_cast<delete_thread&>( thr );
640 nDeleteSuccess += deleter.m_nDeleteSuccess;
641 nDeleteFailed += deleter.m_nDeleteFailed;
646 observer_thread& observer = static_cast<observer_thread&>( thr );
647 nFindEvenSuccess = observer.m_nFindEvenSuccess;
648 nFindEvenFailed = observer.m_nFindEvenFailed;
649 nFindOddSuccess = observer.m_nFindOddSuccess;
650 nFindOddFailed = observer.m_nFindOddFailed;
656 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
658 EXPECT_EQ( nInsertInitFailed, 0u );
659 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
660 EXPECT_EQ( nFindEvenFailed, 0u );
661 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
662 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
665 << std::make_pair( "insert_init_success", nInsertInitSuccess )
666 << std::make_pair( "insert_init_failed", nInsertInitFailed )
667 << std::make_pair( "insert_success", nInsertSuccess )
668 << std::make_pair( "insert_failed", nInsertFailed )
669 << std::make_pair( "delete_success", nDeleteSuccess )
670 << std::make_pair( "delete_failed", nDeleteFailed )
671 << std::make_pair( "find_even_success", nFindEvenSuccess )
672 << std::make_pair( "find_even_failed", nFindEvenFailed )
673 << std::make_pair( "find_odd_success", nFindOddSuccess )
674 << std::make_pair( "find_odd_failed", nFindOddFailed );
679 template <typename Iterator, class Map>
680 void do_test_extract( Map& testMap )
682 typedef Inserter<Map> insert_thread;
683 typedef Deleter<Map, Iterator> delete_thread;
684 typedef Extractor< typename Map::gc, Map > extract_thread;
685 typedef Observer<Map> observer_thread;
687 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
689 cds_test::thread_pool& pool = get_pool();
690 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
691 if ( s_nDelThreadCount )
692 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
693 if ( s_nExtractThreadCount )
694 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
695 if ( s_nFindThreadCount )
696 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
698 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
699 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
700 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
701 << std::make_pair( "find_thread_count", s_nFindThreadCount )
702 << std::make_pair( "map_size", s_nMapSize )
703 << std::make_pair( "pass_count", s_nInsertPassCount );
705 std::chrono::milliseconds duration = pool.run();
707 propout() << std::make_pair( "duration", duration );
709 size_t nInsertInitFailed = 0;
710 size_t nInsertInitSuccess = 0;
711 size_t nInsertSuccess = 0;
712 size_t nInsertFailed = 0;
713 size_t nDeleteSuccess = 0;
714 size_t nDeleteFailed = 0;
715 size_t nExtractSuccess = 0;
716 size_t nExtractFailed = 0;
718 size_t nFindEvenSuccess = 0;
719 size_t nFindEvenFailed = 0;
720 size_t nFindOddSuccess = 0;
721 size_t nFindOddFailed = 0;
723 for ( size_t i = 0; i < pool.size(); ++i ) {
724 cds_test::thread& thr = pool.get( i );
725 switch ( thr.type()) {
726 case inserter_thread:
728 insert_thread& inserter = static_cast<insert_thread&>(thr);
729 nInsertSuccess += inserter.m_nInsertSuccess;
730 nInsertFailed += inserter.m_nInsertFailed;
731 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
732 nInsertInitFailed += inserter.m_nInsertInitFailed;
737 delete_thread& deleter = static_cast<delete_thread&>(thr);
738 nDeleteSuccess += deleter.m_nDeleteSuccess;
739 nDeleteFailed += deleter.m_nDeleteFailed;
742 case extractor_thread:
744 extract_thread& extractor = static_cast<extract_thread&>(thr);
745 nExtractSuccess += extractor.m_nDeleteSuccess;
746 nExtractFailed += extractor.m_nDeleteFailed;
751 observer_thread& observer = static_cast<observer_thread&>( thr );
752 nFindEvenSuccess = observer.m_nFindEvenSuccess;
753 nFindEvenFailed = observer.m_nFindEvenFailed;
754 nFindOddSuccess = observer.m_nFindOddSuccess;
755 nFindOddFailed = observer.m_nFindOddFailed;
763 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
765 EXPECT_EQ( nInsertInitFailed, 0u );
766 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
767 EXPECT_EQ( nFindEvenFailed, 0u );
768 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
769 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
772 << std::make_pair( "insert_init_success", nInsertInitSuccess )
773 << std::make_pair( "insert_init_failed", nInsertInitFailed )
774 << std::make_pair( "insert_success", nInsertSuccess )
775 << std::make_pair( "insert_failed", nInsertFailed )
776 << std::make_pair( "delete_success", nDeleteSuccess )
777 << std::make_pair( "delete_failed", nDeleteFailed )
778 << std::make_pair( "extract_success", nExtractSuccess )
779 << std::make_pair( "extract_failed", nExtractFailed )
780 << std::make_pair( "find_even_success", nFindEvenSuccess )
781 << std::make_pair( "find_even_failed", nFindEvenFailed )
782 << std::make_pair( "find_odd_success", nFindOddSuccess )
783 << std::make_pair( "find_odd_failed", nFindOddFailed );
789 void analyze( Map& testMap )
791 // All even keys must be in the map
793 for ( size_t n = 0; n < s_nMapSize; n +=4 ) {
794 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
795 EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
800 print_stat( propout(), testMap );
802 check_before_cleanup( testMap );
804 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
806 additional_check( testMap );
807 additional_cleanup( testMap );
810 template <class Map, typename Iterator=typename Map::iterator>
811 void run_test_extract()
813 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
815 size_t nMapSize = s_nMapSize;
816 s_nMapSize *= s_nInsThreadCount;
818 Map testMap( *this );
820 s_nMapSize = nMapSize;
821 do_test_extract<Iterator>( testMap );
824 template <class Map, typename Iterator=typename Map::iterator>
827 size_t nMapSize = s_nMapSize;
828 s_nMapSize *= s_nInsThreadCount;
830 Map testMap( *this );
832 s_nMapSize = nMapSize;
833 do_test<Iterator>( testMap );
840 class Map_Iter_Del3_reverse: public Map_Iter_Del3
848 class Map_Iter_Del3_LF: public Map_Iter_Del3
849 , public ::testing::WithParamInterface<size_t>
855 s_nLoadFactor = GetParam();
856 propout() << std::make_pair( "load_factor", s_nLoadFactor );
857 Map_Iter_Del3::run_test<Map>();
861 void run_test_extract()
863 s_nLoadFactor = GetParam();
864 propout() << std::make_pair( "load_factor", s_nLoadFactor );
865 Map_Iter_Del3::run_test_extract<Map>();
868 static std::vector<size_t> get_load_factors();