X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;ds=sidebyside;f=test%2Fstress%2Fpqueue%2Fpop.cpp;h=3006c314c0ddda473ddde616bd6d936ee33fc3cc;hb=7e58366e3d89fd5b1e3db85d2c6e1f1385f2927f;hp=1ac50887f6b8878994b7247d6fa16cbc82631859;hpb=b88919d210afe15078db3c9cbfa09224933bc25e;p=libcds.git diff --git a/test/stress/pqueue/pop.cpp b/test/stress/pqueue/pop.cpp index 1ac50887..3006c314 100644 --- a/test/stress/pqueue/pop.cpp +++ b/test/stress/pqueue/pop.cpp @@ -1,11 +1,11 @@ /* This file is a part of libcds - Concurrent Data Structures library - (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 Source code repo: http://github.com/khizmax/libcds/ Download: http://sourceforge.net/projects/libcds/files/ - + Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: @@ -40,52 +40,6 @@ namespace { typedef cds_test::stress_fixture base_class; protected: - template - class Producer: public cds_test::thread - { - typedef cds_test::thread base_class; - - public: - Producer( cds_test::thread_pool& pool, PQueue& queue ) - : base_class( pool ) - , m_Queue( queue ) - {} - - Producer( Producer& src ) - : base_class( src ) - , m_Queue( src.m_Queue ) - {} - - virtual thread * clone() - { - return new Producer( *this ); - } - - virtual void test() - { - typedef typename PQueue::value_type value_type; - for ( array_type::const_iterator it = m_arr.begin(); it != m_arr.end(); ++it ) { - if ( !m_Queue.push( value_type( *it ) )) - ++m_nPushError; - } - } - - void prepare( size_t nStart, size_t nEnd ) - { - m_arr.reserve( nEnd - nStart ); - for ( size_t i = nStart; i < nEnd; ++i ) - m_arr.push_back( i ); - shuffle( m_arr.begin(), m_arr.end() ); - } - - public: - PQueue& m_Queue; - size_t m_nPushError = 0; - - typedef std::vector array_type; - array_type m_arr; - }; - template class Consumer: public cds_test::thread { @@ -116,18 +70,27 @@ namespace { ++m_nPopSuccess; nPrevKey = val.key; - while ( !m_Queue.empty() ) { - if ( m_Queue.pop( val )) { - ++m_nPopSuccess; - if ( val.key > nPrevKey ) - ++m_nPopError; - else if ( val.key == nPrevKey ) - ++m_nPopErrorEq; - nPrevKey = val.key; + bool prevPopFailed = false; + while ( m_Queue.pop( val )) { + ++m_nPopSuccess; + if ( val.key > nPrevKey ) { + ++m_nPopError; + m_arrFailedPops.emplace_back( failed_pops{ nPrevKey, val.key, static_cast(-1) } ); + prevPopFailed = true; + } + else if ( val.key == nPrevKey ) { + ++m_nPopErrorEq; + m_arrFailedPops.emplace_back( failed_pops{ nPrevKey, val.key, static_cast(-1) } ); + } + else { + if ( prevPopFailed ) + m_arrFailedPops.back().next_key = val.key; + prevPopFailed = false; } - else - ++m_nPopFailed; + if ( nPrevKey > val.key ) + nPrevKey = val.key; } + } else ++m_nPopFailed; @@ -139,6 +102,13 @@ namespace { size_t m_nPopErrorEq = 0; size_t m_nPopSuccess = 0; size_t m_nPopFailed = 0; + + struct failed_pops { + size_t prev_key; + size_t popped_key; + size_t next_key; + }; + std::vector< failed_pops > m_arrFailedPops; }; protected: @@ -146,31 +116,30 @@ namespace { template void test( PQueue& q ) { - size_t const nThreadItemCount = s_nQueueSize / s_nThreadCount; - s_nQueueSize = nThreadItemCount * s_nThreadCount; - cds_test::thread_pool& pool = get_pool(); - propout() << std::make_pair( "thread_count", s_nThreadCount ) - << std::make_pair( "push_count", s_nQueueSize ); - // push { - pool.add( new Producer( pool, q ), s_nThreadCount ); + std::vector< size_t > arr; + arr.reserve( s_nQueueSize ); + for ( size_t i = 0; i < s_nQueueSize; ++i ) + arr.push_back( i ); + shuffle( arr.begin(), arr.end()); - size_t nStart = 0; - for ( size_t i = 0; i < pool.size(); ++i ) { - static_cast&>( pool.get(i) ).prepare( nStart, nStart + nThreadItemCount ); - nStart += nThreadItemCount; + size_t nPushError = 0; + typedef typename PQueue::value_type value_type; + for ( auto it = arr.begin(); it != arr.end(); ++it ) { + if ( !q.push( value_type( *it ))) + ++nPushError; } - - std::chrono::milliseconds duration = pool.run(); - propout() << std::make_pair( "producer_duration", duration ); + s_nQueueSize -= nPushError; } + propout() << std::make_pair( "thread_count", s_nThreadCount ) + << std::make_pair( "push_count", s_nQueueSize ); + // pop { - pool.clear(); pool.add( new Consumer( pool, q ), s_nThreadCount ); std::chrono::milliseconds duration = pool.run(); @@ -188,6 +157,18 @@ namespace { nTotalError += cons.m_nPopError; nTotalErrorEq += cons.m_nPopErrorEq; nTotalFailed += cons.m_nPopFailed; + + if ( !cons.m_arrFailedPops.empty()) { + std::cerr << "Priority violations, thread " << i; + for ( size_t k = 0; k < cons.m_arrFailedPops.size(); ++k ) { + std::cerr << "\n " << "prev_key=" << cons.m_arrFailedPops[k].prev_key << " popped_key=" << cons.m_arrFailedPops[k].popped_key; + if ( cons.m_arrFailedPops[k].next_key != static_cast(-1)) + std::cerr << " next_key=" << cons.m_arrFailedPops[k].next_key; + else + std::cerr << " next_key unspecified"; + } + std::cerr << std::endl; + } } propout() @@ -196,25 +177,25 @@ namespace { << std::make_pair( "error_priority_violation", nTotalError ); EXPECT_EQ( nTotalPopped, s_nQueueSize ); - EXPECT_EQ( nTotalError, 0 ); - EXPECT_EQ( nTotalErrorEq, 0 ); + EXPECT_EQ( nTotalError, 0u ) << "priority violations"; + EXPECT_EQ( nTotalErrorEq, 0u ) << "double key"; } propout() << q.statistics(); } public: - static void SetUpTestCase() - { - cds_test::config const& cfg = get_config( "pqueue_pop" ); - + static void SetUpTestCase() + { + cds_test::config const& cfg = get_config( "pqueue_pop" ); + s_nThreadCount = cfg.get_size_t( "ThreadCount", s_nThreadCount ); s_nQueueSize = cfg.get_size_t( "QueueSize", s_nQueueSize ); - if ( s_nThreadCount == 0 ) + if ( s_nThreadCount == 0u ) s_nThreadCount = 1; - if ( s_nQueueSize == 0 ) - s_nQueueSize = 1000; + if ( s_nQueueSize == 0u ) + s_nQueueSize = 1000; } //static void TearDownTestCase(); @@ -224,25 +205,24 @@ namespace { TEST_F( fixture_t, pqueue_t ) \ { \ typedef pqueue::Types::pqueue_t pqueue_type; \ - pqueue_type pq( s_nQueueSize ); \ + pqueue_type pq( s_nQueueSize + 1 ); \ test( pq ); \ } CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less_stat ) CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_cmp ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_mutex ) + //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_mutex ) // too slow #define CDSSTRESS_MSPriorityQueue_static( fixture_t, pqueue_t ) \ TEST_F( fixture_t, pqueue_t ) \ { \ typedef pqueue::Types::pqueue_t pqueue_type; \ std::unique_ptr< pqueue_type > pq( new pqueue_type ); \ - test( *pq.get() ); \ + test( *pq.get()); \ } //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_less ) //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_less_stat ) //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_cmp ) - //CDSSTRESS_MSPriorityQueue( pqueue_pop, 1MSPriorityQueue_static_mutex ) + //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_static_mutex ) #define CDSSTRESS_PriorityQueue( fixture_t, pqueue_t ) \ @@ -252,70 +232,39 @@ namespace { pqueue_type pq; \ test( pq ); \ } - CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_vector ) - CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_vector_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_deque ) - CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_deque_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_deque ) - CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_deque_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_stable_vector ) - CDSSTRESS_PriorityQueue( pqueue_pop, FCPQueue_boost_stable_vector_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_max_stat ) CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_HP_min_stat ) CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_max_stat ) CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_DHP_min_stat ) // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_max ) // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_max_stat ) // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_min ) // CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpi_min_stat ) CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_max_stat ) CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpb_min_stat ) CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_max_stat ) CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_gpt_min_stat ) #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_max_stat ) CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_shb_min_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_max_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, EllenBinTree_RCU_sht_min_stat ) #endif - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_max_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_HP_min_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_max_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_DHP_min_stat ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpi_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpi_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpb_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpb_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpt_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_gpt_min ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_HP_max ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_HP_min ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_DHP_max ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_DHP_min ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpi_max ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpi_min ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpb_max ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpb_min ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpt_max ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_gpt_min ) #ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_shb_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_shb_min ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_sht_max ) - CDSSTRESS_PriorityQueue( pqueue_pop, SkipList_RCU_sht_min ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_shb_max ) + CDSSTRESS_PriorityQueue( pqueue_pop, SkipList32_RCU_shb_min ) #endif CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_vector_spin ) - CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_vector_mutex ) CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_deque_spin ) - CDSSTRESS_PriorityQueue( pqueue_pop, StdPQueue_deque_mutex ) } // namespace