tests/unit/stack/stack_push.cpp

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