test/stress/stack/push_pop.cpp

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13     list of conditions and the following disclaimer.
  14
  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.
  18
  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.
  29 */
  30
  31 #include "stack_type.h"
  32 #include "../misc/common.h"
  33
  34 namespace {
  35
  36     static size_t s_nPushThreadCount = 4;
  37     static size_t s_nPopThreadCount = 4;
  38     static size_t s_nStackSize = 1000000;
  39     static size_t s_nEliminationStackSize = 500000;
  40     static size_t s_nEliminationSize = 4;
  41
  42     static atomics::atomic<size_t>  s_nWorkingProducers( 0 );
  43
  44     class stack_push_pop : public cds_test::stress_fixture
  45     {
  46     protected:
  47         enum thread_type
  48         {
  49             producer_thread,
  50             consumer_thread
  51         };
  52
  53         struct value_type {
  54             size_t      nNo;
  55             size_t      nThread;
  56
  57             value_type()
  58                 : nNo( 0 )
  59                 , nThread( 0 )
  60             {}
  61             value_type( size_t n )
  62                 : nNo( n )
  63                 , nThread( 0 )
  64             {}
  65         };
  66
  67         static size_t const c_nValArraySize = 1024;
  68
  69         template <class Stack>
  70         class Producer: public cds_test::thread
  71         {
  72             typedef cds_test::thread base_class;
  73
  74         public:
  75             Producer( cds_test::thread_pool& pool, Stack& stack, size_t push_count )
  76                 : base_class( pool, producer_thread )
  77                 , m_stack( stack )
  78                 , m_nItemCount( push_count )
  79                 , m_nPushError( 0 )
  80             {}
  81
  82             Producer( Producer& src )
  83                 : base_class( src )
  84                 , m_stack( src.m_stack )
  85                 , m_nItemCount( src.m_nItemCount )
  86                 , m_nPushError( 0 )
  87             {}
  88
  89             virtual thread * clone()
  90             {
  91                 return new Producer( *this );
  92             }
  93
  94             virtual void test()
  95             {
  96                 memset( m_arrPush, 0, sizeof( m_arrPush ));
  97
  98                 value_type v;
  99                 v.nThread = id();
 100                 for ( size_t i = 0; i < m_nItemCount; ++i ) {
 101                     v.nNo = i % c_nValArraySize;
 102                     if ( m_stack.push( v ))
 103                         ++m_arrPush[v.nNo];
 104                     else
 105                         ++m_nPushError;
 106                 }
 107
 108                 s_nWorkingProducers.fetch_sub( 1, atomics::memory_order_release );
 109             }
 110
 111         public:
 112             Stack&  m_stack;
 113             size_t const m_nItemCount;
 114             size_t  m_nPushError;
 115             size_t  m_arrPush[c_nValArraySize];
 116         };
 117
 118         template <class Stack>
 119         class Consumer : public cds_test::thread
 120         {
 121             typedef cds_test::thread base_class;
 122
 123         public:
 124             Consumer( cds_test::thread_pool& pool, Stack& stack )
 125                 : base_class( pool, consumer_thread )
 126                 , m_stack( stack )
 127                 , m_nPopCount( 0 )
 128                 , m_nPopEmpty( 0 )
 129                 , m_nDirtyPop( 0 )
 130             {}
 131
 132             Consumer( Consumer& src )
 133                 : base_class( src )
 134                 , m_stack( src.m_stack )
 135                 , m_nPopCount( 0 )
 136                 , m_nPopEmpty( 0 )
 137                 , m_nDirtyPop( 0 )
 138             {}
 139
 140             virtual thread * clone()
 141             {
 142                 return new Consumer( *this );
 143             }
 144
 145             virtual void test()
 146             {
 147                 memset( m_arrPop, 0, sizeof( m_arrPop ));
 148
 149                 value_type v;
 150                 while ( !( s_nWorkingProducers.load( atomics::memory_order_acquire ) == 0 && m_stack.empty())) {
 151                     if ( m_stack.pop( v )) {
 152                         ++m_nPopCount;
 153                         if ( v.nNo < sizeof( m_arrPop ) / sizeof( m_arrPop[0] ))
 154                             ++m_arrPop[v.nNo];
 155                         else
 156                             ++m_nDirtyPop;
 157                     }
 158                     else
 159                         ++m_nPopEmpty;
 160                 }
 161             }
 162
 163         public:
 164             Stack& m_stack;
 165             size_t m_nPopCount;
 166             size_t m_nPopEmpty;
 167             size_t m_arrPop[c_nValArraySize];
 168             size_t m_nDirtyPop;
 169         };
 170
 171     protected:
 172         static void SetUpTestCase()
 173         {
 174             cds_test::config const& cfg = get_config("Stack_PushPop");
 175
 176             s_nPushThreadCount = cfg.get_size_t( "PushThreadCount", s_nPushThreadCount );
 177             s_nPopThreadCount  = cfg.get_size_t( "PopThreadCount",  s_nPopThreadCount );
 178             s_nStackSize       = cfg.get_size_t( "StackSize",       s_nStackSize );
 179             s_nEliminationStackSize =
 180                 cfg.get_size_t("EliminationStackSize", s_nEliminationStackSize);
 181             s_nEliminationSize = cfg.get_size_t( "EliminationSize", s_nEliminationSize );
 182
 183             if ( s_nPushThreadCount == 0 )
 184                 s_nPushThreadCount = 1;
 185             if ( s_nPopThreadCount == 0 )
 186                 s_nPopThreadCount = 1;
 187         }
 188
 189         //static void TearDownTestCase();
 190
 191         template <typename Stack>
 192         void test( Stack& stack )
 193         {
 194             cds_test::thread_pool& pool = get_pool();
 195             size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
 196
 197             pool.add( new Producer<Stack>( pool, stack, nPushCount ), s_nPushThreadCount );
 198             pool.add( new Consumer<Stack>( pool, stack ), s_nPopThreadCount );
 199
 200             s_nWorkingProducers.store( s_nPushThreadCount );
 201             s_nStackSize = nPushCount * s_nPushThreadCount;
 202
 203             propout() << std::make_pair( "producer_thread_count", s_nPushThreadCount )
 204                 << std::make_pair( "consumer_thread_count", s_nPopThreadCount )
 205                 << std::make_pair( "push_count", s_nStackSize )
 206 ;
 207
 208             std::chrono::milliseconds duration = pool.run();
 209
 210             propout() << std::make_pair( "duration", duration );
 211
 212             DEBUG(analyze( stack ));
 213
 214             propout() << stack.statistics();
 215         }
 216
 217         template <typename Stack>
 218         void test_elimination( Stack& stack )
 219         {
 220             test( stack );
 221             check_elimination_stat( stack.statistics());
 222         }
 223
 224         void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
 225         {}
 226
 227         void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
 228         {
 229             EXPECT_EQ( s.m_PushCount.get() + s.m_ActivePushCollision.get() + s.m_PassivePushCollision.get(), s_nStackSize );
 230             EXPECT_EQ( s.m_PopCount.get() + s.m_ActivePopCollision.get() + s.m_PassivePopCollision.get(), s_nStackSize );
 231             EXPECT_EQ( s.m_PushCount.get(), s.m_PopCount.get());
 232             EXPECT_EQ( s.m_ActivePopCollision.get(), s.m_PassivePushCollision.get());
 233             EXPECT_EQ( s.m_ActivePushCollision.get(), s.m_PassivePopCollision.get());
 234         }
 235
 236         template< class Stack>
 237         void analyze( Stack& /*stack*/ )
 238         {
 239             cds_test::thread_pool& pool = get_pool();
 240
 241             size_t nPushError = 0;
 242             size_t nPopEmpty = 0;
 243             size_t nPopCount = 0;
 244             size_t arrVal[c_nValArraySize];
 245             memset( arrVal, 0, sizeof( arrVal ));
 246             size_t nDirtyPop = 0;
 247
 248             for ( size_t threadNo = 0; threadNo < pool.size(); ++threadNo ) {
 249                 cds_test::thread& thread = pool.get( threadNo );
 250                 if ( thread.type() == producer_thread ) {
 251                     Producer<Stack>& producer = static_cast<Producer<Stack>&>( thread );
 252
 253                     nPushError += producer.m_nPushError;
 254                     for ( size_t i = 0; i < c_nValArraySize; ++i )
 255                         arrVal[i] += producer.m_arrPush[i];
 256                 }
 257                 else {
 258                     ASSERT_EQ( thread.type(), consumer_thread );
 259                     Consumer<Stack>& consumer = static_cast<Consumer<Stack>&>(thread);
 260
 261                     nPopEmpty += consumer.m_nPopEmpty;
 262                     nPopCount += consumer.m_nPopCount;
 263                     nDirtyPop += consumer.m_nDirtyPop;
 264                     for ( size_t i = 0; i < c_nValArraySize; ++i )
 265                         arrVal[i] -= consumer.m_arrPop[i];
 266                 }
 267             }
 268
 269             EXPECT_EQ( nPopCount, s_nStackSize );
 270             EXPECT_EQ( nDirtyPop, 0u );
 271
 272             for ( size_t i = 0; i < sizeof( arrVal ) / sizeof( arrVal[0] ); ++i ) {
 273                 EXPECT_EQ( arrVal[i], 0u );
 274             }
 275
 276             propout() << std::make_pair( "push_count", s_nStackSize )
 277                       << std::make_pair( "push_error", nPushError )
 278                       << std::make_pair( "pop_empty", nPopEmpty )
 279                       << std::make_pair( "dirty_pop", nDirtyPop )
 280 ;
 281         }
 282     };
 283
 284     CDSSTRESS_TreiberStack( stack_push_pop )
 285
 286     #undef CDSSTRESS_EliminationStack_F
 287
 288     #define CDSSTRESS_EliminationStack_F( test_fixture, type_name ) \
 289     TEST_F( test_fixture, type_name ) \
 290     { \
 291         typedef stack::Types< value_type >::type_name stack_type; \
 292         s_nStackSize = s_nEliminationStackSize; \
 293         stack_type stack( s_nEliminationSize ); \
 294         test_elimination( stack ); \
 295     }
 296
 297     CDSSTRESS_EliminationStack( stack_push_pop )
 298     //CDSSTRESS_FCStack( stack_push_pop )
 299     //CDSSTRESS_FCDeque( stack_push_pop )
 300
 301 } // namespace