From 59965ea1b1413553c875402011dbc4b33db2af6f Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 29 Mar 2015 10:50:05 +0300 Subject: [PATCH] Added more statistics, improved memory ordering --- cds/container/details/bronson_avltree_base.h | 39 +++++++++++ cds/container/impl/bronson_avltree_map_rcu.h | 71 +++++++++++++++++--- tests/unit/print_bronsonavltree_stat.h | 59 +++++++++------- 3 files changed, 133 insertions(+), 36 deletions(-) diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index 2b4839b6..edba654c 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -190,6 +190,19 @@ namespace cds { namespace container { event_counter m_nLeftRightRotation; ///< Count of double left-over-right rotation event_counter m_nRightLeftRotation; ///< Count of double right-over-left rotation + event_counter m_nRotateAfterRightRotation; ///< Count of rotation required after single right rotation + event_counter m_nRemoveAfterRightRotation; ///< Count of removal required after single right rotation + event_counter m_nDamageAfterRightRotation; ///< Count of damaged node after single right rotation + + event_counter m_nRotateAfterLeftRotation; ///< Count of rotation required after signle left rotation + event_counter m_nRemoveAfterLeftRotation; ///< Count of removal required after single left rotation + event_counter m_nDamageAfterLeftRotation; ///< Count of damaged node after single left rotation + + event_counter m_nRotateAfterRLRotation; ///< Count of rotation required after right-over-left rotation + event_counter m_nRemoveAfterRLRotation; ///< Count of removal required after right-over-left rotation + event_counter m_nRotateAfterLRRotation; ///< Count of rotation required after left-over-right rotation + event_counter m_nRemoveAfterLRRotation; ///< Count of removal required after left-over-right rotation + event_counter m_nInsertRebalanceReq; ///< Count of rebalance required after inserting event_counter m_nRemoveRebalanceReq; ///< Count of rebalance required after removing @@ -219,6 +232,19 @@ namespace cds { namespace container { void onRotateRightOverLeft() { ++m_nRightLeftRotation; } void onRotateLeftOverRight() { ++m_nLeftRightRotation; } + void onRotateAfterRightRotation() { ++m_nRotateAfterRightRotation; } + void onRemoveAfterRightRotation() { ++m_nRemoveAfterRightRotation; } + void onDamageAfterRightRotation() { ++m_nDamageAfterRightRotation; } + + void onRotateAfterLeftRotation() { ++m_nRotateAfterLeftRotation; } + void onRemoveAfterLeftRotation() { ++m_nRemoveAfterLeftRotation; } + void onDamageAfterLeftRotation() { ++m_nDamageAfterLeftRotation; } + + void onRotateAfterRLRotation() { ++m_nRotateAfterRLRotation; } + void onRemoveAfterRLRotation() { ++m_nRemoveAfterRLRotation; } + void onRotateAfterLRRotation() { ++m_nRotateAfterLRRotation; } + void onRemoveAfterLRRotation() { ++m_nRemoveAfterLRRotation; } + void onInsertRebalanceRequired() { ++m_nInsertRebalanceReq; } void onRemoveRebalanceRequired() { ++m_nRemoveRebalanceReq; } //@endcond @@ -252,6 +278,19 @@ namespace cds { namespace container { void onRotateRightOverLeft() const {} void onRotateLeftOverRight() const {} + void onRotateAfterRightRotation() const {} + void onRemoveAfterRightRotation() const {} + void onDamageAfterRightRotation() const {} + + void onRotateAfterLeftRotation() const {} + void onRemoveAfterLeftRotation() const {} + void onDamageAfterLeftRotation() const {} + + void onRotateAfterRLRotation() const {} + void onRemoveAfterRLRotation() const {} + void onRotateAfterLRRotation() const {} + void onRemoveAfterLRRotation() const {} + void onInsertRebalanceRequired() const {} void onRemoveRebalanceRequired() const {} //@endcond diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index beecde36..bf778d34 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -969,7 +969,7 @@ namespace cds { namespace container { } } else if ( nChildVersion != node_type::unlinked ) { - if ( pNode->version( memory_model::memory_order_acquire ) != nVersion ) { + if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) { m_stat.onFindRetry(); return find_result::retry; } @@ -1672,9 +1672,13 @@ namespace cds { namespace container { if ( pLRight != nullptr ) pLRight->m_pParent.store( pNode, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); + pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed ); pNode->m_pParent.store( pLeft, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); + if ( pParentLeft == pNode ) pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed ); else { @@ -1683,6 +1687,8 @@ namespace cds { namespace container { } pLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); + // fix up heights links int hNode = 1 + std::max( hLR, hR ); set_height( pNode, hNode ); @@ -1701,6 +1707,7 @@ namespace cds { namespace container { int nodeBalance = hLR - hR; if ( nodeBalance < -1 || nodeBalance > 1 ) { // we need another rotation at pNode + m_stat.onRotateAfterRightRotation(); return pNode; } @@ -1708,17 +1715,22 @@ namespace cds { namespace container { // extra-routing node damage if ( (pLRight == nullptr || hR == 0) && !pNode->is_valued(memory_model::memory_order_relaxed)) { // we need to remove pNode and then repair + m_stat.onRemoveAfterRightRotation(); return pNode; } // we've already fixed the height at pLeft, do we need a rotation here? int leftBalance = hLL - hNode; - if ( leftBalance < -1 || leftBalance > 1 ) + if ( leftBalance < -1 || leftBalance > 1 ) { + m_stat.onRotateAfterRightRotation(); return pLeft; + } // pLeft might also have routing node damage (if pLeft.left was null) - if ( hLL == 0 && !pLeft->is_valued( memory_model::memory_order_relaxed )) + if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_relaxed) ) { + m_stat.onDamageAfterRightRotation(); return pLeft; + } // try to fix the parent height while we've still got the lock return fix_height_locked( pParent ); @@ -1736,9 +1748,13 @@ namespace cds { namespace container { if ( pRLeft != nullptr ) pRLeft->m_pParent.store( pNode, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); + pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed ); pNode->m_pParent.store( pRight, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); + if ( pParentLeft == pNode ) pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed ); else { @@ -1747,6 +1763,8 @@ namespace cds { namespace container { } pRight->m_pParent.store( pParent, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); + // fix up heights int hNode = 1 + std::max( hL, hRL ); set_height( pNode, hNode ); @@ -1756,18 +1774,26 @@ namespace cds { namespace container { m_stat.onRotateLeft(); int nodeBalance = hRL - hL; - if ( nodeBalance < -1 || nodeBalance > 1 ) + if ( nodeBalance < -1 || nodeBalance > 1 ) { + m_stat.onRotateAfterLeftRotation(); return pNode; + } - if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) + if ( (pRLeft == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) { + m_stat.onRemoveAfterLeftRotation(); return pNode; + } int rightBalance = hRR - hNode; - if ( rightBalance < -1 || rightBalance > 1 ) + if ( rightBalance < -1 || rightBalance > 1 ) { + m_stat.onRotateAfterLeftRotation(); return pRight; + } - if ( hRR == 0 && !pRight->is_valued( memory_model::memory_order_relaxed )) + if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_relaxed) ) { + m_stat.onDamageAfterLeftRotation(); return pRight; + } return fix_height_locked( pParent ); } @@ -1789,15 +1815,20 @@ namespace cds { namespace container { pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed ); if ( pLRR != nullptr ) pLRR->m_pParent.store( pNode, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed ); if ( pLRL != nullptr ) pLRL->m_pParent.store( pLeft, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed ); pLeft->m_pParent.store( pLRight, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); + pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed ); pNode->m_pParent.store( pLRight, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); if ( pPL == pNode ) pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed ); @@ -1806,6 +1837,7 @@ namespace cds { namespace container { pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed ); } pLRight->m_pParent.store( pParent, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); // fix up heights int hNode = 1 + std::max( hLRR, hR ); @@ -1833,19 +1865,23 @@ namespace cds { namespace container { int nodeBalance = hLRR - hR; if ( nodeBalance < -1 || nodeBalance > 1 ) { // we need another rotation at pNode + m_stat.onRotateAfterRLRotation(); return pNode; } // pNode might also be damaged by being an unnecessary routing node if ( (pLRR == nullptr || hR == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) { // repair involves splicing out pNode and maybe more rotations + m_stat.onRemoveAfterRLRotation(); return pNode; } // we've already fixed the height at pLRight, do we need a rotation here? int balanceLR = hLeft - hNode; - if ( balanceLR < -1 || balanceLR > 1 ) + if ( balanceLR < -1 || balanceLR > 1 ) { + m_stat.onRotateAfterRLRotation(); return pLRight; + } // try to fix the parent height while we've still got the lock return fix_height_locked( pParent ); @@ -1868,15 +1904,20 @@ namespace cds { namespace container { pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed ); if ( pRLL != nullptr ) pRLL->m_pParent.store( pNode, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed ); if ( pRLR != nullptr ) pRLR->m_pParent.store( pRight, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed ); pRight->m_pParent.store( pRLeft, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); + pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed ); pNode->m_pParent.store( pRLeft, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); if ( pPL == pNode ) pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed ); @@ -1885,6 +1926,7 @@ namespace cds { namespace container { pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed ); } pRLeft->m_pParent.store( pParent, memory_model::memory_order_relaxed ); + atomics::atomic_thread_fence( memory_model::memory_order_acq_rel ); // fix up heights int hNode = 1 + std::max( hL, hRLL ); @@ -1900,14 +1942,21 @@ namespace cds { namespace container { assert( hRR - hRLR <= 1 && hRLR - hRR <= 1 ); int nodeBalance = hRLL - hL; - if ( nodeBalance < -1 || nodeBalance > 1 ) + if ( nodeBalance < -1 || nodeBalance > 1 ) { + m_stat.onRotateAfterLRRotation(); return pNode; - if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued( memory_model::memory_order_relaxed )) + } + + if ( (pRLL == nullptr || hL == 0) && !pNode->is_valued(memory_model::memory_order_relaxed) ) { + m_stat.onRemoveAfterLRRotation(); return pNode; + } int balRL = hRight - hNode; - if ( balRL < -1 || balRL > 1 ) + if ( balRL < -1 || balRL > 1 ) { + m_stat.onRotateAfterLRRotation(); return pRLeft; + } return fix_height_locked( pParent ); } diff --git a/tests/unit/print_bronsonavltree_stat.h b/tests/unit/print_bronsonavltree_stat.h index f237a283..1a1d39d7 100644 --- a/tests/unit/print_bronsonavltree_stat.h +++ b/tests/unit/print_bronsonavltree_stat.h @@ -15,31 +15,40 @@ namespace std { static inline ostream& operator <<(ostream& o, cds::container::bronson_avltree::stat<> const& s) { return o << "\nBronsonAVLTree statistics [cds::container::bronson_avltree::stat]:\n" - << "\t\t m_nFindSuccess: " << s.m_nFindSuccess.get() << "\n" - << "\t\t m_nFindFailed: " << s.m_nFindFailed.get() << "\n" - << "\t\t m_nFindRetry: " << s.m_nFindRetry.get() << "\n" - << "\t\t m_nFindWaitShrinking: " << s.m_nFindWaitShrinking.get() << "\n" - << "\t\t m_nInsertSuccess: " << s.m_nInsertSuccess.get() << "\n" - << "\t\t m_nRelaxedInsertFailed: " << s.m_nRelaxedInsertFailed.get() << "\n" - << "\t\t m_nInsertRetry: " << s.m_nInsertRetry.get() << "\n" - << "\t\t m_nUpdateWaitShrinking: " << s.m_nUpdateWaitShrinking.get() << "\n" - << "\t\t m_nUpdateRetry: " << s.m_nUpdateRetry.get() << "\n" - << "\t\tm_nUpdateRootWaitShrinking: " << s.m_nUpdateRootWaitShrinking.get() << "\n" - << "\t\t m_nUpdateSuccess: " << s.m_nUpdateSuccess.get() << "\n" - << "\t\t m_nUpdateUnlinked: " << s.m_nUpdateUnlinked.get() << "\n" - << "\t\t m_nRemoveRetry: " << s.m_nRemoveRetry.get() << "\n" - << "\t\t m_nRemoveWaitShrinking: " << s.m_nRemoveWaitShrinking.get() << "\n" - << "\t\tm_nRemoveRootWaitShrinking: " << s.m_nRemoveRootWaitShrinking.get() << "\n" - << "\t\t m_nDisposedValue: " << s.m_nDisposedValue.get() << "\n" - << "\t\t m_nDisposedNode: " << s.m_nDisposedNode.get() << "\n" - << "\t\t m_nExtractedValue: " << s.m_nExtractedValue.get() << "\n" - << "\t\t m_nRightRotation: " << s.m_nRightRotation.get() << "\n" - << "\t\t m_nLeftRotation: " << s.m_nLeftRotation.get() << "\n" - << "\t\t m_nLeftRightRotation: " << s.m_nLeftRightRotation.get() << "\n" - << "\t\t m_nRightLeftRotation: " << s.m_nRightLeftRotation.get() << "\n" - << "\t\t m_nInsertRebalanceReq: " << s.m_nInsertRebalanceReq.get() << "\n" - << "\t\t m_nRemoveRebalanceReq: " << s.m_nRemoveRebalanceReq.get() << "\n" - ; + << "\t\t m_nFindSuccess: " << s.m_nFindSuccess.get() << "\n" + << "\t\t m_nFindFailed: " << s.m_nFindFailed.get() << "\n" + << "\t\t m_nFindRetry: " << s.m_nFindRetry.get() << "\n" + << "\t\t m_nFindWaitShrinking: " << s.m_nFindWaitShrinking.get() << "\n" + << "\t\t m_nInsertSuccess: " << s.m_nInsertSuccess.get() << "\n" + << "\t\t m_nRelaxedInsertFailed: " << s.m_nRelaxedInsertFailed.get() << "\n" + << "\t\t m_nInsertRetry: " << s.m_nInsertRetry.get() << "\n" + << "\t\t m_nUpdateWaitShrinking: " << s.m_nUpdateWaitShrinking.get() << "\n" + << "\t\t m_nUpdateRetry: " << s.m_nUpdateRetry.get() << "\n" + << "\t\t m_nUpdateRootWaitShrinking: " << s.m_nUpdateRootWaitShrinking.get() << "\n" + << "\t\t m_nUpdateSuccess: " << s.m_nUpdateSuccess.get() << "\n" + << "\t\t m_nUpdateUnlinked: " << s.m_nUpdateUnlinked.get() << "\n" + << "\t\t m_nRemoveRetry: " << s.m_nRemoveRetry.get() << "\n" + << "\t\t m_nRemoveWaitShrinking: " << s.m_nRemoveWaitShrinking.get() << "\n" + << "\t\t m_nRemoveRootWaitShrinking: " << s.m_nRemoveRootWaitShrinking.get() << "\n" + << "\t\t m_nDisposedValue: " << s.m_nDisposedValue.get() << "\n" + << "\t\t m_nDisposedNode: " << s.m_nDisposedNode.get() << "\n" + << "\t\t m_nExtractedValue: " << s.m_nExtractedValue.get() << "\n" + << "\t\t m_nRightRotation: " << s.m_nRightRotation.get() << "\n" + << "\t\t m_nLeftRotation: " << s.m_nLeftRotation.get() << "\n" + << "\t\t m_nLeftRightRotation: " << s.m_nLeftRightRotation.get() << "\n" + << "\t\t m_nRightLeftRotation: " << s.m_nRightLeftRotation.get() << "\n" + << "\t\t m_nInsertRebalanceReq: " << s.m_nInsertRebalanceReq.get() << "\n" + << "\t\t m_nRemoveRebalanceReq: " << s.m_nRemoveRebalanceReq.get() << "\n" + << "\t\tm_nRotateAfterRightRotation: " << s.m_nRotateAfterRightRotation.get() << "\n" + << "\t\tm_nRemoveAfterRightRotation: " << s.m_nRemoveAfterRightRotation.get() << "\n" + << "\t\tm_nDamageAfterRightRotation: " << s.m_nDamageAfterRightRotation.get() << "\n" + << "\t\t m_nRotateAfterLeftRotation: " << s.m_nRotateAfterLeftRotation.get() << "\n" + << "\t\t m_nRemoveAfterLeftRotation: " << s.m_nRemoveAfterLeftRotation.get() << "\n" + << "\t\t m_nDamageAfterLeftRotation: " << s.m_nDamageAfterLeftRotation.get() << "\n" + << "\t\t m_nRotateAfterRLRotation: " << s.m_nRotateAfterRLRotation.get() << "\n" + << "\t\t m_nRemoveAfterRLRotation: " << s.m_nRemoveAfterRLRotation.get() << "\n" + << "\t\t m_nRotateAfterLRRotation: " << s.m_nRotateAfterLRRotation.get() << "\n" + << "\t\t m_nRemoveAfterLRRotation: " << s.m_nRemoveAfterLRRotation.get() << "\n"; } } //namespace std -- 2.34.1