From: khizmax Date: Wed, 20 Jul 2016 20:38:45 +0000 (+0300) Subject: Added internal statistics for IterableList X-Git-Tag: v2.2.0~187 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=1a28923c2d39a74418cd129c4f48c4ffdb6df33e Added internal statistics for IterableList --- diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h index 2953a791..7ef00bdc 100644 --- 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 }; + /// \p IterableList internal statistics + template + 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 > + 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 { @@ -91,6 +182,13 @@ namespace cds { namespace intrusive { /// 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; @@ -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. + - \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" diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h index 66e018c3..00e20233 100644 --- 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. + 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 O(N). 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::stat stat; ///< Internal statistics 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 + mutable stat m_Stat; ///< Internal statistics //@cond typedef cds::details::Allocator< node_type, node_allocator > cxx_node_allocator; @@ -380,6 +389,14 @@ namespace cds { namespace intrusive { : m_pHead( nullptr ) {} + //@cond + template >::value >> + explicit IterableList( Stat& st ) + : m_pHead( nullptr ) + , m_Stat( st ) + {} + //@endcond + /// 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. - 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 where \p first is \p true if operation is successful, @@ -841,13 +858,18 @@ namespace cds { namespace intrusive { position pos; while ( true ) { - if ( search( refHead, val, pos, key_comparator() ) ) + if ( search( refHead, val, pos, key_comparator() )) { + m_Stat.onInsertFailed(); return false; + } if ( link_node( &val, pos ) ) { ++m_ItemCounter; + m_Stat.onInsertSuccess(); return true; } + + m_Stat.onInsertRetry(); } } @@ -860,14 +882,19 @@ namespace cds { namespace intrusive { guard.assign( &val ); while ( true ) { - if ( search( refHead, val, pos, key_comparator() ) ) + if ( search( refHead, val, pos, key_comparator() ) ) { + m_Stat.onInsertFailed(); return false; + } if ( link_node( &val, pos ) ) { f( val ); ++m_ItemCounter; + m_Stat.onInsertSuccess(); return true; } + + m_Stat.onInsertRetry(); } } @@ -890,19 +917,25 @@ namespace cds { namespace intrusive { retire_data( pos.pFound ); func( val, pos.pFound ); } + m_Stat.onUpdateExisting(); return std::make_pair( true, false ); } } else { - if ( !bInsert ) + if ( !bInsert ) { + m_Stat.onUpdateFailed(); return std::make_pair( false, false ); + } - if ( link_node( &val, pos ) ) { + if ( link_node( &val, pos )) { func( val, static_cast( nullptr )); ++m_ItemCounter; + m_Stat.onUpdateNew(); 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; + m_Stat.onEraseSuccess(); return true; } else @@ -922,7 +956,11 @@ namespace cds { namespace intrusive { } else break; + + m_Stat.onEraseRetry(); } + + m_Stat.onEraseFailed(); return false; } @@ -934,11 +972,16 @@ namespace cds { namespace intrusive { if ( unlink_node( pos )) { f( *pos.pFound ); --m_ItemCounter; + m_Stat.onEraseSuccess(); return true; } else bkoff(); + + m_Stat.onEraseRetry(); } + + m_Stat.onEraseFailed(); return false; } @@ -965,11 +1008,16 @@ namespace cds { namespace intrusive { if ( unlink_node( pos )) { dest.set( pos.pFound ); --m_ItemCounter; + m_Stat.onEraseSuccess(); return true; } else bkoff(); + + m_Stat.onEraseRetry(); } + + m_Stat.onEraseFailed(); 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; - return search( refHead, val, pos, cmp ); + if ( search( refHead, val, pos, cmp ) ) { + m_Stat.onFindSuccess(); + return true; + } + + m_Stat.onFindFailed(); + return false; } template @@ -987,8 +1041,11 @@ namespace cds { namespace intrusive { if ( search( refHead, val, pos, cmp )) { assert( pos.pFound != nullptr ); f( *pos.pFound, val ); + m_Stat.onFindSuccess(); return true; } + + m_Stat.onFindFailed(); return false; } @@ -999,8 +1056,11 @@ namespace cds { namespace intrusive { if ( search( refHead, val, pos, cmp )) { assert( pos.pCur != nullptr ); assert( pos.pFound != nullptr ); + m_Stat.onFindSuccess(); return iterator( pos.pCur, pos.pFound ); } + + m_Stat.onFindFailed(); return iterator{}; } @@ -1010,8 +1070,11 @@ namespace cds { namespace intrusive { position pos; if ( search( refHead, val, pos, cmp )) { guard.set( pos.pFound ); + m_Stat.onFindSuccess(); return true; } + + m_Stat.onFindFailed(); return false; } //@endcond @@ -1058,13 +1121,15 @@ namespace cds { namespace intrusive { 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 ); } - static void delete_node( node_type * pNode ) + void delete_node( node_type * pNode ) { + m_Stat.onNodeRemoved(); 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 ) { diff --git a/test/unit/list/intrusive_iterable_dhp.cpp b/test/unit/list/intrusive_iterable_dhp.cpp index efa335a6..38d8c527 100644 --- 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_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 diff --git a/test/unit/list/intrusive_iterable_hp.cpp b/test/unit/list/intrusive_iterable_hp.cpp index cc4c6972..1e253580 100644 --- 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_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