2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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"
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;
40 static atomics::atomic<size_t> s_nWorkingProducers( 0 );
42 class stack_push_pop : public cds_test::stress_fixture
59 value_type( size_t n )
65 static size_t const c_nValArraySize = 1024;
67 template <class Stack>
68 class Producer: public cds_test::thread
70 typedef cds_test::thread base_class;
73 Producer( cds_test::thread_pool& pool, Stack& stack, size_t push_count )
74 : base_class( pool, producer_thread )
76 , m_nItemCount( push_count )
80 Producer( Producer& src )
82 , m_stack( src.m_stack )
83 , m_nItemCount( src.m_nItemCount )
87 virtual thread * clone()
89 return new Producer( *this );
94 memset( m_arrPush, 0, sizeof( m_arrPush ) );
98 for ( size_t i = 0; i < m_nItemCount; ++i ) {
99 v.nNo = i % c_nValArraySize;
100 if ( m_stack.push( v ) )
106 s_nWorkingProducers.fetch_sub( 1, atomics::memory_order_release );
111 size_t const m_nItemCount;
113 size_t m_arrPush[c_nValArraySize];
116 template <class Stack>
117 class Consumer : public cds_test::thread
119 typedef cds_test::thread base_class;
122 Consumer( cds_test::thread_pool& pool, Stack& stack )
123 : base_class( pool, consumer_thread )
130 Consumer( Consumer& src )
132 , m_stack( src.m_stack )
138 virtual thread * clone()
140 return new Consumer( *this );
145 memset( m_arrPop, 0, sizeof( m_arrPop ) );
148 while ( !( s_nWorkingProducers.load( atomics::memory_order_acquire ) == 0 && m_stack.empty()) ) {
149 if ( m_stack.pop( v ) ) {
151 if ( v.nNo < sizeof( m_arrPop ) / sizeof( m_arrPop[0] ) )
165 size_t m_arrPop[c_nValArraySize];
170 static void SetUpTestCase()
\r
172 cds_test::config const& cfg = get_config("Stack_PushPop");
\r
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 );
179 if ( s_nPushThreadCount == 0 )
180 s_nPushThreadCount = 1;
181 if ( s_nPopThreadCount == 0 )
182 s_nPopThreadCount = 1;
185 //static void TearDownTestCase();
\r
187 template <typename Stack>
188 void test( Stack& stack )
190 cds_test::thread_pool& pool = get_pool();
191 size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
193 pool.add( new Producer<Stack>( pool, stack, nPushCount ), s_nPushThreadCount );
194 pool.add( new Consumer<Stack>( pool, stack ), s_nPopThreadCount );
196 s_nWorkingProducers.store( s_nPushThreadCount );
197 s_nStackSize = nPushCount * s_nPushThreadCount;
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 )
204 std::chrono::milliseconds duration = pool.run();
206 propout() << std::make_pair( "duration", duration );
210 propout() << stack.statistics();
213 template <typename Stack>
214 void test_elimination( Stack& stack )
217 check_elimination_stat( stack.statistics() );
220 void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
223 void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
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() );
232 template< class Stack>
233 void analyze( Stack& stack )
235 cds_test::thread_pool& pool = get_pool();
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;
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 );
249 nPushError += producer.m_nPushError;
250 for ( size_t i = 0; i < c_nValArraySize; ++i )
251 arrVal[i] += producer.m_arrPush[i];
254 ASSERT_EQ( thread.type(), consumer_thread );
255 Consumer<Stack>& consumer = static_cast<Consumer<Stack>&>(thread);
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];
265 EXPECT_EQ( nPopCount, s_nStackSize );
266 EXPECT_EQ( nDirtyPop, 0 );
268 for ( size_t i = 0; i < sizeof( arrVal ) / sizeof( arrVal[0] ); ++i ) {
269 EXPECT_EQ( arrVal[i], 0 );
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 )
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 CDSSTRESS_StdStack( stack_push_pop )