2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #include "stack_type.h"
32 #include "../misc/common.h"
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;
41 static atomics::atomic<size_t> s_nWorkingProducers( 0 );
43 class stack_push_pop : public cds_test::stress_fixture
60 value_type( size_t n )
66 static size_t const c_nValArraySize = 1024;
68 template <class Stack>
69 class Producer: public cds_test::thread
71 typedef cds_test::thread base_class;
74 Producer( cds_test::thread_pool& pool, Stack& stack, size_t push_count )
75 : base_class( pool, producer_thread )
77 , m_nItemCount( push_count )
81 Producer( Producer& src )
83 , m_stack( src.m_stack )
84 , m_nItemCount( src.m_nItemCount )
88 virtual thread * clone()
90 return new Producer( *this );
95 memset( m_arrPush, 0, sizeof( m_arrPush ));
99 for ( size_t i = 0; i < m_nItemCount; ++i ) {
100 v.nNo = i % c_nValArraySize;
101 if ( m_stack.push( v ))
107 s_nWorkingProducers.fetch_sub( 1, atomics::memory_order_release );
112 size_t const m_nItemCount;
114 size_t m_arrPush[c_nValArraySize];
117 template <class Stack>
118 class Consumer : public cds_test::thread
120 typedef cds_test::thread base_class;
123 Consumer( cds_test::thread_pool& pool, Stack& stack )
124 : base_class( pool, consumer_thread )
131 Consumer( Consumer& src )
133 , m_stack( src.m_stack )
139 virtual thread * clone()
141 return new Consumer( *this );
146 memset( m_arrPop, 0, sizeof( m_arrPop ));
149 while ( !( s_nWorkingProducers.load( atomics::memory_order_acquire ) == 0 && m_stack.empty())) {
150 if ( m_stack.pop( v )) {
152 if ( v.nNo < sizeof( m_arrPop ) / sizeof( m_arrPop[0] ))
166 size_t m_arrPop[c_nValArraySize];
171 static void SetUpTestCase()
173 cds_test::config const& cfg = get_config("Stack_PushPop");
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 );
180 if ( s_nPushThreadCount == 0 )
181 s_nPushThreadCount = 1;
182 if ( s_nPopThreadCount == 0 )
183 s_nPopThreadCount = 1;
186 //static void TearDownTestCase();
188 template <typename Stack>
189 void test( Stack& stack )
191 cds_test::thread_pool& pool = get_pool();
192 size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
194 pool.add( new Producer<Stack>( pool, stack, nPushCount ), s_nPushThreadCount );
195 pool.add( new Consumer<Stack>( pool, stack ), s_nPopThreadCount );
197 s_nWorkingProducers.store( s_nPushThreadCount );
198 s_nStackSize = nPushCount * s_nPushThreadCount;
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 )
205 std::chrono::milliseconds duration = pool.run();
207 propout() << std::make_pair( "duration", duration );
209 DEBUG(analyze( stack ));
211 propout() << stack.statistics();
214 template <typename Stack>
215 void test_elimination( Stack& stack )
218 check_elimination_stat( stack.statistics());
221 void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
224 void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
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());
233 template< class Stack>
234 void analyze( Stack& /*stack*/ )
236 cds_test::thread_pool& pool = get_pool();
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;
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 );
250 nPushError += producer.m_nPushError;
251 for ( size_t i = 0; i < c_nValArraySize; ++i )
252 arrVal[i] += producer.m_arrPush[i];
255 ASSERT_EQ( thread.type(), consumer_thread );
256 Consumer<Stack>& consumer = static_cast<Consumer<Stack>&>(thread);
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];
266 EXPECT_EQ( nPopCount, s_nStackSize );
267 EXPECT_EQ( nDirtyPop, 0u );
269 for ( size_t i = 0; i < sizeof( arrVal ) / sizeof( arrVal[0] ); ++i ) {
270 EXPECT_EQ( arrVal[i], 0u );
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 )
281 CDSSTRESS_TreiberStack( stack_push_pop )
282 CDSSTRESS_EliminationStack( stack_push_pop )
283 //CDSSTRESS_FCStack( stack_push_pop )
284 //CDSSTRESS_FCDeque( stack_push_pop )