test/stress/pqueue/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-2016
   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 "pqueue_type.h"
  32 #include "item.h"
  33
  34 namespace {
  35     static size_t s_nThreadCount = 8;
  36     static size_t s_nQueueSize = 2000000;
  37
  38     class pqueue_pop: public cds_test::stress_fixture
  39     {
  40         typedef cds_test::stress_fixture base_class;
  41
  42     protected:
  43         template <class PQueue>
  44         class Consumer: public cds_test::thread
  45         {
  46             typedef cds_test::thread base_class;
  47
  48         public:
  49             Consumer( cds_test::thread_pool& pool, PQueue& queue )
  50                 : base_class( pool )
  51                 , m_Queue( queue )
  52             {}
  53
  54             Consumer( Consumer& src )
  55                 : base_class( src )
  56                 , m_Queue( src.m_Queue )
  57             {}
  58
  59             virtual thread * clone()
  60             {
  61                 return new Consumer( *this );
  62             }
  63
  64             virtual void test()
  65             {
  66                 typedef typename PQueue::value_type value_type;
  67                 size_t nPrevKey;
  68                 value_type val;
  69                 if ( m_Queue.pop( val )) {
  70                     ++m_nPopSuccess;
  71                     nPrevKey = val.key;
  72
  73                     bool prevPopFailed = false;
  74                     while ( m_Queue.pop( val )) {
  75                         ++m_nPopSuccess;
  76                         if ( val.key > nPrevKey ) {
  77                             ++m_nPopError;
  78                             m_arrFailedPops.emplace_back( failed_pops{ nPrevKey, val.key, static_cast<size_t>(-1) } );
  79                             prevPopFailed = true;
  80                         }
  81                         else if ( val.key == nPrevKey ) {
  82                             ++m_nPopErrorEq;
  83                             m_arrFailedPops.emplace_back( failed_pops{ nPrevKey, val.key, static_cast<size_t>(-1) } );
  84                         }
  85                         else {
  86                             if ( prevPopFailed )
  87                                 m_arrFailedPops.back().next_key = val.key;
  88                             prevPopFailed = false;
  89                         }
  90                         nPrevKey = val.key;
  91                     }
  92
  93                 }
  94                 else
  95                     ++m_nPopFailed;
  96             }
  97
  98         public:
  99             PQueue&             m_Queue;
 100             size_t              m_nPopError = 0;
 101             size_t              m_nPopErrorEq = 0;
 102             size_t              m_nPopSuccess = 0;
 103             size_t              m_nPopFailed = 0;
 104
 105             struct failed_pops {
 106                 size_t prev_key;
 107                 size_t popped_key;
 108                 size_t next_key;
 109             };
 110             std::vector< failed_pops > m_arrFailedPops;
 111         };
 112
 113     protected:
 114
 115         template <class PQueue>
 116         void test( PQueue& q )
 117         {
 118             cds_test::thread_pool& pool = get_pool();
 119
 120             propout() << std::make_pair( "thread_count", s_nThreadCount )
 121                 << std::make_pair( "push_count", s_nQueueSize );
 122
 123             // push
 124             {
 125                 std::vector< size_t > arr;
 126                 arr.reserve( s_nQueueSize );
 127                 for ( size_t i = 0; i < s_nQueueSize; ++i )
 128                     arr.push_back( i );
 129                 shuffle( arr.begin(), arr.end() );
 130
 131                 size_t nPushError = 0;
 132                 typedef typename PQueue::value_type value_type;
 133                 for ( auto it = arr.begin(); it != arr.end(); ++it ) {
 134                     if ( !q.push( value_type( *it ) ))
 135                         ++nPushError;
 136                 }
 137                 s_nQueueSize -= nPushError;
 138             }
 139
 140             // pop
 141             {
 142                 pool.add( new Consumer<PQueue>( pool, q ), s_nThreadCount );
 143
 144                 std::chrono::milliseconds duration = pool.run();
 145                 propout() << std::make_pair( "consumer_duration", duration );
 146
 147                 // Analyze result
 148                 size_t nTotalPopped = 0;
 149                 size_t nTotalError = 0;
 150                 size_t nTotalErrorEq = 0;
 151                 size_t nTotalFailed = 0;
 152                 for ( size_t i = 0; i < pool.size(); ++i ) {
 153                     Consumer<PQueue>& cons = static_cast<Consumer<PQueue>&>( pool.get(i));
 154
 155                     nTotalPopped  += cons.m_nPopSuccess;
 156                     nTotalError   += cons.m_nPopError;
 157                     nTotalErrorEq += cons.m_nPopErrorEq;
 158                     nTotalFailed  += cons.m_nPopFailed;
 159
 160                     if ( !cons.m_arrFailedPops.empty() ) {
 161                         std::cerr << "Priority violations, thread " << i;
 162                         for ( size_t k = 0; k < cons.m_arrFailedPops.size(); ++k ) {
 163                             std::cerr << "\n    " << "prev_key=" << cons.m_arrFailedPops[k].prev_key << " popped_key=" << cons.m_arrFailedPops[k].popped_key
 164                                 << " next_key=" << cons.m_arrFailedPops[k].next_key;
 165                         }
 166                         std::cerr << std::endl;
 167                     }
 168                 }
 169
 170                 propout()
 171                     << std::make_pair( "total_popped", nTotalPopped )
 172                     << std::make_pair( "error_pop_double", nTotalErrorEq )
 173                     << std::make_pair( "error_priority_violation", nTotalError );
 174
 175                 EXPECT_EQ( nTotalPopped, s_nQueueSize );
 176                 EXPECT_EQ( nTotalError, 0 ) << "priority violations";
 177                 EXPECT_EQ( nTotalErrorEq, 0 ) << "double key";
 178             }
 179
 180             propout() << q.statistics();
 181         }
 182
 183     public:
 184         static void SetUpTestCase()\r
 185         {\r
 186             cds_test::config const& cfg = get_config( "pqueue_pop" );\r
 187 \r
 188             s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount );
 189             s_nQueueSize = cfg.get_size_t( "QueueSize", s_nQueueSize );
 190
 191             if ( s_nThreadCount == 0 )
 192                 s_nThreadCount = 1;
 193             if ( s_nQueueSize == 0 )
 194                 s_nQueueSize = 1000;\r
 195         }
 196
 197         //static void TearDownTestCase();
 198     };
 199
 200 #define CDSSTRESS_MSPriorityQueue( fixture_t, pqueue_t ) \
 201     TEST_F( fixture_t, pqueue_t ) \
 202     { \
 203         typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
 204         pqueue_type pq( s_nQueueSize + 1 ); \
 205         test( pq ); \
 206     }
 207     CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less )
 208     CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less_stat )
 209     CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_cmp )
 210     //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_mutex ) // too slow
 211
 212 #define CDSSTRESS_MSPriorityQueue_static( fixture_t, pqueue_t ) \
 213     TEST_F( fixture_t, pqueue_t ) \
 214     { \
 215         typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
 216         std::unique_ptr< pqueue_type > pq( new pqueue_type ); \
 217         test( *pq.get() ); \
 218     }
 219     //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_less )
 220     //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_less_stat )
 221     //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_cmp )
 222     //CDSSTRESS_MSPriorityQueue( pqueue_pop, 1MSPriorityQueue_static_mutex )
 223
 224
 225 #define CDSSTRESS_PriorityQueue( fixture_t, pqueue_t ) \
 226     TEST_F( fixture_t, pqueue_t ) \
 227     { \
 228         typedef pqueue::Types<pqueue::simple_value>::pqueue_t pqueue_type; \
 229         pqueue_type pq; \
 230         test( pq ); \
 231     }
 232     CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_vector )
 233     CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_vector_stat )
 234     CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_deque )
 235     CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_deque_stat )
 236     CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_deque )
 237     CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_deque_stat )
 238     CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_stable_vector )
 239     CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_stable_vector_stat )
 240
 241     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_max )
 242     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_max_stat )
 243     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_min )
 244     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_min_stat )
 245     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_max )
 246     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_max_stat )
 247     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_min )
 248     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_min_stat )
 249     // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_max )
 250     // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_max_stat )
 251     // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_min )
 252     // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_min_stat )
 253     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_max )
 254     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_max_stat )
 255     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_min )
 256     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_min_stat )
 257     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_max )
 258     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_max_stat )
 259     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_min )
 260     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_min_stat )
 261 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 262     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_max )
 263     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_max_stat )
 264     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_min )
 265     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_min_stat )
 266     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_max )
 267     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_max_stat )
 268     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_min )
 269     CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_min_stat )
 270 #endif
 271
 272     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_max )
 273     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_max_stat )
 274     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_min )
 275     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_min_stat )
 276     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_max )
 277     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_max_stat )
 278     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_min )
 279     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_min_stat )
 280     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpi_max )
 281     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpi_min )
 282     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpb_max )
 283     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpb_min )
 284     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpt_max )
 285     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpt_min )
 286 #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED
 287     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_shb_max )
 288     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_shb_min )
 289     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_sht_max )
 290     CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_sht_min )
 291 #endif
 292
 293     CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_vector_spin )
 294     CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_vector_mutex )
 295     CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_deque_spin )
 296     CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_deque_mutex )
 297
 298 } // namespace