From: khizmax Date: Tue, 2 Aug 2016 18:58:26 +0000 (+0300) Subject: MSPriorityQueue: removed monotonic_counter due its horrible performance X-Git-Tag: v2.2.0~159^2~1 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=3a020bfb0f4f3a7e0302ea1849c38dd0142bbe3d MSPriorityQueue: removed monotonic_counter due its horrible performance --- diff --git a/cds/container/mspriority_queue.h b/cds/container/mspriority_queue.h index 77e7ea00..cde91454 100644 --- a/cds/container/mspriority_queue.h +++ b/cds/container/mspriority_queue.h @@ -48,13 +48,9 @@ namespace cds { namespace container { /// Synonym for \p cds::intrusive::mspriority_queue::empty_stat typedef cds::intrusive::mspriority_queue::empty_stat empty_stat; - - /// Synonym for \p cds::intrusive::mspriority_queue::monotonic_counter - typedef cds::intrusive::mspriority_queue::monotonic_counter monotonic_counter; #else using cds::intrusive::mspriority_queue::stat; using cds::intrusive::mspriority_queue::empty_stat; - using cds::intrusive::mspriority_queue::monotonic_counter; #endif /// MSPriorityQueue traits @@ -95,8 +91,6 @@ namespace cds { namespace container { If the compiler supports move semantics it would be better to specify the move policy based on the move semantics for type \p T. - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead) - - \p opt::item_counter - an item counter type for \p MSPriorityQueue. - Available type: \p cds::bitop::bit_reverse_counter, \p mspriority_queue::monotonic_counter. See \p cds::intrusive::mspriority_queue::traits::item_counter for details. */ template struct make_traits { @@ -151,7 +145,7 @@ namespace cds { namespace container { typedef typename base_class::lock_type lock_type; ///< heap's size lock type typedef typename base_class::back_off back_off ; ///< Back-off strategy typedef typename traits::stat stat; ///< internal statistics type, see \p intrusive::mspriority_queue::traits::stat - typedef typename traits::item_counter item_counter;///< Item counter type, see \p intrusive::mspriority_queue::traits::item_counter + typedef typename base_class::item_counter item_counter;///< Item counter type typedef typename traits::allocator::template rebind::other allocator_type; ///< Value allocator typedef typename traits::move_policy move_policy; ///< Move policy for type \p T diff --git a/cds/intrusive/mspriority_queue.h b/cds/intrusive/mspriority_queue.h index fb920a8c..7b8476e4 100644 --- a/cds/intrusive/mspriority_queue.h +++ b/cds/intrusive/mspriority_queue.h @@ -93,37 +93,6 @@ namespace cds { namespace intrusive { //@endcond }; - /// Monotonic item counter, see \p traits::item_counter for explanation - class monotonic_counter - { - //@cond - public: - typedef size_t counter_type; - - monotonic_counter() - : m_nCounter(0) - {} - - size_t inc() - { - return ++m_nCounter; - } - - size_t dec() - { - return m_nCounter--; - } - - size_t value() const - { - return m_nCounter; - } - - private: - size_t m_nCounter; - //@endcond - }; - /// MSPriorityQueue traits struct traits { /// Storage type @@ -160,20 +129,6 @@ namespace cds { namespace intrusive { or any other with interface like \p %mspriority_queue::stat */ typedef empty_stat stat; - - /// Item counter type - /** - Two type are possible: - - \p cds::bitop::bit_reverse_counter - a counter described in original paper, - which was developed for reducing lock contention. However, bit-reversing technigue requires more memory than classic heapifying algorithm - because of sparsing of elements: for priority queue of max size \p N the bit-reversing technique requires array size up to 2K - where \p K - the nearest power of two such that 2K >= N. - - \p mspriority_queue::monotonic_counter - a classic monotonic item counter. This counter can lead to false sharing under high contention. - By the other hand, for priority queue of max size \p N it requires \p N array size. - - By default, \p MSPriorityQueue uses \p %cds::bitop::bit_reverse_counter as described in original paper. - */ - typedef cds::bitop::bit_reverse_counter<> item_counter; }; /// Metafunction converting option list to traits @@ -189,8 +144,6 @@ namespace cds { namespace intrusive { - \p opt::lock_type - lock type. Default is \p cds::sync::spin - \p opt::back_off - back-off strategy. Default is \p cds::backoff::yield - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead) - - \p opt::item_counter - an item counter type for \p MSPriorityQueue. - Available type: \p cds::bitop::bit_reverse_counter, \p mspriority_queue::monotonic_counter. See \p traits::item_counter for details. */ template struct make_traits { @@ -248,7 +201,7 @@ namespace cds { namespace intrusive { typedef typename traits::lock_type lock_type; ///< heap's size lock type typedef typename traits::back_off back_off; ///< Back-off strategy typedef typename traits::stat stat; ///< internal statistics type, see \p mspriority_queue::traits::stat - typedef typename traits::item_counter item_counter;///< Item counter type, see \p mspriority_queue::traits::item_counter + typedef typename cds::bitop::bit_reverse_counter<> item_counter;///< Item counter type protected: //@cond diff --git a/test/stress/pqueue/pop.cpp b/test/stress/pqueue/pop.cpp index e939d691..cef5f0b3 100644 --- a/test/stress/pqueue/pop.cpp +++ b/test/stress/pqueue/pop.cpp @@ -208,10 +208,8 @@ namespace { pqueue_type pq( s_nQueueSize + 1 ); \ test( pq ); \ } - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_monotonic_less_stat ) + 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 ) // too slow @@ -225,7 +223,7 @@ namespace { //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 ) \ diff --git a/test/stress/pqueue/pqueue_type.h b/test/stress/pqueue/pqueue_type.h index 83dee9da..2728fa28 100644 --- a/test/stress/pqueue/pqueue_type.h +++ b/test/stress/pqueue/pqueue_type.h @@ -396,30 +396,13 @@ namespace pqueue { { typedef co::v::initialized_dynamic_buffer< char > buffer; }; + typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn > MSPriorityQueue_dyn_less; - struct traits_MSPriorityQueue_dyn_bitreverse_less : public traits_MSPriorityQueue_dyn - { - typedef cds::bitop::bit_reverse_counter<> item_counter; - }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_bitreverse_less > MSPriorityQueue_dyn_bitreverse_less; - - struct traits_MSPriorityQueue_dyn_bitreverse_less_stat: public traits_MSPriorityQueue_dyn_bitreverse_less - { - typedef cc::mspriority_queue::stat<> stat; - }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_bitreverse_less_stat > MSPriorityQueue_dyn_bitreverse_less_stat; - - struct traits_MSPriorityQueue_dyn_monotonic_less: public traits_MSPriorityQueue_dyn - { - typedef cds::intrusive::mspriority_queue::monotonic_counter item_counter; - }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_monotonic_less > MSPriorityQueue_dyn_monotonic_less; - - struct traits_MSPriorityQueue_dyn_monotonic_less_stat: public traits_MSPriorityQueue_dyn_monotonic_less + struct traits_MSPriorityQueue_dyn_less_stat: public traits_MSPriorityQueue_dyn { typedef cc::mspriority_queue::stat<> stat; }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_monotonic_less_stat > MSPriorityQueue_dyn_monotonic_less_stat; + typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less_stat > MSPriorityQueue_dyn_less_stat; struct traits_MSPriorityQueue_dyn_cmp : public diff --git a/test/stress/pqueue/push.cpp b/test/stress/pqueue/push.cpp index d66fe76e..f85f9e96 100644 --- a/test/stress/pqueue/push.cpp +++ b/test/stress/pqueue/push.cpp @@ -169,10 +169,8 @@ namespace pqueue { pqueue_type pq( s_nQueueSize ); \ test( pq ); \ } - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_monotonic_less_stat ) + CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_less ) + CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_less_stat ) CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_cmp ) //CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_mutex ) // too slow @@ -186,7 +184,7 @@ namespace pqueue { //CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_static_less ) //CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_static_less_stat ) //CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_static_cmp ) - //CDSSTRESS_MSPriorityQueue( pqueue_push, 1MSPriorityQueue_static_mutex ) + //CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_static_mutex ) #define CDSSTRESS_PriorityQueue( fixture_t, pqueue_t ) \ diff --git a/test/stress/pqueue/push_pop.cpp b/test/stress/pqueue/push_pop.cpp index b529c69d..f4cc2053 100644 --- a/test/stress/pqueue/push_pop.cpp +++ b/test/stress/pqueue/push_pop.cpp @@ -223,10 +223,8 @@ namespace { pqueue_type pq( s_nQueueSize ); \ test( pq ); \ } - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_monotonic_less_stat ) + CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_less ) + CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_less_stat ) CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_cmp ) //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_mutex ) // too slow @@ -240,7 +238,7 @@ namespace { //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_static_less ) //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_static_less_stat ) //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_static_cmp ) - //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, 1MSPriorityQueue_static_mutex ) + //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_static_mutex ) #define CDSSTRESS_PriorityQueue( fixture_t, pqueue_t ) \ diff --git a/test/unit/pqueue/intrusive_mspqueue.cpp b/test/unit/pqueue/intrusive_mspqueue.cpp index ee95693c..c5e29c07 100644 --- a/test/unit/pqueue/intrusive_mspqueue.cpp +++ b/test/unit/pqueue/intrusive_mspqueue.cpp @@ -267,32 +267,4 @@ namespace { test( *pq ); } - TEST_F( IntrusiveMSPQueue, bit_reverse_counter ) - { - typedef cds::intrusive::MSPriorityQueue< value_type, - cds::intrusive::mspriority_queue::make_traits< - cds::opt::buffer< dyn_buffer_type > - , cds::opt::less< less > - , cds::opt::item_counter< cds::bitop::bit_reverse_counter<>> - >::type - > pqueue; - - pqueue pq( c_nCapacity ); - test( pq ); - } - - TEST_F( IntrusiveMSPQueue, monotonic_counter ) - { - typedef cds::intrusive::MSPriorityQueue< value_type, - cds::intrusive::mspriority_queue::make_traits< - cds::opt::buffer< dyn_buffer_type > - , cds::opt::less< less > - , cds::opt::item_counter< cds::intrusive::mspriority_queue::monotonic_counter > - >::type - > pqueue; - - pqueue pq( c_nCapacity ); - test( pq ); - } - } // namespace diff --git a/test/unit/pqueue/mspqueue.cpp b/test/unit/pqueue/mspqueue.cpp index cf278ef3..88ce0373 100644 --- a/test/unit/pqueue/mspqueue.cpp +++ b/test/unit/pqueue/mspqueue.cpp @@ -282,32 +282,4 @@ namespace { test( *pq ); } - TEST_F( MSPQueue, bit_reverse_counter ) - { - typedef cds::container::MSPriorityQueue< value_type, - cds::container::mspriority_queue::make_traits< - cds::opt::buffer< dyn_buffer_type > - ,cds::opt::less< less > - ,cds::opt::item_counter< cds::bitop::bit_reverse_counter<>> - >::type - > pqueue; - - pqueue pq( c_nCapacity ); - test( pq ); - } - - TEST_F( MSPQueue, monotonic_counter ) - { - typedef cds::container::MSPriorityQueue< value_type, - cds::container::mspriority_queue::make_traits< - cds::opt::buffer< dyn_buffer_type > - , cds::opt::less< less > - , cds::opt::item_counter< cds::container::mspriority_queue::monotonic_counter> - >::type - > pqueue; - - pqueue pq( c_nCapacity ); - test( pq ); - } - } // namespace