From b55f2b953cf848b99698374c8a8afd9aaf465974 Mon Sep 17 00:00:00 2001 From: Mike Krinkin Date: Fri, 17 Apr 2015 00:44:07 +0300 Subject: [PATCH] Optimize fast path in inc_item_count. --- cds/intrusive/split_list.h | 29 ++++++++++++++++++++++++----- cds/intrusive/split_list_nogc.h | 30 +++++++++++++++++++++++++----- cds/intrusive/split_list_rcu.h | 29 ++++++++++++++++++++++++----- 3 files changed, 73 insertions(+), 15 deletions(-) diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h index 7a923dc8..2d78c141 100644 --- a/cds/intrusive/split_list.h +++ b/cds/intrusive/split_list.h @@ -4,6 +4,7 @@ #define CDSLIB_INTRUSIVE_SPLIT_LIST_H #include +#include namespace cds { namespace intrusive { @@ -349,6 +350,7 @@ namespace cds { namespace intrusive { ordered_list_wrapper m_List; ///< Ordered list containing split-list items bucket_table m_Buckets; ///< bucket table atomics::atomic m_nBucketCountLog2; ///< log2( current bucket count ) + atomics::atomic m_nMaxItemCount; ///< number of items container can hold, before we have to resize item_counter m_ItemCounter; ///< Item counter hash m_HashFunctor; ///< Hash functor stat m_Stat; ///< Internal statistics @@ -457,13 +459,28 @@ namespace cds { namespace intrusive { m_Buckets.bucket( 0, pNode ); } + static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor ) + { + return nBucketCount * nLoadFactor; + } + void inc_item_count() { - size_t sz = m_nBucketCountLog2.load(atomics::memory_order_relaxed); - if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && (static_cast(1) << sz ) < m_Buckets.capacity() ) - { - m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); - } + size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed); + if ( ++m_ItemCounter <= nMaxCount ) + return; + + const size_t nLoadFactor = m_Buckets.load_factor(); + size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed); + const size_t nBucketCount = static_cast(1) << sz; + if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor )) + return; // someone already have updated m_nBucketCountLog2, so stop here + + const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor ) + : std::numeric_limits::max(); + m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed, + memory_model::memory_order_relaxed ); + m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_seq_cst, memory_model::memory_order_relaxed ); } template @@ -587,6 +604,7 @@ namespace cds { namespace intrusive { */ SplitListSet() : m_nBucketCountLog2(1) + , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) ) { init(); } @@ -598,6 +616,7 @@ namespace cds { namespace intrusive { ) : m_Buckets( nItemCount, nLoadFactor ) , m_nBucketCountLog2(1) + , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) ) { init(); } diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h index 8166312f..5ae837c8 100644 --- a/cds/intrusive/split_list_nogc.h +++ b/cds/intrusive/split_list_nogc.h @@ -6,6 +6,8 @@ #include #include +#include + namespace cds { namespace intrusive { /// Split-ordered list (template specialization for gc::nogc) @@ -144,6 +146,7 @@ namespace cds { namespace intrusive { ordered_list_wrapper m_List; ///< Ordered list containing split-list items bucket_table m_Buckets; ///< bucket table atomics::atomic m_nBucketCountLog2; ///< log2( current bucket count ) + atomics::atomic m_nMaxItemCount; ///< number of items container can hold, before we have to resize item_counter m_ItemCounter; ///< Item counter hash m_HashFunctor; ///< Hash functor stat m_Stat; ///< Internal statistics @@ -253,13 +256,28 @@ namespace cds { namespace intrusive { m_Buckets.bucket( 0, pNode ); } - void inc_item_count() + static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor ) + { + return nBucketCount * nLoadFactor; + } + + void inc_item_count() { + size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed); + if ( ++m_ItemCounter <= nMaxCount ) + return; + + const size_t nLoadFactor = m_Buckets.load_factor(); size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed); - if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() ) - { - m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); - } + const size_t nBucketCount = static_cast(1) << sz; + if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor )) + return; // someone already have updated m_nBucketCountLog2, so stop here + + const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor ) + : std::numeric_limits::max(); + m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed, + memory_model::memory_order_relaxed ); + m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_seq_cst, memory_model::memory_order_relaxed ); } //@endcond @@ -273,6 +291,7 @@ namespace cds { namespace intrusive { */ SplitListSet() : m_nBucketCountLog2(1) + , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) ) { init(); } @@ -284,6 +303,7 @@ namespace cds { namespace intrusive { ) : m_Buckets( nItemCount, nLoadFactor ) , m_nBucketCountLog2(1) + , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) ) { init(); } diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h index 8a7916b4..f83bd7d2 100644 --- a/cds/intrusive/split_list_rcu.h +++ b/cds/intrusive/split_list_rcu.h @@ -5,6 +5,7 @@ #include #include +#include namespace cds { namespace intrusive { @@ -241,6 +242,7 @@ namespace cds { namespace intrusive { ordered_list_wrapper m_List; ///< Ordered list containing split-list items bucket_table m_Buckets; ///< bucket table atomics::atomic m_nBucketCountLog2; ///< log2( current bucket count ) + atomics::atomic m_nMaxItemCount; ///< number of items container can hold, before we have to resize item_counter m_ItemCounter; ///< Item counter hash m_HashFunctor; ///< Hash functor stat m_Stat; ///< Internal stattistics accumulator @@ -350,13 +352,28 @@ namespace cds { namespace intrusive { m_Buckets.bucket( 0, pNode ); } - void inc_item_count() + static size_t max_item_count( size_t nBucketCount, size_t nLoadFactor ) { + return nBucketCount * nLoadFactor; + } + + void inc_item_count() + { + size_t nMaxCount = m_nMaxItemCount.load(memory_model::memory_order_relaxed); + if ( ++m_ItemCounter <= nMaxCount ) + return; + + const size_t nLoadFactor = m_Buckets.load_factor(); size_t sz = m_nBucketCountLog2.load(memory_model::memory_order_relaxed); - if ( ( ++m_ItemCounter >> sz ) > m_Buckets.load_factor() && ((size_t)(1 << sz )) < m_Buckets.capacity() ) - { - m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed ); - } + const size_t nBucketCount = static_cast(1) << sz; + if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor )) + return; // someone already have updated m_nBucketCountLog2, so stop here + + const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor ) + : std::numeric_limits::max(); + m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed, + memory_model::memory_order_relaxed ); + m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_seq_cst, memory_model::memory_order_relaxed ); } template @@ -465,6 +482,7 @@ namespace cds { namespace intrusive { */ SplitListSet() : m_nBucketCountLog2(1) + , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) ) { init(); } @@ -476,6 +494,7 @@ namespace cds { namespace intrusive { ) : m_Buckets( nItemCount, nLoadFactor ) , m_nBucketCountLog2(1) + , m_nMaxItemCount( max_item_count(2, m_Buckets.load_factor()) ) { init(); } -- 2.34.1