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())
87 // boost::container::flat_map requires operator =
88 // cppcheck-suppress operatorEqVarError
89 value& operator=( value const& v )
93 threadId = v.threadId;
94 nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
95 bInitialized = v.bInitialized;
101 size_t * m_pKeyFirst;
103 std::unique_ptr< size_t[] > m_pKeyArr;
112 class Inserter: public cds_test::thread
114 typedef cds_test::thread base_class;
117 typedef typename Set::value_type keyval_type;
119 struct insert_functor {
120 size_t nTestFunctorRef;
125 insert_functor( insert_functor const& ) = delete;
127 void operator()( keyval_type& val )
129 std::unique_lock< typename value::lock_type> ac( val.val.m_access );
131 val.val.nKey = val.key;
132 val.val.nData = val.key * 8;
135 val.val.bInitialized = true;
140 size_t m_nInsertSuccess = 0;
141 size_t m_nInsertFailed = 0;
142 size_t m_nTestFunctorRef = 0;
145 Inserter( cds_test::thread_pool& pool, Set& set )
146 : base_class( pool, insert_thread )
150 Inserter( Inserter& src )
155 virtual thread * clone()
157 return new Inserter( *this );
163 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
165 size_t * pKeyFirst = fixture.m_pKeyFirst;
166 size_t * pKeyLast = fixture.m_pKeyLast;
167 size_t const nPassCount = fixture.s_nThreadPassCount;
169 // func is passed by reference
173 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
174 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
175 if ( rSet.insert( *p, std::ref( func )))
183 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
184 for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
185 if ( rSet.insert( *p, std::ref( func )))
193 m_nTestFunctorRef = func.nTestFunctorRef;
198 class Updater: public cds_test::thread
200 typedef cds_test::thread base_class;
203 typedef typename Set::value_type keyval_type;
205 struct update_functor {
207 size_t nModified = 0;
210 update_functor( const update_functor& ) = delete;
212 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
214 std::unique_lock<typename value::lock_type> ac( val.val.m_access );
215 if ( !val.val.bInitialized )
217 val.val.nKey = val.key;
218 val.val.nData = val.key * 8;
219 val.val.bInitialized = true;
226 val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
231 void operator()( keyval_type& cur, keyval_type * old )
233 operator()( old == nullptr, cur, 0 );
238 size_t m_nUpdateFailed = 0;
239 size_t m_nUpdateCreated = 0;
240 size_t m_nUpdateExisted = 0;
241 size_t m_nFunctorCreated = 0;
242 size_t m_nFunctorModified = 0;
245 Updater( cds_test::thread_pool& pool, Set& set )
246 : base_class( pool, update_thread )
250 Updater( Updater& src )
255 virtual thread * clone()
257 return new Updater( *this );
264 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
265 size_t * pKeyFirst = fixture.m_pKeyFirst;
266 size_t * pKeyLast = fixture.m_pKeyLast;
267 size_t const nPassCount = fixture.s_nThreadPassCount;
272 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
273 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
274 std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
287 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
288 for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
289 std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
302 m_nFunctorCreated = func.nCreated;
303 m_nFunctorModified = func.nModified;
308 class Deleter: public cds_test::thread
310 typedef cds_test::thread base_class;
313 typedef typename Set::value_type keyval_type;
315 struct value_container
319 size_t nSuccessItem = 0;
320 size_t nFailedItem = 0;
323 struct erase_functor {
324 value_container m_cnt;
326 void operator ()( keyval_type const& itm )
328 keyval_type& item = const_cast<keyval_type&>(itm);
332 std::unique_lock< typename value::lock_type> ac( item.val.m_access );
333 if ( item.val.bInitialized ) {
334 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
335 ++m_cnt.nSuccessItem;
346 cds::backoff::yield()();
352 size_t m_nDeleteSuccess = 0;
353 size_t m_nDeleteFailed = 0;
354 size_t m_nValueSuccess = 0;
355 size_t m_nValueFailed = 0;
358 Deleter( cds_test::thread_pool& pool, Set& set )
359 : base_class( pool, delete_thread )
363 Deleter( Deleter& src )
368 virtual thread * clone()
370 return new Deleter( *this );
377 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
378 size_t * pKeyFirst = fixture.m_pKeyFirst;
379 size_t * pKeyLast = fixture.m_pKeyLast;
380 size_t const nPassCount = fixture.s_nThreadPassCount;
385 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
386 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
387 func.m_cnt.nKeyExpected = *p;
388 if ( rSet.erase( *p, std::ref( func )))
396 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
397 for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
398 func.m_cnt.nKeyExpected = *p;
399 if ( rSet.erase( *p, std::ref( func )))
407 m_nValueSuccess = func.m_cnt.nSuccessItem;
408 m_nValueFailed = func.m_cnt.nFailedItem;
415 void run_test( Set& testSet )
417 typedef Inserter<Set> InserterThread;
418 typedef Deleter<Set> DeleterThread;
419 typedef Updater<Set> UpdaterThread;
421 m_pKeyArr.reset( new size_t[ s_nSetSize ] );
422 m_pKeyFirst = m_pKeyArr.get();
423 m_pKeyLast = m_pKeyFirst + s_nSetSize;
424 for ( size_t i = 0; i < s_nSetSize; ++i )
426 shuffle( m_pKeyFirst, m_pKeyLast );
428 cds_test::thread_pool& pool = get_pool();
429 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
430 pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
431 pool.add( new UpdaterThread( pool, testSet ), s_nUpdateThreadCount );
433 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
434 << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
435 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
436 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
437 << std::make_pair( "set_size", s_nSetSize );
439 std::chrono::milliseconds duration = pool.run();
441 propout() << std::make_pair( "duration", duration );
443 size_t nInsertSuccess = 0;
444 size_t nInsertFailed = 0;
445 size_t nDeleteSuccess = 0;
446 size_t nDeleteFailed = 0;
447 size_t nDelValueSuccess = 0;
448 size_t nDelValueFailed = 0;
449 size_t nUpdateFailed = 0;
450 size_t nUpdateCreated = 0;
451 size_t nUpdateModified = 0;
452 size_t nEnsFuncCreated = 0;
453 size_t nEnsFuncModified = 0;
454 size_t nTestFunctorRef = 0;
456 for ( size_t i = 0; i < pool.size(); ++i ) {
457 cds_test::thread& thr = pool.get( i );
458 switch ( thr.type()) {
461 InserterThread& inserter = static_cast<InserterThread&>( thr );
462 nInsertSuccess += inserter.m_nInsertSuccess;
463 nInsertFailed += inserter.m_nInsertFailed;
464 nTestFunctorRef += inserter.m_nTestFunctorRef;
469 UpdaterThread& updater = static_cast<UpdaterThread&>(thr);
470 nUpdateCreated += updater.m_nUpdateCreated;
471 nUpdateModified += updater.m_nUpdateExisted;
472 nUpdateFailed += updater.m_nUpdateFailed;
473 nEnsFuncCreated += updater.m_nFunctorCreated;
474 nEnsFuncModified += updater.m_nFunctorModified;
479 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
480 nDeleteSuccess += deleter.m_nDeleteSuccess;
481 nDeleteFailed += deleter.m_nDeleteFailed;
482 nDelValueSuccess += deleter.m_nValueSuccess;
483 nDelValueFailed += deleter.m_nValueFailed;
490 << std::make_pair( "insert_success", nInsertSuccess )
491 << std::make_pair( "delete_success", nDeleteSuccess )
492 << std::make_pair( "insert_failed", nInsertFailed )
493 << std::make_pair( "delete_failed", nDeleteFailed )
494 << std::make_pair( "update_created", nUpdateCreated )
495 << std::make_pair( "update_modified", nUpdateModified )
496 << std::make_pair( "update_failed", nUpdateFailed )
497 << std::make_pair( "final_set_size", testSet.size());
500 EXPECT_EQ( nDelValueFailed, 0u );
501 EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
503 EXPECT_EQ( nUpdateFailed, 0u );
504 EXPECT_EQ( nUpdateCreated, nEnsFuncCreated );
505 EXPECT_EQ( nUpdateModified, nEnsFuncModified );
507 // nTestFunctorRef is call count of insert functor
508 EXPECT_EQ( nTestFunctorRef, nInsertSuccess );
511 for ( size_t * p = m_pKeyFirst; p != m_pKeyLast; ++p )
514 EXPECT_TRUE( testSet.empty());
515 EXPECT_EQ( testSet.size(), 0u );
517 additional_check( testSet );
518 print_stat( propout(), testSet );
520 additional_cleanup( testSet );
536 for ( auto it = s.begin(); it != s.end(); ++it )
537 std::cout << "key=" << it->key << std::endl;
541 class Set_InsDel_func_LF: public Set_InsDel_func
542 , public ::testing::WithParamInterface<size_t>
548 s_nLoadFactor = GetParam();
549 propout() << std::make_pair( "load_factor", s_nLoadFactor );
550 Set_InsDel_func::run_test<Set>();
556 s_nLoadFactor = GetParam();
557 propout() << std::make_pair( "load_factor", s_nLoadFactor );
558 Set_InsDel_func::run_test2<Set>();
561 static std::vector<size_t> get_load_factors();