2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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.
32 #include <cds/os/topology.h>
42 key_thread( size_t key, size_t threadNo )
43 : nKey( static_cast<uint32_t>(key))
44 , nThread( static_cast<uint16_t>(threadNo))
53 static_assert(sizeof( key_thread ) % 8 == 0, "Key size mismatch!!!");
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<key_thread>
91 bool operator()( key_thread const& k1, key_thread const& k2 ) const
93 if ( k1.nKey <= k2.nKey )
94 return k1.nKey < k2.nKey || k1.nThread < k2.nThread;
100 struct hash<key_thread>
102 typedef size_t result_type;
103 typedef key_thread argument_type;
105 size_t operator()( key_thread const& k ) const
107 return std::hash<size_t>()(k.nKey);
109 size_t operator()( size_t k ) const
111 return std::hash<size_t>()(k);
115 class Map_Del3: public cds_test::stress_fixture
118 static size_t s_nInsThreadCount; // insert thread count
119 static size_t s_nDelThreadCount; // delete thread count
120 static size_t s_nExtractThreadCount; // extract thread count
121 static size_t s_nMapSize; // max map size
122 static size_t s_nMaxLoadFactor; // maximum load factor
123 static size_t s_nInsertPassCount;
124 static size_t s_nOriginalPassCount;
125 static size_t s_nPassCount;
126 static size_t s_nBronsonAVLTreeMapPassCount;
127 static size_t s_nEllenBinTreeMapPassCount;
128 static size_t s_nFeldmanPassCount;
129 static size_t s_nMichaelMapPassCount;
130 static size_t s_nSkipListMapPassCount;
132 static size_t s_nFindThreadCount; // find thread count
134 static size_t s_nCuckooInitialSize; // initial size for CuckooMap
135 static size_t s_nCuckooProbesetSize; // CuckooMap probeset size (only for list-based probeset)
136 static size_t s_nCuckooProbesetThreshold; // CuckooMap probeset threshold (0 - use default)
138 static size_t s_nFeldmanMap_HeadBits;
139 static size_t s_nFeldmanMap_ArrayBits;
141 static size_t s_nLoadFactor; // current load factor
143 static std::vector<size_t> m_arrElements;
145 static void SetUpTestCase();
146 static void TearDownTestCase();
148 template <typename Pred>
149 static void prepare_array( std::vector<size_t>& arr, Pred pred )
151 arr.reserve( m_arrElements.size());
152 for ( auto el : m_arrElements ) {
156 arr.resize( arr.size());
157 shuffle( arr.begin(), arr.end());
161 typedef key_thread key_type;
162 typedef size_t value_type;
163 typedef std::pair<key_type const, value_type> pair_type;
165 atomics::atomic<size_t> m_nInsThreadCount;
174 // Inserts keys from [0..N)
176 class Inserter: public cds_test::thread
178 typedef cds_test::thread base_class;
183 template <typename Q>
184 void operator()( bool /*bNew*/, Q const& ) const
187 template <typename Q, typename V>
188 void operator()( bool /*bNew*/, Q const&, V& ) const
192 template <typename Q>
193 void operator()( Q&, Q*) const
199 prepare_array( m_arr, []( size_t ) -> bool { return true; } );
200 for ( size_t i = 0; i < m_arr.size(); ++i ) {
201 if ( m_Map.insert( key_type( m_arr[i], id())))
202 ++m_nInsertInitSuccess;
204 ++m_nInsertInitFailed;
209 size_t m_nInsertSuccess = 0;
210 size_t m_nInsertFailed = 0;
211 size_t m_nInsertInitSuccess = 0;
212 size_t m_nInsertInitFailed = 0;
214 std::vector<size_t> m_arr;
217 Inserter( cds_test::thread_pool& pool, Map& map )
218 : base_class( pool, inserter_thread )
224 Inserter( Inserter& src )
231 virtual thread * clone()
233 return new Inserter( *this );
239 Map_Del3& fixture = pool().template fixture<Map_Del3>();
243 for (auto el : m_arr) {
245 if (rMap.insert(key_type(el, id())))
256 bool operator()( key_type const& k1, key_type const& k2 ) const
258 return k1.nKey == k2.nKey;
260 bool operator()( size_t k1, key_type const& k2 ) const
262 return k1 == k2.nKey;
264 bool operator()( key_type const& k1, size_t k2 ) const
266 return k1.nKey == k2;
271 bool operator()( key_type const& k1, key_type const& k2 ) const
273 return k1.nKey < k2.nKey;
275 bool operator()( size_t k1, key_type const& k2 ) const
279 bool operator()( key_type const& k1, size_t k2 ) const
284 typedef key_equal equal_to;
287 // Deletes odd keys from [0..N)
289 class Deleter: public cds_test::thread
291 typedef cds_test::thread base_class;
296 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
300 size_t m_nDeleteSuccess = 0;
301 size_t m_nDeleteFailed = 0;
303 std::vector<size_t> m_arr;
306 Deleter( cds_test::thread_pool& pool, Map& map )
307 : base_class( pool, deleter_thread )
313 Deleter( Deleter& src )
320 virtual thread * clone()
322 return new Deleter( *this );
329 Map_Del3& fixture = pool().template fixture<Map_Del3>();
330 size_t const nInsThreadCount = s_nInsThreadCount;
332 for (auto el : m_arr) {
333 for (size_t k = 0; k < nInsThreadCount; ++k) {
334 if (rMap.erase(key_type(el, k)))
344 // Deletes odd keys from [0..N)
345 template <class GC, class Map >
346 class Extractor: public cds_test::thread
348 typedef cds_test::thread base_class;
353 prepare_array( m_arr, []( size_t el ) ->bool { return ( el & 3 ) != 0; } );
357 size_t m_nDeleteSuccess = 0;
358 size_t m_nDeleteFailed = 0;
360 std::vector<size_t> m_arr;
363 Extractor( cds_test::thread_pool& pool, Map& map )
364 : base_class( pool, extractor_thread )
370 Extractor( Extractor& src )
377 virtual thread * clone()
379 return new Extractor( *this );
386 typename Map::guarded_ptr gp;
387 Map_Del3& fixture = pool().template fixture<Map_Del3>();
388 size_t const nInsThreadCount = s_nInsThreadCount;
390 for (auto el : m_arr) {
391 for (size_t k = 0; k < nInsThreadCount; ++k) {
392 gp = rMap.extract(key_type(el, k));
404 template <class RCU, class Map >
405 class Extractor< cds::urcu::gc<RCU>, Map > : public cds_test::thread
407 typedef cds_test::thread base_class;
412 prepare_array( m_arr, []( size_t el ) -> bool { return ( el & 3 ) != 0; } );
416 size_t m_nDeleteSuccess = 0;
417 size_t m_nDeleteFailed = 0;
419 std::vector<size_t> m_arr;
422 Extractor( cds_test::thread_pool& pool, Map& map )
423 : base_class( pool, extractor_thread )
429 Extractor( Extractor& src )
436 virtual thread * clone()
438 return new Extractor( *this );
444 Map_Del3& fixture = pool().template fixture<Map_Del3>();
446 typename Map::exempt_ptr xp;
447 size_t const nInsThreadCount = s_nInsThreadCount;
449 for (size_t k = 0; k < nInsThreadCount; ++k) {
450 for (auto el : m_arr) {
451 if (Map::c_bExtractLockExternal) {
452 typename Map::rcu_lock l;
453 xp = rMap.extract(key_type(el, k));
459 xp = rMap.extract(key_type(el, k));
474 class Observer: public cds_test::thread
476 typedef cds_test::thread base_class;
480 size_t m_nFindEvenSuccess = 0;
481 size_t m_nFindEvenFailed = 0;
482 size_t m_nFindOddSuccess = 0;
483 size_t m_nFindOddFailed = 0;
486 Observer( cds_test::thread_pool& pool, Map& map )
487 : base_class( pool, find_thread )
491 Observer( Observer& src )
496 virtual thread * clone()
498 return new Observer( *this );
504 Map_Del3& fixture = pool().template fixture<Map_Del3>();
505 std::vector<size_t> const& arr = m_arrElements;
506 size_t const nInsThreadCount = s_nInsThreadCount;
508 for (size_t key : arr) {
510 for (size_t k = 0; k < nInsThreadCount; ++k) {
511 if (map.contains(key_thread(key, k)))
517 // even keys MUST be in the map
518 for (size_t k = 0; k < nInsThreadCount; ++k) {
519 if (map.contains(key_thread(key, k)))
520 ++m_nFindEvenSuccess;
531 void do_test( Map& testMap )
533 typedef Inserter<Map> insert_thread;
534 typedef Deleter<Map> delete_thread;
535 typedef Observer<Map> observer_thread;
537 m_nInsThreadCount.store( s_nInsThreadCount, atomics::memory_order_release );
539 cds_test::thread_pool& pool = get_pool();
540 pool.add( new insert_thread( pool, testMap ), s_nInsThreadCount );
541 pool.add( new delete_thread( pool, testMap ), s_nDelThreadCount ? s_nDelThreadCount : cds::OS::topology::processor_count());
542 if ( s_nFindThreadCount )
543 pool.add( new observer_thread( pool, testMap ), s_nFindThreadCount );
545 propout() << std::make_pair( "insert_thread_count", s_nInsThreadCount )
546 << std::make_pair( "delete_thread_count", s_nDelThreadCount )
547 << std::make_pair( "find_thread_count", s_nFindThreadCount )
548 << std::make_pair( "map_size", s_nMapSize )
549 << std::make_pair( "pass_count", s_nInsertPassCount );
551 std::chrono::milliseconds duration = pool.run();
553 propout() << std::make_pair( "duration", duration );
555 size_t nInsertInitFailed = 0;
556 size_t nInsertInitSuccess = 0;
557 size_t nInsertSuccess = 0;
558 size_t nInsertFailed = 0;
559 size_t nDeleteSuccess = 0;
560 size_t nDeleteFailed = 0;
562 size_t nFindEvenSuccess = 0;
563 size_t nFindEvenFailed = 0;
564 size_t nFindOddSuccess = 0;
565 size_t nFindOddFailed = 0;
567 for ( size_t i = 0; i < pool.size(); ++i ) {
568 cds_test::thread& thr = pool.get( i );
569 switch ( thr.type()) {
570 case inserter_thread:
572 insert_thread& inserter = static_cast<insert_thread&>( thr );
573 nInsertSuccess += inserter.m_nInsertSuccess;
574 nInsertFailed += inserter.m_nInsertFailed;
575 nInsertInitSuccess += inserter.m_nInsertInitSuccess;
576 nInsertInitFailed += inserter.m_nInsertInitFailed;
581 delete_thread& deleter = static_cast<delete_thread&>( thr );
582 nDeleteSuccess += deleter.m_nDeleteSuccess;
583 nDeleteFailed += deleter.m_nDeleteFailed;
588 observer_thread& observer = static_cast<observer_thread&>( thr );
589 nFindEvenSuccess = observer.m_nFindEvenSuccess;
590 nFindEvenFailed = observer.m_nFindEvenFailed;
591 nFindOddSuccess = observer.m_nFindOddSuccess;
592 nFindOddFailed = observer.m_nFindOddFailed;
598 size_t const nInitialOddKeys = ( s_nMapSize * s_nInsThreadCount ) * 3 / 4;
600 EXPECT_EQ( nInsertInitFailed, 0u );
601 EXPECT_EQ( nInsertInitSuccess, s_nMapSize * s_nInsThreadCount );
602 EXPECT_EQ( nFindEvenFailed, 0u );
603 EXPECT_GE( nInsertSuccess + nInitialOddKeys, nDeleteSuccess );
604 EXPECT_LE( nInsertSuccess, nDeleteSuccess );
607 << std::make_pair( "insert_init_success", nInsertInitSuccess )
608 << std::make_pair( "insert_init_failed", nInsertInitFailed )
609 << std::make_pair( "insert_success", nInsertSuccess )
610 << std::make_pair( "insert_failed", nInsertFailed )
611 << std::make_pair( "delete_success", nDeleteSuccess )
612 << std::make_pair( "delete_failed", nDeleteFailed )
613 << std::make_pair( "find_even_success", nFindEvenSuccess )
614 << std::make_pair( "find_even_failed", nFindEvenFailed )
615 << std::make_pair( "find_odd_success", nFindOddSuccess )
616 << std::make_pair( "find_odd_failed", nFindOddFailed );
622 void do_test_extract( Map& testMap )
624 typedef Inserter<Map> insert_thread;
625 typedef Deleter<Map> delete_thread;
626 typedef Extractor< typename Map::gc, Map > extract_thread;
627 typedef Observer<Map> observer_thread;
629 cds_test::thread_pool &pool = get_pool();
630 std::unique_ptr<insert_thread> inserter(
631 new insert_thread(pool, testMap));
632 std::unique_ptr<delete_thread> deleter(
633 new delete_thread(pool, testMap));
634 std::unique_ptr<extract_thread> extractor(
635 new extract_thread(pool, testMap));
636 std::unique_ptr<observer_thread> observer(
637 new observer_thread(pool, testMap));
639 for (size_t nPass = 0; nPass < s_nPassCount; ++nPass) {
653 void analyze( Map& testMap )
655 // All even keys must be in the map
657 for ( size_t n = 0; n < s_nMapSize; n +=4 ) {
658 for ( size_t i = 0; i < s_nInsThreadCount; ++i ) {
659 EXPECT_TRUE( testMap.contains( key_type( n, i ))) << "key=" << n << "/" << i;
664 print_stat( propout(), testMap );
666 check_before_cleanup( testMap );
668 EXPECT_TRUE( testMap.empty()) << "map.size=" << testMap.size();
670 additional_check( testMap );
671 additional_cleanup( testMap );
675 void run_test_extract()
677 static_assert( Map::c_bExtractSupported, "Map class must support extract() method" );
679 size_t nMapSize = s_nMapSize;
680 s_nMapSize *= s_nInsThreadCount;
682 Map testMap( *this );
684 s_nMapSize = nMapSize;
685 do_test_extract( testMap );
691 size_t nMapSize = s_nMapSize;
692 s_nMapSize *= s_nInsThreadCount;
694 Map testMap( *this );
696 s_nMapSize = nMapSize;
704 void run_bronson_avl_tree();
707 void run_ellen_bin_tree();
710 void run_skip_list();
716 class Map_Del3_LF: public Map_Del3
717 , public ::testing::WithParamInterface<size_t>
723 s_nLoadFactor = GetParam();
724 propout() << std::make_pair( "load_factor", s_nLoadFactor );
725 Map_Del3::run_test<Map>();
729 void run_test_extract()
731 s_nLoadFactor = GetParam();
732 propout() << std::make_pair( "load_factor", s_nLoadFactor );
733 Map_Del3::run_test_extract<Map>();
736 static std::vector<size_t> get_load_factors();