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