From d43bc2812d0b9b35a5471f550a4d6d8eeff8a2d9 Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 4 Dec 2014 16:19:28 +0300 Subject: [PATCH] Improve cds::gc::DHP scan() performance --- cds/gc/details/dhp.h | 37 ++++++++++++++++++++++++++----------- src/dhp_gc.cpp | 24 +++++++++++++++++++----- 2 files changed, 45 insertions(+), 16 deletions(-) diff --git a/cds/gc/details/dhp.h b/cds/gc/details/dhp.h index 3f30422d..142cabb8 100644 --- a/cds/gc/details/dhp.h +++ b/cds/gc/details/dhp.h @@ -269,6 +269,21 @@ namespace cds { namespace gc { return m_nItemCount.fetch_add( 1, atomics::memory_order_relaxed ) + 1; } + /// Pushes [pFirst, pLast] list linked by pNext field. + size_t push_list( retired_ptr_node* pFirst, retired_ptr_node* pLast, size_t nSize ) + { + assert( pFirst ); + assert( pLast ); + + retired_ptr_node * pHead = m_pHead.load( atomics::memory_order_acquire ); + do { + pLast->m_pNext = pHead; + // pHead is changed by compare_exchange_weak + } while ( !m_pHead.compare_exchange_weak( pHead, pFirst, atomics::memory_order_release, atomics::memory_order_relaxed ) ); + + return m_nItemCount.fetch_add( nSize, atomics::memory_order_relaxed ) + 1; + } + /// Result of \ref dhp_gc_privatve "privatize" function. /** The \p privatize function returns retired node list as \p first and the size of that list as \p second. @@ -311,17 +326,17 @@ namespace cds { namespace gc { /// Pool block struct block { - block * pNext ; ///< next block - item items[m_nItemPerBlock] ; ///< item array + block * pNext; ///< next block + item items[m_nItemPerBlock]; ///< item array }; - atomics::atomic m_pBlockListHead ; ///< head of of allocated block list + atomics::atomic m_pBlockListHead; ///< head of of allocated block list // To solve ABA problem we use epoch-based approach - static const unsigned int c_nEpochCount = 4 ; ///< Max epoch count - atomics::atomic m_nCurEpoch ; ///< Current epoch - atomics::atomic m_pEpochFree[c_nEpochCount] ; ///< List of free item per epoch - atomics::atomic m_pGlobalFreeHead ; ///< Head of unallocated item list + static const unsigned int c_nEpochCount = 4; ///< Max epoch count + atomics::atomic m_nCurEpoch; ///< Current epoch + atomics::atomic m_pEpochFree[c_nEpochCount]; ///< List of free item per epoch + atomics::atomic m_pGlobalFreeHead; ///< Head of unallocated item list cds::details::Allocator< block, Alloc > m_BlockAllocator ; ///< block allocator @@ -338,7 +353,7 @@ namespace cds { namespace gc { CDS_STRICT_DO( pItem->m_pNext = nullptr ); } - // link new block to block list + // links new block to the block list { block * pHead = m_pBlockListHead.load(atomics::memory_order_acquire); do { @@ -347,7 +362,7 @@ namespace cds { namespace gc { } while ( !m_pBlockListHead.compare_exchange_weak( pHead, pNew, atomics::memory_order_release, atomics::memory_order_relaxed )); } - // link block's items to free list + // links block's items to the free list { item * pHead = m_pGlobalFreeHead.load(atomics::memory_order_acquire); do { @@ -394,7 +409,7 @@ namespace cds { namespace gc { m_nCurEpoch.fetch_add( 1, atomics::memory_order_acq_rel ); } - /// Allocates new retired pointer + /// Allocates the new retired pointer retired_ptr_node& alloc() { unsigned int nEpoch; @@ -432,7 +447,7 @@ namespace cds { namespace gc { return node; } - /// Places the list (pHead, pTail) of retired pointers to pool (frees retired pointers) + /// Places the list [pHead, pTail] of retired pointers to pool (frees retired pointers) /** The list is linked on the m_pNextFree field */ diff --git a/src/dhp_gc.cpp b/src/dhp_gc.cpp index 04377f88..375fb8b7 100644 --- a/src/dhp_gc.cpp +++ b/src/dhp_gc.cpp @@ -183,6 +183,11 @@ namespace cds { namespace gc { namespace dhp { } // Liberate cycle + + details::retired_ptr_node * pBusyFirst = nullptr; + details::retired_ptr_node * pBusyLast = nullptr; + size_t nBusyCount = 0; + for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) ) { // get guarded pointer @@ -195,15 +200,24 @@ namespace cds { namespace gc { namespace dhp { // pRetired is the head of retired pointers list for which the m_ptr.m_p field is equal // List is linked on m_pNextFree field - do { - details::retired_ptr_node * pNext = pRetired->m_pNextFree; - m_RetiredBuffer.push( *pRetired ); - pRetired = pNext; - } while ( pRetired ); + if ( pBusyLast ) + pBusyLast->m_pNext = pRetired; + else + pBusyFirst = pRetired; + pBusyLast = pRetired; + ++nBusyCount; + while ( pBusyLast->m_pNextFree ) { + pBusyLast = pBusyLast->m_pNext = pBusyLast->m_pNextFree; + ++nBusyCount; + } } } } + // Place [pBusyList, pBusyLast] back to m_RetiredBuffer + if ( pBusyFirst ) + m_RetiredBuffer.push_list( pBusyFirst, pBusyLast, nBusyCount ); + // Free all retired pointers details::liberate_set::list_range range = set.free_all(); -- 2.34.1