tests/unit/stack/stack_push.cpp

   1 //$$CDS-header$$
   2
   3 #include "cppunit/thread.h"
   4 #include "stack/stack_type.h"
   5 #include "print_deque_stat.h"
   6
   7 // Multi-threaded stack test for push operation
   8 namespace stack {
   9
  10 #define TEST_CASE( Q ) void Q()          { test_unbounded< Types<SimpleValue>::Q >(); }
  11 #define TEST_ELIMINATION( Q ) void Q()   { test_elimination< Types<SimpleValue>::Q >(); }
  12 #define TEST_BOUNDED( Q ) void Q()       { test_bounded< Types<SimpleValue>::Q >(); }
  13
  14     namespace {
  15         static size_t s_nThreadCount = 8;
  16         static size_t s_nStackSize = 10000000;
  17         static size_t s_nEliminationSize = 4;
  18
  19         struct SimpleValue {
  20             size_t      nNo;
  21             size_t      nThread;
  22
  23             SimpleValue(): nNo(0), nThread(0) {}
  24             SimpleValue( size_t n ): nNo(n), nThread(0) {}
  25             size_t getNo() const { return  nNo; }
  26         };
  27     }
  28
  29     class Stack_Push: public CppUnitMini::TestCase
  30     {
  31         template <class Stack>
  32         class Thread: public CppUnitMini::TestThread
  33         {
  34             virtual TestThread *    clone()
  35             {
  36                 return new Thread( *this );
  37             }
  38         public:
  39             Stack&              m_Stack;
  40             double              m_fTime;
  41             size_t              m_nStartItem;
  42             size_t              m_nEndItem;
  43             size_t              m_nPushError;
  44
  45         public:
  46             Thread( CppUnitMini::ThreadPool& pool, Stack& s )
  47                 : CppUnitMini::TestThread( pool )
  48                 , m_Stack( s )
  49             {}
  50             Thread( Thread& src )
  51                 : CppUnitMini::TestThread( src )
  52                 , m_Stack( src.m_Stack )
  53             {}
  54
  55             Stack_Push&  getTest()
  56             {
  57                 return reinterpret_cast<Stack_Push&>( m_Pool.m_Test );
  58             }
  59
  60             virtual void init()
  61             {
  62                 cds::threading::Manager::attachThread();
  63             }
  64             virtual void fini()
  65             {
  66                 cds::threading::Manager::detachThread();
  67             }
  68
  69             virtual void test()
  70             {
  71                 m_fTime = m_Timer.duration();
  72
  73                 m_nPushError = 0;
  74                 SimpleValue v;
  75                 v.nThread = m_nThreadNo;
  76                 for ( v.nNo = m_nStartItem; v.nNo < m_nEndItem; ++v.nNo ) {
  77                     if ( !m_Stack.push( v ))
  78                         ++m_nPushError;
  79                 }
  80
  81                 m_fTime = m_Timer.duration() - m_fTime;
  82             }
  83         };
  84
  85     protected:
  86         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
  87             s_nThreadCount = cfg.getULong("ThreadCount", 8 );
  88             s_nStackSize = cfg.getULong("StackSize", 10000000 );
  89             s_nEliminationSize = cfg.getULong("EliminationSize", 4 );
  90         }
  91
  92         template <class Stack>
  93         void analyze( CppUnitMini::ThreadPool& pool, Stack& testStack  )
  94         {
  95             size_t nThreadItems = s_nStackSize / s_nThreadCount;
  96             std::vector<size_t> aThread;
  97             aThread.resize(s_nThreadCount);
  98
  99             double fTime = 0;
 100             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 101                 Thread<Stack> * pThread = reinterpret_cast<Thread<Stack> *>(*it);
 102                 fTime += pThread->m_fTime;
 103                 if ( pThread->m_nPushError != 0 )
 104                     CPPUNIT_MSG("     ERROR: thread push error count=" << pThread->m_nPushError );
 105                 aThread[ pThread->m_nThreadNo] = pThread->m_nEndItem - 1;
 106             }
 107             CPPUNIT_MSG( "     Duration=" << (fTime / s_nThreadCount) );
 108             CPPUNIT_ASSERT( !testStack.empty() )
 109
 110             size_t * arr = new size_t[ s_nStackSize ];
 111             memset(arr, 0, sizeof(arr[0]) * s_nStackSize );
 112
 113             cds::OS::Timer      timer;
 114             CPPUNIT_MSG( "   Pop (single-threaded)..." );
 115             size_t nPopped = 0;
 116             SimpleValue val;
 117             while ( testStack.pop( val )) {
 118                 nPopped++;
 119                 ++arr[ val.getNo() ];
 120                 CPPUNIT_ASSERT( val.nThread < s_nThreadCount);
 121                 CPPUNIT_ASSERT( aThread[val.nThread] == val.nNo );
 122                 aThread[val.nThread]--;
 123             }
 124             CPPUNIT_MSG( "     Duration=" << timer.duration() );
 125
 126             size_t nTotalItems = nThreadItems * s_nThreadCount;
 127             size_t nError = 0;
 128             for ( size_t i = 0; i < nTotalItems; ++i ) {
 129                 if ( arr[i] != 1 ) {
 130                     CPPUNIT_MSG( "   ERROR: Item " << i << " has not been pushed" );
 131                     CPPUNIT_ASSERT( ++nError > 10 );
 132                 }
 133             }
 134
 135             delete [] arr;
 136         }
 137
 138         // Unbounded stack test
 139         template <class Stack>
 140         void test_unbounded()
 141         {
 142             Stack testStack;
 143             test( testStack );
 144         }
 145
 146         // Unbounded elimination stack test
 147         template <class Stack>
 148         void test_elimination()
 149         {
 150             Stack testStack( s_nEliminationSize );
 151             test( testStack );
 152             check_elimination_stat( testStack.statistics() );
 153         }
 154         void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
 155         {}
 156         void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
 157         {
 158             CPPUNIT_CHECK( s.m_PushCount.get() == s.m_PopCount.get() );
 159         }
 160
 161         // Bounded stack test
 162         template <class Stack>
 163         void test_bounded()
 164         {
 165             Stack testStack( s_nStackSize );
 166             test( testStack );
 167         }
 168
 169         template <class Stack>
 170         void test( Stack& testStack )
 171         {
 172             CppUnitMini::ThreadPool pool( *this );
 173             pool.add( new Thread<Stack>( pool, testStack ), s_nThreadCount );
 174
 175             size_t nStart = 0;
 176             size_t nThreadItemCount = s_nStackSize / s_nThreadCount;
 177             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 178                 Thread<Stack> * pThread = reinterpret_cast<Thread<Stack> *>(*it);
 179                 pThread->m_nStartItem = nStart;
 180                 nStart += nThreadItemCount;
 181                 pThread->m_nEndItem = nStart;
 182             }
 183
 184             CPPUNIT_MSG( "   Push test, thread count=" << s_nThreadCount
 185                 << " items=" << (nThreadItemCount * s_nThreadCount)
 186                 << "...");
 187             pool.run();
 188
 189             analyze( pool, testStack );
 190             CPPUNIT_MSG( testStack.statistics() );
 191         }
 192
 193     protected:
 194 #   include "stack/stack_defs.h"
 195         CDSUNIT_DECLARE_TreiberStack
 196         CDSUNIT_DECLARE_EliminationStack
 197         CDSUNIT_DECLARE_FCStack
 198         CDSUNIT_DECLARE_FCDeque
 199         CDSUNIT_DECLARE_MichaelDeque
 200         CDSUNIT_DECLARE_StdStack
 201
 202         CPPUNIT_TEST_SUITE(Stack_Push)
 203             CDSUNIT_TEST_TreiberStack
 204             CDSUNIT_TEST_EliminationStack
 205             CDSUNIT_TEST_FCStack
 206             CDSUNIT_TEST_FCDeque
 207             CDSUNIT_TEST_MichaelDeque
 208             CDSUNIT_TEST_StdStack
 209         CPPUNIT_TEST_SUITE_END();
 210     };
 211 } // namespace stack
 212
 213 CPPUNIT_TEST_SUITE_REGISTRATION(stack::Stack_Push);