56917927cfa9686cf7000dceeb16a1bc0c667a04
[libcds.git] / 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