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))
51 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
54 struct cmp<key_thread> {
55 int operator ()(key_thread const& k1, key_thread const& k2) const
57 if ( k1.nKey < k2.nKey )
59 if ( k1.nKey > k2.nKey )
61 if ( k1.nThread < k2.nThread )
63 if ( k1.nThread > k2.nThread )
67 int operator ()(key_thread const& k1, size_t k2) const
75 int operator ()(size_t k1, key_thread const& k2) const
86 struct less<set::key_thread>
88 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
90 if ( k1.nKey <= k2.nKey )
91 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
97 struct hash<set::key_thread>
99 typedef size_t result_type;
100 typedef set::key_thread argument_type;
102 size_t operator()( set::key_thread const& k ) const
104 return std::hash<size_t>()(k.nKey);
106 size_t operator()( size_t k ) const
108 return std::hash<size_t>()(k);
113 class Set_DelOdd: public cds_test::stress_fixture
116 static size_t s_nSetSize; // max set size
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_nMaxLoadFactor; // maximum load factor
122 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
123 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
124 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
126 static size_t s_nFeldmanSet_HeadBits;
127 static size_t s_nFeldmanSet_ArrayBits;
129 static size_t s_nLoadFactor;
131 static std::vector<size_t> m_arrData;
133 static void SetUpTestCase();
134 static void TearDownTestCase();
137 typedef key_thread key_type;
138 typedef size_t value_type;
140 atomics::atomic<size_t> m_nInsThreadCount;
149 // Inserts keys from [0..N)
151 class Inserter: public cds_test::thread
153 typedef cds_test::thread base_class;
156 struct update_functor
158 template <typename Q>
159 void operator()( bool /*bNew*/, key_value_pair const&, Q const& )
162 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/)
166 size_t m_nInsertSuccess = 0;
167 size_t m_nInsertFailed = 0;
170 Inserter( cds_test::thread_pool& pool, Set& set )
171 : base_class( pool, inserter_thread )
175 Inserter( Inserter& src )
180 virtual thread * clone()
182 return new Inserter( *this );
188 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
190 std::vector<size_t>& arrData = fixture.m_arrData;
191 for ( size_t i = 0; i < arrData.size(); ++i ) {
192 if ( rSet.insert( key_type( arrData[i], id() )))
199 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
200 if ( arrData[i] & 1 )
201 rSet.update( key_type( arrData[i], id() ), f, true );
204 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
209 bool operator()( key_type const& k1, key_type const& k2 ) const
211 return k1.nKey == k2.nKey;
213 bool operator()( size_t k1, key_type const& k2 ) const
215 return k1 == k2.nKey;
217 bool operator()( key_type const& k1, size_t k2 ) const
219 return k1.nKey == k2;
221 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
223 return operator()( k1.key, k2.key );
225 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
227 return operator()( k1.key, k2 );
229 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
231 return operator()( k1, k2.key );
233 bool operator ()( key_value_pair const& k1, size_t k2 ) const
235 return operator()( k1.key, k2 );
237 bool operator ()( size_t k1, key_value_pair const& k2 ) const
239 return operator()( k1, k2.key );
244 bool operator()( key_type const& k1, key_type const& k2 ) const
246 return k1.nKey < k2.nKey;
248 bool operator()( size_t k1, key_type const& k2 ) const
252 bool operator()( key_type const& k1, size_t k2 ) const
256 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
258 return operator()( k1.key, k2.key );
260 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
262 return operator()( k1.key, k2 );
264 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
266 return operator()( k1, k2.key );
268 bool operator ()( key_value_pair const& k1, size_t k2 ) const
270 return operator()( k1.key, k2 );
272 bool operator ()( size_t k1, key_value_pair const& k2 ) const
274 return operator()( k1, k2.key );
277 typedef key_equal equal_to;
280 // Deletes odd keys from [0..N)
282 class Deleter: public cds_test::thread
284 typedef cds_test::thread base_class;
288 size_t m_nDeleteSuccess = 0;
289 size_t m_nDeleteFailed = 0;
292 Deleter( cds_test::thread_pool& pool, Set& set )
293 : base_class( pool, deleter_thread )
296 Deleter( Deleter& src )
301 virtual thread * clone()
303 return new Deleter( *this );
306 template <typename SetType, bool>
308 static bool erase( SetType& s, size_t key, size_t /*thread*/)
310 return s.erase_with( key, key_less() );
314 template <typename SetType>
315 struct eraser<SetType, true> {
316 static bool erase(SetType& s, size_t key, size_t thread)
318 return s.erase( key_type(key, thread));
326 size_t const nInsThreadCount = s_nInsThreadCount;
327 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
328 std::vector<size_t>& arrData = fixture.m_arrData;
331 for (size_t i = 0; i < arrData.size(); ++i) {
332 if ( arrData[i] & 1 ) {
333 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
334 if ( eraser<Set, Set::c_bEraseExactKey>::erase( rSet, arrData[i], k ))
340 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
345 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
346 if ( arrData[i] & 1 ) {
347 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
348 if (eraser<Set, Set::c_bEraseExactKey>::erase(rSet, arrData[i], k))
354 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
361 // Extracts odd keys from [0..N)
362 template <typename GC, class Set>
363 class Extractor: public cds_test::thread
365 typedef cds_test::thread base_class;
369 size_t m_nExtractSuccess = 0;
370 size_t m_nExtractFailed = 0;
373 Extractor( cds_test::thread_pool& pool, Set& set )
374 : base_class( pool, extractor_thread )
378 Extractor( Extractor& src )
383 virtual thread * clone()
385 return new Extractor( *this );
388 template <typename SetType, bool>
390 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t /*thread*/)
392 return s.extract_with( key, key_less());
396 template <typename SetType>
397 struct extractor<SetType, true> {
398 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t thread)
400 return s.extract( key_type(key, thread));
408 typename Set::guarded_ptr gp;
410 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
411 std::vector<size_t>& arrData = fixture.m_arrData;
412 size_t const nInsThreadCount = s_nInsThreadCount;
415 for ( size_t i = 0; i < arrData.size(); ++i ) {
416 if ( arrData[i] & 1 ) {
417 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
418 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k );
426 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
431 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
432 if ( arrData[i] & 1 ) {
433 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
434 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
442 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
449 template <typename RCU, class Set>
450 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
452 typedef cds_test::thread base_class;
456 size_t m_nExtractSuccess = 0;
457 size_t m_nExtractFailed = 0;
460 Extractor( cds_test::thread_pool& pool, Set& set )
461 : base_class( pool, extractor_thread )
465 Extractor( Extractor& src )
470 virtual thread * clone()
472 return new Extractor( *this );
475 template <typename SetType, bool>
477 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t /*thread*/)
479 return s.extract_with(key, key_less());
483 template <typename SetType>
484 struct extractor<SetType, true> {
485 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t thread)
487 return s.extract(key_type(key, thread));
495 typename Set::exempt_ptr xp;
497 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
498 std::vector<size_t>& arrData = fixture.m_arrData;
499 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
502 for ( size_t i = 0; i < arrData.size(); ++i ) {
503 if ( arrData[i] & 1 ) {
504 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
505 if ( Set::c_bExtractLockExternal ) {
506 typename Set::rcu_lock l;
507 xp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
514 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
523 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
528 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
529 if ( arrData[i] & 1 ) {
530 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
531 if ( Set::c_bExtractLockExternal ) {
532 typename Set::rcu_lock l;
533 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
540 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
549 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
558 void do_test_with( Set& testSet )
560 typedef Inserter<Set> insert_thread;
561 typedef Deleter<Set> delete_thread;
563 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
565 cds_test::thread_pool& pool = get_pool();
566 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
567 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
569 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
570 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
571 << std::make_pair( "set_size", s_nSetSize );
573 std::chrono::milliseconds duration = pool.run();
575 propout() << std::make_pair( "duration", duration );
577 size_t nInsertSuccess = 0;
578 size_t nInsertFailed = 0;
579 size_t nDeleteSuccess = 0;
580 size_t nDeleteFailed = 0;
582 for ( size_t i = 0; i < pool.size(); ++i ) {
583 cds_test::thread& thr = pool.get( i );
584 if ( thr.type() == inserter_thread ) {
585 insert_thread& inserter = static_cast<insert_thread&>(thr);
586 nInsertSuccess += inserter.m_nInsertSuccess;
587 nInsertFailed += inserter.m_nInsertFailed;
590 assert( thr.type() == deleter_thread );
591 delete_thread& deleter = static_cast<delete_thread&>(thr);
592 nDeleteSuccess += deleter.m_nDeleteSuccess;
593 nDeleteFailed += deleter.m_nDeleteFailed;
597 EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount );
598 EXPECT_EQ( nInsertFailed, 0 );
601 << std::make_pair( "insert_success", nInsertSuccess )
602 << std::make_pair( "insert_failed", nInsertFailed )
603 << std::make_pair( "delete_success", nDeleteSuccess )
604 << std::make_pair( "delete_failed", nDeleteFailed );
608 void do_test_extract_with( Set& testSet )
610 typedef Inserter<Set> insert_thread;
611 typedef Deleter<Set> delete_thread;
612 typedef Extractor< typename Set::gc, Set > extract_thread;
614 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
616 cds_test::thread_pool& pool = get_pool();
617 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
618 if ( s_nDelThreadCount )
619 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
620 if ( s_nExtractThreadCount )
621 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
623 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
624 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
625 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
626 << std::make_pair( "set_size", s_nSetSize );
628 std::chrono::milliseconds duration = pool.run();
630 propout() << std::make_pair( "duration", duration );
632 size_t nInsertSuccess = 0;
633 size_t nInsertFailed = 0;
634 size_t nDeleteSuccess = 0;
635 size_t nDeleteFailed = 0;
636 size_t nExtractSuccess = 0;
637 size_t nExtractFailed = 0;
638 for ( size_t i = 0; i < pool.size(); ++i ) {
639 cds_test::thread& thr = pool.get( i );
640 switch ( thr.type() ) {
641 case inserter_thread:
643 insert_thread& inserter = static_cast<insert_thread&>( thr );
644 nInsertSuccess += inserter.m_nInsertSuccess;
645 nInsertFailed += inserter.m_nInsertFailed;
650 delete_thread& deleter = static_cast<delete_thread&>(thr);
651 nDeleteSuccess += deleter.m_nDeleteSuccess;
652 nDeleteFailed += deleter.m_nDeleteFailed;
655 case extractor_thread:
657 extract_thread& extractor = static_cast<extract_thread&>(thr);
658 nExtractSuccess += extractor.m_nExtractSuccess;
659 nExtractFailed += extractor.m_nExtractFailed;
667 EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount );
668 EXPECT_EQ( nInsertFailed, 0 );
671 << std::make_pair( "insert_success", nInsertSuccess )
672 << std::make_pair( "insert_failed", nInsertFailed )
673 << std::make_pair( "delete_success", nDeleteSuccess )
674 << std::make_pair( "delete_failed", nDeleteFailed )
675 << std::make_pair( "extract_success", nExtractSuccess )
676 << std::make_pair( "extract_failed", nExtractFailed );
679 template <typename Set>
680 void analyze( Set& testSet )
682 // All even keys must be in the set
684 for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
685 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
686 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
691 check_before_clear( testSet );
694 EXPECT_TRUE( testSet.empty() ) << "set.size=" << testSet.size();
696 additional_check( testSet );
697 print_stat( propout(), testSet );
698 additional_cleanup( testSet );
704 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
706 Set testSet( *this );
707 do_test_with( testSet );
712 void run_test_extract()
714 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
716 Set testSet( *this );
717 do_test_extract_with( testSet );
722 class Set_DelOdd_LF: public Set_DelOdd
723 , public ::testing::WithParamInterface<size_t>
729 s_nLoadFactor = GetParam();
730 propout() << std::make_pair( "load_factor", s_nLoadFactor );
731 Set_DelOdd::run_test<Set>();
735 void run_test_extract()
737 s_nLoadFactor = GetParam();
738 propout() << std::make_pair( "load_factor", s_nLoadFactor );
739 Set_DelOdd::run_test_extract<Set>();
742 static std::vector<size_t> get_load_factors();