Added internal statistics for IterableList

diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h
index 2953a791b3e4fe2aee15a380082b7a8e3f839788..7ef00bdcd8846ddba37667b082a74de45297ac69 100644 (file)
--- a/cds/intrusive/details/iterable_list_base.h
+++ b/cds/intrusive/details/iterable_list_base.h
@@ -67,6 +67,97 @@ namespace cds { namespace intrusive {
             //@endcond
         };
 
             //@endcond
         };
 

+        /// \p IterableList internal statistics
+        template <typename EventCounter = cds::atomicity::event_counter>
+        struct stat {
+            typedef EventCounter event_counter; ///< Event counter type
+
+            event_counter   m_nInsertSuccess;   ///< Number of success \p insert() operations
+            event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
+            event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
+            event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
+            event_counter   m_nUpdateExisting;  ///< Number of existing item updates
+            event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
+            event_counter   m_nUpdateRetry;     ///< Number of attempts to update the item
+            event_counter   m_nEraseSuccess;    ///< Number of successful \p erase(), \p unlink(), \p extract() operations
+            event_counter   m_nEraseFailed;     ///< Number of failed \p erase(), \p unlink(), \p extract() operations
+            event_counter   m_nEraseRetry;      ///< Number of attempts to \p erase() an item
+            event_counter   m_nFindSuccess;     ///< Number of successful \p find() and \p get() operations
+            event_counter   m_nFindFailed;      ///< Number of failed \p find() and \p get() operations
+
+            event_counter   m_nNodeCreated;     ///< Number of created internal nodes
+            event_counter   m_nNodeRemoved;     ///< Number of removed internal nodes
+
+            //@cond
+            void onInsertSuccess()      { ++m_nInsertSuccess;   }
+            void onInsertFailed()       { ++m_nInsertFailed;    }
+            void onInsertRetry()        { ++m_nInsertRetry;     }
+            void onUpdateNew()          { ++m_nUpdateNew;       }
+            void onUpdateExisting()     { ++m_nUpdateExisting;  }
+            void onUpdateFailed()       { ++m_nUpdateFailed;    }
+            void onUpdateRetry()        { ++m_nUpdateRetry;     }
+            void onEraseSuccess()       { ++m_nEraseSuccess;    }
+            void onEraseFailed()        { ++m_nEraseFailed;     }
+            void onEraseRetry()         { ++m_nEraseRetry;      }
+            void onFindSuccess()        { ++m_nFindSuccess;     }
+            void onFindFailed()         { ++m_nFindFailed;      }
+
+            void onNodeCreated()        { ++m_nNodeCreated;     }
+            void onNodeRemoved()        { ++m_nNodeRemoved;     }
+            //@endcond
+        };
+
+        /// \p IterableList empty internal statistics
+        struct empty_stat {
+            //@cond
+            void onInsertSuccess()              const {}
+            void onInsertFailed()               const {}
+            void onInsertRetry()                const {}
+            void onUpdateNew()                  const {}
+            void onUpdateExisting()             const {}
+            void onUpdateFailed()               const {}
+            void onUpdateRetry()                const {}
+            void onEraseSuccess()               const {}
+            void onEraseFailed()                const {}
+            void onEraseRetry()                 const {}
+            void onFindSuccess()                const {}
+            void onFindFailed()                 const {}
+
+            void onNodeCreated()                const {}
+            void onNodeRemoved()                const {}
+            //@endcond
+        };
+
+        //@cond
+        template <typename Stat = iterable_list::stat<>>
+        struct wrapped_stat {
+            typedef Stat stat_type;
+
+            wrapped_stat( stat_type& st )
+                : m_stat( st )
+            {}
+
+            void onInsertSuccess()   { m_stat.onInsertSuccess(); }
+            void onInsertFailed()    { m_stat.onInsertFailed();  }
+            void onInsertRetry()     { m_stat.onInsertRetry();   }
+            void onUpdateNew()       { m_stat.onUpdateNew();     }
+            void onUpdateExisting()  { m_stat.onUpdateExisting();}
+            void onUpdateFailed()    { m_stat.onUpdateFailed();  }
+            void onUpdateRetry()     { m_stat.onUpdateRetry();   }
+            void onEraseSuccess()    { m_stat.onEraseSuccess();  }
+            void onEraseFailed()     { m_stat.onEraseFailed();   }
+            void onEraseRetry()      { m_stat.onEraseRetry();    }
+            void onFindSuccess()     { m_stat.onFindSuccess();   }
+            void onFindFailed()      { m_stat.onFindFailed();    }
+
+            void onNodeCreated()     { m_stat.onNodeCreated();   }
+            void onNodeRemoved()     { m_stat.onNodeRemoved();   }
+
+            stat_type& m_stat;
+        };
+        //@endcond
+
+

         /// \p IterableList traits
         struct traits
         {
         /// \p IterableList traits
         struct traits
         {


@@ -91,6 +182,13 @@ namespace cds { namespace intrusive {
             /// Disposer for removing items
             typedef opt::v::empty_disposer          disposer;
 
             /// Disposer for removing items
             typedef opt::v::empty_disposer          disposer;
 

+            /// Internal statistics
+            /**
+                By default, internal statistics is disabled (\p iterable_list::empty_stat).
+                Use \p iterable_list::stat to enable it.
+            */
+            typedef empty_stat                      stat;
+

             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
             typedef atomicity::empty_item_counter     item_counter;
 
             /// Item counting feature; by default, disabled. Use \p cds::atomicity::item_counter to enable item counting
             typedef atomicity::empty_item_counter     item_counter;
 


@@ -120,6 +218,8 @@ namespace cds { namespace intrusive {
                 of GC schema the disposer may be called asynchronously.
             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
                  To enable item counting use \p atomicity::item_counter.
                 of GC schema the disposer may be called asynchronously.
             - \p opt::item_counter - the type of item counting feature. Default is disabled (\p atomicity::empty_item_counter).
                  To enable item counting use \p atomicity::item_counter.

+            - \p opt::stat - internal statistics. By default, it is disabled (\p iterable_list::empty_stat).
+                To enable it use \p iterable_list::stat

             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"
             - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
                 or \p opt::v::sequential_consistent (sequentially consistent memory model).
             - \p opt::rcu_check_deadlock - a deadlock checking policy for \ref cds_intrusive_IterableList_rcu "RCU-based IterableList"

diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h
index 66e018c310260910ac58cb08ef0dcac9665f3a84..00e20233d37140c574fede39db2f567f8d709819 100644 (file)
--- a/cds/intrusive/impl/iterable_list.h
+++ b/cds/intrusive/impl/iterable_list.h
@@ -45,6 +45,13 @@ namespace cds { namespace intrusive {
         any hook in \p T to be stored in the list.
 
         Usually, ordered single-linked list is used as a building block for the hash table implementation.
         any hook in \p T to be stored in the list.
 
         Usually, ordered single-linked list is used as a building block for the hash table implementation.

+        Iterable list is suitable for almost append-only hash table because the list doesn't delete
+        its internal node when erasing a key but it is marked them as empty to be reused in the future.
+        However, plenty of empty nodes degrades performance.
+        Separation of internal nodes and user data implies the need for an allocator for internal node
+        so the iterable list is not fully intrusive. Nevertheless, if you need thread-safe iterator,
+        the iterable list is good choice.
+

         The complexity of searching is <tt>O(N)</tt>.
 
         Template arguments:
         The complexity of searching is <tt>O(N)</tt>.
 
         Template arguments:


@@ -130,6 +137,7 @@ namespace cds { namespace intrusive {
         typedef typename traits::item_counter   item_counter;   ///< Item counting policy used
         typedef typename traits::memory_model   memory_model;   ///< Memory ordering. See \p cds::opt::memory_model option
         typedef typename traits::node_allocator node_allocator; ///< Node allocator
         typedef typename traits::item_counter   item_counter;   ///< Item counting policy used
         typedef typename traits::memory_model   memory_model;   ///< Memory ordering. See \p cds::opt::memory_model option
         typedef typename traits::node_allocator node_allocator; ///< Node allocator

+        typedef typename traits::stat           stat;           ///< Internal statistics

 
         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 
 
         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 


@@ -153,6 +161,7 @@ namespace cds { namespace intrusive {
 
         atomic_node_ptr m_pHead;        ///< Head pointer
         item_counter    m_ItemCounter;  ///< Item counter
 
         atomic_node_ptr m_pHead;        ///< Head pointer
         item_counter    m_ItemCounter;  ///< Item counter

+        mutable stat    m_Stat;         ///< Internal statistics

 
         //@cond
         typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;
 
         //@cond
         typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator;


@@ -380,6 +389,14 @@ namespace cds { namespace intrusive {
             : m_pHead( nullptr )
         {}
 
             : m_pHead( nullptr )
         {}
 

+        //@cond
+        template <typename Stat, typename = std::enable_if<std::is_same<stat, iterable_list::wrapped_stat<Stat>>::value >>
+        explicit IterableList( Stat& st )
+            : m_pHead( nullptr )
+            , m_Stat( st )
+        {}
+        //@endcond
+

         /// Destroys the list object
         ~IterableList()
         {
         /// Destroys the list object
         ~IterableList()
         {


@@ -455,7 +472,7 @@ namespace cds { namespace intrusive {
 
             If the item \p val is not found in the list, then \p val is inserted
             iff \p bInsert is \p true.
 
             If the item \p val is not found in the list, then \p val is inserted
             iff \p bInsert is \p true.

-            Otherwise, the current element is changed to \p val, the element will be retired later
+            Otherwise, the current element is changed to \p val, the old element will be retired later

             by call \p Traits::disposer.
 
             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,
             by call \p Traits::disposer.
 
             Returns std::pair<bool, bool> where \p first is \p true if operation is successful,


@@ -841,13 +858,18 @@ namespace cds { namespace intrusive {
             position pos;
 
             while ( true ) {
             position pos;
 
             while ( true ) {

-                if ( search( refHead, val, pos, key_comparator() ) )
+                if ( search( refHead, val, pos, key_comparator() )) {
+                    m_Stat.onInsertFailed();

                     return false;
                     return false;

+                }

 
                 if ( link_node( &val, pos ) ) {
                     ++m_ItemCounter;
 
                 if ( link_node( &val, pos ) ) {
                     ++m_ItemCounter;

+                    m_Stat.onInsertSuccess();

                     return true;
                 }
                     return true;
                 }

+
+                m_Stat.onInsertRetry();

             }
         }
 
             }
         }
 


@@ -860,14 +882,19 @@ namespace cds { namespace intrusive {
             guard.assign( &val );
 
             while ( true ) {
             guard.assign( &val );
 
             while ( true ) {

-                if ( search( refHead, val, pos, key_comparator() ) )
+                if ( search( refHead, val, pos, key_comparator() ) ) {
+                    m_Stat.onInsertFailed();

                     return false;
                     return false;

+                }

 
                 if ( link_node( &val, pos ) ) {
                     f( val );
                     ++m_ItemCounter;
 
                 if ( link_node( &val, pos ) ) {
                     f( val );
                     ++m_ItemCounter;

+                    m_Stat.onInsertSuccess();

                     return true;
                 }
                     return true;
                 }

+
+                m_Stat.onInsertRetry();

             }
         }
 
             }
         }
 


@@ -890,19 +917,25 @@ namespace cds { namespace intrusive {
                             retire_data( pos.pFound );
                             func( val, pos.pFound );
                         }
                             retire_data( pos.pFound );
                             func( val, pos.pFound );
                         }

+                        m_Stat.onUpdateExisting();

                         return std::make_pair( true, false );
                     }
                 }
                 else {
                         return std::make_pair( true, false );
                     }
                 }
                 else {

-                    if ( !bInsert )
+                    if ( !bInsert ) {
+                        m_Stat.onUpdateFailed();

                         return std::make_pair( false, false );
                         return std::make_pair( false, false );

+                    }

 
 

-                    if ( link_node( &val, pos ) ) {
+                    if ( link_node( &val, pos )) {

                         func( val, static_cast<value_type*>( nullptr ));
                         ++m_ItemCounter;
                         func( val, static_cast<value_type*>( nullptr ));
                         ++m_ItemCounter;

+                        m_Stat.onUpdateNew();

                         return std::make_pair( true, true );
                     }
                 }
                         return std::make_pair( true, true );
                     }
                 }

+
+                m_Stat.onUpdateRetry();

             }
         }
 
             }
         }
 


@@ -915,6 +948,7 @@ namespace cds { namespace intrusive {
                 if ( pos.pFound == &val ) {
                     if ( unlink_node( pos )) {
                         --m_ItemCounter;
                 if ( pos.pFound == &val ) {
                     if ( unlink_node( pos )) {
                         --m_ItemCounter;

+                        m_Stat.onEraseSuccess();

                         return true;
                     }
                     else
                         return true;
                     }
                     else


@@ -922,7 +956,11 @@ namespace cds { namespace intrusive {
                 }
                 else
                     break;
                 }
                 else
                     break;

+
+                m_Stat.onEraseRetry();

             }
             }

+
+            m_Stat.onEraseFailed();

             return false;
         }
 
             return false;
         }
 


@@ -934,11 +972,16 @@ namespace cds { namespace intrusive {
                 if ( unlink_node( pos )) {
                     f( *pos.pFound );
                     --m_ItemCounter;
                 if ( unlink_node( pos )) {
                     f( *pos.pFound );
                     --m_ItemCounter;

+                    m_Stat.onEraseSuccess();

                     return true;
                 }
                 else
                     bkoff();
                     return true;
                 }
                 else
                     bkoff();

+
+                m_Stat.onEraseRetry();

             }
             }

+
+            m_Stat.onEraseFailed();

             return false;
         }
 
             return false;
         }
 


@@ -965,11 +1008,16 @@ namespace cds { namespace intrusive {
                 if ( unlink_node( pos )) {
                     dest.set( pos.pFound );
                     --m_ItemCounter;
                 if ( unlink_node( pos )) {
                     dest.set( pos.pFound );
                     --m_ItemCounter;

+                    m_Stat.onEraseSuccess();

                     return true;
                 }
                 else
                     bkoff();
                     return true;
                 }
                 else
                     bkoff();

+
+                m_Stat.onEraseRetry();

             }
             }

+
+            m_Stat.onEraseFailed();

             return false;
         }
 
             return false;
         }
 


@@ -977,7 +1025,13 @@ namespace cds { namespace intrusive {
         bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
         {
             position pos;
         bool find_at( atomic_node_ptr const& refHead, Q const& val, Compare cmp ) const
         {
             position pos;

-            return search( refHead, val, pos, cmp );
+            if ( search( refHead, val, pos, cmp ) ) {
+                m_Stat.onFindSuccess();
+                return true;
+            }
+
+            m_Stat.onFindFailed();
+            return false;

         }
 
         template <typename Q, typename Compare, typename Func>
         }
 
         template <typename Q, typename Compare, typename Func>


@@ -987,8 +1041,11 @@ namespace cds { namespace intrusive {
             if ( search( refHead, val, pos, cmp )) {
                 assert( pos.pFound != nullptr );
                 f( *pos.pFound, val );
             if ( search( refHead, val, pos, cmp )) {
                 assert( pos.pFound != nullptr );
                 f( *pos.pFound, val );

+                m_Stat.onFindSuccess();

                 return true;
             }
                 return true;
             }

+
+            m_Stat.onFindFailed();

             return false;
         }
 
             return false;
         }
 


@@ -999,8 +1056,11 @@ namespace cds { namespace intrusive {
             if ( search( refHead, val, pos, cmp )) {
                 assert( pos.pCur != nullptr );
                 assert( pos.pFound != nullptr );
             if ( search( refHead, val, pos, cmp )) {
                 assert( pos.pCur != nullptr );
                 assert( pos.pFound != nullptr );

+                m_Stat.onFindSuccess();

                 return iterator( pos.pCur, pos.pFound );
             }
                 return iterator( pos.pCur, pos.pFound );
             }

+
+            m_Stat.onFindFailed();

             return iterator{};
         }
 
             return iterator{};
         }
 


@@ -1010,8 +1070,11 @@ namespace cds { namespace intrusive {
             position pos;
             if ( search( refHead, val, pos, cmp )) {
                 guard.set( pos.pFound );
             position pos;
             if ( search( refHead, val, pos, cmp )) {
                 guard.set( pos.pFound );

+                m_Stat.onFindSuccess();

                 return true;
             }
                 return true;
             }

+
+            m_Stat.onFindFailed();

             return false;
         }
         //@endcond
             return false;
         }
         //@endcond


@@ -1058,13 +1121,15 @@ namespace cds { namespace intrusive {
 
     private:
         //@cond
 
     private:
         //@cond

-        static node_type * alloc_node( value_type * pVal )
+        node_type * alloc_node( value_type * pVal )

         {
         {

+            m_Stat.onNodeCreated();

             return cxx_node_allocator().New( pVal );
         }
 
             return cxx_node_allocator().New( pVal );
         }
 

-        static void delete_node( node_type * pNode )
+        void delete_node( node_type * pNode )

         {
         {

+            m_Stat.onNodeRemoved();

             cxx_node_allocator().Delete( pNode );
         }
 
             cxx_node_allocator().Delete( pNode );
         }
 


@@ -1087,7 +1152,7 @@ namespace cds { namespace intrusive {
             }
         }
 
             }
         }
 

-        static bool link_node( value_type * pVal, position& pos )
+        bool link_node( value_type * pVal, position& pos )

         {
             if ( pos.pPrev ) {
                 if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) {
         {
             if ( pos.pPrev ) {
                 if ( pos.pPrev->data.load( memory_model::memory_order_relaxed ) == nullptr ) {

diff --git a/test/unit/list/intrusive_iterable_dhp.cpp b/test/unit/list/intrusive_iterable_dhp.cpp
index efa335a62954993788b42975a3855bb139f1b5e7..38d8c5274f7fc993cc920880eb9906335b0b6d29 100644 (file)
--- a/test/unit/list/intrusive_iterable_dhp.cpp
+++ b/test/unit/list/intrusive_iterable_dhp.cpp
@@ -136,4 +136,37 @@ namespace {
         test_hp( l );
     }
 
         test_hp( l );
     }
 

+    TEST_F( IntrusiveIterableList_DHP, stat )
+    {
+        struct traits: public ci::iterable_list::traits {
+            typedef mock_disposer disposer;
+            typedef intrusive_iterable_list::less< item_type > less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::iterable_list::stat<> stat;
+        };
+        typedef ci::IterableList< gc_type, item_type, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( IntrusiveIterableList_DHP, wrapped_stat )
+    {
+        struct traits: public ci::iterable_list::traits {
+            typedef mock_disposer disposer;
+            typedef intrusive_iterable_list::less< item_type > less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::iterable_list::wrapped_stat<> stat;
+        };
+        typedef ci::IterableList< gc_type, item_type, traits > list_type;
+
+        traits::stat::stat_type st;
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+

 } // namespace
 } // namespace

diff --git a/test/unit/list/intrusive_iterable_hp.cpp b/test/unit/list/intrusive_iterable_hp.cpp
index cc4c697286edc0148e499a5df7a8b172119f0aa2..1e253580149d3ebcd09a0719b9170c8119899960 100644 (file)
--- a/test/unit/list/intrusive_iterable_hp.cpp
+++ b/test/unit/list/intrusive_iterable_hp.cpp
@@ -137,4 +137,38 @@ namespace {
         test_hp( l );
     }
 
         test_hp( l );
     }
 

+    TEST_F( IntrusiveIterableList_HP, stat )
+    {
+        struct traits: public ci::iterable_list::traits {
+            typedef mock_disposer disposer;
+            typedef intrusive_iterable_list::less< item_type > less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::iterable_list::stat<> stat;
+        };
+        typedef ci::IterableList< gc_type, item_type, traits > list_type;
+
+        list_type l;
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+
+    TEST_F( IntrusiveIterableList_HP, wrapped_stat )
+    {
+        struct traits: public ci::iterable_list::traits {
+            typedef mock_disposer disposer;
+            typedef intrusive_iterable_list::less< item_type > less;
+            typedef cds::atomicity::item_counter item_counter;
+            typedef cds::intrusive::iterable_list::wrapped_stat<> stat;
+        };
+        typedef ci::IterableList< gc_type, item_type, traits > list_type;
+
+        traits::stat::stat_type st;
+
+        list_type l( st );
+        test_common( l );
+        test_ordered_iterator( l );
+        test_hp( l );
+    }
+

 } // namespace
 } // namespace