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.
35 class Set_InsDel_func: public cds_test::stress_fixture
38 static size_t s_nSetSize; // set size
39 static size_t s_nInsertThreadCount; // count of insertion thread
40 static size_t s_nDeleteThreadCount; // count of deletion thread
41 static size_t s_nUpdateThreadCount; // count of updating thread
42 static size_t s_nThreadPassCount; // pass count for each thread
43 static size_t s_nMaxLoadFactor; // maximum load factor
45 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
46 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
47 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
49 static size_t s_nFeldmanSet_HeadBits;
50 static size_t s_nFeldmanSet_ArrayBits;
52 static size_t s_nLoadFactor;
54 static void SetUpTestCase();
55 //static void TearDownTestCase();
58 typedef size_t key_type;
63 atomics::atomic<size_t> nUpdateCall;
64 bool volatile bInitialized;
65 cds::OS::ThreadId threadId ; // insert thread id
67 typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
68 mutable lock_type m_access;
74 , bInitialized( false )
75 , threadId( cds::OS::get_current_thread_id() )
78 value( value const& s )
81 , nUpdateCall(s.nUpdateCall.load(atomics::memory_order_relaxed))
82 , bInitialized( s.bInitialized )
83 , threadId( cds::OS::get_current_thread_id() )
86 // boost::container::flat_map requires operator =
87 value& operator=( value const& v )
91 nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
92 bInitialized = v.bInitialized;
109 class Inserter: public cds_test::thread
111 typedef cds_test::thread base_class;
114 typedef typename Set::value_type keyval_type;
116 struct insert_functor {
117 size_t nTestFunctorRef;
122 insert_functor( insert_functor const& ) = delete;
124 void operator()( keyval_type& val )
126 std::unique_lock< typename value::lock_type> ac( val.val.m_access );
128 val.val.nKey = val.key;
129 val.val.nData = val.key * 8;
132 val.val.bInitialized = true;
137 size_t m_nInsertSuccess = 0;
138 size_t m_nInsertFailed = 0;
140 size_t m_nTestFunctorRef = 0;
143 Inserter( cds_test::thread_pool& pool, Set& set )
144 : base_class( pool, insert_thread )
148 Inserter( Inserter& src )
153 virtual thread * clone()
155 return new Inserter( *this );
161 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
163 size_t * pKeyFirst = fixture.m_pKeyFirst;
164 size_t * pKeyLast = fixture.m_pKeyLast;
165 size_t const nPassCount = fixture.s_nThreadPassCount;
167 // func is passed by reference
171 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
172 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
173 if ( rSet.insert( *p, std::ref( func )))
181 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
182 for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
183 if ( rSet.insert( *p, std::ref( func )))
191 m_nTestFunctorRef = func.nTestFunctorRef;
196 class Updater: public cds_test::thread
198 typedef cds_test::thread base_class;
201 typedef typename Set::value_type keyval_type;
203 struct update_functor {
205 size_t nModified = 0;
208 update_functor( const update_functor& ) = delete;
210 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
212 std::unique_lock<typename value::lock_type> ac( val.val.m_access );
213 if ( !val.val.bInitialized )
215 val.val.nKey = val.key;
216 val.val.nData = val.key * 8;
217 val.val.bInitialized = true;
224 val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
229 void operator()( keyval_type& cur, keyval_type * old )
231 operator()( old == nullptr, cur, 0 );
236 size_t m_nUpdateFailed = 0;
237 size_t m_nUpdateCreated = 0;
238 size_t m_nUpdateExisted = 0;
239 size_t m_nFunctorCreated = 0;
240 size_t m_nFunctorModified = 0;
243 Updater( cds_test::thread_pool& pool, Set& set )
244 : base_class( pool, update_thread )
248 Updater( Updater& src )
253 virtual thread * clone()
255 return new Updater( *this );
262 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
263 size_t * pKeyFirst = fixture.m_pKeyFirst;
264 size_t * pKeyLast = fixture.m_pKeyLast;
265 size_t const nPassCount = fixture.s_nThreadPassCount;
270 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
271 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
272 std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
285 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
286 for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
287 std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
300 m_nFunctorCreated = func.nCreated;
301 m_nFunctorModified = func.nModified;
306 class Deleter: public cds_test::thread
308 typedef cds_test::thread base_class;
311 typedef typename Set::value_type keyval_type;
313 struct value_container
317 size_t nSuccessItem = 0;
318 size_t nFailedItem = 0;
321 struct erase_functor {
322 value_container m_cnt;
324 void operator ()( keyval_type const& itm )
326 keyval_type& item = const_cast<keyval_type&>(itm);
330 std::unique_lock< typename value::lock_type> ac( item.val.m_access );
331 if ( item.val.bInitialized ) {
332 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
333 ++m_cnt.nSuccessItem;
344 cds::backoff::yield()();
350 size_t m_nDeleteSuccess = 0;
351 size_t m_nDeleteFailed = 0;
353 size_t m_nValueSuccess = 0;
354 size_t m_nValueFailed = 0;
357 Deleter( cds_test::thread_pool& pool, Set& set )
358 : base_class( pool, delete_thread )
362 Deleter( Deleter& src )
367 virtual thread * clone()
369 return new Deleter( *this );
376 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
377 size_t * pKeyFirst = fixture.m_pKeyFirst;
378 size_t * pKeyLast = fixture.m_pKeyLast;
379 size_t const nPassCount = fixture.s_nThreadPassCount;
384 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
385 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
386 func.m_cnt.nKeyExpected = *p;
387 if ( rSet.erase( *p, std::ref( func )))
395 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
396 for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
397 func.m_cnt.nKeyExpected = *p;
398 if ( rSet.erase( *p, std::ref( func )))
406 m_nValueSuccess = func.m_cnt.nSuccessItem;
407 m_nValueFailed = func.m_cnt.nFailedItem;
414 void run_test( Set& testSet )
416 typedef Inserter<Set> InserterThread;
417 typedef Deleter<Set> DeleterThread;
418 typedef Updater<Set> UpdaterThread;
420 m_pKeyArr = new size_t[ s_nSetSize ];
421 m_pKeyFirst = m_pKeyArr;
422 m_pKeyLast = m_pKeyFirst + s_nSetSize;
423 for ( size_t i = 0; i < s_nSetSize; ++i )
425 shuffle( m_pKeyFirst, m_pKeyLast );
427 cds_test::thread_pool& pool = get_pool();
428 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
429 pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
430 pool.add( new UpdaterThread( pool, testSet ), s_nUpdateThreadCount );
432 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
433 << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
434 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
435 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
436 << std::make_pair( "set_size", s_nSetSize );
438 std::chrono::milliseconds duration = pool.run();
440 propout() << std::make_pair( "duration", duration );
444 size_t nInsertSuccess = 0;
445 size_t nInsertFailed = 0;
446 size_t nDeleteSuccess = 0;
447 size_t nDeleteFailed = 0;
448 size_t nDelValueSuccess = 0;
449 size_t nDelValueFailed = 0;
450 size_t nUpdateFailed = 0;
451 size_t nUpdateCreated = 0;
452 size_t nUpdateModified = 0;
453 size_t nEnsFuncCreated = 0;
454 size_t nEnsFuncModified = 0;
455 size_t nTestFunctorRef = 0;
457 for ( size_t i = 0; i < pool.size(); ++i ) {
458 cds_test::thread& thr = pool.get( i );
459 switch ( thr.type() ) {
462 InserterThread& inserter = static_cast<InserterThread&>( thr );
463 nInsertSuccess += inserter.m_nInsertSuccess;
464 nInsertFailed += inserter.m_nInsertFailed;
465 nTestFunctorRef += inserter.m_nTestFunctorRef;
470 UpdaterThread& updater = static_cast<UpdaterThread&>(thr);
471 nUpdateCreated += updater.m_nUpdateCreated;
472 nUpdateModified += updater.m_nUpdateExisted;
473 nUpdateFailed += updater.m_nUpdateFailed;
474 nEnsFuncCreated += updater.m_nFunctorCreated;
475 nEnsFuncModified += updater.m_nFunctorModified;
480 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
481 nDeleteSuccess += deleter.m_nDeleteSuccess;
482 nDeleteFailed += deleter.m_nDeleteFailed;
483 nDelValueSuccess += deleter.m_nValueSuccess;
484 nDelValueFailed += deleter.m_nValueFailed;
491 << std::make_pair( "insert_success", nInsertSuccess )
492 << std::make_pair( "delete_success", nDeleteSuccess )
493 << std::make_pair( "insert_failed", nInsertFailed )
494 << std::make_pair( "delete_failed", nDeleteFailed )
495 << std::make_pair( "update_created", nUpdateCreated )
496 << std::make_pair( "update_modified", nUpdateModified )
497 << std::make_pair( "update_failed", nUpdateFailed )
498 << std::make_pair( "final_set_size", testSet.size() );
501 EXPECT_EQ( nDelValueFailed, 0 );
502 EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
504 EXPECT_EQ( nUpdateFailed, 0 );
505 EXPECT_EQ( nUpdateCreated, nEnsFuncCreated );
506 EXPECT_EQ( nUpdateModified, nEnsFuncModified );
508 // nTestFunctorRef is call count of insert functor
509 EXPECT_EQ( nTestFunctorRef, nInsertSuccess );
512 EXPECT_TRUE( testSet.empty() );
514 additional_check( testSet );
515 print_stat( propout(), testSet );
517 additional_cleanup( testSet );
528 class Set_InsDel_func_LF: public Set_InsDel_func
529 , public ::testing::WithParamInterface<size_t>
535 s_nLoadFactor = GetParam();
536 propout() << std::make_pair( "load_factor", s_nLoadFactor );
537 Set_InsDel_func::run_test<Set>();
540 static std::vector<size_t> get_load_factors();