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 "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 while ( !m_Queue.empty() ) {
74 if ( m_Queue.pop( val )) {
76 if ( val.key > nPrevKey ) {
78 m_arrFailedPops.emplace_back( failed_pops{ nPrevKey, val.key } );
80 else if ( val.key == nPrevKey ) {
82 m_arrFailedPops.emplace_back( failed_pops{ nPrevKey, val.key } );
96 size_t m_nPopError = 0;
97 size_t m_nPopErrorEq = 0;
98 size_t m_nPopSuccess = 0;
99 size_t m_nPopFailed = 0;
105 std::vector< failed_pops > m_arrFailedPops;
110 template <class PQueue>
111 void test( PQueue& q )
113 cds_test::thread_pool& pool = get_pool();
115 propout() << std::make_pair( "thread_count", s_nThreadCount )
116 << std::make_pair( "push_count", s_nQueueSize );
120 std::vector< size_t > arr;
121 arr.reserve( s_nQueueSize );
122 for ( size_t i = 0; i < s_nQueueSize; ++i )
124 shuffle( arr.begin(), arr.end() );
126 typedef typename PQueue::value_type value_type;
127 for ( auto it = arr.begin(); it != arr.end(); ++it )
128 q.push( value_type( *it ));
133 pool.add( new Consumer<PQueue>( pool, q ), s_nThreadCount );
135 std::chrono::milliseconds duration = pool.run();
136 propout() << std::make_pair( "consumer_duration", duration );
139 size_t nTotalPopped = 0;
140 size_t nTotalError = 0;
141 size_t nTotalErrorEq = 0;
142 size_t nTotalFailed = 0;
143 for ( size_t i = 0; i < pool.size(); ++i ) {
144 Consumer<PQueue>& cons = static_cast<Consumer<PQueue>&>( pool.get(i));
146 nTotalPopped += cons.m_nPopSuccess;
147 nTotalError += cons.m_nPopError;
148 nTotalErrorEq += cons.m_nPopErrorEq;
149 nTotalFailed += cons.m_nPopFailed;
151 if ( !cons.m_arrFailedPops.empty() ) {
152 std::cerr << "Priority violations, thread " << i;
153 for ( size_t k = 0; k < cons.m_arrFailedPops.size(); ++k ) {
154 std::cerr << "\n " << "prev_key=" << cons.m_arrFailedPops[k].prev_key << " popped_key=" << cons.m_arrFailedPops[k].popped_key;
156 std::cerr << std::endl;
161 << std::make_pair( "total_popped", nTotalPopped )
162 << std::make_pair( "error_pop_double", nTotalErrorEq )
163 << std::make_pair( "error_priority_violation", nTotalError );
165 EXPECT_EQ( nTotalPopped, s_nQueueSize );
166 EXPECT_EQ( nTotalError, 0 );
167 EXPECT_EQ( nTotalErrorEq, 0 );
170 propout() << q.statistics();
174 static void SetUpTestCase()
\r
176 cds_test::config const& cfg = get_config( "pqueue_pop" );
\r
178 s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
179 s_nQueueSize = cfg.get_size_t( "QueueSize", s_nQueueSize );
181 if ( s_nThreadCount == 0 )
183 if ( s_nQueueSize == 0 )
184 s_nQueueSize = 1000;
\r
187 //static void TearDownTestCase();
190 #define CDSSTRESS_MSPriorityQueue( fixture_t, pqueue_t ) \
191 TEST_F( fixture_t, pqueue_t ) \
193 typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
194 pqueue_type pq( s_nQueueSize + 1 ); \
197 CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less )
198 CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less_stat )
199 CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_cmp )
200 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_mutex ) // too slow
202 #define CDSSTRESS_MSPriorityQueue_static( fixture_t, pqueue_t ) \
203 TEST_F( fixture_t, pqueue_t ) \
205 typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
206 std::unique_ptr< pqueue_type > pq( new pqueue_type ); \
209 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_less )
210 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_less_stat )
211 //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_cmp )
212 //CDSSTRESS_MSPriorityQueue( pqueue_pop, 1MSPriorityQueue_static_mutex )
215 #define CDSSTRESS_PriorityQueue( fixture_t, pqueue_t ) \
216 TEST_F( fixture_t, pqueue_t ) \
218 typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
222 CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_vector )
223 CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_vector_stat )
224 CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_deque )
225 CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_deque_stat )
226 CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_deque )
227 CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_deque_stat )
228 CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_stable_vector )
229 CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_stable_vector_stat )
231 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_max )
232 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_max_stat )
233 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_min )
234 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_min_stat )
235 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_max )
236 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_max_stat )
237 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_min )
238 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_min_stat )
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_max_stat )
245 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_min )
246 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_min_stat )
247 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_max )
248 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_max_stat )
249 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_min )
250 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_min_stat )
251 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
252 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_max )
253 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_max_stat )
254 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_min )
255 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_min_stat )
256 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_max )
257 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_max_stat )
258 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_min )
259 CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_min_stat )
262 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_max )
263 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_max_stat )
264 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_min )
265 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_min_stat )
266 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_max )
267 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_max_stat )
268 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_min )
269 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_min_stat )
270 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpi_max )
271 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpi_min )
272 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpb_max )
273 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpb_min )
274 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpt_max )
275 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpt_min )
276 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
277 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_shb_max )
278 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_shb_min )
279 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_sht_max )
280 CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_sht_min )
283 CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_vector_spin )
284 CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_vector_mutex )
285 CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_deque_spin )
286 CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_deque_mutex )