X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fintrusive%2Fsegmented_queue.h;h=3b71512772f3c6dffbfd05e31bdeab4907c08a24;hb=aedb7b04a9f5c986ab614dc7c56333eb324f4b91;hp=1b61e12b6f2a1b4b01b0737101afa0170b349b3a;hpb=785a8577b9d9ad4988c494055a9a95f1cbf62d65;p=libcds.git diff --git a/cds/intrusive/segmented_queue.h b/cds/intrusive/segmented_queue.h index 1b61e12b..3b715127 100644 --- a/cds/intrusive/segmented_queue.h +++ b/cds/intrusive/segmented_queue.h @@ -4,7 +4,7 @@ #define __CDS_INTRUSIVE_SEGMENTED_QUEUE_H #include -#include +#include #include #include #include @@ -24,7 +24,8 @@ namespace cds { namespace intrusive { /// SegmentedQueue internal statistics. May be used for debugging or profiling template - struct stat { + struct stat + { typedef Counter counter_type; ///< Counter type counter_type m_nPush; ///< Push count @@ -69,8 +70,8 @@ namespace cds { namespace intrusive { //@endcond }; - /// SegmentedQueue default type traits - struct type_traits { + /// SegmentedQueue default traits + struct traits { /// Element disposer that is called when the item to be dequeued. Default is opt::v::empty_disposer (no disposer) typedef opt::v::empty_disposer disposer; @@ -91,6 +92,15 @@ namespace cds { namespace intrusive { /// Alignment of critical data, default is cache line alignment. See cds::opt::alignment option specification enum { alignment = opt::cache_line_alignment }; + /// Padding of segment data, default is no special padding + /** + The segment is just an array of atomic data pointers, + so, the high load leads to false sharing and performance degradation. + A padding of segment data can eliminate false sharing issue. + On the other hand, the padding leads to increase segment size. + */ + enum { padding = opt::no_special_padding }; + /// Segment allocator. Default is \ref CDS_DEFAULT_ALLOCATOR typedef CDS_DEFAULT_ALLOCATOR allocator; @@ -103,7 +113,7 @@ namespace cds { namespace intrusive { /// Metafunction converting option list to traits for SegmentedQueue /** - The metafunction can be useful if a few fields in \ref type_traits should be changed. + The metafunction can be useful if a few fields in \p segmented_queue::traits should be changed. For example: \code typedef cds::intrusive::segmented_queue::make_traits< @@ -111,30 +121,32 @@ namespace cds { namespace intrusive { >::type my_segmented_queue_traits; \endcode This code creates \p %SegmentedQueue type traits with item counting feature, - all other \p type_traits members left unchanged. + all other \p %segmented_queue::traits members left unchanged. \p Options are: - \p opt::disposer - the functor used for dispose removed items. - - \p opt::stat - internal statistics, possible type: \ref stat, \ref empty_stat (the default) - - \p opt::item_counter - item counting feature. Note that atomicity::empty_item_counetr is not suitable + - \p opt::stat - internal statistics, possible type: \p segmented_queue::stat, \p segmented_queue::empty_stat (the default) + - \p opt::item_counter - item counting feature. Note that \p atomicity::empty_item_counetr is not suitable for segmented queue. - \p opt::memory_model - memory model, default is \p opt::v::relaxed_ordering. See option description for the full list of possible models - \p opt::alignment - the alignment for critical data, see option description for explanation - - \p opt::allocator - the allocator used t maintain segments. + - \p opt::padding - the padding of segment data, default no special padding. + See \p traits::padding for explanation. + - \p opt::allocator - the allocator to be used for maintaining segments. - \p opt::lock_type - a mutual exclusion lock type used to maintain internal list of allocated segments. Default is \p cds::opt::Spin, \p std::mutex is also suitable. - \p opt::permutation_generator - a random permutation generator for sequence [0, quasi_factor), - default is cds::opt::v::random2_permutation + default is \p cds::opt::v::random2_permutation */ - template + template struct make_traits { # ifdef CDS_DOXYGEN_INVOKED typedef implementation_defined type ; ///< Metafunction result # else typedef typename cds::opt::make_options< - typename cds::opt::find_type_traits< type_traits, CDS_OPTIONS9 >::type - ,CDS_OPTIONS9 + typename cds::opt::find_type_traits< traits, Options... >::type + ,Options... >::type type; # endif }; @@ -177,64 +189,65 @@ namespace cds { namespace intrusive { Template parameters: - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::PTB - \p T - the type of values stored in the queue - - \p Traits - queue type traits, default is segmented_queue::type_traits. - segmented_queue::make_traits metafunction can be used to construct the + - \p Traits - queue type traits, default is \p segmented_queue::traits. + \p segmented_queue::make_traits metafunction can be used to construct the type traits. The queue stores the pointers to enqueued items so no special node hooks are needed. */ - template + template class SegmentedQueue { public: - typedef GC gc ; ///< Garbage collector - typedef T value_type ; ///< type of the value stored in the queue - typedef Traits options ; ///< Queue's traits - - typedef typename options::disposer disposer ; ///< value disposer, called only in \p clear() when the element to be dequeued - typedef typename options::allocator allocator ; ///< Allocator maintaining the segments - typedef typename options::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option - typedef typename options::item_counter item_counter; ///< Item counting policy, see cds::opt::item_counter option setter - typedef typename options::stat stat ; ///< Internal statistics policy - typedef typename options::lock_type lock_type ; ///< Type of mutex for maintaining an internal list of allocated segments. - typedef typename options::permutation_generator permutation_generator; ///< Random permutation generator for sequence [0, quasi-factor) + typedef GC gc; ///< Garbage collector + typedef T value_type; ///< type of the value stored in the queue + typedef Traits traits; ///< Queue traits + + typedef typename traits::disposer disposer ; ///< value disposer, called only in \p clear() when the element to be dequeued + typedef typename traits::allocator allocator; ///< Allocator maintaining the segments + typedef typename traits::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option + typedef typename traits::item_counter item_counter; ///< Item counting policy, see cds::opt::item_counter option setter + typedef typename traits::stat stat; ///< Internal statistics policy + typedef typename traits::lock_type lock_type; ///< Type of mutex for maintaining an internal list of allocated segments. + typedef typename traits::permutation_generator permutation_generator; ///< Random permutation generator for sequence [0, quasi-factor) static const size_t m_nHazardPtrCount = 2 ; ///< Count of hazard pointer required for the algorithm protected: //@cond // Segment cell. LSB is used as deleted mark - typedef cds::details::marked_ptr< value_type, 1 > cell; + typedef cds::details::marked_ptr< value_type, 1 > regular_cell; + typedef atomics::atomic< regular_cell > atomic_cell; + typedef typename cds::opt::details::apply_padding< atomic_cell, traits::padding >::type cell; // Segment struct segment: public boost::intrusive::slist_base_hook<> { - atomics::atomic< cell > * cells; // Cell array of size \ref m_nQuasiFactor - size_t version; // version tag (ABA prevention tag) + cell * cells; // Cell array of size \ref m_nQuasiFactor + size_t version; // version tag (ABA prevention tag) // cell array is placed here in one continuous memory block // Initializes the segment segment( size_t nCellCount ) // MSVC warning C4355: 'this': used in base member initializer list - : cells( reinterpret_cast< atomics::atomic< cell > * >( this + 1 )) + : cells( reinterpret_cast< cell *>( this + 1 )) , version( 0 ) { init( nCellCount ); } + segment() = delete; + void init( size_t nCellCount ) { - atomics::atomic< cell > * pLastCell = cells + nCellCount; - for ( atomics::atomic< cell > * pCell = cells; pCell < pLastCell; ++pCell ) - pCell->store( cell(), atomics::memory_order_relaxed ); + cell * pLastCell = cells + nCellCount; + for ( cell* pCell = cells; pCell < pLastCell; ++pCell ) + pCell->data.store( regular_cell(), atomics::memory_order_relaxed ); atomics::atomic_thread_fence( memory_model::memory_order_release ); } - - private: - segment(); //=delete }; - typedef typename opt::details::alignment_setter< atomics::atomic, options::alignment >::type aligned_segment_ptr; + typedef typename opt::details::alignment_setter< atomics::atomic, traits::alignment >::type aligned_segment_ptr; //@endcond protected: @@ -300,9 +313,9 @@ namespace cds { namespace intrusive { bool populated( segment const& s ) const { // The lock should be held - atomics::atomic< cell > const * pLastCell = s.cells + quasi_factor(); - for ( atomics::atomic< cell > const * pCell = s.cells; pCell < pLastCell; ++pCell ) { - if ( !pCell->load( memory_model::memory_order_relaxed ).all() ) + cell const * pLastCell = s.cells + quasi_factor(); + for ( cell const * pCell = s.cells; pCell < pLastCell; ++pCell ) { + if ( !pCell->data.load( memory_model::memory_order_relaxed ).all() ) return false; } return true; @@ -310,9 +323,9 @@ namespace cds { namespace intrusive { bool exhausted( segment const& s ) const { // The lock should be held - atomics::atomic< cell > const * pLastCell = s.cells + quasi_factor(); - for ( atomics::atomic< cell > const * pCell = s.cells; pCell < pLastCell; ++pCell ) { - if ( !pCell->load( memory_model::memory_order_relaxed ).bits() ) + cell const * pLastCell = s.cells + quasi_factor(); + for ( cell const * pCell = s.cells; pCell < pLastCell; ++pCell ) { + if ( !pCell->data.load( memory_model::memory_order_relaxed ).bits() ) return false; } return true; @@ -462,18 +475,18 @@ namespace cds { namespace intrusive { ++m_ItemCounter; while ( true ) { - CDS_DEBUG_DO( size_t nLoopCount = 0); + CDS_DEBUG_ONLY( size_t nLoopCount = 0); do { typename permutation_generator::integer_type i = gen; - CDS_DEBUG_DO( ++nLoopCount ); - if ( pTailSegment->cells[i].load(memory_model::memory_order_relaxed).all() ) { + CDS_DEBUG_ONLY( ++nLoopCount ); + if ( pTailSegment->cells[i].data.load(memory_model::memory_order_relaxed).all() ) { // Cell is not empty, go next m_Stat.onPushPopulated(); } else { // Empty cell found, try to enqueue here - cell nullCell; - if ( pTailSegment->cells[i].compare_exchange_strong( nullCell, cell( &val ), + regular_cell nullCell; + if ( pTailSegment->cells[i].data.compare_exchange_strong( nullCell, regular_cell( &val ), memory_model::memory_order_release, atomics::memory_order_relaxed )) { // Ok to push item @@ -620,16 +633,16 @@ namespace cds { namespace intrusive { } bool bHadNullValue = false; - cell item; - CDS_DEBUG_DO( size_t nLoopCount = 0 ); + regular_cell item; + CDS_DEBUG_ONLY( size_t nLoopCount = 0 ); do { typename permutation_generator::integer_type i = gen; - CDS_DEBUG_DO( ++nLoopCount ); + CDS_DEBUG_ONLY( ++nLoopCount ); // Guard the item // In segmented queue the cell cannot be reused // So no loop is needed here to protect the cell - item = pHeadSegment->cells[i].load( memory_model::memory_order_relaxed ); + item = pHeadSegment->cells[i].data.load( memory_model::memory_order_relaxed ); itemGuard.assign( item.ptr() ); // Check if this cell is empty, which means an element @@ -640,7 +653,7 @@ namespace cds { namespace intrusive { // If the item is not deleted yet if ( !item.bits() ) { // Try to mark the cell as deleted - if ( pHeadSegment->cells[i].compare_exchange_strong( item, item | 1, + if ( pHeadSegment->cells[i].data.compare_exchange_strong( item, item | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) { --m_ItemCounter;