xenium
Loading...
Searching...
No Matches
chase_work_stealing_deque.hpp
1//
2// Copyright (c) 2018-2020 Manuel Pöter.
3// Licensed under the MIT License. See LICENSE file in the project root for full license information.
4//
5
6#ifndef XENIUM_CHASE_WORK_STEALING_DEQUE_HPP
7#define XENIUM_CHASE_WORK_STEALING_DEQUE_HPP
8
9#include <xenium/parameter.hpp>
10#include <xenium/policy.hpp>
11#include <xenium/detail/fixed_size_circular_array.hpp>
12#include <xenium/detail/growing_circular_array.hpp>
13
14#include <atomic>
15#include <cassert>
16
17namespace xenium {
37template <class T, class... Policies>
39 using value_type = T*;
40 static constexpr std::size_t capacity = parameter::value_param_t<std::size_t, policy::capacity, 128, Policies...>::value;
41 using container = parameter::type_param_t<policy::container, detail::growing_circular_array<T, capacity>, Policies...>;
42
44
47
48 chase_work_stealing_deque& operator=(const chase_work_stealing_deque&) = delete;
50
51 bool try_push(value_type item);
52 [[nodiscard]] bool try_pop(value_type &result);
53 [[nodiscard]] bool try_steal(value_type &result);
54
55 std::size_t size() {
56 auto t = top.load(std::memory_order_relaxed);
57 return bottom.load(std::memory_order_relaxed) - t; }
58private:
59 container items;
60 std::atomic<std::size_t> bottom;
61 std::atomic<std::size_t> top;
62};
63
64template <class T, class... Policies>
66 bottom(),
67 top()
68{}
69
70template <class T, class... Policies>
71bool chase_work_stealing_deque<T, Policies...>::try_push(value_type item) {
72 auto b = bottom.load(std::memory_order_relaxed);
73 auto t = top.load(std::memory_order_relaxed);
74 auto size = b - t;
75 if (size >= items.capacity()) {
76 if (items.can_grow()) {
77 items.grow(b, t);
78 assert(size < items.capacity());
79 // TODO - need to update top??
80 }
81 else
82 return false;
83 }
84
85 items.put(b, item, std::memory_order_relaxed);
86
87 // (1) - this release-store synchronizes-with the seq-cst-load (4)
88 bottom.store(b + 1, std::memory_order_release);
89 return true;
90}
91
92template <class T, class... Policies>
93bool chase_work_stealing_deque<T, Policies...>::try_pop(value_type &result) {
94 auto b = bottom.load(std::memory_order_relaxed);
95 auto t = top.load(std::memory_order_relaxed);
96 if (b == t)
97 return false;
98
99 // We have to use seq-cst order for operations on bottom as well as top to ensure
100 // that when two threads compete for the last item either one sees the updated bottom
101 // (pop wins), or one sees the updated top (steal wins).
102
103 --b;
104 // (2) - this seq-cst-store enforces a total order with the seq-cst-load (4)
105 bottom.store(b, std::memory_order_seq_cst);
106
107 auto item = items.get(b, std::memory_order_relaxed);
108 // (3) - this seq-cst-load enforces a total order with the seq-cst-CAS (5)
109 t = top.load(std::memory_order_seq_cst);
110 if (b > t) {
111 result = item;
112 return true;
113 }
114
115 if (b == t) {
116 if (top.compare_exchange_strong(t, t + 1, std::memory_order_relaxed)) {
117 bottom.store(t + 1, std::memory_order_relaxed);
118 result = item;
119 return true;
120 } else {
121 bottom.store(t, std::memory_order_relaxed);
122 return false;
123 }
124 }
125
126 assert(b == t - 1);
127 bottom.store(t, std::memory_order_relaxed);
128 return false;
129}
130
131template <class T, class... Policies>
132bool chase_work_stealing_deque<T, Policies...>::try_steal(value_type &result) {
133 auto t = top.load(std::memory_order_relaxed);
134
135 // (4) - this seq-cst-load enforces a total order with the seq-cst-store (2)
136 // and synchronizes-with the release-store (1)
137 auto b = bottom.load(std::memory_order_seq_cst);
138 auto size = (int)b - (int)t;
139 if (size <= 0)
140 return false;
141
142 auto item = items.get(t, std::memory_order_relaxed);
143 // (5) - this seq-cst-CAS enforces a total order with the seq-cst-load (3)
144 if (top.compare_exchange_strong(t, t + 1, std::memory_order_seq_cst, std::memory_order_relaxed)) {
145 result = item;
146 return true;
147 }
148
149 return false;
150}
151}
152
153#endif
A lock-free work stealing deque.
Definition chase_work_stealing_deque.hpp:38
Policy to configure the capacity of various containers.
Definition policy.hpp:61