MSPriorityQueue: removed monotonic_counter due its horrible performance

diff --git a/cds/container/mspriority_queue.h b/cds/container/mspriority_queue.h
index 77e7ea0..cde9145 100644 (file)
--- 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 <typename... Options>
         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<value_type>::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 fb920a8..7b8476e 100644 (file)
--- 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 <a href="http://www.research.ibm.com/people/m/michael/ipl-1996.pdf">original paper</a>,
-                  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 2<sup>K</sup>
-                  where \p K - the nearest power of two such that <tt>2<sup>K</sup> >= N</tt>.
-                - \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 <typename... Options>
         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 e939d69..cef5f0b 100644 (file)
--- 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 83dee9d..2728fa2 100644 (file)
--- 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 d66fe76..f85f9e9 100644 (file)
--- 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 b529c69..f4cc205 100644 (file)
--- 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 ee95693..c5e29c0 100644 (file)
--- 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 cf278ef..88ce037 100644 (file)
--- 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