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
  33 namespace {
  34
  35     static size_t s_nPushThreadCount = 4;
  36     static size_t s_nPopThreadCount = 4;
  37     static size_t s_nStackSize = 1000000;
  38     static size_t s_nEliminationSize = 4;
  39
  40     static atomics::atomic<size_t>  s_nWorkingProducers( 0 );
  41
  42     class stack_push_pop : public cds_test::stress_fixture
  43     {
  44     protected:
  45         enum thread_type
  46         {
  47             producer_thread,
  48             consumer_thread
  49         };
  50
  51         struct value_type {
  52             size_t      nNo;
  53             size_t      nThread;
  54
  55             value_type()
  56                 : nNo( 0 )
  57                 , nThread( 0 )
  58             {}
  59             value_type( size_t n )
  60                 : nNo( n )
  61                 , nThread( 0 )
  62             {}
  63         };
  64
  65         static size_t const c_nValArraySize = 1024;
  66
  67         template <class Stack>
  68         class Producer: public cds_test::thread
  69         {
  70             typedef cds_test::thread base_class;
  71
  72         public:
  73             Producer( cds_test::thread_pool& pool, Stack& stack, size_t push_count )
  74                 : base_class( pool, producer_thread )
  75                 , m_stack( stack )
  76                 , m_nItemCount( push_count )
  77                 , m_nPushError( 0 )
  78             {}
  79
  80             Producer( Producer& src )
  81                 : base_class( src )
  82                 , m_stack( src.m_stack )
  83                 , m_nItemCount( src.m_nItemCount )
  84                 , m_nPushError( 0 )
  85             {}
  86
  87             virtual thread * clone()
  88             {
  89                 return new Producer( *this );
  90             }
  91
  92             virtual void test()
  93             {
  94                 memset( m_arrPush, 0, sizeof( m_arrPush ));
  95
  96                 value_type v;
  97                 v.nThread = id();
  98                 for ( size_t i = 0; i < m_nItemCount; ++i ) {
  99                     v.nNo = i % c_nValArraySize;
 100                     if ( m_stack.push( v ))
 101                         ++m_arrPush[v.nNo];
 102                     else
 103                         ++m_nPushError;
 104                 }
 105
 106                 s_nWorkingProducers.fetch_sub( 1, atomics::memory_order_release );
 107             }
 108
 109         public:
 110             Stack&  m_stack;
 111             size_t const m_nItemCount;
 112             size_t  m_nPushError;
 113             size_t  m_arrPush[c_nValArraySize];
 114         };
 115
 116         template <class Stack>
 117         class Consumer : public cds_test::thread
 118         {
 119             typedef cds_test::thread base_class;
 120
 121         public:
 122             Consumer( cds_test::thread_pool& pool, Stack& stack )
 123                 : base_class( pool, consumer_thread )
 124                 , m_stack( stack )
 125                 , m_nPopCount( 0 )
 126                 , m_nPopEmpty( 0 )
 127                 , m_nDirtyPop( 0 )
 128             {}
 129
 130             Consumer( Consumer& src )
 131                 : base_class( src )
 132                 , m_stack( src.m_stack )
 133                 , m_nPopCount( 0 )
 134                 , m_nPopEmpty( 0 )
 135                 , m_nDirtyPop( 0 )
 136             {}
 137
 138             virtual thread * clone()
 139             {
 140                 return new Consumer( *this );
 141             }
 142
 143             virtual void test()
 144             {
 145                 memset( m_arrPop, 0, sizeof( m_arrPop ));
 146
 147                 value_type v;
 148                 while ( !( s_nWorkingProducers.load( atomics::memory_order_acquire ) == 0 && m_stack.empty())) {
 149                     if ( m_stack.pop( v )) {
 150                         ++m_nPopCount;
 151                         if ( v.nNo < sizeof( m_arrPop ) / sizeof( m_arrPop[0] ))
 152                             ++m_arrPop[v.nNo];
 153                         else
 154                             ++m_nDirtyPop;
 155                     }
 156                     else
 157                         ++m_nPopEmpty;
 158                 }
 159             }
 160
 161         public:
 162             Stack& m_stack;
 163             size_t m_nPopCount;
 164             size_t m_nPopEmpty;
 165             size_t m_arrPop[c_nValArraySize];
 166             size_t m_nDirtyPop;
 167         };
 168
 169     protected:
 170         static void SetUpTestCase()
 171         {
 172             cds_test::config const& cfg = get_config("Stack_PushPop");
 173
 174             s_nPushThreadCount = cfg.get_size_t( "PushThreadCount", s_nPushThreadCount );
 175             s_nPopThreadCount  = cfg.get_size_t( "PopThreadCount",  s_nPopThreadCount );
 176             s_nStackSize       = cfg.get_size_t( "StackSize",       s_nStackSize );
 177             s_nEliminationSize = cfg.get_size_t( "EliminationSize", s_nEliminationSize );
 178
 179             if ( s_nPushThreadCount == 0 )
 180                 s_nPushThreadCount = 1;
 181             if ( s_nPopThreadCount == 0 )
 182                 s_nPopThreadCount = 1;
 183         }
 184
 185         //static void TearDownTestCase();
 186
 187         template <typename Stack>
 188         void test( Stack& stack )
 189         {
 190             cds_test::thread_pool& pool = get_pool();
 191             size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
 192
 193             pool.add( new Producer<Stack>( pool, stack, nPushCount ), s_nPushThreadCount );
 194             pool.add( new Consumer<Stack>( pool, stack ), s_nPopThreadCount );
 195
 196             s_nWorkingProducers.store( s_nPushThreadCount );
 197             s_nStackSize = nPushCount * s_nPushThreadCount;
 198
 199             propout() << std::make_pair( "producer_thread_count", s_nPushThreadCount )
 200                 << std::make_pair( "consumer_thread_count", s_nPopThreadCount )
 201                 << std::make_pair( "push_count", s_nStackSize )
 202 ;
 203
 204             std::chrono::milliseconds duration = pool.run();
 205
 206             propout() << std::make_pair( "duration", duration );
 207
 208             analyze( stack );
 209
 210             propout() << stack.statistics();
 211         }
 212
 213         template <typename Stack>
 214         void test_elimination( Stack& stack )
 215         {
 216             test( stack );
 217             check_elimination_stat( stack.statistics());
 218         }
 219
 220         void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
 221         {}
 222
 223         void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
 224         {
 225             EXPECT_EQ( s.m_PushCount.get() + s.m_ActivePushCollision.get() + s.m_PassivePushCollision.get(), s_nStackSize );
 226             EXPECT_EQ( s.m_PopCount.get() + s.m_ActivePopCollision.get() + s.m_PassivePopCollision.get(), s_nStackSize );
 227             EXPECT_EQ( s.m_PushCount.get(), s.m_PopCount.get());
 228             EXPECT_EQ( s.m_ActivePopCollision.get(), s.m_PassivePushCollision.get());
 229             EXPECT_EQ( s.m_ActivePushCollision.get(), s.m_PassivePopCollision.get());
 230         }
 231
 232         template< class Stack>
 233         void analyze( Stack& /*stack*/ )
 234         {
 235             cds_test::thread_pool& pool = get_pool();
 236
 237             size_t nPushError = 0;
 238             size_t nPopEmpty = 0;
 239             size_t nPopCount = 0;
 240             size_t arrVal[c_nValArraySize];
 241             memset( arrVal, 0, sizeof( arrVal ));
 242             size_t nDirtyPop = 0;
 243
 244             for ( size_t threadNo = 0; threadNo < pool.size(); ++threadNo ) {
 245                 cds_test::thread& thread = pool.get( threadNo );
 246                 if ( thread.type() == producer_thread ) {
 247                     Producer<Stack>& producer = static_cast<Producer<Stack>&>( thread );
 248
 249                     nPushError += producer.m_nPushError;
 250                     for ( size_t i = 0; i < c_nValArraySize; ++i )
 251                         arrVal[i] += producer.m_arrPush[i];
 252                 }
 253                 else {
 254                     ASSERT_EQ( thread.type(), consumer_thread );
 255                     Consumer<Stack>& consumer = static_cast<Consumer<Stack>&>(thread);
 256
 257                     nPopEmpty += consumer.m_nPopEmpty;
 258                     nPopCount += consumer.m_nPopCount;
 259                     nDirtyPop += consumer.m_nDirtyPop;
 260                     for ( size_t i = 0; i < c_nValArraySize; ++i )
 261                         arrVal[i] -= consumer.m_arrPop[i];
 262                 }
 263             }
 264
 265             EXPECT_EQ( nPopCount, s_nStackSize );
 266             EXPECT_EQ( nDirtyPop, 0u );
 267
 268             for ( size_t i = 0; i < sizeof( arrVal ) / sizeof( arrVal[0] ); ++i ) {
 269                 EXPECT_EQ( arrVal[i], 0u );
 270             }
 271
 272             propout() << std::make_pair( "push_count", s_nStackSize )
 273                       << std::make_pair( "push_error", nPushError )
 274                       << std::make_pair( "pop_empty", nPopEmpty )
 275                       << std::make_pair( "dirty_pop", nDirtyPop )
 276 ;
 277         }
 278     };
 279
 280     CDSSTRESS_TreiberStack( stack_push_pop )
 281     CDSSTRESS_EliminationStack( stack_push_pop )
 282     //CDSSTRESS_FCStack( stack_push_pop )
 283     //CDSSTRESS_FCDeque( stack_push_pop )
 284
 285 } // namespace