3 #ifndef CDSLIB_CONTAINER_SEGMENTED_QUEUE_H
4 #define CDSLIB_CONTAINER_SEGMENTED_QUEUE_H
7 #include <functional> // ref
8 #include <cds/intrusive/segmented_queue.h>
9 #include <cds/details/trivial_assign.h>
11 namespace cds { namespace container {
13 /// SegmentedQueue -related declarations
14 namespace segmented_queue {
16 # ifdef CDS_DOXYGEN_INVOKED
17 /// SegmentedQueue internal statistics
18 typedef cds::intrusive::segmented_queue::stat stat;
20 using cds::intrusive::segmented_queue::stat;
23 /// SegmentedQueue empty internal statistics (no overhead)
24 typedef cds::intrusive::segmented_queue::empty_stat empty_stat;
26 /// SegmentedQueue default type traits
29 /// Item allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
30 typedef CDS_DEFAULT_ALLOCATOR node_allocator;
32 /// Item counter, default is atomicity::item_counter
34 The item counting is an essential part of segmented queue algorithm.
35 The \p empty() member function is based on checking <tt>size() == 0</tt>.
36 Therefore, dummy item counter like atomicity::empty_item_counter is not the proper counter.
38 typedef atomicity::item_counter item_counter;
40 /// Internal statistics, possible predefined types are \ref stat, \ref empty_stat (the default)
41 typedef segmented_queue::empty_stat stat;
43 /// Memory model, default is opt::v::relaxed_ordering. See cds::opt::memory_model for the full list of possible types
44 typedef opt::v::relaxed_ordering memory_model;
46 /// Alignment of critical data, default is cache line alignment. See cds::opt::alignment option specification
47 enum { alignment = opt::cache_line_alignment };
49 /// Padding of segment data, default is no special padding
51 The segment is just an array of atomic data pointers,
52 so, the high load leads to false sharing and performance degradation.
53 A padding of segment data can eliminate false sharing issue.
54 On the other hand, the padding leads to increase segment size.
56 enum { padding = cds::intrusive::segmented_queue::traits::padding };
58 /// Segment allocator. Default is \ref CDS_DEFAULT_ALLOCATOR
59 typedef CDS_DEFAULT_ALLOCATOR allocator;
61 /// Lock type used to maintain an internal list of allocated segments
62 typedef cds::sync::spin lock_type;
64 /// Random \ref cds::opt::permutation_generator "permutation generator" for sequence [0, quasi_factor)
65 typedef cds::opt::v::random2_permutation<int> permutation_generator;
68 /// Metafunction converting option list to traits for SegmentedQueue
70 The metafunction can be useful if a few fields in \p segmented_queue::traits should be changed.
73 typedef cds::container::segmented_queue::make_traits<
74 cds::opt::item_counter< cds::atomicity::item_counter >
75 >::type my_segmented_queue_traits;
77 This code creates \p %SegmentedQueue type traits with item counting feature,
78 all other \p segmented_queue::traits members left unchanged.
81 - \p opt::node_allocator - node allocator.
82 - \p opt::stat - internal statistics, possible type: \p segmented_queue::stat, \p segmented_queue::empty_stat (the default)
83 - \p opt::item_counter - item counting feature. Note that \p atomicity::empty_item_counetr is not suitable
85 - \p opt::memory_model - memory model, default is \p opt::v::relaxed_ordering.
86 See option description for the full list of possible models
87 - \p opt::alignment - the alignment of critical data, see option description for explanation
88 - \p opt::padding - the padding of segment data, default no special padding.
89 See \p traits::padding for explanation.
90 - \p opt::allocator - the allocator used to maintain segments.
91 - \p opt::lock_type - a mutual exclusion lock type used to maintain internal list of allocated
92 segments. Default is \p cds::opt::Spin, \p std::mutex is also suitable.
93 - \p opt::permutation_generator - a random permutation generator for sequence [0, quasi_factor),
94 default is \p cds::opt::v::random2_permutation<int>
96 template <typename... Options>
98 # ifdef CDS_DOXYGEN_INVOKED
99 typedef implementation_defined type ; ///< Metafunction result
101 typedef typename cds::opt::make_options<
102 typename cds::opt::find_type_traits< traits, Options... >::type
108 } // namespace segmented_queue
113 template <typename GC, typename T, typename Traits>
114 struct make_segmented_queue
117 typedef T value_type;
118 typedef Traits original_type_traits;
120 typedef cds::details::Allocator< T, typename original_type_traits::node_allocator > cxx_node_allocator;
121 struct node_disposer {
122 void operator()( T * p )
124 cxx_node_allocator().Delete( p );
128 struct intrusive_type_traits: public original_type_traits
130 typedef node_disposer disposer;
133 typedef cds::intrusive::SegmentedQueue< gc, value_type, intrusive_type_traits > type;
136 } // namespace details
140 /** @ingroup cds_nonintrusive_queue
142 The queue is based on work
143 - [2010] Afek, Korland, Yanovsky "Quasi-Linearizability: relaxed consistency for improved concurrency"
145 In this paper the authors offer a relaxed version of linearizability, so-called quasi-linearizability,
146 that preserves some of the intuition, provides a flexible way to control the level of relaxation
147 and supports th implementation of more concurrent and scalable data structure.
148 Intuitively, the linearizability requires each run to be equivalent in some sense to a serial run
149 of the algorithm. This equivalence to some serial run imposes strong synchronization requirements
150 that in many cases results in limited scalability and synchronization bottleneck.
152 The general idea is that the queue maintains a linked list of segments, each segment is an array of
153 nodes in the size of the quasi factor, and each node has a deleted boolean marker, which states
154 if it has been dequeued. Each producer iterates over last segment in the linked list in some random
155 permutation order. Whet it finds an empty cell it performs a CAS operation attempting to enqueue its
156 new element. In case the entire segment has been scanned and no available cell is found (implying
157 that the segment is full), then it attempts to add a new segment to the list.
159 The dequeue operation is similar: the consumer iterates over the first segment in the linked list
160 in some random permutation order. When it finds an item which has not yet been dequeued, it performs
161 CAS on its deleted marker in order to "delete" it, if succeeded this item is considered dequeued.
162 In case the entire segment was scanned and all the nodes have already been dequeued (implying that
163 the segment is empty), then it attempts to remove this segment from the linked list and starts
164 the same process on the next segment. If there is no next segment, the queue is considered empty.
166 Based on the fact that most of the time threads do not add or remove segments, most of the work
167 is done in parallel on different cells in the segments. This ensures a controlled contention
168 depending on the segment size, which is quasi factor.
170 The segmented queue is an <i>unfair</i> queue since it violates the strong FIFO order but no more than
171 quasi factor. It means that the consumer dequeues any item from the current first segment.
174 - \p GC - a garbage collector, possible types are cds::gc::HP, cds::gc::DHP
175 - \p T - the type of values stored in the queue
176 - \p Traits - queue type traits, default is \p segmented_queue::traits.
177 \p segmented_queue::make_traits metafunction can be used to construct your
180 template <class GC, typename T, typename Traits = segmented_queue::traits >
181 class SegmentedQueue:
182 #ifdef CDS_DOXYGEN_INVOKED
183 public cds::intrusive::SegmentedQueue< GC, T, Traits >
185 public details::make_segmented_queue< GC, T, Traits >::type
189 typedef details::make_segmented_queue< GC, T, Traits > maker;
190 typedef typename maker::type base_class;
193 typedef GC gc; ///< Garbage collector
194 typedef T value_type; ///< type of the value stored in the queue
195 typedef Traits traits; ///< Queue traits
197 typedef typename traits::node_allocator node_allocator; ///< Node allocator
198 typedef typename base_class::memory_model memory_model; ///< Memory ordering. See cds::opt::memory_model option
199 typedef typename base_class::item_counter item_counter; ///< Item counting policy, see cds::opt::item_counter option setter
200 typedef typename base_class::stat stat ; ///< Internal statistics policy
201 typedef typename base_class::lock_type lock_type ; ///< Type of mutex for maintaining an internal list of allocated segments.
202 typedef typename base_class::permutation_generator permutation_generator; ///< Random permutation generator for sequence [0, quasi-factor)
204 static const size_t c_nHazardPtrCount = base_class::c_nHazardPtrCount ; ///< Count of hazard pointer required for the algorithm
208 typedef typename maker::cxx_node_allocator cxx_node_allocator;
209 typedef std::unique_ptr< value_type, typename maker::node_disposer > scoped_node_ptr;
211 static value_type * alloc_node( value_type const& v )
213 return cxx_node_allocator().New( v );
216 static value_type * alloc_node()
218 return cxx_node_allocator().New();
221 template <typename... Args>
222 static value_type * alloc_node_move( Args&&... args )
224 return cxx_node_allocator().MoveNew( std::forward<Args>( args )... );
229 /// Initializes the empty queue
231 size_t nQuasiFactor ///< Quasi factor. If it is not a power of 2 it is rounded up to nearest power of 2. Minimum is 2.
233 : base_class( nQuasiFactor )
236 /// Clears the queue and deletes all internal data
240 /// Inserts a new element at last segment of the queue
242 The function makes queue node in dynamic memory calling copy constructor for \p val
243 and then it calls intrusive::SEgmentedQueue::enqueue.
244 Returns \p true if success, \p false otherwise.
246 bool enqueue( value_type const& val )
248 scoped_node_ptr p( alloc_node(val) );
249 if ( base_class::enqueue( *p ) ) {
256 /// Enqueues data to the queue using a functor
258 \p Func is a functor called to create node.
259 The functor \p f takes one argument - a reference to a new node of type \ref value_type :
261 cds::container::SegmentedQueue< cds::gc::HP, Foo > myQueue;
263 myQueue.enqueue_with( [&bar]( Foo& dest ) { dest = bar; } );
266 template <typename Func>
267 bool enqueue_with( Func f )
269 scoped_node_ptr p( alloc_node() );
271 if ( base_class::enqueue( *p ) ) {
279 /// Synonym for \p enqueue() member function
280 bool push( value_type const& val )
282 return enqueue( val );
285 /// Synonym for \p enqueue_with() member function
286 template <typename Func>
287 bool push_with( Func f )
289 return enqueue_with( f );
292 /// Enqueues data of type \ref value_type constructed with <tt>std::forward<Args>(args)...</tt>
293 template <typename... Args>
294 bool emplace( Args&&... args )
296 scoped_node_ptr p( alloc_node_move( std::forward<Args>(args)... ) );
297 if ( base_class::enqueue( *p )) {
304 /// Dequeues a value from the queue
306 If queue is not empty, the function returns \p true, \p dest contains copy of
307 dequeued value. The assignment operator for type \ref value_type is invoked.
308 If queue is empty, the function returns \p false, \p dest is unchanged.
310 bool dequeue( value_type& dest )
312 return dequeue_with( [&dest]( value_type& src ) { dest = src; });
315 /// Dequeues a value using a functor
317 \p Func is a functor called to copy dequeued value.
318 The functor takes one argument - a reference to removed node:
320 cds:container::MSQueue< cds::gc::HP, Foo > myQueue;
322 myQueue.dequeue_with( [&bar]( Foo& src ) { bar = std::move( src );});
324 The functor is called only if the queue is not empty.
326 template <typename Func>
327 bool dequeue_with( Func f )
329 value_type * p = base_class::dequeue();
332 gc::template retire< typename maker::node_disposer >( p );
338 /// Synonym for \p dequeue_with() function
339 template <typename Func>
340 bool pop_with( Func f )
342 return dequeue_with( f );
345 /// Synonym for \p dequeue() function
346 bool pop( value_type& dest )
348 return dequeue( dest );
351 /// Checks if the queue is empty
353 The original segmented queue algorithm does not allow to check emptiness accurately
354 because \p empty() is unlinearizable.
355 This function tests queue's emptiness checking <tt>size() == 0</tt>,
356 so, the item counting feature is an essential part of queue's algorithm.
360 return base_class::empty();
365 The function repeatedly calls \ref dequeue until it returns \p nullptr.
366 The disposer specified in \p Traits template argument is called for each removed item.
373 /// Returns queue's item count
376 return base_class::size();
379 /// Returns reference to internal statistics
381 The type of internal statistics is specified by \p Traits template argument.
383 const stat& statistics() const
385 return base_class::statistics();
388 /// Returns quasi factor, a power-of-two number
389 size_t quasi_factor() const
391 return base_class::quasi_factor();
395 }} // namespace cds::container
397 #endif // #ifndef CDSLIB_CONTAINER_SEGMENTED_QUEUE_H