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;
139 size_t m_nTestFunctorRef = 0;
142 Inserter( cds_test::thread_pool& pool, Set& set )
143 : base_class( pool, insert_thread )
147 Inserter( Inserter& src )
152 virtual thread * clone()
154 return new Inserter( *this );
160 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
162 size_t * pKeyFirst = fixture.m_pKeyFirst;
163 size_t * pKeyLast = fixture.m_pKeyLast;
164 size_t const nPassCount = fixture.s_nThreadPassCount;
166 // func is passed by reference
170 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
171 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
172 if ( rSet.insert( *p, std::ref( func )))
180 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
181 for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
182 if ( rSet.insert( *p, std::ref( func )))
190 m_nTestFunctorRef = func.nTestFunctorRef;
195 class Updater: public cds_test::thread
197 typedef cds_test::thread base_class;
200 typedef typename Set::value_type keyval_type;
202 struct update_functor {
204 size_t nModified = 0;
207 update_functor( const update_functor& ) = delete;
209 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
211 std::unique_lock<typename value::lock_type> ac( val.val.m_access );
212 if ( !val.val.bInitialized )
214 val.val.nKey = val.key;
215 val.val.nData = val.key * 8;
216 val.val.bInitialized = true;
223 val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
228 void operator()( keyval_type& cur, keyval_type * old )
230 operator()( old == nullptr, cur, 0 );
235 size_t m_nUpdateFailed = 0;
236 size_t m_nUpdateCreated = 0;
237 size_t m_nUpdateExisted = 0;
238 size_t m_nFunctorCreated = 0;
239 size_t m_nFunctorModified = 0;
242 Updater( cds_test::thread_pool& pool, Set& set )
243 : base_class( pool, update_thread )
247 Updater( Updater& src )
252 virtual thread * clone()
254 return new Updater( *this );
261 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
262 size_t * pKeyFirst = fixture.m_pKeyFirst;
263 size_t * pKeyLast = fixture.m_pKeyLast;
264 size_t const nPassCount = fixture.s_nThreadPassCount;
269 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
270 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
271 std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
284 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
285 for ( size_t * p = pKeyLast - 1 ; p >= pKeyFirst; --p ) {
286 std::pair<bool, bool> ret = rSet.update( *p, std::ref( func ), true );
299 m_nFunctorCreated = func.nCreated;
300 m_nFunctorModified = func.nModified;
305 class Deleter: public cds_test::thread
307 typedef cds_test::thread base_class;
310 typedef typename Set::value_type keyval_type;
312 struct value_container
316 size_t nSuccessItem = 0;
317 size_t nFailedItem = 0;
320 struct erase_functor {
321 value_container m_cnt;
323 void operator ()( keyval_type const& itm )
325 keyval_type& item = const_cast<keyval_type&>(itm);
329 std::unique_lock< typename value::lock_type> ac( item.val.m_access );
330 if ( item.val.bInitialized ) {
331 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
332 ++m_cnt.nSuccessItem;
343 cds::backoff::yield()();
349 size_t m_nDeleteSuccess = 0;
350 size_t m_nDeleteFailed = 0;
351 size_t m_nValueSuccess = 0;
352 size_t m_nValueFailed = 0;
355 Deleter( cds_test::thread_pool& pool, Set& set )
356 : base_class( pool, delete_thread )
360 Deleter( Deleter& src )
365 virtual thread * clone()
367 return new Deleter( *this );
374 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
375 size_t * pKeyFirst = fixture.m_pKeyFirst;
376 size_t * pKeyLast = fixture.m_pKeyLast;
377 size_t const nPassCount = fixture.s_nThreadPassCount;
382 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
383 for ( size_t * p = pKeyFirst; p < pKeyLast; ++p ) {
384 func.m_cnt.nKeyExpected = *p;
385 if ( rSet.erase( *p, std::ref( func )))
393 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
394 for ( size_t * p = pKeyLast - 1; p >= pKeyFirst; --p ) {
395 func.m_cnt.nKeyExpected = *p;
396 if ( rSet.erase( *p, std::ref( func )))
404 m_nValueSuccess = func.m_cnt.nSuccessItem;
405 m_nValueFailed = func.m_cnt.nFailedItem;
412 void run_test( Set& testSet )
414 typedef Inserter<Set> InserterThread;
415 typedef Deleter<Set> DeleterThread;
416 typedef Updater<Set> UpdaterThread;
418 m_pKeyArr = new size_t[ s_nSetSize ];
419 m_pKeyFirst = m_pKeyArr;
420 m_pKeyLast = m_pKeyFirst + s_nSetSize;
421 for ( size_t i = 0; i < s_nSetSize; ++i )
423 shuffle( m_pKeyFirst, m_pKeyLast );
425 cds_test::thread_pool& pool = get_pool();
426 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
427 pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
428 pool.add( new UpdaterThread( pool, testSet ), s_nUpdateThreadCount );
430 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
431 << std::make_pair( "update_thread_count", s_nUpdateThreadCount )
432 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
433 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
434 << std::make_pair( "set_size", s_nSetSize );
436 std::chrono::milliseconds duration = pool.run();
438 propout() << std::make_pair( "duration", duration );
442 size_t nInsertSuccess = 0;
443 size_t nInsertFailed = 0;
444 size_t nDeleteSuccess = 0;
445 size_t nDeleteFailed = 0;
446 size_t nDelValueSuccess = 0;
447 size_t nDelValueFailed = 0;
448 size_t nUpdateFailed = 0;
449 size_t nUpdateCreated = 0;
450 size_t nUpdateModified = 0;
451 size_t nEnsFuncCreated = 0;
452 size_t nEnsFuncModified = 0;
453 size_t nTestFunctorRef = 0;
455 for ( size_t i = 0; i < pool.size(); ++i ) {
456 cds_test::thread& thr = pool.get( i );
457 switch ( thr.type() ) {
460 InserterThread& inserter = static_cast<InserterThread&>( thr );
461 nInsertSuccess += inserter.m_nInsertSuccess;
462 nInsertFailed += inserter.m_nInsertFailed;
463 nTestFunctorRef += inserter.m_nTestFunctorRef;
468 UpdaterThread& updater = static_cast<UpdaterThread&>(thr);
469 nUpdateCreated += updater.m_nUpdateCreated;
470 nUpdateModified += updater.m_nUpdateExisted;
471 nUpdateFailed += updater.m_nUpdateFailed;
472 nEnsFuncCreated += updater.m_nFunctorCreated;
473 nEnsFuncModified += updater.m_nFunctorModified;
478 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
479 nDeleteSuccess += deleter.m_nDeleteSuccess;
480 nDeleteFailed += deleter.m_nDeleteFailed;
481 nDelValueSuccess += deleter.m_nValueSuccess;
482 nDelValueFailed += deleter.m_nValueFailed;
489 << std::make_pair( "insert_success", nInsertSuccess )
490 << std::make_pair( "delete_success", nDeleteSuccess )
491 << std::make_pair( "insert_failed", nInsertFailed )
492 << std::make_pair( "delete_failed", nDeleteFailed )
493 << std::make_pair( "update_created", nUpdateCreated )
494 << std::make_pair( "update_modified", nUpdateModified )
495 << std::make_pair( "update_failed", nUpdateFailed )
496 << std::make_pair( "final_set_size", testSet.size() );
499 EXPECT_EQ( nDelValueFailed, 0 );
500 EXPECT_EQ( nDelValueSuccess, nDeleteSuccess );
502 EXPECT_EQ( nUpdateFailed, 0 );
503 EXPECT_EQ( nUpdateCreated, nEnsFuncCreated );
504 EXPECT_EQ( nUpdateModified, nEnsFuncModified );
506 // nTestFunctorRef is call count of insert functor
507 EXPECT_EQ( nTestFunctorRef, nInsertSuccess );
510 EXPECT_TRUE( testSet.empty() );
512 additional_check( testSet );
513 print_stat( propout(), testSet );
515 additional_cleanup( testSet );
526 class Set_InsDel_func_LF: public Set_InsDel_func
527 , public ::testing::WithParamInterface<size_t>
533 s_nLoadFactor = GetParam();
534 propout() << std::make_pair( "load_factor", s_nLoadFactor );
535 Set_InsDel_func::run_test<Set>();
538 static std::vector<size_t> get_load_factors();