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_Iter_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_nFeldmanMap_HeadBits;
128 static size_t s_nFeldmanMap_ArrayBits;
130 static size_t s_nLoadFactor; // current load factor
132 static std::vector<size_t> m_arrElements;
134 static void SetUpTestCase();
135 static void TearDownTestCase();
137 template <typename Pred>
138 static void prepare_array( std::vector<size_t>& arr, Pred pred )
140 arr.reserve( m_arrElements.size());
141 for ( auto el : m_arrElements ) {
145 arr.resize( arr.size());
146 shuffle( arr.begin(), arr.end());
150 typedef key_thread key_type;
151 typedef size_t value_type;
152 typedef std::pair<key_type const, value_type> pair_type;
154 atomics::atomic<size_t> m_nInsThreadCount;
163 // Inserts keys from [0..N)
165 class Inserter: public cds_test::thread
167 typedef cds_test::thread base_class;
172 template <typename Q>
173 void operator()( bool /*bNew*/, Q const& ) const
176 template <typename Q, typename V>
177 void operator()( bool /*bNew*/, Q const&, V& ) const
181 template <typename Q>
182 void operator()( Q&, Q*) const
188 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
189 for ( size_t i = 0; i < m_arr.size(); ++i ) {
190 if ( m_Map.insert( key_type( m_arr[i], id())))
191 ++m_nInsertInitSuccess;
193 ++m_nInsertInitFailed;
198 size_t m_nInsertSuccess = 0;
199 size_t m_nInsertFailed = 0;
200 size_t m_nInsertInitSuccess = 0;
201 size_t m_nInsertInitFailed = 0;
203 std::vector<size_t> m_arr;
206 Inserter( cds_test::thread_pool& pool, Map& map )
207 : base_class( pool, inserter_thread )
213 Inserter( Inserter& src )
220 virtual thread * clone()
222 return new Inserter( *this );
228 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
232 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
235 for ( auto el : m_arr ) {
237 if ( rMap.insert( key_type( el, id())))
246 for ( auto el : m_arr ) {
250 std::tie( success, inserted ) = rMap.update( key_type( el, id()), f );
251 if ( success && inserted )
260 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
266 bool operator()( key_type const& k1, key_type const& k2 ) const
268 return k1.nKey == k2.nKey;
270 bool operator()( size_t k1, key_type const& k2 ) const
272 return k1 == k2.nKey;
274 bool operator()( key_type const& k1, size_t k2 ) const
276 return k1.nKey == k2;
281 bool operator()( key_type const& k1, key_type const& k2 ) const
283 return k1.nKey < k2.nKey;
285 bool operator()( size_t k1, key_type const& k2 ) const
289 bool operator()( key_type const& k1, size_t k2 ) const
294 typedef key_equal equal_to;
297 // Deletes odd keys from [0..N)
298 template <class Map, typename Iterator>
299 class Deleter: public cds_test::thread
301 typedef cds_test::thread base_class;
306 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
310 size_t m_nDeleteSuccess = 0;
311 size_t m_nDeleteFailed = 0;
313 std::vector<size_t> m_arr;
316 Deleter( cds_test::thread_pool& pool, Map& map )
317 : base_class( pool, deleter_thread )
323 Deleter( Deleter& src )
330 virtual thread * clone()
332 return new Deleter( *this );
339 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
342 auto itEnd = rMap.template get_end<Iterator>();
343 for ( auto it = rMap.template get_begin<Iterator>(); it != itEnd; ++it ) {
344 if ( it->first.nKey & 3 ) {
345 if ( rMap.erase_at( it ))
351 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
355 // Deletes odd keys from [0..N)
356 template <class GC, class Map >
357 class Extractor: public cds_test::thread
359 typedef cds_test::thread base_class;
364 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
368 size_t m_nDeleteSuccess = 0;
369 size_t m_nDeleteFailed = 0;
371 std::vector<size_t> m_arr;
374 Extractor( cds_test::thread_pool& pool, Map& map )
375 : base_class( pool, extractor_thread )
381 Extractor( Extractor& src )
388 virtual thread * clone()
390 return new Extractor( *this );
397 typename Map::guarded_ptr gp;
398 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
399 size_t const nInsThreadCount = s_nInsThreadCount;
403 for ( auto el : m_arr ) {
404 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
405 gp = rMap.extract( key_type( el, k ));
415 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
416 for ( auto el: m_arr ) {
417 gp = rMap.extract( key_type( el, k ));
426 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
432 template <class RCU, class Map >
433 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
435 typedef cds_test::thread base_class;
440 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
444 size_t m_nDeleteSuccess = 0;
445 size_t m_nDeleteFailed = 0;
447 std::vector<size_t> m_arr;
450 Extractor( cds_test::thread_pool& pool, Map& map )
451 : base_class( pool, extractor_thread )
457 Extractor( Extractor& src )
464 virtual thread * clone()
466 return new Extractor( *this );
472 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
474 typename Map::exempt_ptr xp;
475 size_t const nInsThreadCount = s_nInsThreadCount;
479 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
480 for ( auto el: m_arr ) {
481 if ( Map::c_bExtractLockExternal ) {
482 typename Map::rcu_lock l;
483 xp = rMap.extract( key_type( el, k ));
490 xp = rMap.extract( key_type( el, k ));
501 for ( auto el : m_arr ) {
502 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
503 if ( Map::c_bExtractLockExternal ) {
504 typename Map::rcu_lock l;
505 xp = rMap.extract( key_type( el, k ));
512 xp = rMap.extract( key_type( el, k ));
522 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
530 class Observer: public cds_test::thread
532 typedef cds_test::thread base_class;
536 size_t m_nFindEvenSuccess = 0;
537 size_t m_nFindEvenFailed = 0;
538 size_t m_nFindOddSuccess = 0;
539 size_t m_nFindOddFailed = 0;
542 Observer( cds_test::thread_pool& pool, Map& map )
543 : base_class( pool, find_thread )
547 Observer( Observer& src )
552 virtual thread * clone()
554 return new Observer( *this );
560 Map_Iter_Del3& fixture = pool().template fixture<Map_Iter_Del3>();
561 std::vector<size_t> const& arr = m_arrElements;
562 size_t const nInsThreadCount = s_nInsThreadCount;
565 for ( size_t key : arr ) {
567 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
568 if ( map.contains( key_thread( key, k )))
575 // even keys MUST be in the map
576 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
577 if ( map.contains( key_thread( key, k )))
578 ++m_nFindEvenSuccess;
584 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
589 template <typename Iterator, class Map>
590 void do_test( Map& testMap )
592 typedef Inserter<Map> insert_thread;
593 typedef Deleter<Map, Iterator> delete_thread;
594 typedef Observer<Map> observer_thread;
596 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
598 cds_test::thread_pool& pool = get_pool();
599 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
600 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
601 if ( s_nFindThreadCount )
602 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
604 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
605 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
606 << std::make_pair( "find_thread_count", s_nFindThreadCount )
607 << std::make_pair( "map_size", s_nMapSize )
608 << std::make_pair( "pass_count", s_nInsertPassCount );
610 std::chrono::milliseconds duration = pool.run();
612 propout() << std::make_pair( "duration", duration );
614 size_t nInsertInitFailed = 0;
615 size_t nInsertInitSuccess = 0;
616 size_t nInsertSuccess = 0;
617 size_t nInsertFailed = 0;
618 size_t nDeleteSuccess = 0;
619 size_t nDeleteFailed = 0;
621 size_t nFindEvenSuccess = 0;
622 size_t nFindEvenFailed = 0;
623 size_t nFindOddSuccess = 0;
624 size_t nFindOddFailed = 0;
626 for ( size_t i = 0; i < pool.size(); ++i ) {
627 cds_test::thread& thr = pool.get( i );
628 switch ( thr.type()) {
629 case inserter_thread:
631 insert_thread& inserter = static_cast<insert_thread&>( thr );
632 nInsertSuccess += inserter.m_nInsertSuccess;
633 nInsertFailed += inserter.m_nInsertFailed;
634 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
635 nInsertInitFailed += inserter.m_nInsertInitFailed;
640 delete_thread& deleter = static_cast<delete_thread&>( thr );
641 nDeleteSuccess += deleter.m_nDeleteSuccess;
642 nDeleteFailed += deleter.m_nDeleteFailed;
647 observer_thread& observer = static_cast<observer_thread&>( thr );
648 nFindEvenSuccess = observer.m_nFindEvenSuccess;
649 nFindEvenFailed = observer.m_nFindEvenFailed;
650 nFindOddSuccess = observer.m_nFindOddSuccess;
651 nFindOddFailed = observer.m_nFindOddFailed;
657 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
659 EXPECT_EQ( nInsertInitFailed, 0u );
660 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
661 EXPECT_EQ( nFindEvenFailed, 0u );
662 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
663 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
666 << std::make_pair( "insert_init_success", nInsertInitSuccess )
667 << std::make_pair( "insert_init_failed", nInsertInitFailed )
668 << std::make_pair( "insert_success", nInsertSuccess )
669 << std::make_pair( "insert_failed", nInsertFailed )
670 << std::make_pair( "delete_success", nDeleteSuccess )
671 << std::make_pair( "delete_failed", nDeleteFailed )
672 << std::make_pair( "find_even_success", nFindEvenSuccess )
673 << std::make_pair( "find_even_failed", nFindEvenFailed )
674 << std::make_pair( "find_odd_success", nFindOddSuccess )
675 << std::make_pair( "find_odd_failed", nFindOddFailed );
677 DEBUG(analyze( testMap ));
680 template <typename Iterator, class Map>
681 void do_test_extract( Map& testMap )
683 typedef Inserter<Map> insert_thread;
684 typedef Deleter<Map, Iterator> delete_thread;
685 typedef Extractor< typename Map::gc, Map > extract_thread;
686 typedef Observer<Map> observer_thread;
688 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
690 cds_test::thread_pool& pool = get_pool();
691 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
692 if ( s_nDelThreadCount )
693 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
694 if ( s_nExtractThreadCount )
695 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
696 if ( s_nFindThreadCount )
697 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
699 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
700 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
701 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
702 << std::make_pair( "find_thread_count", s_nFindThreadCount )
703 << std::make_pair( "map_size", s_nMapSize )
704 << std::make_pair( "pass_count", s_nInsertPassCount );
706 std::chrono::milliseconds duration = pool.run();
708 propout() << std::make_pair( "duration", duration );
710 size_t nInsertInitFailed = 0;
711 size_t nInsertInitSuccess = 0;
712 size_t nInsertSuccess = 0;
713 size_t nInsertFailed = 0;
714 size_t nDeleteSuccess = 0;
715 size_t nDeleteFailed = 0;
716 size_t nExtractSuccess = 0;
717 size_t nExtractFailed = 0;
719 size_t nFindEvenSuccess = 0;
720 size_t nFindEvenFailed = 0;
721 size_t nFindOddSuccess = 0;
722 size_t nFindOddFailed = 0;
724 for ( size_t i = 0; i < pool.size(); ++i ) {
725 cds_test::thread& thr = pool.get( i );
726 switch ( thr.type()) {
727 case inserter_thread:
729 insert_thread& inserter = static_cast<insert_thread&>(thr);
730 nInsertSuccess += inserter.m_nInsertSuccess;
731 nInsertFailed += inserter.m_nInsertFailed;
732 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
733 nInsertInitFailed += inserter.m_nInsertInitFailed;
738 delete_thread& deleter = static_cast<delete_thread&>(thr);
739 nDeleteSuccess += deleter.m_nDeleteSuccess;
740 nDeleteFailed += deleter.m_nDeleteFailed;
743 case extractor_thread:
745 extract_thread& extractor = static_cast<extract_thread&>(thr);
746 nExtractSuccess += extractor.m_nDeleteSuccess;
747 nExtractFailed += extractor.m_nDeleteFailed;
752 observer_thread& observer = static_cast<observer_thread&>( thr );
753 nFindEvenSuccess = observer.m_nFindEvenSuccess;
754 nFindEvenFailed = observer.m_nFindEvenFailed;
755 nFindOddSuccess = observer.m_nFindOddSuccess;
756 nFindOddFailed = observer.m_nFindOddFailed;
764 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
766 EXPECT_EQ( nInsertInitFailed, 0u );
767 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
768 EXPECT_EQ( nFindEvenFailed, 0u );
769 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
770 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
773 << std::make_pair( "insert_init_success", nInsertInitSuccess )
774 << std::make_pair( "insert_init_failed", nInsertInitFailed )
775 << std::make_pair( "insert_success", nInsertSuccess )
776 << std::make_pair( "insert_failed", nInsertFailed )
777 << std::make_pair( "delete_success", nDeleteSuccess )
778 << std::make_pair( "delete_failed", nDeleteFailed )
779 << std::make_pair( "extract_success", nExtractSuccess )
780 << std::make_pair( "extract_failed", nExtractFailed )
781 << std::make_pair( "find_even_success", nFindEvenSuccess )
782 << std::make_pair( "find_even_failed", nFindEvenFailed )
783 << std::make_pair( "find_odd_success", nFindOddSuccess )
784 << std::make_pair( "find_odd_failed", nFindOddFailed );
786 DEBUG(analyze( testMap ));
790 void analyze( Map& testMap )
792 // All even keys must be in the map
794 for ( size_t n = 0; n < s_nMapSize; n +=4 ) {
795 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
796 EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
801 print_stat( propout(), testMap );
803 check_before_cleanup( testMap );
805 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
807 additional_check( testMap );
808 additional_cleanup( testMap );
811 template <class Map, typename Iterator=typename Map::iterator>
812 void run_test_extract()
814 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
816 size_t nMapSize = s_nMapSize;
817 s_nMapSize *= s_nInsThreadCount;
819 Map testMap( *this );
821 s_nMapSize = nMapSize;
822 do_test_extract<Iterator>( testMap );
825 template <class Map, typename Iterator=typename Map::iterator>
828 size_t nMapSize = s_nMapSize;
829 s_nMapSize *= s_nInsThreadCount;
831 Map testMap( *this );
833 s_nMapSize = nMapSize;
834 do_test<Iterator>( testMap );
841 class Map_Iter_Del3_reverse: public Map_Iter_Del3
849 class Map_Iter_Del3_LF: public Map_Iter_Del3
850 , public ::testing::WithParamInterface<size_t>
856 s_nLoadFactor = GetParam();
857 propout() << std::make_pair( "load_factor", s_nLoadFactor );
858 Map_Iter_Del3::run_test<Map>();
862 void run_test_extract()
864 s_nLoadFactor = GetParam();
865 propout() << std::make_pair( "load_factor", s_nLoadFactor );
866 Map_Iter_Del3::run_test_extract<Map>();
869 static std::vector<size_t> get_load_factors();