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;
124 static size_t s_nCuckooInitialSize; // initial size for CuckooMap
125 static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
126 static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
128 static size_t s_nFeldmanMap_HeadBits;
129 static size_t s_nFeldmanMap_ArrayBits;
131 static size_t s_nLoadFactor; // current load factor
133 static std::vector<size_t> m_arrElements;
135 static void SetUpTestCase();
136 static void TearDownTestCase();
138 template <typename Pred>
139 static void prepare_array( std::vector<size_t>& arr, Pred pred )
141 arr.reserve( m_arrElements.size() );
142 for ( auto el : m_arrElements ) {
146 arr.resize( arr.size() );
147 shuffle( arr.begin(), arr.end() );
151 typedef key_thread key_type;
152 typedef size_t value_type;
153 typedef std::pair<key_type const, value_type> pair_type;
155 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_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
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)
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 & 1 ) != 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_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
340 size_t const nInsThreadCount = s_nInsThreadCount;
344 for ( auto el: m_arr ) {
345 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
346 if ( rMap.erase( key_type( el, k )))
354 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
355 for ( auto el: m_arr ) {
356 if ( rMap.erase( key_type( el, k ) ) )
363 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
369 // Deletes odd keys from [0..N)
370 template <class GC, class Map >
371 class Extractor: public cds_test::thread
373 typedef cds_test::thread base_class;
378 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
382 size_t m_nDeleteSuccess = 0;
383 size_t m_nDeleteFailed = 0;
385 std::vector<size_t> m_arr;
388 Extractor( cds_test::thread_pool& pool, Map& map )
389 : base_class( pool, extractor_thread )
395 Extractor( Extractor& src )
402 virtual thread * clone()
404 return new Extractor( *this );
411 typename Map::guarded_ptr gp;
412 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
413 size_t const nInsThreadCount = s_nInsThreadCount;
417 for ( auto el : m_arr ) {
418 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
419 gp = rMap.extract( key_type( el, k ));
429 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
430 for ( auto el: m_arr ) {
431 gp = rMap.extract( key_type( el, k ) );
440 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
446 template <class RCU, class Map >
447 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
449 typedef cds_test::thread base_class;
454 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
458 size_t m_nDeleteSuccess = 0;
459 size_t m_nDeleteFailed = 0;
461 std::vector<size_t> m_arr;
464 Extractor( cds_test::thread_pool& pool, Map& map )
465 : base_class( pool, extractor_thread )
471 Extractor( Extractor& src )
478 virtual thread * clone()
480 return new Extractor( *this );
486 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
488 typename Map::exempt_ptr xp;
489 size_t const nInsThreadCount = s_nInsThreadCount;
493 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
494 for ( auto el: m_arr ) {
495 if ( Map::c_bExtractLockExternal ) {
496 typename Map::rcu_lock l;
497 xp = rMap.extract( key_type( el, k ) );
504 xp = rMap.extract( key_type( el, k ) );
515 for ( auto el : m_arr ) {
516 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
517 if ( Map::c_bExtractLockExternal ) {
518 typename Map::rcu_lock l;
519 xp = rMap.extract( key_type( el, k ) );
526 xp = rMap.extract( key_type( el, k ) );
536 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
544 void do_test( Map& testMap )
546 typedef Inserter<Map> insert_thread;
547 typedef Deleter<Map> delete_thread;
549 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
551 cds_test::thread_pool& pool = get_pool();
552 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
553 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
555 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
556 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
557 << std::make_pair( "map_size", s_nMapSize )
558 << std::make_pair( "pass_count", s_nInsertPassCount );
560 std::chrono::milliseconds duration = pool.run();
562 propout() << std::make_pair( "duration", duration );
564 size_t nInsertInitFailed = 0;
565 size_t nInsertInitSuccess = 0;
566 size_t nInsertSuccess = 0;
567 size_t nInsertFailed = 0;
568 size_t nDeleteSuccess = 0;
569 size_t nDeleteFailed = 0;
571 for ( size_t i = 0; i < pool.size(); ++i ) {
572 cds_test::thread& thr = pool.get( i );
573 if ( thr.type() == inserter_thread ) {
574 insert_thread& inserter = static_cast<insert_thread&>(thr);
575 nInsertSuccess += inserter.m_nInsertSuccess;
576 nInsertFailed += inserter.m_nInsertFailed;
577 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
578 nInsertInitFailed += inserter.m_nInsertInitFailed;
581 assert( thr.type() == deleter_thread );
582 delete_thread& deleter = static_cast<delete_thread&>(thr);
583 nDeleteSuccess += deleter.m_nDeleteSuccess;
584 nDeleteFailed += deleter.m_nDeleteFailed;
588 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
590 EXPECT_EQ( nInsertInitFailed, 0u );
591 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
592 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
593 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
596 << std::make_pair( "insert_init_success", nInsertInitSuccess )
597 << std::make_pair( "insert_init_failed", nInsertInitFailed )
598 << std::make_pair( "insert_success", nInsertSuccess )
599 << std::make_pair( "insert_failed", nInsertFailed )
600 << std::make_pair( "delete_success", nDeleteSuccess )
601 << std::make_pair( "delete_failed", nDeleteFailed );
607 void do_test_extract( Map& testMap )
609 typedef Inserter<Map> insert_thread;
610 typedef Deleter<Map> delete_thread;
611 typedef Extractor< typename Map::gc, Map > extract_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 if ( s_nDelThreadCount )
618 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
619 if ( s_nExtractThreadCount )
620 pool.add( new extract_thread( pool, testMap ), s_nExtractThreadCount );
622 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
623 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
624 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
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;
638 size_t nExtractSuccess = 0;
639 size_t nExtractFailed = 0;
640 for ( size_t i = 0; i < pool.size(); ++i ) {
641 cds_test::thread& thr = pool.get( i );
642 switch ( thr.type()) {
643 case inserter_thread:
645 insert_thread& inserter = static_cast<insert_thread&>(thr);
646 nInsertSuccess += inserter.m_nInsertSuccess;
647 nInsertFailed += inserter.m_nInsertFailed;
648 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
649 nInsertInitFailed += inserter.m_nInsertInitFailed;
654 delete_thread& deleter = static_cast<delete_thread&>(thr);
655 nDeleteSuccess += deleter.m_nDeleteSuccess;
656 nDeleteFailed += deleter.m_nDeleteFailed;
659 case extractor_thread:
661 extract_thread& extractor = static_cast<extract_thread&>(thr);
662 nExtractSuccess += extractor.m_nDeleteSuccess;
663 nExtractFailed += extractor.m_nDeleteFailed;
671 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) / 2;
673 EXPECT_EQ( nInsertInitFailed, 0u );
674 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
675 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
676 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
679 << std::make_pair( "insert_init_success", nInsertInitSuccess )
680 << std::make_pair( "insert_init_failed", nInsertInitFailed )
681 << std::make_pair( "insert_success", nInsertSuccess )
682 << std::make_pair( "insert_failed", nInsertFailed )
683 << std::make_pair( "delete_success", nDeleteSuccess )
684 << std::make_pair( "delete_failed", nDeleteFailed )
685 << std::make_pair( "extract_success", nExtractSuccess )
686 << std::make_pair( "extract_failed", nExtractFailed );
692 void analyze( Map& testMap )
694 // All even keys must be in the map
696 for ( size_t n = 0; n < s_nMapSize; n +=2 ) {
697 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
698 EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
703 print_stat( propout(), testMap );
705 check_before_cleanup( testMap );
707 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
709 additional_check( testMap );
710 additional_cleanup( testMap );
714 void run_test_extract()
716 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
718 size_t nMapSize = s_nMapSize;
719 s_nMapSize *= s_nInsThreadCount;
721 Map testMap( *this );
723 s_nMapSize = nMapSize;
724 do_test_extract( testMap );
730 size_t nMapSize = s_nMapSize;
731 s_nMapSize *= s_nInsThreadCount;
733 Map testMap( *this );
735 s_nMapSize = nMapSize;
743 class Map_DelOdd_LF: public Map_DelOdd
744 , public ::testing::WithParamInterface<size_t>
750 s_nLoadFactor = GetParam();
751 propout() << std::make_pair( "load_factor", s_nLoadFactor );
752 Map_DelOdd::run_test<Map>();
756 void run_test_extract()
758 s_nLoadFactor = GetParam();
759 propout() << std::make_pair( "load_factor", s_nLoadFactor );
760 Map_DelOdd::run_test_extract<Map>();
763 static std::vector<size_t> get_load_factors();