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))
54 typedef set_type_base<key_thread, size_t>::key_val key_value_pair;
57 struct cmp<key_thread> {
58 int operator ()(key_thread const& k1, key_thread const& k2) const
60 if ( k1.nKey < k2.nKey )
62 if ( k1.nKey > k2.nKey )
64 if ( k1.nThread < k2.nThread )
66 if ( k1.nThread > k2.nThread )
70 int operator ()(key_thread const& k1, size_t k2) const
78 int operator ()(size_t k1, key_thread const& k2) const
89 struct less<set::key_thread>
91 bool operator()( set::key_thread const& k1, set::key_thread const& k2 ) const
93 if ( k1.nKey <= k2.nKey )
94 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
100 struct hash<set::key_thread>
102 typedef size_t result_type;
103 typedef set::key_thread argument_type;
105 size_t operator()( set::key_thread const& k ) const
107 return std::hash<size_t>()(k.nKey);
110 size_t operator()( size_t k ) const
112 return std::hash<size_t>()(k);
117 class Set_DelOdd: public cds_test::stress_fixture
120 static size_t s_nSetSize; // max set size
121 static size_t s_nInsThreadCount; // insert thread count
122 static size_t s_nDelThreadCount; // delete thread count
123 static size_t s_nExtractThreadCount; // extract thread count
124 static size_t s_nMaxLoadFactor; // maximum load factor
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();
141 typedef key_thread key_type;
142 typedef size_t value_type;
144 atomics::atomic<size_t> m_nInsThreadCount;
153 // Inserts keys from [0..N)
155 class Inserter: public cds_test::thread
157 typedef cds_test::thread base_class;
160 struct update_functor
162 template <typename Q>
163 void operator()( bool /*bNew*/, key_value_pair const&, Q const& ) const
166 void operator()(key_value_pair& /*cur*/, key_value_pair * /*prev*/) const
170 size_t m_nInsertSuccess = 0;
171 size_t m_nInsertFailed = 0;
174 Inserter( cds_test::thread_pool& pool, Set& set )
175 : base_class( pool, inserter_thread )
179 Inserter( Inserter& src )
184 virtual thread * clone()
186 return new Inserter( *this );
192 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
194 std::vector<size_t>& arrData = fixture.m_arrData;
195 for ( size_t i = 0; i < arrData.size(); ++i ) {
196 if ( rSet.insert( key_type( arrData[i], id() )))
203 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
204 if ( arrData[i] & 1 )
205 rSet.update( key_type( arrData[i], id() ), f, true );
208 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_release );
213 bool operator()( key_type const& k1, key_type const& k2 ) const
215 return k1.nKey == k2.nKey;
217 bool operator()( size_t k1, key_type const& k2 ) const
219 return k1 == k2.nKey;
221 bool operator()( key_type const& k1, size_t k2 ) const
223 return k1.nKey == k2;
225 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
227 return operator()( k1.key, k2.key );
229 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
231 return operator()( k1.key, k2 );
233 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
235 return operator()( k1, k2.key );
237 bool operator ()( key_value_pair const& k1, size_t k2 ) const
239 return operator()( k1.key, k2 );
241 bool operator ()( size_t k1, key_value_pair const& k2 ) const
243 return operator()( k1, k2.key );
248 bool operator()( key_type const& k1, key_type const& k2 ) const
250 return k1.nKey < k2.nKey;
252 bool operator()( size_t k1, key_type const& k2 ) const
256 bool operator()( key_type const& k1, size_t k2 ) const
260 bool operator ()( key_value_pair const& k1, key_value_pair const& k2 ) const
262 return operator()( k1.key, k2.key );
264 bool operator ()( key_value_pair const& k1, key_type const& k2 ) const
266 return operator()( k1.key, k2 );
268 bool operator ()( key_type const& k1, key_value_pair const& k2 ) const
270 return operator()( k1, k2.key );
272 bool operator ()( key_value_pair const& k1, size_t k2 ) const
274 return operator()( k1.key, k2 );
276 bool operator ()( size_t k1, key_value_pair const& k2 ) const
278 return operator()( k1, k2.key );
281 typedef key_equal equal_to;
284 // Deletes odd keys from [0..N)
286 class Deleter: public cds_test::thread
288 typedef cds_test::thread base_class;
292 size_t m_nDeleteSuccess = 0;
293 size_t m_nDeleteFailed = 0;
296 Deleter( cds_test::thread_pool& pool, Set& set )
297 : base_class( pool, deleter_thread )
300 Deleter( Deleter& src )
305 virtual thread * clone()
307 return new Deleter( *this );
310 template <typename SetType, bool>
312 static bool erase( SetType& s, size_t key, size_t /*thread*/)
314 return s.erase_with( key, key_less() );
318 template <typename SetType>
319 struct eraser<SetType, true> {
320 static bool erase(SetType& s, size_t key, size_t thread)
322 return s.erase( key_type(key, thread));
330 size_t const nInsThreadCount = s_nInsThreadCount;
331 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
332 std::vector<size_t>& arrData = fixture.m_arrData;
335 for (size_t i = 0; i < arrData.size(); ++i) {
336 if ( arrData[i] & 1 ) {
337 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
338 if ( eraser<Set, Set::c_bEraseExactKey>::erase( rSet, arrData[i], k ))
344 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
349 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
350 if ( arrData[i] & 1 ) {
351 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
352 if (eraser<Set, Set::c_bEraseExactKey>::erase(rSet, arrData[i], k))
358 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
365 // Extracts odd keys from [0..N)
366 template <typename GC, class Set>
367 class Extractor: public cds_test::thread
369 typedef cds_test::thread base_class;
373 size_t m_nExtractSuccess = 0;
374 size_t m_nExtractFailed = 0;
377 Extractor( cds_test::thread_pool& pool, Set& set )
378 : base_class( pool, extractor_thread )
382 Extractor( Extractor& src )
387 virtual thread * clone()
389 return new Extractor( *this );
392 template <typename SetType, bool>
394 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t /*thread*/)
396 return s.extract_with( key, key_less());
400 template <typename SetType>
401 struct extractor<SetType, true> {
402 static typename SetType::guarded_ptr extract(SetType& s, size_t key, size_t thread)
404 return s.extract( key_type(key, thread));
412 typename Set::guarded_ptr gp;
414 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
415 std::vector<size_t>& arrData = fixture.m_arrData;
416 size_t const nInsThreadCount = s_nInsThreadCount;
419 for ( size_t i = 0; i < arrData.size(); ++i ) {
420 if ( arrData[i] & 1 ) {
421 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
422 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k );
430 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
435 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
436 if ( arrData[i] & 1 ) {
437 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
438 gp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
446 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
453 template <typename RCU, class Set>
454 class Extractor< cds::urcu::gc<RCU>, Set >: public cds_test::thread
456 typedef cds_test::thread base_class;
460 size_t m_nExtractSuccess = 0;
461 size_t m_nExtractFailed = 0;
464 Extractor( cds_test::thread_pool& pool, Set& set )
465 : base_class( pool, extractor_thread )
469 Extractor( Extractor& src )
474 virtual thread * clone()
476 return new Extractor( *this );
479 template <typename SetType, bool>
481 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t /*thread*/)
483 return s.extract_with(key, key_less());
487 template <typename SetType>
488 struct extractor<SetType, true> {
489 static typename SetType::exempt_ptr extract(SetType& s, size_t key, size_t thread)
491 return s.extract(key_type(key, thread));
499 typename Set::exempt_ptr xp;
501 Set_DelOdd& fixture = pool().template fixture<Set_DelOdd>();
502 std::vector<size_t>& arrData = fixture.m_arrData;
503 size_t const nInsThreadCount = fixture.s_nInsThreadCount;
506 for ( size_t i = 0; i < arrData.size(); ++i ) {
507 if ( arrData[i] & 1 ) {
508 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
509 if ( Set::c_bExtractLockExternal ) {
510 typename Set::rcu_lock l;
511 xp = extractor<Set, Set::c_bEraseExactKey>::extract( rSet, arrData[i], k);
518 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
527 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
532 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
533 if ( arrData[i] & 1 ) {
534 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
535 if ( Set::c_bExtractLockExternal ) {
536 typename Set::rcu_lock l;
537 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
544 xp = extractor<Set, Set::c_bEraseExactKey>::extract(rSet, arrData[i], k);
553 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
562 void do_test_with( Set& testSet )
564 typedef Inserter<Set> insert_thread;
565 typedef Deleter<Set> delete_thread;
567 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
569 cds_test::thread_pool& pool = get_pool();
570 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
571 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
573 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
574 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
575 << std::make_pair( "set_size", s_nSetSize );
577 std::chrono::milliseconds duration = pool.run();
579 propout() << std::make_pair( "duration", duration );
581 size_t nInsertSuccess = 0;
582 size_t nInsertFailed = 0;
583 size_t nDeleteSuccess = 0;
584 size_t nDeleteFailed = 0;
586 for ( size_t i = 0; i < pool.size(); ++i ) {
587 cds_test::thread& thr = pool.get( i );
588 if ( thr.type() == inserter_thread ) {
589 insert_thread& inserter = static_cast<insert_thread&>(thr);
590 nInsertSuccess += inserter.m_nInsertSuccess;
591 nInsertFailed += inserter.m_nInsertFailed;
594 assert( thr.type() == deleter_thread );
595 delete_thread& deleter = static_cast<delete_thread&>(thr);
596 nDeleteSuccess += deleter.m_nDeleteSuccess;
597 nDeleteFailed += deleter.m_nDeleteFailed;
601 EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount );
602 EXPECT_EQ( nInsertFailed, 0u );
605 << std::make_pair( "insert_success", nInsertSuccess )
606 << std::make_pair( "insert_failed", nInsertFailed )
607 << std::make_pair( "delete_success", nDeleteSuccess )
608 << std::make_pair( "delete_failed", nDeleteFailed );
612 void do_test_extract_with( Set& testSet )
614 typedef Inserter<Set> insert_thread;
615 typedef Deleter<Set> delete_thread;
616 typedef Extractor< typename Set::gc, Set > extract_thread;
618 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
620 cds_test::thread_pool& pool = get_pool();
621 pool.add( new insert_thread( pool, testSet ), s_nInsThreadCount );
622 if ( s_nDelThreadCount )
623 pool.add( new delete_thread( pool, testSet ), s_nDelThreadCount );
624 if ( s_nExtractThreadCount )
625 pool.add( new extract_thread( pool, testSet ), s_nExtractThreadCount );
627 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
628 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
629 << std::make_pair( "extract_thread_count", s_nExtractThreadCount )
630 << std::make_pair( "set_size", s_nSetSize );
632 std::chrono::milliseconds duration = pool.run();
634 propout() << std::make_pair( "duration", duration );
636 size_t nInsertSuccess = 0;
637 size_t nInsertFailed = 0;
638 size_t nDeleteSuccess = 0;
639 size_t nDeleteFailed = 0;
640 size_t nExtractSuccess = 0;
641 size_t nExtractFailed = 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;
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_nExtractSuccess;
663 nExtractFailed += extractor.m_nExtractFailed;
671 EXPECT_EQ( nInsertSuccess, s_nSetSize * s_nInsThreadCount );
672 EXPECT_EQ( nInsertFailed, 0u );
675 << std::make_pair( "insert_success", nInsertSuccess )
676 << std::make_pair( "insert_failed", nInsertFailed )
677 << std::make_pair( "delete_success", nDeleteSuccess )
678 << std::make_pair( "delete_failed", nDeleteFailed )
679 << std::make_pair( "extract_success", nExtractSuccess )
680 << std::make_pair( "extract_failed", nExtractFailed );
683 template <typename Set>
684 void analyze( Set& testSet )
686 // All even keys must be in the set
688 for ( size_t n = 0; n < s_nSetSize; n +=2 ) {
689 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
690 EXPECT_TRUE( testSet.contains( key_type( n, i ))) << "key=" << n << "/" << i;
695 check_before_clear( testSet );
698 EXPECT_TRUE( testSet.empty() ) << "set.size=" << testSet.size();
700 additional_check( testSet );
701 print_stat( propout(), testSet );
702 additional_cleanup( testSet );
708 static_assert( !Set::c_bExtractSupported, "Set class must not support extract() method" );
710 Set testSet( *this );
711 do_test_with( testSet );
716 void run_test_extract()
718 static_assert( Set::c_bExtractSupported, "Set class must support extract() method" );
720 Set testSet( *this );
721 do_test_extract_with( testSet );
726 class Set_DelOdd_LF: public Set_DelOdd
727 , public ::testing::WithParamInterface<size_t>
733 s_nLoadFactor = GetParam();
734 propout() << std::make_pair( "load_factor", s_nLoadFactor );
735 Set_DelOdd::run_test<Set>();
739 void run_test_extract()
741 s_nLoadFactor = GetParam();
742 propout() << std::make_pair( "load_factor", s_nLoadFactor );
743 Set_DelOdd::run_test_extract<Set>();
746 static std::vector<size_t> get_load_factors();