tests/unit/stack/stack_pushpop.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/pop 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_nPushThreadCount = 4;
  16         static size_t s_nPopThreadCount = 4;
  17         static size_t s_nStackSize = 1000000;
  18         static size_t s_nEliminationSize = 4;
  19
  20         struct SimpleValue {
  21             size_t      nNo;
  22             size_t      nThread;
  23
  24             SimpleValue(): nNo(0), nThread(0) {}
  25             SimpleValue( size_t n ): nNo(n), nThread(0) {}
  26             size_t getNo() const { return  nNo; }
  27         };
  28     }
  29
  30     class Stack_PushPop: public CppUnitMini::TestCase
  31     {
  32         CDS_ATOMIC::atomic<size_t>  m_nWorkingProducers;
  33         static size_t const c_nValArraySize = 1024;
  34
  35         template <class Stack>
  36         class Pusher: public CppUnitMini::TestThread
  37         {
  38             virtual TestThread *    clone()
  39             {
  40                 return new Pusher( *this );
  41             }
  42         public:
  43             Stack&              m_Stack;
  44             size_t              m_nItemCount;
  45             size_t              m_nPushError;
  46             size_t              m_arrPush[c_nValArraySize];
  47
  48         public:
  49             Pusher( CppUnitMini::ThreadPool& pool, Stack& s )
  50                 : CppUnitMini::TestThread( pool )
  51                 , m_Stack( s )
  52             {}
  53             Pusher( Pusher& src )
  54                 : CppUnitMini::TestThread( src )
  55                 , m_Stack( src.m_Stack )
  56             {}
  57
  58             Stack_PushPop&  getTest()
  59             {
  60                 return reinterpret_cast<Stack_PushPop&>( m_Pool.m_Test );
  61             }
  62
  63             virtual void init()
  64             {
  65                 cds::threading::Manager::attachThread();
  66             }
  67             virtual void fini()
  68             {
  69                 cds::threading::Manager::detachThread();
  70             }
  71
  72             virtual void test()
  73             {
  74                 m_nPushError = 0;
  75                 memset( m_arrPush, 0, sizeof(m_arrPush));
  76
  77                 SimpleValue v;
  78                 v.nThread = m_nThreadNo;
  79                 for ( size_t i = 0; i < m_nItemCount; ++i ) {
  80                     v.nNo = i % c_nValArraySize;
  81                     if ( m_Stack.push( v ))
  82                         ++m_arrPush[v.nNo];
  83                     else
  84                         ++m_nPushError;
  85                 }
  86
  87
  88                 getTest().m_nWorkingProducers.fetch_sub(1, CDS_ATOMIC::memory_order_release);
  89             }
  90         };
  91
  92         template <class Stack>
  93         class Popper: public CppUnitMini::TestThread
  94         {
  95             virtual TestThread *    clone()
  96             {
  97                 return new Popper( *this );
  98             }
  99         public:
 100             Stack&              m_Stack;
 101             size_t              m_nPopCount;
 102             size_t              m_nPopEmpty;
 103             size_t              m_arrPop[c_nValArraySize];
 104             size_t              m_nDirtyPop;
 105         public:
 106             Popper( CppUnitMini::ThreadPool& pool, Stack& s )
 107                 : CppUnitMini::TestThread( pool )
 108                 , m_Stack( s )
 109             {}
 110             Popper( Popper& src )
 111                 : CppUnitMini::TestThread( src )
 112                 , m_Stack( src.m_Stack )
 113             {}
 114
 115             Stack_PushPop&  getTest()
 116             {
 117                 return reinterpret_cast<Stack_PushPop&>( m_Pool.m_Test );
 118             }
 119
 120             virtual void init()
 121             {
 122                 cds::threading::Manager::attachThread();
 123             }
 124             virtual void fini()
 125             {
 126                 cds::threading::Manager::detachThread();
 127             }
 128
 129             virtual void test()
 130             {
 131                 m_nPopEmpty = 0;
 132                 m_nPopCount = 0;
 133                 m_nDirtyPop = 0;
 134                 memset( m_arrPop, 0, sizeof(m_arrPop));
 135
 136                 SimpleValue v;
 137                 while ( !(getTest().m_nWorkingProducers.load(CDS_ATOMIC::memory_order_acquire) == 0 && m_Stack.empty()) ) {
 138                     if ( m_Stack.pop( v )) {
 139                         ++m_nPopCount;
 140                         if ( v.nNo < sizeof(m_arrPop)/sizeof(m_arrPop[0]) )
 141                             ++m_arrPop[v.nNo];
 142                         else
 143                             ++m_nDirtyPop;
 144                     }
 145                     else
 146                         ++m_nPopEmpty;
 147                 }
 148             }
 149         };
 150
 151     protected:
 152         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 153             s_nPushThreadCount = cfg.getULong("PushThreadCount", 4 );
 154             s_nPopThreadCount = cfg.getULong("PopThreadCount", 4 );
 155             s_nStackSize = cfg.getULong("StackSize", 1000000 );
 156             s_nEliminationSize = cfg.getULong("EliminationSize", 4 );
 157         }
 158
 159         template <class Stack>
 160         void analyze( CppUnitMini::ThreadPool& pool, Stack& testStack  )
 161         {
 162             size_t nPushError = 0;
 163             size_t nPopEmpty = 0;
 164             size_t nPopCount = 0;
 165             size_t arrVal[c_nValArraySize];
 166             memset( arrVal, 0, sizeof(arrVal));
 167             size_t nDirtyPop = 0;
 168
 169             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 170                 CppUnitMini::TestThread * pThread = *it;
 171                 Pusher<Stack> * pPusher = dynamic_cast< Pusher<Stack> *>( pThread );
 172                 if ( pPusher ) {
 173                     nPushError += pPusher->m_nPushError;
 174                     for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
 175                         arrVal[i] += pPusher->m_arrPush[i];
 176                 }
 177                 else {
 178                     Popper<Stack> * pPopper = dynamic_cast<Popper<Stack> *>( pThread );
 179                     assert( pPopper );
 180                     nPopEmpty += pPopper->m_nPopEmpty;
 181                     nPopCount += pPopper->m_nPopCount;
 182                     nDirtyPop += pPopper->m_nDirtyPop;
 183                     for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
 184                         arrVal[i] -= pPopper->m_arrPop[i];
 185                 }
 186             }
 187
 188             CPPUNIT_MSG( "Push count=" << s_nStackSize
 189                 << " push error=" << nPushError
 190                 << " pop count=" << nPopCount
 191                 << " pop empty=" << nPopEmpty
 192                 << " dirty pop=" << nDirtyPop
 193                 );
 194             CPPUNIT_CHECK( nPopCount == s_nStackSize );
 195             CPPUNIT_CHECK( nDirtyPop == 0 );
 196             for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i ) {
 197                 CPPUNIT_CHECK_EX( arrVal[i] == 0, "arrVal[" << i << "]=" << long(arrVal[i]) );
 198             }
 199         }
 200
 201         // Unbounded stack test
 202         template <class Stack>
 203         void test_unbounded()
 204         {
 205             Stack testStack;
 206             test( testStack );
 207         }
 208
 209         // Unbounded elimination stack test
 210         template <class Stack>
 211         void test_elimination()
 212         {
 213             Stack testStack( s_nEliminationSize );
 214             test( testStack );
 215             check_elimination_stat( testStack.statistics() );
 216         }
 217         void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
 218         {}
 219         void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
 220         {
 221             CPPUNIT_CHECK( s.m_PushCount.get() + s.m_ActivePushCollision.get() + s.m_PassivePushCollision.get() == s_nStackSize );
 222             CPPUNIT_CHECK( s.m_PopCount.get() + s.m_ActivePopCollision.get() + s.m_PassivePopCollision.get() == s_nStackSize );
 223             CPPUNIT_CHECK( s.m_PushCount.get() == s.m_PopCount.get() );
 224             CPPUNIT_CHECK( s.m_ActivePopCollision.get() == s.m_PassivePushCollision.get() );
 225             CPPUNIT_CHECK( s.m_ActivePushCollision.get() == s.m_PassivePopCollision.get() );
 226         }
 227
 228         // Bounded stack test
 229         template <class Stack>
 230         void test_bounded()
 231         {
 232             Stack testStack( s_nStackSize );
 233             test( testStack );
 234         }
 235
 236         template <class Stack>
 237         void test( Stack& testStack )
 238         {
 239             m_nWorkingProducers.store(s_nPushThreadCount, CDS_ATOMIC::memory_order_release);
 240             size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
 241
 242             CppUnitMini::ThreadPool pool( *this );
 243             pool.add( new Pusher<Stack>( pool, testStack ), s_nPushThreadCount );
 244             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it )
 245                 static_cast<Pusher<Stack>* >( *it )->m_nItemCount = nPushCount;
 246             pool.add( new Popper<Stack>( pool, testStack ), s_nPopThreadCount );
 247
 248             CPPUNIT_MSG( "   Push/Pop test, push thread count=" << s_nPushThreadCount
 249                 << " pop thread count=" << s_nPopThreadCount
 250                 << " items=" << (nPushCount * s_nPushThreadCount)
 251                 << "...");
 252             pool.run();
 253             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 254
 255             s_nStackSize = nPushCount * s_nPushThreadCount;
 256             analyze( pool, testStack );
 257             CPPUNIT_MSG( testStack.statistics() );
 258         }
 259
 260     protected:
 261 #   include "stack/stack_defs.h"
 262         CDSUNIT_DECLARE_TreiberStack
 263         CDSUNIT_DECLARE_EliminationStack
 264         CDSUNIT_DECLARE_FCStack
 265         CDSUNIT_DECLARE_FCDeque
 266         CDSUNIT_DECLARE_MichaelDeque
 267         CDSUNIT_DECLARE_StdStack
 268
 269         CPPUNIT_TEST_SUITE(Stack_PushPop)
 270             CDSUNIT_TEST_TreiberStack
 271             CDSUNIT_TEST_EliminationStack
 272             CDSUNIT_TEST_FCStack
 273             CDSUNIT_TEST_FCDeque
 274             CDSUNIT_TEST_MichaelDeque
 275             CDSUNIT_TEST_StdStack
 276         CPPUNIT_TEST_SUITE_END();
 277     };
 278 } // namespace stack
 279
 280 CPPUNIT_TEST_SUITE_REGISTRATION(stack::Stack_PushPop);