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
123 static size_t s_nCuckooInitialSize; // initial size for CuckooMap
124 static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
125 static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
127 static size_t s_nFeldmanMap_HeadBits;
128 static size_t s_nFeldmanMap_ArrayBits;
130 static size_t s_nLoadFactor; // current load factor
132 static std::vector<size_t> m_arrInsert;
133 static std::vector<size_t> m_arrRemove;
135 static void SetUpTestCase();
136 static void TearDownTestCase();
139 typedef key_thread key_type;
140 typedef size_t value_type;
141 typedef std::pair<key_type const, value_type> pair_type;
143 atomics::atomic<size_t> m_nInsThreadCount;
151 // Inserts keys from [0..N)
153 class Inserter: public cds_test::thread
155 typedef cds_test::thread base_class;
160 template <typename Q>
161 void operator()( bool /*bNew*/, Q const& ) const
164 template <typename Q, typename V>
165 void operator()( bool /*bNew*/, Q const&, V& ) const
169 template <typename Q>
170 void operator()( Q&, Q*) const
174 size_t m_nInsertSuccess = 0;
175 size_t m_nInsertFailed = 0;
178 Inserter( cds_test::thread_pool& pool, Map& map )
179 : base_class( pool, inserter_thread )
183 Inserter( Inserter& src )
188 virtual thread * clone()
190 return new Inserter( *this );
196 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
198 std::vector<size_t>& arrData = fixture.m_arrInsert;
199 for ( size_t i = 0; i < arrData.size(); ++i ) {
200 if ( rMap.insert( key_type( arrData[i], id())))
207 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
208 if ( arrData[i] & 1 ) {
209 rMap.update( key_type( arrData[i], id()), f );
213 fixture.m_nInsThreadCount.fetch_sub( 1, atomics::memory_order_acquire );
218 bool operator()( key_type const& k1, key_type const& k2 ) const
220 return k1.nKey == k2.nKey;
222 bool operator()( size_t k1, key_type const& k2 ) const
224 return k1 == k2.nKey;
226 bool operator()( key_type const& k1, size_t k2 ) const
228 return k1.nKey == k2;
233 bool operator()( key_type const& k1, key_type const& k2 ) const
235 return k1.nKey < k2.nKey;
237 bool operator()( size_t k1, key_type const& k2 ) const
241 bool operator()( key_type const& k1, size_t k2 ) const
246 typedef key_equal equal_to;
249 // Deletes odd keys from [0..N)
251 class Deleter: public cds_test::thread
253 typedef cds_test::thread base_class;
257 size_t m_nDeleteSuccess = 0;
258 size_t m_nDeleteFailed = 0;
261 Deleter( cds_test::thread_pool& pool, Map& map )
262 : base_class( pool, deleter_thread )
265 Deleter( Deleter& src )
270 virtual thread * clone()
272 return new Deleter( *this );
275 template <typename MapType, bool>
277 static bool erase(MapType& map, size_t key, size_t /*insThread*/)
279 return map.erase_with(key, key_less());
283 template <typename MapType>
284 struct eraser<MapType, true>
286 static bool erase(MapType& map, size_t key, size_t insThread)
288 return map.erase(key_type(key, insThread));
296 Map_DelOdd& fixture = pool().template fixture<Map_DelOdd>();
297 size_t const nInsThreadCount = s_nInsThreadCount;
299 for ( size_t pass = 0; pass < 2; pass++ ) {
300 std::vector<size_t>& arrData = fixture.m_arrRemove;
302 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
303 for ( size_t i = 0; i < arrData.size(); ++i ) {
304 if ( arrData[i] & 1 ) {
305 if ( Map::c_bEraseExactKey ) {
306 for (size_t key = 0; key < nInsThreadCount; ++key) {
307 if ( eraser<Map, Map::c_bEraseExactKey>::erase( rMap, arrData[i], key ))
314 if ( eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
321 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
326 for ( size_t k = 0; k < nInsThreadCount; ++k ) {
327 for ( size_t i = arrData.size() - 1; i > 0; --i ) {
328 if ( arrData[i] & 1 ) {
329 if ( Map::c_bEraseExactKey ) {
330 for (size_t key = 0; key < nInsThreadCount; ++key) {
331 if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], key))
338 if (eraser<Map, Map::c_bEraseExactKey>::erase(rMap, arrData[i], 0))
345 if ( fixture.m_nInsThreadCount.load( atomics::memory_order_acquire ) == 0 )
353 // Deletes odd keys from [0..N)
354 template <class GC, class Map >
355 class Extractor: public cds_test::thread
357 typedef cds_test::thread base_class;
361 size_t m_nDeleteSuccess = 0;
362 size_t m_nDeleteFailed = 0;
365 Extractor( cds_test::thread_pool& pool, Map& map )
366 : base_class( pool, extractor_thread )
370 Extractor( Extractor& src )
375 virtual thread * clone()
377 return new Extractor( *this );
380 template <typename MapType, bool>
382 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t /*insThread*/)
384 return map.extract_with(key, key_less());
388 template <typename MapType>
389 struct extractor<MapType, true>
391 static typename Map::guarded_ptr extract(MapType& map, size_t key, size_t insThread)
393 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, 0u );
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, 0u );
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();