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.
40 key_thread( size_t key, size_t threadNo )
41 : nKey( static_cast<uint32_t>(key))
42 , nThread( static_cast<uint16_t>(threadNo))
51 static_assert(sizeof( key_thread ) % 8 == 0, "Key type size mismatch");
53 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
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<set::key_thread>
90 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
92 if ( k1.nKey <= k2.nKey )
93 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
99 struct hash<set::key_thread>
101 typedef size_t result_type;
102 typedef set::key_thread argument_type;
104 size_t operator()( set::key_thread const& k ) const
106 return std::hash<size_t>()(k.nKey);
109 size_t operator()( size_t k ) const
111 return std::hash<size_t>()(k);
116 class Set_DelOdd: public cds_test::stress_fixture
119 static size_t s_nSetSize; // max set size
120 static size_t s_nInsThreadCount; // insert thread count
121 static size_t s_nDelThreadCount; // delete thread count
122 static size_t s_nExtractThreadCount; // extract thread count
123 static size_t s_nMaxLoadFactor; // maximum load factor
124 static size_t s_nInsertPassCount;
126 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
127 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
128 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
130 static size_t s_nFeldmanSet_HeadBits;
131 static size_t s_nFeldmanSet_ArrayBits;
133 static size_t s_nLoadFactor;
135 static std::vector<size_t> m_arrData;
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_arrData.size() );
144 for ( auto el : m_arrData ) {
148 arr.resize( arr.size() );
149 shuffle( arr.begin(), arr.end() );
153 typedef key_thread key_type;
154 typedef size_t value_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;
172 struct update_functor
174 template <typename Q>
175 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
178 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
184 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
185 for ( size_t i = 0; i < m_arr.size(); ++i ) {
186 if ( m_Set.insert( key_type( m_arr[i], id() ) ) )
187 ++m_nInsertInitSuccess;
189 ++m_nInsertInitFailed;
194 size_t m_nInsertSuccess = 0;
195 size_t m_nInsertFailed = 0;
196 size_t m_nInsertInitSuccess = 0;
197 size_t m_nInsertInitFailed = 0;
199 std::vector<size_t> m_arr;
202 Inserter( cds_test::thread_pool& pool, Set& set )
203 : base_class( pool, inserter_thread )
209 Inserter( Inserter& src )
216 virtual thread * clone()
218 return new Inserter( *this );
224 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
226 for ( size_t nPass = 0; nPass < s_nInsertPassCount; ++nPass ) {
229 for ( auto el : m_arr ) {
231 if ( rSet.insert( key_type( el, id() ) ) )
240 for ( auto el : m_arr ) {
244 std::tie( success, inserted ) = rSet.update( key_type( el, id() ), update_functor() );
245 if ( success && inserted )
254 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
260 bool operator()( key_type const& k1, key_type const& k2 ) const
262 return k1.nKey == k2.nKey;
264 bool operator()( size_t k1, key_type const& k2 ) const
266 return k1 == k2.nKey;
268 bool operator()( key_type const& k1, size_t k2 ) const
270 return k1.nKey == k2;
272 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
274 return operator()( k1.key, k2.key );
276 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
278 return operator()( k1.key, k2 );
280 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
282 return operator()( k1, k2.key );
284 bool operator ()( key_value_pair const& k1, size_t k2 ) const
286 return operator()( k1.key, k2 );
288 bool operator ()( size_t k1, key_value_pair const& k2 ) const
290 return operator()( k1, k2.key );
295 bool operator()( key_type const& k1, key_type const& k2 ) const
297 return k1.nKey < k2.nKey;
299 bool operator()( size_t k1, key_type const& k2 ) const
303 bool operator()( key_type const& k1, size_t k2 ) const
307 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
309 return operator()( k1.key, k2.key );
311 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
313 return operator()( k1.key, k2 );
315 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
317 return operator()( k1, k2.key );
319 bool operator ()( key_value_pair const& k1, size_t k2 ) const
321 return operator()( k1.key, k2 );
323 bool operator ()( size_t k1, key_value_pair const& k2 ) const
325 return operator()( k1, k2.key );
328 typedef key_equal equal_to;
331 // Deletes odd keys from [0..N)
333 class Deleter: public cds_test::thread
335 typedef cds_test::thread base_class;
340 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
344 size_t m_nDeleteSuccess = 0;
345 size_t m_nDeleteFailed = 0;
347 std::vector<size_t> m_arr;
350 Deleter( cds_test::thread_pool& pool, Set& set )
351 : base_class( pool, deleter_thread )
356 Deleter( Deleter& src )
363 virtual thread * clone()
365 return new Deleter( *this );
368 template <typename SetType, bool>
370 static bool erase( SetType& s, size_t key, size_t /*thread*/)
372 return s.erase_with( key, key_less());
376 template <typename SetType>
377 struct eraser<SetType, true> {
378 static bool erase(SetType& s, size_t key, size_t thread)
380 return s.erase( key_type(key, thread));
388 size_t const nInsThreadCount = s_nInsThreadCount;
389 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
393 for ( auto el : m_arr ) {
394 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
395 if ( rSet.erase( key_type( el, k ) ) )
403 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
404 for ( auto el : m_arr ) {
405 if ( rSet.erase( key_type( el, k ) ) )
412 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
418 // Extracts odd keys from [0..N)
419 template <typename GC, class Set>
420 class Extractor: public cds_test::thread
422 typedef cds_test::thread base_class;
425 std::vector<size_t> m_arr;
429 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 1 ) != 0; } );
433 size_t m_nExtractSuccess = 0;
434 size_t m_nExtractFailed = 0;
437 Extractor( cds_test::thread_pool& pool, Set& set )
438 : base_class( pool, extractor_thread )
444 Extractor( Extractor& src )
451 virtual thread * clone()
453 return new Extractor( *this );
459 typename Set::guarded_ptr gp;
461 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
462 size_t const nInsThreadCount = s_nInsThreadCount;
466 for ( auto el : m_arr ) {
467 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
468 gp = rSet.extract( key_type( el, k ) );
478 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
479 for ( auto el : m_arr ) {
480 gp = rSet.extract( key_type( el, k ) );
489 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
495 template <typename RCU, class Set>
496 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
498 typedef cds_test::thread base_class;
500 std::vector<size_t> m_arr;
504 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 1 ) != 0; } );
508 size_t m_nExtractSuccess = 0;
509 size_t m_nExtractFailed = 0;
512 Extractor( cds_test::thread_pool& pool, Set& set )
513 : base_class( pool, extractor_thread )
519 Extractor( Extractor& src )
526 virtual thread * clone()
528 return new Extractor( *this );
534 typename Set::exempt_ptr xp;
536 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
537 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
541 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
542 for ( auto el : m_arr ) {
543 if ( Set::c_bExtractLockExternal ) {
544 typename Set::rcu_lock l;
545 xp = rSet.extract( key_type( el, k ) );
552 xp = rSet.extract( key_type( el, k ) );
563 for ( auto el : m_arr ) {
564 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
565 if ( Set::c_bExtractLockExternal ) {
566 typename Set::rcu_lock l;
567 xp = rSet.extract( key_type( el, k ) );
574 xp = rSet.extract( key_type( el, k ) );
584 } while ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) != 0 );
592 void do_test_with( Set& testSet )
594 typedef Inserter<Set> insert_thread;
595 typedef Deleter<Set> delete_thread;
597 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
599 cds_test::thread_pool& pool = get_pool();
600 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
601 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
603 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
604 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
605 << std::make_pair( "set_size", s_nSetSize )
606 << std::make_pair( "pass_count", s_nInsertPassCount );
608 std::chrono::milliseconds duration = pool.run();
610 propout() << std::make_pair( "duration", duration );
612 size_t nInsertInitFailed = 0;
613 size_t nInsertInitSuccess = 0;
614 size_t nInsertSuccess = 0;
615 size_t nInsertFailed = 0;
616 size_t nDeleteSuccess = 0;
617 size_t nDeleteFailed = 0;
619 for ( size_t i = 0; i < pool.size(); ++i ) {
620 cds_test::thread& thr = pool.get( i );
621 if ( thr.type() == inserter_thread ) {
622 insert_thread& inserter = static_cast<insert_thread&>(thr);
623 nInsertSuccess += inserter.m_nInsertSuccess;
624 nInsertFailed += inserter.m_nInsertFailed;
625 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
626 nInsertInitFailed += inserter.m_nInsertInitFailed;
629 assert( thr.type() == deleter_thread );
630 delete_thread& deleter = static_cast<delete_thread&>(thr);
631 nDeleteSuccess += deleter.m_nDeleteSuccess;
632 nDeleteFailed += deleter.m_nDeleteFailed;
636 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
638 EXPECT_EQ( nInsertInitFailed, 0u );
639 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
640 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
641 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
644 << std::make_pair( "insert_init_success", nInsertInitSuccess )
645 << std::make_pair( "insert_init_failed", nInsertInitFailed )
646 << std::make_pair( "insert_success", nInsertSuccess )
647 << std::make_pair( "insert_failed", nInsertFailed )
648 << std::make_pair( "delete_success", nDeleteSuccess )
649 << std::make_pair( "delete_failed", nDeleteFailed );
653 void do_test_extract_with( Set& testSet )
655 typedef Inserter<Set> insert_thread;
656 typedef Deleter<Set> delete_thread;
657 typedef Extractor< typename Set::gc, Set > extract_thread;
659 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
661 cds_test::thread_pool& pool = get_pool();
662 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
663 if ( s_nDelThreadCount )
664 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
665 if ( s_nExtractThreadCount )
666 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
668 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
669 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
670 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
671 << std::make_pair( "set_size", s_nSetSize )
672 << std::make_pair( "pass_count", s_nInsertPassCount );
674 std::chrono::milliseconds duration = pool.run();
676 propout() << std::make_pair( "duration", duration );
678 size_t nInsertInitFailed = 0;
679 size_t nInsertInitSuccess = 0;
680 size_t nInsertSuccess = 0;
681 size_t nInsertFailed = 0;
682 size_t nDeleteSuccess = 0;
683 size_t nDeleteFailed = 0;
684 size_t nExtractSuccess = 0;
685 size_t nExtractFailed = 0;
686 for ( size_t i = 0; i < pool.size(); ++i ) {
687 cds_test::thread& thr = pool.get( i );
688 switch ( thr.type()) {
689 case inserter_thread:
691 insert_thread& inserter = static_cast<insert_thread&>( thr );
692 nInsertSuccess += inserter.m_nInsertSuccess;
693 nInsertFailed += inserter.m_nInsertFailed;
694 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
695 nInsertInitFailed += inserter.m_nInsertInitFailed;
700 delete_thread& deleter = static_cast<delete_thread&>(thr);
701 nDeleteSuccess += deleter.m_nDeleteSuccess;
702 nDeleteFailed += deleter.m_nDeleteFailed;
705 case extractor_thread:
707 extract_thread& extractor = static_cast<extract_thread&>(thr);
708 nExtractSuccess += extractor.m_nExtractSuccess;
709 nExtractFailed += extractor.m_nExtractFailed;
717 size_t const nInitialOddKeys = ( s_nSetSize * s_nInsThreadCount ) / 2;
719 EXPECT_EQ( nInsertInitFailed, 0u );
720 EXPECT_EQ( nInsertInitSuccess, s_nSetSize * s_nInsThreadCount );
721 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess + nExtractSuccess );
722 EXPECT_LE( nInsertSuccess, nDeleteSuccess + nExtractSuccess );
725 << std::make_pair( "insert_init_success", nInsertInitSuccess )
726 << std::make_pair( "insert_init_failed", nInsertInitFailed )
727 << std::make_pair( "insert_success", nInsertSuccess )
728 << std::make_pair( "insert_failed", nInsertFailed )
729 << std::make_pair( "delete_success", nDeleteSuccess )
730 << std::make_pair( "delete_failed", nDeleteFailed )
731 << std::make_pair( "extract_success", nExtractSuccess )
732 << std::make_pair( "extract_failed", nExtractFailed );
735 template <typename Set>
736 void analyze( Set& testSet )
738 // All even keys must be in the set
740 for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
741 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
742 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
747 check_before_clear( testSet );
750 EXPECT_TRUE( testSet.empty()) << "set.size=" << testSet.size();
752 additional_check( testSet );
753 print_stat( propout(), testSet );
754 additional_cleanup( testSet );
760 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
762 Set testSet( *this );
763 do_test_with( testSet );
768 void run_test_extract()
770 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
772 Set testSet( *this );
773 do_test_extract_with( testSet );
781 class Set_DelOdd_LF: public Set_DelOdd
782 , public ::testing::WithParamInterface<size_t>
788 s_nLoadFactor = GetParam();
789 propout() << std::make_pair( "load_factor", s_nLoadFactor );
790 Set_DelOdd::run_test<Set>();
794 void run_test_extract()
796 s_nLoadFactor = GetParam();
797 propout() << std::make_pair( "load_factor", s_nLoadFactor );
798 Set_DelOdd::run_test_extract<Set>();
801 static std::vector<size_t> get_load_factors();