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.
31 #include "set2/set_type.h"
32 #include "cppunit/thread.h"
38 #define TEST_CASE(TAG, X) void X();
40 class Set_InsDel_string: public CppUnitMini::TestCase
43 size_t c_nSetSize = 1000000; // set size
44 size_t c_nInsertThreadCount = 4; // count of insertion thread
45 size_t c_nDeleteThreadCount = 4; // count of deletion thread
46 size_t c_nThreadPassCount = 4; // pass count for each thread
47 size_t c_nMaxLoadFactor = 8; // maximum load factor
48 bool c_bPrintGCState = true;
50 size_t c_nCuckooInitialSize = 1024;// initial size for CuckooSet
51 size_t c_nCuckooProbesetSize = 16; // CuckooSet probeset size (only for list-based probeset)
52 size_t c_nCuckooProbesetThreshold = 0; // CUckooSet probeset threshold (0 - use default)
54 size_t c_nFeldmanSet_HeadBits = 10;
55 size_t c_nFeldmanSet_ArrayBits = 4;
57 size_t c_nLoadFactor = 2;
60 typedef std::string key_type;
61 typedef size_t value_type;
63 const std::vector<std::string> * m_parrString;
66 class Inserter: public CppUnitMini::TestThread
69 typedef typename Set::value_type keyval_type;
71 virtual Inserter * clone()
73 return new Inserter( *this );
76 size_t m_nInsertSuccess;
77 size_t m_nInsertFailed;
80 Inserter( CppUnitMini::ThreadPool& pool, Set& rSet )
81 : CppUnitMini::TestThread( pool )
84 Inserter( Inserter& src )
85 : CppUnitMini::TestThread( src )
89 Set_InsDel_string& getTest()
91 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
94 virtual void init() { cds::threading::Manager::attachThread() ; }
95 virtual void fini() { cds::threading::Manager::detachThread() ; }
104 const std::vector<std::string>& arrString = *getTest().m_parrString;
105 size_t nArrSize = arrString.size();
106 size_t const nSetSize = getTest().c_nSetSize;
107 size_t const nPassCount = getTest().c_nThreadPassCount;
109 if ( m_nThreadNo & 1 ) {
110 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
111 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
112 if ( rSet.insert( keyval_type(arrString[nItem % nArrSize], nItem * 8) ) )
120 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
121 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
122 if ( rSet.insert( keyval_type( arrString[nItem % nArrSize], nItem * 8) ) )
133 class Deleter: public CppUnitMini::TestThread
137 virtual Deleter * clone()
139 return new Deleter( *this );
142 size_t m_nDeleteSuccess;
143 size_t m_nDeleteFailed;
146 Deleter( CppUnitMini::ThreadPool& pool, Set& rSet )
147 : CppUnitMini::TestThread( pool )
150 Deleter( Deleter& src )
151 : CppUnitMini::TestThread( src )
155 Set_InsDel_string& getTest()
157 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
160 virtual void init() { cds::threading::Manager::attachThread() ; }
161 virtual void fini() { cds::threading::Manager::detachThread() ; }
170 const std::vector<std::string>& arrString = *getTest().m_parrString;
171 size_t nArrSize = arrString.size();
172 size_t const nSetSize = getTest().c_nSetSize;
173 size_t const nPassCount = getTest().c_nThreadPassCount;
175 if ( m_nThreadNo & 1 ) {
176 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
177 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
178 if ( rSet.erase( arrString[nItem % nArrSize] ) )
186 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
187 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
188 if ( rSet.erase( arrString[nItem % nArrSize] ) )
198 template <typename GC, class Set>
199 class Extractor: public CppUnitMini::TestThread
203 virtual Extractor * clone()
205 return new Extractor( *this );
208 size_t m_nDeleteSuccess;
209 size_t m_nDeleteFailed;
212 Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
213 : CppUnitMini::TestThread( pool )
216 Extractor( Extractor& src )
217 : CppUnitMini::TestThread( src )
221 Set_InsDel_string& getTest()
223 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
226 virtual void init() { cds::threading::Manager::attachThread() ; }
227 virtual void fini() { cds::threading::Manager::detachThread() ; }
236 typename Set::guarded_ptr gp;
238 const std::vector<std::string>& arrString = *getTest().m_parrString;
239 size_t nArrSize = arrString.size();
240 size_t const nSetSize = getTest().c_nSetSize;
241 size_t const nPassCount = getTest().c_nThreadPassCount;
243 if ( m_nThreadNo & 1 ) {
244 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
245 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
246 gp = rSet.extract( arrString[nItem % nArrSize]);
256 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
257 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
258 gp = rSet.extract( arrString[nItem % nArrSize]);
270 template <typename RCU, class Set>
271 class Extractor<cds::urcu::gc<RCU>, Set >: public CppUnitMini::TestThread
275 virtual Extractor * clone()
277 return new Extractor( *this );
280 size_t m_nDeleteSuccess;
281 size_t m_nDeleteFailed;
284 Extractor( CppUnitMini::ThreadPool& pool, Set& rSet )
285 : CppUnitMini::TestThread( pool )
288 Extractor( Extractor& src )
289 : CppUnitMini::TestThread( src )
293 Set_InsDel_string& getTest()
295 return reinterpret_cast<Set_InsDel_string&>( m_Pool.m_Test );
298 virtual void init() { cds::threading::Manager::attachThread() ; }
299 virtual void fini() { cds::threading::Manager::detachThread() ; }
308 typename Set::exempt_ptr xp;
310 const std::vector<std::string>& arrString = *getTest().m_parrString;
311 size_t nArrSize = arrString.size();
312 size_t const nSetSize = getTest().c_nSetSize;
313 size_t const nPassCount = getTest().c_nThreadPassCount;
315 if ( m_nThreadNo & 1 ) {
316 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
317 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
318 if ( Set::c_bExtractLockExternal ) {
320 typename Set::rcu_lock l;
321 xp = rSet.extract( arrString[nItem % nArrSize] );
329 xp = rSet.extract( arrString[nItem % nArrSize] );
340 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
341 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
342 if ( Set::c_bExtractLockExternal ) {
344 typename Set::rcu_lock l;
345 xp = rSet.extract( arrString[nItem % nArrSize] );
353 xp = rSet.extract( arrString[nItem % nArrSize] );
368 void do_test( Set& testSet )
370 typedef Inserter<Set> InserterThread;
371 typedef Deleter<Set> DeleterThread;
372 cds::OS::Timer timer;
374 CppUnitMini::ThreadPool pool( *this );
375 pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
376 pool.add( new DeleterThread( pool, testSet ), c_nDeleteThreadCount );
378 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
380 size_t nInsertSuccess = 0;
381 size_t nInsertFailed = 0;
382 size_t nDeleteSuccess = 0;
383 size_t nDeleteFailed = 0;
384 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
385 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
387 nInsertSuccess += pThread->m_nInsertSuccess;
388 nInsertFailed += pThread->m_nInsertFailed;
391 DeleterThread * p = static_cast<DeleterThread *>( *it );
392 nDeleteSuccess += p->m_nDeleteSuccess;
393 nDeleteFailed += p->m_nDeleteFailed;
397 CPPUNIT_MSG( " Totals: Ins succ=" << nInsertSuccess
398 << " Del succ=" << nDeleteSuccess << "\n"
399 << " : Ins fail=" << nInsertFailed
400 << " Del fail=" << nDeleteFailed
401 << " Set size=" << testSet.size()
405 CPPUNIT_MSG( " Clear set (single-threaded)..." );
407 for ( size_t i = 0; i < m_parrString->size(); ++i )
408 testSet.erase( (*m_parrString)[i] );
409 CPPUNIT_MSG( " Duration=" << timer.duration() );
410 CPPUNIT_ASSERT( testSet.empty() );
412 additional_check( testSet );
413 print_stat( testSet );
414 additional_cleanup( testSet );
418 void do_test_extract( Set& testSet )
420 typedef Inserter<Set> InserterThread;
421 typedef Deleter<Set> DeleterThread;
422 typedef Extractor<typename Set::gc, Set> ExtractThread;
424 size_t nDelThreadCount = c_nDeleteThreadCount / 2;
426 CppUnitMini::ThreadPool pool( *this );
427 pool.add( new InserterThread( pool, testSet ), c_nInsertThreadCount );
428 pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
429 pool.add( new ExtractThread( pool, testSet ), c_nDeleteThreadCount - nDelThreadCount );
431 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
433 size_t nInsertSuccess = 0;
434 size_t nInsertFailed = 0;
435 size_t nDeleteSuccess = 0;
436 size_t nDeleteFailed = 0;
437 size_t nExtractSuccess = 0;
438 size_t nExtractFailed = 0;
439 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
440 InserterThread * pThread = dynamic_cast<InserterThread *>( *it );
442 nInsertSuccess += pThread->m_nInsertSuccess;
443 nInsertFailed += pThread->m_nInsertFailed;
446 DeleterThread * p = dynamic_cast<DeleterThread *>( *it );
448 nDeleteSuccess += p->m_nDeleteSuccess;
449 nDeleteFailed += p->m_nDeleteFailed;
452 ExtractThread * pExtract = dynamic_cast<ExtractThread *>( *it );
454 nExtractSuccess += pExtract->m_nDeleteSuccess;
455 nExtractFailed += pExtract->m_nDeleteFailed;
460 CPPUNIT_MSG( " Totals: Ins succ=" << nInsertSuccess
461 << " Del succ=" << nDeleteSuccess
462 << " Extract succ= " << nExtractSuccess << "\n"
463 << " : Ins fail=" << nInsertFailed
464 << " Del fail=" << nDeleteFailed
465 << " Extract fail=" << nExtractFailed
466 << " Set size=" << testSet.size()
470 CPPUNIT_MSG( " Clear set (single-threaded)..." );
471 cds::OS::Timer timer;
472 for ( size_t i = 0; i < m_parrString->size(); ++i )
473 testSet.erase( (*m_parrString)[i] );
474 CPPUNIT_MSG( " Duration=" << timer.duration() );
475 CPPUNIT_ASSERT( testSet.empty() );
477 additional_check( testSet );
478 print_stat( testSet );
479 additional_cleanup( testSet );
485 m_parrString = &CppUnitMini::TestCase::getTestStrings();
487 CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
488 << " delete=" << c_nDeleteThreadCount
489 << " pass count=" << c_nThreadPassCount
490 << " set size=" << c_nSetSize
493 if ( Set::c_bLoadFactorDepended ) {
494 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
495 CPPUNIT_MSG(" LoadFactor = " << c_nLoadFactor );
498 if ( c_bPrintGCState )
505 if ( c_bPrintGCState )
511 void run_test_extract()
513 m_parrString = &CppUnitMini::TestCase::getTestStrings();
515 CPPUNIT_MSG( "Thread count: insert=" << c_nInsertThreadCount
516 << " delete=" << c_nDeleteThreadCount
517 << " pass count=" << c_nThreadPassCount
518 << " set size=" << c_nSetSize
521 if ( Set::c_bLoadFactorDepended ) {
522 for ( c_nLoadFactor = 1; c_nLoadFactor <= c_nMaxLoadFactor; c_nLoadFactor *= 2 ) {
523 CPPUNIT_MSG(" LoadFactor = " << c_nLoadFactor );
525 do_test_extract( s );
526 if ( c_bPrintGCState )
532 do_test_extract( s );
533 if ( c_bPrintGCState )
538 void setUpParams( const CppUnitMini::TestCfg& cfg );
540 # include "set2/set_defs.h"
541 CDSUNIT_DECLARE_MichaelSet
542 CDSUNIT_DECLARE_SplitList
543 CDSUNIT_DECLARE_StripedSet
544 CDSUNIT_DECLARE_RefinableSet
545 CDSUNIT_DECLARE_CuckooSet
546 CDSUNIT_DECLARE_SkipListSet
547 CDSUNIT_DECLARE_EllenBinTreeSet
548 CDSUNIT_DECLARE_FeldmanHashSet_stdhash
549 CDSUNIT_DECLARE_FeldmanHashSet_city
550 CDSUNIT_DECLARE_StdSet
552 CPPUNIT_TEST_SUITE_(Set_InsDel_string, "Map_InsDel_func")
553 CDSUNIT_TEST_MichaelSet
554 CDSUNIT_TEST_SplitList
555 CDSUNIT_TEST_SkipListSet
556 CDSUNIT_TEST_FeldmanHashSet_stdhash
557 CDSUNIT_TEST_FeldmanHashSet_city
558 CDSUNIT_TEST_EllenBinTreeSet
559 CDSUNIT_TEST_StripedSet
560 CDSUNIT_TEST_RefinableSet
561 CDSUNIT_TEST_CuckooSet
563 CPPUNIT_TEST_SUITE_END();