FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

perf(wsq): remove UnboundedWSQ::pop() and relax steal() ordering; · taskflow/taskflow@af2908a · GitHub

  1. taskflow
  2. taskflow

Repository navigation

Commit af2908a

Browse files
wicyn
committed
perf(wsq): remove UnboundedWSQ::pop() and relax steal() ordering;
 downgrade BoundedWSQ::steal() top load and pop() CAS to relaxed/acq_rel UnboundedWSQ is used only as the executor's overflow region: the owner only pushes and thieves only steal — the owner never pops. With pop() gone as dead code, the cross-variable Dekker mutual-exclusion structure between top and bottom disappears, and that structure was the sole reason steal() needed a seq_cst fence and a seq_cst CAS. The downgrades follow from this: UnboundedWSQ::steal() - Remove the seq_cst fence: it existed only to pair with pop()'s fence in the single total order S and arbitrate the "last element" race. With no pop(), the fence has nothing to pair with. - CAS success order seq_cst -> acq_rel: the only remaining contention is thief-vs-thief on the single variable top. CAS RMW atomicity guarantees exactly one thief wins, and release/acquire is sufficient to chain top's modification order; no cross-variable total order is required. - _top.load acquire -> relaxed: top increases monotonically, so relaxed can at worst read a smaller, stale value, making the t<b check conservative (one missed steal, never out of bounds); the CAS then re-validates against the latest top and returns empty on failure. Slot-data visibility is carried by _bottom.load(acquire) paired with push()'s release, independent of how top is read. BoundedWSQ::steal() - Only _top.load acquire -> relaxed. BoundedWSQ still has pop(), so the Dekker structure remains and both the seq_cst fence and the seq_cst CAS are kept unchanged. Relaxing the top load is safe: the seq_cst fence immediately following it is a full barrier that already prevents the top load from being reordered with the subsequent bottom load and slot load — the LoadLoad reordering that acquire was meant to block is already covered by the fence. Slot visibility likewise depends on bottom's acquire chain, not on how top is read. BoundedWSQ::pop() - CAS success order seq_cst -> acq_rel. The seq_cst fence in pop() is retained, and so is steal()'s seq_cst fence and steal()'s seq_cst CAS. The argument that pop()'s CAS need not enter S: * The Dekker / SB exclusion that prevents fast-path double-take is carried entirely by the two seq_cst fences plus steal()'s seq_cst CAS anchor. pop()'s own side is cleanly SB-shaped (store bottom; seq_cst fence; load top), so its fence does the SB duty on its own — pop()'s CAS is not the anchor for either fence. * pop()'s CAS executes only on the t==b (last-element) path, i.e. never on the fast path. That path is single-variable contention: owner-CAS vs thief-CAS both move top from t to t+1, and RMW atomicity guarantees exactly one winner regardless of memory order. acq_rel provides the acquire needed to observe the loser/winner state and the release to publish the claim; entry into the global total order S is not required. Net effect: pop() keeps its seq_cst fence (load-bearing) but drops one seq_cst RMW on the cold last-element path. Tests (wsq_test.cpp) - UnboundedWSQ tests converted to steal-only; all UnboundedWSQ::pop() calls removed. BoundedWSQ tests are untouched (BoundedWSQ still has pop()). - UnboundedWSQ.Resize: drain loop pop() -> steal(). - UnboundedWSQ.Owner / ValueType: dropped the LIFO pop() verification; the pre-existing steal() FIFO check now covers the single-thread path. Removed the now-duplicated second push round. - UnboundedWSQ.*Consumers / *.BulkPush: dropped the "master/bulk push and pop" LIFO blocks; in the concurrent phase the owner only pushes and waits (while(consumed != N) yield()) for thieves to drain, since a steal-only owner cannot pop. `items` is now collected solely from `stolens`, and the trailing pop()==nullptr assertion is removed (steal()==nullptr kept).
1 parent d0ba007 commit af2908a

2 files changed

Lines changed: 410 additions & 512 deletions

File tree

‎taskflow/core/wsq.hpp‎

Lines changed: 6 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
#pragma once
1+
#pragma once
22

33
#include <bit>
44

@@ -293,28 +293,6 @@ class UnboundedWSQ {
293293
template <typename I>
294294
void bulk_push(I& first, size_t N);
295295

296-
/**
297-
@brief pops out an item from the queue
298-
299-
This method pops an item from the queue.
300-
If the queue is empty, empty_value() is returned.
301-
The elements popped out from the queue follow a last-in-first-out (LIFO) order.
302-
303-
@code{.cpp}
304-
tf::UnboundedWSQ<int> wsq(10);
305-
wsq.push(1);
306-
wsq.push(2);
307-
wsq.push(3);
308-
assert(wsq.pop().value() = 3);
309-
assert(wsq.pop().value() = 2);
310-
assert(wsq.pop().value() = 1);
311-
assert(wsq.pop() == std::nullopt);
312-
@endcode
313-
314-
Only the owner thread can pop out an item from the queue.
315-
*/
316-
value_type pop();
317-
318296
/**
319297
@brief steals an item from the queue
320298
@@ -440,46 +418,12 @@ void UnboundedWSQ<T>::bulk_push(I& first, size_t N) {
440418
_bottom.store(b, std::memory_order_release);
441419
}
442420

443-
// Function: pop
444-
template <typename T>
445-
typename UnboundedWSQ<T>::value_type
446-
UnboundedWSQ<T>::pop() {
447-
448-
int64_t b = _bottom.load(std::memory_order_relaxed) - 1;
449-
Array* a = _array.load(std::memory_order_relaxed);
450-
_bottom.store(b, std::memory_order_relaxed);
451-
std::atomic_thread_fence(std::memory_order_seq_cst);
452-
int64_t t = _top.load(std::memory_order_relaxed);
453-
454-
//T item {nullptr};
455-
auto item = empty_value();
456-
457-
if(t <= b) {
458-
item = a->pop(b);
459-
if(t == b) {
460-
// the last item just got stolen
461-
if(!_top.compare_exchange_strong(t, t+1, std::memory_order_seq_cst,
462-
std::memory_order_relaxed)) {
463-
//item = nullptr;
464-
item = empty_value();
465-
}
466-
_bottom.store(b + 1, std::memory_order_relaxed);
467-
}
468-
}
469-
else {
470-
_bottom.store(b + 1, std::memory_order_relaxed);
471-
}
472-
473-
return item;
474-
}
475-
476421
// Function: steal
477422
template <typename T>
478423
typename UnboundedWSQ<T>::value_type
479424
UnboundedWSQ<T>::steal() {
480425

481-
int64_t t = _top.load(std::memory_order_acquire);
482-
std::atomic_thread_fence(std::memory_order_seq_cst);
426+
int64_t t = _top.load(std::memory_order_relaxed);
483427
int64_t b = _bottom.load(std::memory_order_acquire);
484428

485429
//T item {nullptr};
@@ -489,7 +433,7 @@ UnboundedWSQ<T>::steal() {
489433
Array* a = _array.load(std::memory_order_consume);
490434
item = a->pop(t);
491435
if(!_top.compare_exchange_strong(t, t+1,
492-
std::memory_order_seq_cst,
436+
std::memory_order_acq_rel,
493437
std::memory_order_relaxed)) {
494438
//return nullptr;
495439
return empty_value();
@@ -833,8 +777,8 @@ BoundedWSQ<T, LogSize>::pop() {
833777
item = _buffer[b & BufferMask].load(std::memory_order_relaxed);
834778
if(t == b) {
835779
// the last item just got stolen
836-
if(!_top.compare_exchange_strong(t, t+1,
837-
std::memory_order_seq_cst,
780+
if(!_top.compare_exchange_strong(t, t+1,
781+
std::memory_order_acq_rel,
838782
std::memory_order_relaxed)) {
839783
//item = nullptr;
840784
item = empty_value();
@@ -853,7 +797,7 @@ BoundedWSQ<T, LogSize>::pop() {
853797
template <typename T, size_t LogSize>
854798
typename BoundedWSQ<T, LogSize>::value_type
855799
BoundedWSQ<T, LogSize>::steal() {
856-
int64_t t = _top.load(std::memory_order_acquire);
800+
int64_t t = _top.load(std::memory_order_relaxed);
857801
std::atomic_thread_fence(std::memory_order_seq_cst);
858802
int64_t b = _bottom.load(std::memory_order_acquire);
859803

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL