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