xenium
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 
17 namespace xenium {
37 template <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; }
58 private:
59  container items;
60  std::atomic<std::size_t> bottom;
61  std::atomic<std::size_t> top;
62 };
63 
64 template <class T, class... Policies>
66  bottom(),
67  top()
68 {}
69 
70 template <class T, class... Policies>
71 bool 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 
92 template <class T, class... Policies>
93 bool 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 
131 template <class T, class... Policies>
132 bool 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
xenium::chase_work_stealing_deque
A lock-free work stealing deque.
Definition: chase_work_stealing_deque.hpp:38
xenium::policy::capacity
Policy to configure the capacity of various containers.
Definition: policy.hpp:61