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 "pqueue_type.h"
35 static size_t s_nThreadCount = 8;
36 static size_t s_nQueueSize = 2000000;
38 class pqueue_pop: public cds_test::stress_fixture
40 typedef cds_test::stress_fixture base_class;
43 template <class PQueue>
44 class Consumer: public cds_test::thread
46 typedef cds_test::thread base_class;
49 Consumer( cds_test::thread_pool& pool, PQueue& queue )
54 Consumer( Consumer& src )
56 , m_Queue( src.m_Queue )
59 virtual thread * clone()
61 return new Consumer( *this );
66 typedef typename PQueue::value_type value_type;
69 if ( m_Queue.pop( val )) {
73 bool prevPopFailed = false;
74 while ( m_Queue.pop( val )) {
76 if ( val.key > nPrevKey ) {
78 m_arrFailedPops.emplace_back( failed_pops{ nPrevKey, val.key, static_cast<size_t>(-1) } );
81 else if ( val.key == nPrevKey ) {
83 m_arrFailedPops.emplace_back( failed_pops{ nPrevKey, val.key, static_cast<size_t>(-1) } );
87 m_arrFailedPops.back().next_key = val.key;
88 prevPopFailed = false;
90 if ( nPrevKey > val.key )
101 size_t m_nPopError = 0;
102 size_t m_nPopErrorEq = 0;
103 size_t m_nPopSuccess = 0;
104 size_t m_nPopFailed = 0;
111 std::vector< failed_pops > m_arrFailedPops;
116 template <class PQueue>
117 void test( PQueue& q )
119 cds_test::thread_pool& pool = get_pool();
123 std::vector< size_t > arr;
124 arr.reserve( s_nQueueSize );
125 for ( size_t i = 0; i < s_nQueueSize; ++i )
127 shuffle( arr.begin(), arr.end());
129 size_t nPushError = 0;
130 typedef typename PQueue::value_type value_type;
131 for ( auto it = arr.begin(); it != arr.end(); ++it ) {
132 if ( !q.push( value_type( *it )))
135 s_nQueueSize -= nPushError;
138 propout() << std::make_pair( "thread_count", s_nThreadCount )
139 << std::make_pair( "push_count", s_nQueueSize );
143 pool.add( new Consumer<PQueue>( pool, q ), s_nThreadCount );
145 std::chrono::milliseconds duration = pool.run();
146 propout() << std::make_pair( "consumer_duration", duration );
149 size_t nTotalPopped = 0;
150 size_t nTotalError = 0;
151 size_t nTotalErrorEq = 0;
152 size_t nTotalFailed = 0;
153 for ( size_t i = 0; i < pool.size(); ++i ) {
154 Consumer<PQueue>& cons = static_cast<Consumer<PQueue>&>( pool.get(i));
156 nTotalPopped += cons.m_nPopSuccess;
157 nTotalError += cons.m_nPopError;
158 nTotalErrorEq += cons.m_nPopErrorEq;
159 nTotalFailed += cons.m_nPopFailed;
161 if ( !cons.m_arrFailedPops.empty()) {
162 std::cerr << "Priority violations, thread " << i;
163 for ( size_t k = 0; k < cons.m_arrFailedPops.size(); ++k ) {
164 std::cerr << "\n " << "prev_key=" << cons.m_arrFailedPops[k].prev_key << " popped_key=" << cons.m_arrFailedPops[k].popped_key;
165 if ( cons.m_arrFailedPops[k].next_key != static_cast<size_t>(-1))
166 std::cerr << " next_key=" << cons.m_arrFailedPops[k].next_key;
168 std::cerr << " next_key unspecified";
170 std::cerr << std::endl;
175 << std::make_pair( "total_popped", nTotalPopped )
176 << std::make_pair( "error_pop_double", nTotalErrorEq )
177 << std::make_pair( "error_priority_violation", nTotalError );
179 EXPECT_EQ( nTotalPopped, s_nQueueSize );
180 EXPECT_EQ( nTotalError, 0u ) << "priority violations";
181 EXPECT_EQ( nTotalErrorEq, 0u ) << "double key";
184 propout() << q.statistics();
188 static void SetUpTestCase()
190 cds_test::config const& cfg = get_config( "pqueue_pop" );
192 s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
193 s_nQueueSize = cfg.get_size_t( "QueueSize", s_nQueueSize );
195 if ( s_nThreadCount == 0u )
197 if ( s_nQueueSize == 0u )
201 //static void TearDownTestCase();
204 #define CDSSTRESS_MSPriorityQueue( fixture_t, pqueue_t ) \
205 TEST_F( fixture_t, pqueue_t ) \
207 typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
208 pqueue_type pq( s_nQueueSize + 1 ); \
211 CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less )
212 CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_cmp )
213 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_mutex ) // too slow
215 #define CDSSTRESS_MSPriorityQueue_static( fixture_t, pqueue_t ) \
216 TEST_F( fixture_t, pqueue_t ) \
218 typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
219 std::unique_ptr< pqueue_type > pq( new pqueue_type ); \
222 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_less )
223 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_less_stat )
224 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_cmp )
225 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_mutex )
228 #define CDSSTRESS_PriorityQueue( fixture_t, pqueue_t ) \
229 TEST_F( fixture_t, pqueue_t ) \
231 typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
235 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_max )
236 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_min )
237 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_max )
238 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_min )
239 // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_max )
240 // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_max_stat )
241 // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_min )
242 // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_min_stat )
243 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_max )
244 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_min )
245 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_max )
246 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_min )
247 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
248 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_max )
249 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_min )
252 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_HP_max )
253 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_HP_min )
254 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_DHP_max )
255 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_DHP_min )
256 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpi_max )
257 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpi_min )
258 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpb_max )
259 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpb_min )
260 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpt_max )
261 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpt_min )
262 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
263 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_shb_max )
264 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_shb_min )
267 CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_vector_spin )
268 CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_deque_spin )