| 1 | //===----------------------------------------------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | |
| 9 | #ifndef _LIBCPP___PSTL_BACKENDS_STATPART_DECOUPLED_LOOKBACK_H |
| 10 | #define _LIBCPP___PSTL_BACKENDS_STATPART_DECOUPLED_LOOKBACK_H |
| 11 | |
| 12 | #include <__assert> |
| 13 | #include <__atomic/atomic.h> |
| 14 | #include <__atomic/atomic_sync.h> |
| 15 | #include <__atomic/memory_order.h> |
| 16 | #include <__config> |
| 17 | #include <__cstddef/size_t.h> |
| 18 | #include <__memory/addressof.h> |
| 19 | #include <__memory/construct_at.h> |
| 20 | #include <__new/global_new_delete.h> |
| 21 | #include <__new/nothrow_t.h> |
| 22 | #include <__optional/nullopt_t.h> |
| 23 | #include <__optional/optional.h> |
| 24 | #include <__utility/exchange.h> |
| 25 | #include <__utility/forward.h> |
| 26 | #include <__utility/move.h> |
| 27 | |
| 28 | #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) |
| 29 | # pragma GCC system_header |
| 30 | #endif |
| 31 | |
| 32 | _LIBCPP_PUSH_MACROS |
| 33 | #include <__undef_macros> |
| 34 | |
| 35 | #if _LIBCPP_STD_VER >= 17 |
| 36 | |
| 37 | _LIBCPP_BEGIN_NAMESPACE_STD |
| 38 | namespace __pstl { |
| 39 | |
| 40 | namespace __statpart { |
| 41 | |
| 42 | // Based on the paper "Single-pass Parallel Prefix Scan with Decoupled Look-back" (Merrill, Garland, 2016). |
| 43 | |
| 44 | inline constexpr unsigned char __decoupled_lookback_status_invalid = 0; |
| 45 | inline constexpr unsigned char __decoupled_lookback_status_aggregate_available = 1 << 0; |
| 46 | inline constexpr unsigned char __decoupled_lookback_status_prefix_available = 1 << 1; |
| 47 | |
| 48 | // __decoupled_lookback_partition contains 2 values of _Tp (local aggregate and inclusive prefix) and a status flag. |
| 49 | // The values can be initialized by a thread working on this partition by calling __construct_aggregate or |
| 50 | // __construct_inclusive_prefix. These functions implicitly update the status flag and notify any thread potentially |
| 51 | // waiting on it. |
| 52 | // Other threads reaching this partition via a lookback should use __acquire_available_status() to wait until either of |
| 53 | // the two values is available. Depending on the status flag, the constructed values can be accessed via __aggregate() |
| 54 | // and __inclusive_prefix(). |
| 55 | template <typename _Tp> |
| 56 | struct _LIBCPP_HIDE_FROM_ABI __decoupled_lookback_partition { |
| 57 | _LIBCPP_HIDE_FROM_ABI __decoupled_lookback_partition() {} |
| 58 | __decoupled_lookback_partition(const __decoupled_lookback_partition&) = delete; |
| 59 | __decoupled_lookback_partition& operator=(const __decoupled_lookback_partition&) = delete; |
| 60 | |
| 61 | // Destructor: destroy the aggregate and inclusive prefix if they have been constructed. |
| 62 | _LIBCPP_HIDE_FROM_ABI ~__decoupled_lookback_partition() { |
| 63 | unsigned char __flag = __status_flag_.load(m: std::memory_order_relaxed); |
| 64 | if (__flag & __decoupled_lookback_status_aggregate_available) { |
| 65 | __aggregate_.~_Tp(); |
| 66 | } |
| 67 | if (__flag & __decoupled_lookback_status_prefix_available) { |
| 68 | __inclusive_prefix_.~_Tp(); |
| 69 | } |
| 70 | } |
| 71 | |
| 72 | // Acquire the current status of the partition. |
| 73 | // If no value is published yet, wait until one becomes available. |
| 74 | _LIBCPP_HIDE_FROM_ABI unsigned char __acquire_available_status() { |
| 75 | unsigned char __current_status = __status_flag_.load(m: std::memory_order_acquire); |
| 76 | if (__current_status != __decoupled_lookback_status_invalid) |
| 77 | return __current_status; |
| 78 | std::__atomic_wait(a&: __status_flag_, val: __decoupled_lookback_status_invalid, order: std::memory_order_acquire); |
| 79 | return __status_flag_.load(m: std::memory_order_acquire); |
| 80 | } |
| 81 | |
| 82 | // Construct the aggregate value of the partition and publish this change. |
| 83 | template <class... _Args> |
| 84 | _LIBCPP_HIDE_FROM_ABI void __construct_aggregate(_Args&&... __args) { |
| 85 | _LIBCPP_ASSERT_INTERNAL((__status_flag_.load() & __decoupled_lookback_status_aggregate_available) == 0, |
| 86 | "__decoupled_lookback_status_aggregate_available flag must not be set" ); |
| 87 | std::__construct_at(std::addressof(__aggregate_), std::forward<_Args>(__args)...); |
| 88 | __status_flag_.fetch_or(op: __decoupled_lookback_status_aggregate_available, m: std::memory_order_release); |
| 89 | std::__atomic_notify_all(a: __status_flag_); |
| 90 | } |
| 91 | |
| 92 | // Access the aggregate value of the partition. |
| 93 | // Precondition: __acquire_available_status() & __decoupled_lookback_status_aggregate_available |
| 94 | _LIBCPP_HIDE_FROM_ABI const _Tp& __aggregate() const { |
| 95 | _LIBCPP_ASSERT_INTERNAL((__status_flag_.load() & __decoupled_lookback_status_aggregate_available) != 0, |
| 96 | "__decoupled_lookback_status_aggregate_available flag must be set" ); |
| 97 | return __aggregate_; |
| 98 | } |
| 99 | |
| 100 | // Construct the inclusive prefix of the partition and publish this change. |
| 101 | template <class... _Args> |
| 102 | _LIBCPP_HIDE_FROM_ABI void __construct_inclusive_prefix(_Args&&... __args) { |
| 103 | _LIBCPP_ASSERT_INTERNAL((__status_flag_.load() & __decoupled_lookback_status_prefix_available) == 0, |
| 104 | "__decoupled_lookback_status_prefix_available flag must not be set" ); |
| 105 | std::__construct_at(std::addressof(__inclusive_prefix_), std::forward<_Args>(__args)...); |
| 106 | __status_flag_.fetch_or(op: __decoupled_lookback_status_prefix_available, m: std::memory_order_release); |
| 107 | std::__atomic_notify_all(a: __status_flag_); |
| 108 | } |
| 109 | |
| 110 | // Access the inclusive prefix of the partition. |
| 111 | // Precondition: __acquire_available_status() & __decoupled_lookback_status_prefix_available |
| 112 | _LIBCPP_HIDE_FROM_ABI const _Tp& __inclusive_prefix() const { |
| 113 | _LIBCPP_ASSERT_INTERNAL((__status_flag_.load() & __decoupled_lookback_status_prefix_available) != 0, |
| 114 | "__decoupled_lookback_status_prefix_available flag must be set" ); |
| 115 | return __inclusive_prefix_; |
| 116 | } |
| 117 | |
| 118 | private: |
| 119 | // Storage for the aggregate reduced value of the partition. |
| 120 | union { |
| 121 | _Tp __aggregate_; |
| 122 | }; |
| 123 | |
| 124 | // Storage for the inclusive prefix of the partition. |
| 125 | union { |
| 126 | _Tp __inclusive_prefix_; |
| 127 | }; |
| 128 | |
| 129 | // Atomic/waitable flag indicating the status of the partition. |
| 130 | std::atomic<unsigned char> __status_flag_{__decoupled_lookback_status_invalid}; |
| 131 | |
| 132 | // NB! Currently the layout of __decoupled_lookback_partition allows for false sharing to occur. |
| 133 | }; |
| 134 | |
| 135 | // __decoupled_lookback holds a dynamically-allocated array of __decoupled_lookback_partition. |
| 136 | // Created by __make_decoupled_lookback(). |
| 137 | template <typename _Tp> |
| 138 | class _LIBCPP_HIDE_FROM_ABI __decoupled_lookback { |
| 139 | public: |
| 140 | _LIBCPP_HIDE_FROM_ABI __decoupled_lookback(__decoupled_lookback&& __other) noexcept |
| 141 | : __partitions_(std::exchange(__other.__partitions_, nullptr)), |
| 142 | __partitions_count_(std::exchange(obj&: __other.__partitions_count_, new_value: 0)) {} |
| 143 | |
| 144 | __decoupled_lookback(const __decoupled_lookback&) = delete; |
| 145 | __decoupled_lookback& operator=(const __decoupled_lookback&) = delete; |
| 146 | __decoupled_lookback& operator=(__decoupled_lookback&&) = delete; |
| 147 | |
| 148 | _LIBCPP_HIDE_FROM_ABI ~__decoupled_lookback() { delete[] __partitions_; } |
| 149 | |
| 150 | // Returns the number of partitions in the lookback. |
| 151 | _LIBCPP_HIDE_FROM_ABI size_t __size() const { return __partitions_count_; } |
| 152 | |
| 153 | // Provides a pointer to the first partition in a contiguous storage. |
| 154 | _LIBCPP_HIDE_FROM_ABI __decoupled_lookback_partition<_Tp>* __partitions() const { return __partitions_; } |
| 155 | |
| 156 | // Provides a reference to the specified partition. |
| 157 | _LIBCPP_HIDE_FROM_ABI __decoupled_lookback_partition<_Tp>& __partition(size_t __index) const { |
| 158 | _LIBCPP_ASSERT_INTERNAL(__index < __partitions_count_, "__index must be less than __partitions_count_" ); |
| 159 | return __partitions_[__index]; |
| 160 | } |
| 161 | |
| 162 | private: |
| 163 | _LIBCPP_HIDE_FROM_ABI __decoupled_lookback() = default; |
| 164 | |
| 165 | __decoupled_lookback_partition<_Tp>* __partitions_ = nullptr; |
| 166 | size_t __partitions_count_ = 0; |
| 167 | |
| 168 | template <class _Up> |
| 169 | friend _LIBCPP_HIDE_FROM_ABI optional<__decoupled_lookback<_Up>> __make_decoupled_lookback(size_t) noexcept; |
| 170 | }; |
| 171 | |
| 172 | // Creates a lookback partition with the specified capacity. |
| 173 | // In case memory allocation fails, returns std::nullopt. |
| 174 | template <typename _Tp> |
| 175 | _LIBCPP_HIDE_FROM_ABI optional<__decoupled_lookback<_Tp>> __make_decoupled_lookback(size_t __size) noexcept { |
| 176 | __decoupled_lookback<_Tp> __lookback; |
| 177 | __lookback.__partitions_ = new (std::nothrow) __decoupled_lookback_partition<_Tp>[__size]; |
| 178 | if (!__lookback.__partitions_) |
| 179 | return nullopt; |
| 180 | __lookback.__partitions_count_ = __size; |
| 181 | return __lookback; |
| 182 | } |
| 183 | |
| 184 | // Calculate an inclusive prefix of a given partition that currently has only an aggregate. |
| 185 | // Performs reductions of aggregate values until it arrives at a partition with an available prefix. |
| 186 | // Precondition: __partition->__acquire_available_status() == __decoupled_lookback_status_aggregate_available. |
| 187 | template <typename _Tp, class _BinaryOperation> |
| 188 | _LIBCPP_HIDE_FROM_ABI _Tp |
| 189 | __calculate_inclusive_prefix_of_partition(__decoupled_lookback_partition<_Tp>* __partition, _BinaryOperation __reduce) { |
| 190 | // Start at the given partition. |
| 191 | _Tp __prefix = __partition->__aggregate(); |
| 192 | while (true) { |
| 193 | // Move to the previous partition and check its status. |
| 194 | --__partition; |
| 195 | unsigned char __status = __partition->__acquire_available_status(); |
| 196 | if (__status & __decoupled_lookback_status_prefix_available) { |
| 197 | // Found a partition with an available prefix - can perform a final reduction and terminate. |
| 198 | return __reduce(__partition->__inclusive_prefix(), std::move(__prefix)); |
| 199 | } |
| 200 | // Reduce with another aggregate and continue moving left. |
| 201 | __prefix = __reduce(__partition->__aggregate(), std::move(__prefix)); |
| 202 | } |
| 203 | } |
| 204 | |
| 205 | } // namespace __statpart |
| 206 | |
| 207 | } // namespace __pstl |
| 208 | _LIBCPP_END_NAMESPACE_STD |
| 209 | |
| 210 | #endif // _LIBCPP_STD_VER >= 17 |
| 211 | |
| 212 | _LIBCPP_POP_MACROS |
| 213 | |
| 214 | #endif // _LIBCPP___PSTL_BACKENDS_STATPART_DECOUPLED_LOOKBACK_H |
| 215 | |