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.
42 key_thread( size_t key, size_t threadNo )
43 : nKey( static_cast<uint32_t>(key))
44 , nThread( static_cast<uint16_t>(threadNo))
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<key_thread>
88 bool operator()( key_thread const& k1, key_thread const& k2 ) const
90 if ( k1.nKey <= k2.nKey )
91 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
97 struct hash<key_thread>
99 typedef size_t result_type;
100 typedef key_thread argument_type;
102 size_t operator()( 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);
112 class Map_DelOdd: public cds_test::stress_fixture
115 static size_t s_nInsThreadCount; // insert thread count
116 static size_t s_nDelThreadCount; // delete thread count
117 static size_t s_nExtractThreadCount; // extract thread count
118 static size_t s_nMapSize; // max map size
119 static size_t s_nMaxLoadFactor; // maximum load factor
121 static size_t s_nCuckooInitialSize; // initial size for CuckooMap
122 static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
123 static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
125 static size_t s_nFeldmanMap_HeadBits;
126 static size_t s_nFeldmanMap_ArrayBits;
128 static size_t s_nLoadFactor; // current load factor
130 static std::vector<size_t> m_arrInsert;
131 static std::vector<size_t> m_arrRemove;
133 static void SetUpTestCase();
134 static void TearDownTestCase();
137 typedef key_thread key_type;
138 typedef size_t value_type;
139 typedef std::pair<key_type const, value_type> pair_type;
141 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;
158 template <typename Q>
159 void operator()( bool /*bNew*/, Q const& )
161 template <typename Q, typename V>
162 void operator()( bool /*bNew*/, Q const&, V& )
166 template <typename Q>
167 void operator()( Q&, Q*)
171 size_t m_nInsertSuccess = 0;
172 size_t m_nInsertFailed = 0;
175 Inserter( cds_test::thread_pool& pool, Map& map )
176 : base_class( pool, inserter_thread )
180 Inserter( Inserter& src )
185 virtual thread * clone()
187 return new Inserter( *this );
193 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
195 std::vector<size_t>& arrData = fixture.m_arrInsert;
196 for ( size_t i = 0; i < arrData.size(); ++i ) {
197 if ( rMap.insert( key_type( arrData[i], id() )))
204 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
205 if ( arrData[i] & 1 ) {
206 rMap.update( key_type( arrData[i], id() ), f );
210 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_acquire );
215 bool operator()( key_type const& k1, key_type const& k2 ) const
217 return k1.nKey == k2.nKey;
219 bool operator()( size_t k1, key_type const& k2 ) const
221 return k1 == k2.nKey;
223 bool operator()( key_type const& k1, size_t k2 ) const
225 return k1.nKey == k2;
230 bool operator()( key_type const& k1, key_type const& k2 ) const
232 return k1.nKey < k2.nKey;
234 bool operator()( size_t k1, key_type const& k2 ) const
238 bool operator()( key_type const& k1, size_t k2 ) const
243 typedef key_equal equal_to;
246 // Deletes odd keys from [0..N)
248 class Deleter: public cds_test::thread
250 typedef cds_test::thread base_class;
254 size_t m_nDeleteSuccess = 0;
255 size_t m_nDeleteFailed = 0;
258 Deleter( cds_test::thread_pool& pool, Map& map )
259 : base_class( pool, deleter_thread )
262 Deleter( Deleter& src )
267 virtual thread * clone()
269 return new Deleter( *this );
272 template <typename MapType, bool>
274 static bool erase(MapType& map, size_t key, size_t /*insThread*/)
276 return map.erase_with(key, key_less());
280 template <typename MapType>
281 struct eraser<MapType, true>
283 static bool erase(MapType& map, size_t key, size_t insThread)
285 return map.erase(key_type(key, insThread));
293 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
294 size_t const nInsThreadCount = s_nInsThreadCount;
296 for ( size_t pass = 0; pass < 2; pass++ ) {
297 std::vector<size_t>& arrData = fixture.m_arrRemove;
299 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
300 for ( size_t i = 0; i < arrData.size(); ++i ) {
301 if ( arrData[i] & 1 ) {
302 if ( Map::c_bEraseExactKey ) {
303 for (size_t key = 0; key < nInsThreadCount; ++key) {
304 if ( eraser<Map, Map::c_bEraseExactKey>::erase( rMap, arrData[i], key ))
311 if ( eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
318 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
323 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
324 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
325 if ( arrData[i] & 1 ) {
326 if ( Map::c_bEraseExactKey ) {
327 for (size_t key = 0; key < nInsThreadCount; ++key) {
328 if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], key))
335 if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
342 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
350 // Deletes odd keys from [0..N)
351 template <class GC, class Map >
352 class Extractor: public cds_test::thread
354 typedef cds_test::thread base_class;
358 size_t m_nDeleteSuccess = 0;
359 size_t m_nDeleteFailed = 0;
362 Extractor( cds_test::thread_pool& pool, Map& map )
363 : base_class( pool, extractor_thread )
367 Extractor( Extractor& src )
372 virtual thread * clone()
374 return new Extractor( *this );
377 template <typename MapType, bool>
379 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t /*insThread*/)
381 return map.extract_with(key, key_less());
385 template <typename MapType>
386 struct extractor<MapType, true>
388 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t insThread)
390 return map.extract(key_type(key, insThread));
401 typename Map::guarded_ptr gp;
402 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
403 size_t const nInsThreadCount = s_nInsThreadCount;
405 for ( size_t pass = 0; pass < 2; ++pass ) {
406 std::vector<size_t>& arrData = fixture.m_arrRemove;
408 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
409 for ( size_t i = 0; i < arrData.size(); ++i ) {
410 if ( arrData[i] & 1 ) {
411 gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k );
419 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
424 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
425 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
426 if ( arrData[i] & 1 ) {
427 gp = extractor< Map, Map::c_bEraseExactKey >::extract( rMap, arrData[i], k);
435 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
443 template <class RCU, class Map >
444 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
446 typedef cds_test::thread base_class;
450 size_t m_nDeleteSuccess = 0;
451 size_t m_nDeleteFailed = 0;
454 Extractor( cds_test::thread_pool& pool, Map& map )
455 : base_class( pool, extractor_thread )
459 Extractor( Extractor& src )
464 virtual thread * clone()
466 return new Extractor( *this );
469 template <typename MapType, bool>
471 static typename Map::exempt_ptr extract( MapType& map, size_t key, size_t /*insThread*/ )
473 return map.extract_with( key, key_less());
477 template <typename MapType>
478 struct extractor<MapType, true>
480 static typename Map::exempt_ptr extract(MapType& map, size_t key, size_t insThread)
482 return map.extract( key_type(key, insThread));
489 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
491 typename Map::exempt_ptr xp;
492 size_t const nInsThreadCount = s_nInsThreadCount;
494 std::vector<size_t>& arrData = fixture.m_arrRemove;
496 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
497 for ( size_t i = 0; i < arrData.size(); ++i ) {
498 if ( arrData[i] & 1 ) {
499 if ( Map::c_bExtractLockExternal ) {
501 typename Map::rcu_lock l;
502 xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k );
510 xp = extractor<Map, Map::c_bEraseExactKey>::extract( rMap, arrData[i], k);
519 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
524 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
525 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
526 if ( arrData[i] & 1 ) {
527 if ( Map::c_bExtractLockExternal ) {
529 typename Map::rcu_lock l;
530 xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
538 xp = extractor<Map, Map::c_bEraseExactKey>::extract(rMap, arrData[i], k);
547 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
556 void do_test( Map& testMap )
558 typedef Inserter<Map> insert_thread;
559 typedef Deleter<Map> delete_thread;
561 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
563 cds_test::thread_pool& pool = get_pool();
564 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
565 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count() );
567 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
568 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
569 << std::make_pair( "map_size", s_nMapSize );
571 std::chrono::milliseconds duration = pool.run();
573 propout() << std::make_pair( "duration", duration );
575 size_t nInsertSuccess = 0;
576 size_t nInsertFailed = 0;
577 size_t nDeleteSuccess = 0;
578 size_t nDeleteFailed = 0;
580 for ( size_t i = 0; i < pool.size(); ++i ) {
581 cds_test::thread& thr = pool.get( i );
582 if ( thr.type() == inserter_thread ) {
583 insert_thread& inserter = static_cast<insert_thread&>(thr);
584 nInsertSuccess += inserter.m_nInsertSuccess;
585 nInsertFailed += inserter.m_nInsertFailed;
588 assert( thr.type() == deleter_thread );
589 delete_thread& deleter = static_cast<delete_thread&>(thr);
590 nDeleteSuccess += deleter.m_nDeleteSuccess;
591 nDeleteFailed += deleter.m_nDeleteFailed;
595 EXPECT_EQ( nInsertSuccess, s_nMapSize * s_nInsThreadCount );
596 EXPECT_EQ( nInsertFailed, 0 );
599 << std::make_pair( "insert_success", nInsertSuccess )
600 << std::make_pair( "insert_failed", nInsertFailed )
601 << std::make_pair( "delete_success", nDeleteSuccess )
602 << std::make_pair( "delete_failed", nDeleteFailed );
608 void do_test_extract( Map& testMap )
610 typedef Inserter<Map> insert_thread;
611 typedef Deleter<Map> delete_thread;
612 typedef Extractor< typename Map::gc, Map > 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, testMap ), s_nInsThreadCount );
618 if ( s_nDelThreadCount )
619 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount );
620 if ( s_nExtractThreadCount )
621 pool.add( new extract_thread( pool, testMap ), 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( "map_size", s_nMapSize );
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_nDeleteSuccess;
659 nExtractFailed += extractor.m_nDeleteFailed;
667 EXPECT_EQ( nInsertSuccess, s_nMapSize * 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 );
682 void analyze( Map& testMap )
684 // All even keys must be in the map
686 for ( size_t n = 0; n < s_nMapSize; n +=2 ) {
687 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
688 EXPECT_TRUE( testMap.contains( key_type( n, i ) ) ) << "key=" << n << "/" << i;
693 print_stat( propout(), testMap );
695 check_before_cleanup( testMap );
697 EXPECT_TRUE( testMap.empty() ) << "map.size=" << testMap.size();
699 additional_check( testMap );
700 additional_cleanup( testMap );
704 void run_test_extract()
706 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
708 Map testMap( *this );
709 do_test_extract( testMap );
715 Map testMap( *this );
720 class Map_DelOdd_LF: public Map_DelOdd
721 , public ::testing::WithParamInterface<size_t>
727 s_nLoadFactor = GetParam();
728 propout() << std::make_pair( "load_factor", s_nLoadFactor );
729 Map_DelOdd::run_test<Map>();
733 void run_test_extract()
735 s_nLoadFactor = GetParam();
736 propout() << std::make_pair( "load_factor", s_nLoadFactor );
737 Map_DelOdd::run_test_extract<Map>();
740 static std::vector<size_t> get_load_factors();