2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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.
41 key_thread( size_t key, size_t threadNo )
42 : nKey( static_cast<uint32_t>(key))
43 , nThread( static_cast<uint16_t>(threadNo))
52 static_assert(sizeof( key_thread ) % 8 == 0, "Key size mismatch!!!");
56 struct cmp<key_thread> {
57 int operator ()(key_thread const& k1, key_thread const& k2) const
59 if ( k1.nKey < k2.nKey )
61 if ( k1.nKey > k2.nKey )
63 if ( k1.nThread < k2.nThread )
65 if ( k1.nThread > k2.nThread )
69 int operator ()(key_thread const& k1, size_t k2) const
77 int operator ()(size_t k1, key_thread const& k2) const
88 struct less<key_thread>
90 bool operator()( key_thread const& k1, key_thread const& k2 ) const
92 if ( k1.nKey <= k2.nKey )
93 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
99 struct hash<key_thread>
101 typedef size_t result_type;
102 typedef key_thread argument_type;
104 size_t operator()( key_thread const& k ) const
106 return std::hash<size_t>()(k.nKey);
108 size_t operator()( size_t k ) const
110 return std::hash<size_t>()(k);
114 class Map_DelOdd: public cds_test::stress_fixture
117 static size_t s_nInsThreadCount; // insert thread count
118 static size_t s_nDelThreadCount; // delete thread count
119 static size_t s_nExtractThreadCount; // extract thread count
120 static size_t s_nMapSize; // max map size
121 static size_t s_nMaxLoadFactor; // maximum load factor
122 static size_t s_nInsertPassCount;
123 static size_t s_nFindThreadCount; // find thread count
125 static size_t s_nCuckooInitialSize; // initial size for CuckooMap
126 static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
127 static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
129 static size_t s_nFeldmanMap_HeadBits;
130 static size_t s_nFeldmanMap_ArrayBits;
132 static size_t s_nLoadFactor; // current load factor
134 static std::vector<size_t> m_arrElements;
136 static void SetUpTestCase();
137 static void TearDownTestCase();
139 template <typename Pred>
140 static void prepare_array( std::vector<size_t>& arr, Pred pred )
142 arr.reserve( m_arrElements.size() );
143 for ( auto el : m_arrElements ) {
147 arr.resize( arr.size() );
148 shuffle( arr.begin(), arr.end() );
152 typedef key_thread key_type;
153 typedef size_t value_type;
154 typedef std::pair<key_type const, value_type> pair_type;
156 atomics::atomic<size_t> m_nInsThreadCount;
165 // Inserts keys from [0..N)
167 class Inserter: public cds_test::thread
169 typedef cds_test::thread base_class;
174 template <typename Q>
175 void operator()( bool /*bNew*/, Q const& ) const
178 template <typename Q, typename V>
179 void operator()( bool /*bNew*/, Q const&, V& ) const
183 template <typename Q>
184 void operator()( Q&, Q*) const
190 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
191 for ( size_t i = 0; i < m_arr.size(); ++i ) {
192 if ( m_Map.insert( key_type( m_arr[i], id() ) ) )
193 ++m_nInsertInitSuccess;
195 ++m_nInsertInitFailed;
200 size_t m_nInsertSuccess = 0;
201 size_t m_nInsertFailed = 0;
202 size_t m_nInsertInitSuccess = 0;
203 size_t m_nInsertInitFailed = 0;
205 std::vector<size_t> m_arr;
208 Inserter( cds_test::thread_pool& pool, Map& map )
209 : base_class( pool, inserter_thread )
215 Inserter( Inserter& src )
222 virtual thread * clone()
224 return new Inserter( *this );
230 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
234 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
237 for ( auto el : m_arr ) {
239 if ( rMap.insert( key_type( el, id() )))
248 for ( auto el : m_arr ) {
252 std::tie( success, inserted ) = rMap.update( key_type( el, id() ), f );
253 if ( success && inserted )
262 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
268 bool operator()( key_type const& k1, key_type const& k2 ) const
270 return k1.nKey == k2.nKey;
272 bool operator()( size_t k1, key_type const& k2 ) const
274 return k1 == k2.nKey;
276 bool operator()( key_type const& k1, size_t k2 ) const
278 return k1.nKey == k2;
283 bool operator()( key_type const& k1, key_type const& k2 ) const
285 return k1.nKey < k2.nKey;
287 bool operator()( size_t k1, key_type const& k2 ) const
291 bool operator()( key_type const& k1, size_t k2 ) const
296 typedef key_equal equal_to;
299 // Deletes odd keys from [0..N)
301 class Deleter: public cds_test::thread
303 typedef cds_test::thread base_class;
308 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
312 size_t m_nDeleteSuccess = 0;
313 size_t m_nDeleteFailed = 0;
315 std::vector<size_t> m_arr;
318 Deleter( cds_test::thread_pool& pool, Map& map )
319 : base_class( pool, deleter_thread )
325 Deleter( Deleter& src )
332 virtual thread * clone()
334 return new Deleter( *this );
341 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
342 size_t const nInsThreadCount = s_nInsThreadCount;
346 for ( auto el: m_arr ) {
347 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
348 if ( rMap.erase( key_type( el, k )))
356 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
357 for ( auto el: m_arr ) {
358 if ( rMap.erase( key_type( el, k ) ) )
365 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
371 // Deletes odd keys from [0..N)
372 template <class GC, class Map >
373 class Extractor: public cds_test::thread
375 typedef cds_test::thread base_class;
380 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
384 size_t m_nDeleteSuccess = 0;
385 size_t m_nDeleteFailed = 0;
387 std::vector<size_t> m_arr;
390 Extractor( cds_test::thread_pool& pool, Map& map )
391 : base_class( pool, extractor_thread )
397 Extractor( Extractor& src )
404 virtual thread * clone()
406 return new Extractor( *this );
413 typename Map::guarded_ptr gp;
414 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
415 size_t const nInsThreadCount = s_nInsThreadCount;
419 for ( auto el : m_arr ) {
420 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
421 gp = rMap.extract( key_type( el, k ));
431 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
432 for ( auto el: m_arr ) {
433 gp = rMap.extract( key_type( el, k ) );
442 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
448 template <class RCU, class Map >
449 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
451 typedef cds_test::thread base_class;
456 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
460 size_t m_nDeleteSuccess = 0;
461 size_t m_nDeleteFailed = 0;
463 std::vector<size_t> m_arr;
466 Extractor( cds_test::thread_pool& pool, Map& map )
467 : base_class( pool, extractor_thread )
473 Extractor( Extractor& src )
480 virtual thread * clone()
482 return new Extractor( *this );
488 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
490 typename Map::exempt_ptr xp;
491 size_t const nInsThreadCount = s_nInsThreadCount;
495 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
496 for ( auto el: m_arr ) {
497 if ( Map::c_bExtractLockExternal ) {
498 typename Map::rcu_lock l;
499 xp = rMap.extract( key_type( el, k ) );
506 xp = rMap.extract( key_type( el, k ) );
517 for ( auto el : m_arr ) {
518 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
519 if ( Map::c_bExtractLockExternal ) {
520 typename Map::rcu_lock l;
521 xp = rMap.extract( key_type( el, k ) );
528 xp = rMap.extract( key_type( el, k ) );
538 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
546 class Observer: public cds_test::thread
548 typedef cds_test::thread base_class;
552 size_t m_nFindEvenSuccess = 0;
553 size_t m_nFindEvenFailed = 0;
554 size_t m_nFindOddSuccess = 0;
555 size_t m_nFindOddFailed = 0;
558 Observer( cds_test::thread_pool& pool, Map& map )
559 : base_class( pool, find_thread )
563 Observer( Observer& src )
568 virtual thread * clone()
570 return new Observer( *this );
576 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
577 std::vector<size_t> const& arr = m_arrElements;
578 size_t const nInsThreadCount = s_nInsThreadCount;
581 for ( size_t key : arr ) {
583 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
584 if ( map.contains( key_thread( key, k )))
591 // even keys MUST be in the map
592 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
593 if ( map.contains( key_thread( key, k )))
594 ++m_nFindEvenSuccess;
600 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
606 void do_test( Map& testMap )
608 typedef Inserter<Map> insert_thread;
609 typedef Deleter<Map> delete_thread;
610 typedef Observer<Map> observer_thread;
612 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
614 cds_test::thread_pool& pool = get_pool();
615 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
616 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
617 if ( s_nFindThreadCount )
618 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
620 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
621 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
622 << std::make_pair( "find_thread_count", s_nFindThreadCount )
623 << std::make_pair( "map_size", s_nMapSize )
624 << std::make_pair( "pass_count", s_nInsertPassCount );
626 std::chrono::milliseconds duration = pool.run();
628 propout() << std::make_pair( "duration", duration );
630 size_t nInsertInitFailed = 0;
631 size_t nInsertInitSuccess = 0;
632 size_t nInsertSuccess = 0;
633 size_t nInsertFailed = 0;
634 size_t nDeleteSuccess = 0;
635 size_t nDeleteFailed = 0;
637 size_t nFindEvenSuccess = 0;
638 size_t nFindEvenFailed = 0;
639 size_t nFindOddSuccess = 0;
640 size_t nFindOddFailed = 0;
642 for ( size_t i = 0; i < pool.size(); ++i ) {
643 cds_test::thread& thr = pool.get( i );
644 switch ( thr.type() ) {
645 case inserter_thread:
647 insert_thread& inserter = static_cast<insert_thread&>( thr );
648 nInsertSuccess += inserter.m_nInsertSuccess;
649 nInsertFailed += inserter.m_nInsertFailed;
650 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
651 nInsertInitFailed += inserter.m_nInsertInitFailed;
656 delete_thread& deleter = static_cast<delete_thread&>( thr );
657 nDeleteSuccess += deleter.m_nDeleteSuccess;
658 nDeleteFailed += deleter.m_nDeleteFailed;
663 observer_thread& observer = static_cast<observer_thread&>( thr );
664 nFindEvenSuccess = observer.m_nFindEvenSuccess;
665 nFindEvenFailed = observer.m_nFindEvenFailed;
666 nFindOddSuccess = observer.m_nFindOddSuccess;
667 nFindOddFailed = observer.m_nFindOddFailed;
673 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
675 EXPECT_EQ( nInsertInitFailed, 0u );
676 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
677 EXPECT_EQ( nFindEvenFailed, 0u );
678 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
679 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
682 << std::make_pair( "insert_init_success", nInsertInitSuccess )
683 << std::make_pair( "insert_init_failed", nInsertInitFailed )
684 << std::make_pair( "insert_success", nInsertSuccess )
685 << std::make_pair( "insert_failed", nInsertFailed )
686 << std::make_pair( "delete_success", nDeleteSuccess )
687 << std::make_pair( "delete_failed", nDeleteFailed )
688 << std::make_pair( "find_even_success", nFindEvenSuccess )
689 << std::make_pair( "find_even_failed", nFindEvenFailed )
690 << std::make_pair( "find_odd_success", nFindOddSuccess )
691 << std::make_pair( "find_odd_failed", nFindOddFailed );
697 void do_test_extract( Map& testMap )
699 typedef Inserter<Map> insert_thread;
700 typedef Deleter<Map> delete_thread;
701 typedef Extractor< typename Map::gc, Map > extract_thread;
702 typedef Observer<Map> observer_thread;
704 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
706 cds_test::thread_pool& pool = get_pool();
707 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
708 if ( s_nDelThreadCount )
709 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
710 if ( s_nExtractThreadCount )
711 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
712 if ( s_nFindThreadCount )
713 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
715 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
716 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
717 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
718 << std::make_pair( "find_thread_count", s_nFindThreadCount )
719 << std::make_pair( "map_size", s_nMapSize )
720 << std::make_pair( "pass_count", s_nInsertPassCount );
722 std::chrono::milliseconds duration = pool.run();
724 propout() << std::make_pair( "duration", duration );
726 size_t nInsertInitFailed = 0;
727 size_t nInsertInitSuccess = 0;
728 size_t nInsertSuccess = 0;
729 size_t nInsertFailed = 0;
730 size_t nDeleteSuccess = 0;
731 size_t nDeleteFailed = 0;
732 size_t nExtractSuccess = 0;
733 size_t nExtractFailed = 0;
735 size_t nFindEvenSuccess = 0;
736 size_t nFindEvenFailed = 0;
737 size_t nFindOddSuccess = 0;
738 size_t nFindOddFailed = 0;
740 for ( size_t i = 0; i < pool.size(); ++i ) {
741 cds_test::thread& thr = pool.get( i );
742 switch ( thr.type()) {
743 case inserter_thread:
745 insert_thread& inserter = static_cast<insert_thread&>(thr);
746 nInsertSuccess += inserter.m_nInsertSuccess;
747 nInsertFailed += inserter.m_nInsertFailed;
748 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
749 nInsertInitFailed += inserter.m_nInsertInitFailed;
754 delete_thread& deleter = static_cast<delete_thread&>(thr);
755 nDeleteSuccess += deleter.m_nDeleteSuccess;
756 nDeleteFailed += deleter.m_nDeleteFailed;
759 case extractor_thread:
761 extract_thread& extractor = static_cast<extract_thread&>(thr);
762 nExtractSuccess += extractor.m_nDeleteSuccess;
763 nExtractFailed += extractor.m_nDeleteFailed;
768 observer_thread& observer = static_cast<observer_thread&>( thr );
769 nFindEvenSuccess = observer.m_nFindEvenSuccess;
770 nFindEvenFailed = observer.m_nFindEvenFailed;
771 nFindOddSuccess = observer.m_nFindOddSuccess;
772 nFindOddFailed = observer.m_nFindOddFailed;
780 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
782 EXPECT_EQ( nInsertInitFailed, 0u );
783 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
784 EXPECT_EQ( nFindEvenFailed, 0u );
785 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
786 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
789 << std::make_pair( "insert_init_success", nInsertInitSuccess )
790 << std::make_pair( "insert_init_failed", nInsertInitFailed )
791 << std::make_pair( "insert_success", nInsertSuccess )
792 << std::make_pair( "insert_failed", nInsertFailed )
793 << std::make_pair( "delete_success", nDeleteSuccess )
794 << std::make_pair( "delete_failed", nDeleteFailed )
795 << std::make_pair( "extract_success", nExtractSuccess )
796 << std::make_pair( "extract_failed", nExtractFailed )
797 << std::make_pair( "find_even_success", nFindEvenSuccess )
798 << std::make_pair( "find_even_failed", nFindEvenFailed )
799 << std::make_pair( "find_odd_success", nFindOddSuccess )
800 << std::make_pair( "find_odd_failed", nFindOddFailed );
806 void analyze( Map& testMap )
808 // All even keys must be in the map
810 for ( size_t n = 0; n < s_nMapSize; n +=2 ) {
811 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
812 EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
817 print_stat( propout(), testMap );
819 check_before_cleanup( testMap );
821 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
823 additional_check( testMap );
824 additional_cleanup( testMap );
828 void run_test_extract()
830 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
832 size_t nMapSize = s_nMapSize;
833 s_nMapSize *= s_nInsThreadCount;
835 Map testMap( *this );
837 s_nMapSize = nMapSize;
838 do_test_extract( testMap );
844 size_t nMapSize = s_nMapSize;
845 s_nMapSize *= s_nInsThreadCount;
847 Map testMap( *this );
849 s_nMapSize = nMapSize;
857 class Map_DelOdd_LF: public Map_DelOdd
858 , public ::testing::WithParamInterface<size_t>
864 s_nLoadFactor = GetParam();
865 propout() << std::make_pair( "load_factor", s_nLoadFactor );
866 Map_DelOdd::run_test<Map>();
870 void run_test_extract()
872 s_nLoadFactor = GetParam();
873 propout() << std::make_pair( "load_factor", s_nLoadFactor );
874 Map_DelOdd::run_test_extract<Map>();
877 static std::vector<size_t> get_load_factors();