Changeset View
Standalone View
source/ps/Future.h
- This file was added.
/* Copyright (C) 2021 Wildfire Games. | ||||||||||||
* This file is part of 0 A.D. | ||||||||||||
* | ||||||||||||
* 0 A.D. is free software: you can redistribute it and/or modify | ||||||||||||
* it under the terms of the GNU General Public License as published by | ||||||||||||
* the Free Software Foundation, either version 2 of the License, or | ||||||||||||
* (at your option) any later version. | ||||||||||||
* | ||||||||||||
* 0 A.D. is distributed in the hope that it will be useful, | ||||||||||||
* but WITHOUT ANY WARRANTY; without even the implied warranty of | ||||||||||||
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||||||||||||
* GNU General Public License for more details. | ||||||||||||
* | ||||||||||||
* You should have received a copy of the GNU General Public License | ||||||||||||
* along with 0 A.D. If not, see <http://www.gnu.org/licenses/>. | ||||||||||||
*/ | ||||||||||||
#ifndef INCLUDED_FUTURE | ||||||||||||
#define INCLUDED_FUTURE | ||||||||||||
#include "ps/FutureForward.h" | ||||||||||||
#include <atomic> | ||||||||||||
#include <condition_variable> | ||||||||||||
#include <functional> | ||||||||||||
#include <mutex> | ||||||||||||
#include <type_traits> | ||||||||||||
Stan: #include <memory> | ||||||||||||
template<typename ResultType> | ||||||||||||
class PackagedTask; | ||||||||||||
namespace FutureSharedStateDetail | ||||||||||||
{ | ||||||||||||
enum class Status | ||||||||||||
{ | ||||||||||||
PENDING, | ||||||||||||
STARTED, | ||||||||||||
DONE, | ||||||||||||
CANCELED | ||||||||||||
}; | ||||||||||||
template<typename ResultType> | ||||||||||||
class SharedStateResult | ||||||||||||
{ | ||||||||||||
public: | ||||||||||||
void ResetResult() | ||||||||||||
{ | ||||||||||||
if (m_HasResult) | ||||||||||||
Not Done Inline Actionsenum class? Stan: enum class? | ||||||||||||
Done Inline Actionsmeh, internal use. wraitii: meh, internal use. | ||||||||||||
Not Done Inline ActionsYour usage of it is a bit inconsistent below. Stan: Your usage of it is a bit inconsistent below. | ||||||||||||
Not Done Inline ActionsIt doesn't make sense to have a shorter name, ResultType is short enough. vladislavbelov: It doesn't make sense to have a shorter name, `ResultType` is short enough. | ||||||||||||
m_Result.m_Result.~ResultType(); | ||||||||||||
m_HasResult = false; | ||||||||||||
} | ||||||||||||
union Result | ||||||||||||
{ | ||||||||||||
std::aligned_storage_t<sizeof(ResultType), alignof(ResultType)> m_Bytes; | ||||||||||||
ResultType m_Result; | ||||||||||||
Result() : m_Bytes() {}; | ||||||||||||
~Result() {}; | ||||||||||||
}; | ||||||||||||
// We don't use Result directly so the result doesn't have to be default constructible. | ||||||||||||
Result m_Result; | ||||||||||||
bool m_HasResult = false; | ||||||||||||
}; | ||||||||||||
// Don't have m_Result for void ReturnType | ||||||||||||
template<> | ||||||||||||
class SharedStateResult<void> | ||||||||||||
{ | ||||||||||||
}; | ||||||||||||
/** | ||||||||||||
* The shared state between futures and packaged state. | ||||||||||||
* Holds all relevant data. | ||||||||||||
*/ | ||||||||||||
template<typename ResultType> | ||||||||||||
class SharedState : public SharedStateResult<ResultType> | ||||||||||||
{ | ||||||||||||
static constexpr bool VoidResult = std::is_same_v<ResultType, void>; | ||||||||||||
public: | ||||||||||||
SharedState(std::function<ResultType()>&& func) : m_Func(func) {} | ||||||||||||
~SharedState() | ||||||||||||
{ | ||||||||||||
// For safety, wait on started task completion, but not on pending ones (auto-cancelled). | ||||||||||||
if (!Cancel()) | ||||||||||||
{ | ||||||||||||
Wait(); | ||||||||||||
Cancel(); | ||||||||||||
} | ||||||||||||
if constexpr (!VoidResult) | ||||||||||||
SharedStateResult<ResultType>::ResetResult(); | ||||||||||||
} | ||||||||||||
Not Done Inline Actionsinline / const? Stan: inline / const? | ||||||||||||
Done Inline Actionscan't / can't because of how compare_exchange_strong is designed. wraitii: can't / can't because of how compare_exchange_strong is designed. | ||||||||||||
SharedState(const SharedState&) = delete; | ||||||||||||
SharedState(SharedState&&) = delete; | ||||||||||||
bool IsDoneOrCanceled() const | ||||||||||||
{ | ||||||||||||
return m_Status == Status::DONE || m_Status == Status::CANCELED; | ||||||||||||
} | ||||||||||||
void Wait() | ||||||||||||
vladislavbelovUnsubmitted Not Done Inline ActionsWait for? vladislavbelov: Wait for? | ||||||||||||
wraitiiAuthorUnsubmitted Done Inline ActionsLike Get, this matches the std::future name, which seemed better. wraitii: Like `Get`, this matches the std::future name, which seemed better. | ||||||||||||
vladislavbelovUnsubmitted Not Done Inline ActionsI mean the name could be more detailed. vladislavbelov: I mean the name could be more detailed. | ||||||||||||
{ | ||||||||||||
// Fast path: we're already done. | ||||||||||||
if (IsDoneOrCanceled()) | ||||||||||||
return; | ||||||||||||
// Slow path: we aren't done when we run the above check. Lock and wait until we are. | ||||||||||||
std::unique_lock<std::mutex> lock(m_Mutex); | ||||||||||||
m_ConditionVariable.wait(lock, [this]() -> bool { return IsDoneOrCanceled(); }); | ||||||||||||
} | ||||||||||||
/** | ||||||||||||
Done Inline ActionsWhy INVALID and not CANCELED? How to differentiate an invalid and canceled future? vladislavbelov: Why `INVALID` and not `CANCELED`? How to differentiate an invalid and canceled future? | ||||||||||||
Done Inline ActionsIt's essentially the same. A Future with a shared state can only end in INVALID state when cancelled manually or the result is extracted. A future without a shared state isn't valid. wraitii: It's essentially the same. A Future with a shared state can only end in INVALID state when… | ||||||||||||
Done Inline ActionsIt's unclear by reading a client code that status == Status::INVALID check for a cancelation. vladislavbelov: It's unclear by reading a client code that `status == Status::INVALID` check for a cancelation. | ||||||||||||
Done Inline ActionsWell, I've switch to CANCELED wraitii: Well, I've switch to CANCELED | ||||||||||||
* If the task is pending, cancel it by marking it as done. | ||||||||||||
* @return true if the task was indeed cancelled, false otherwise (the task is running or already done). | ||||||||||||
Not Done Inline ActionsThe comment isn't more accurate: "as cancelled" or nothing? Polakrity: The comment isn't more accurate: `"as cancelled"` or nothing? | ||||||||||||
*/ | ||||||||||||
bool Cancel() | ||||||||||||
{ | ||||||||||||
Status expected = Status::PENDING; | ||||||||||||
bool cancelled = m_Status.compare_exchange_strong(expected, Status::CANCELED); | ||||||||||||
// If we're done, invalidate, if we're pending, atomically cancel, otherwise fail. | ||||||||||||
if (cancelled || m_Status == Status::DONE) | ||||||||||||
{ | ||||||||||||
if (m_Status == Status::DONE) | ||||||||||||
m_Status = Status::CANCELED; | ||||||||||||
if constexpr (!VoidResult) | ||||||||||||
SharedStateResult<ResultType>::ResetResult(); | ||||||||||||
m_ConditionVariable.notify_all(); | ||||||||||||
return cancelled; | ||||||||||||
} | ||||||||||||
return false; | ||||||||||||
} | ||||||||||||
Not Done Inline Actionsearly return? Stan: early return? | ||||||||||||
/** | ||||||||||||
* Move the result away from the shared state, mark the future invalid. | ||||||||||||
*/ | ||||||||||||
template<typename _ResultType = ResultType> | ||||||||||||
std::enable_if_t<!std::is_same_v<_ResultType, void>, ResultType> GetResult() | ||||||||||||
{ | ||||||||||||
Not Done Inline ActionsCan we avoid this raw creation? Stan: Can we avoid this raw creation? | ||||||||||||
Done Inline ActionsThis is placement new, not raw creation & yes but this makes it possible to return a non-default initialised type, which I want to keep. wraitii: This is placement new, not raw creation & yes but this makes it possible to return a non… | ||||||||||||
// The caller must ensure that this is only called if we have a result. | ||||||||||||
ENSURE(SharedStateResult<ResultType>::m_HasResult); | ||||||||||||
m_Status = Status::CANCELED; | ||||||||||||
SharedStateResult<ResultType>::m_HasResult = false; | ||||||||||||
if constexpr (!VoidResult) | ||||||||||||
return std::move(SharedStateResult<ResultType>::m_Result.m_Result); | ||||||||||||
else | ||||||||||||
return; | ||||||||||||
} | ||||||||||||
Not Done Inline ActionsThis return is expected? Polakrity: This return is expected? | ||||||||||||
Done Inline ActionsMh, no longer necessary in this variant of the code, thanks for noting. wraitii: Mh, no longer necessary in this variant of the code, thanks for noting. | ||||||||||||
Not Done Inline ActionsPENDING can be default vladislavbelov: `PENDING` can be default | ||||||||||||
Done Inline Actions? You mean rename 'PENDING' to 'DEFAULT' ? wraitii: ? You mean rename 'PENDING' to 'DEFAULT' ? | ||||||||||||
Not Done Inline ActionsMmm, I think the comment is outdated. vladislavbelov: Mmm, I think the comment is outdated. | ||||||||||||
std::atomic<Status> m_Status = Status::PENDING; | ||||||||||||
std::mutex m_Mutex; | ||||||||||||
std::condition_variable m_ConditionVariable; | ||||||||||||
std::function<ResultType()> m_Func; | ||||||||||||
Done Inline ActionsIt's not good to have additional members for testing. I don't see a strong to have in SharedState. vladislavbelov: It's not good to have additional members for testing. I don't see a strong to have in… | ||||||||||||
Done Inline ActionsThis isn't here for testing, it's actually where the continuation task is stored. I stored it here because Future doesn't keep a reference to the PackagedTask, but to the shared state, and so storing the continuation in the packagedTask wouldn't work (you wouldn't be able to cancel it). Likewise, storing it in the future wouldn't work, since destroying the future doesn't cancel the tasks (this is debatable - it seems like it can be useful, also sometimes dangerous, dunno). Keeping a link to the parent future in the continued future is also a no-go since that would make the future parametrised on the parent, itself parametrised on the parent etc. I might be missing something, but it just seemed more convenient to store the continuation here. wraitii: This isn't here for testing, it's actually where the continuation task is stored.
I stored it… | ||||||||||||
Not Done Inline ActionsAllocating std::function for each frame might be noticeable for performance. Especially in case of many tasks. vladislavbelov: Allocating `std::function` for each frame might be noticeable for performance. Especially in… | ||||||||||||
Done Inline ActionsI'm not sure what you're referring to? This is a unique_ptr, so there's no allocation unless there is a continuation. wraitii: I'm not sure what you're referring to? This is a unique_ptr, so there's no allocation unless… | ||||||||||||
Not Done Inline ActionsIdeally rendering tasks will be dependent on each other, and all these tasks will be created each frame. So I'd prefer a cheaper solution for dependencies. vladislavbelov: Ideally rendering tasks will be dependent on each other, and all these tasks will be created… | ||||||||||||
}; | ||||||||||||
} // namespace FutureSharedStateDetail | ||||||||||||
/** | ||||||||||||
* Corresponds to std::future. | ||||||||||||
* Unlike std::future, Future can request the cancellation of the task that would produce the result. | ||||||||||||
* This makes it more similar to Java's CancellableTask or C#'s Task. | ||||||||||||
* The name Future was kept over Task so it would be more familiar to C++ users, | ||||||||||||
* but this all should be revised once Concurrency TS wraps up. | ||||||||||||
* | ||||||||||||
* Future is _not_ thread-safe. Call it from a single thread or ensure synchronization externally. | ||||||||||||
Not Done Inline ActionsSpecialization for the void type might make the code more clear. Also there is std::optional which allows to remove useless BadFutureAccess. vladislavbelov: Specialization for the `void` type might make the code more clear. Also there is `std… | ||||||||||||
Done Inline Actionsstd::optional isn't usable since our minimum supported Xcode doesn't have it. That could be remedied, but I didn't do it here. I'm mostly throwing because the C++ standard throws in that case. wraitii: `std::optional` isn't usable since our minimum supported Xcode doesn't have it. That could be… | ||||||||||||
Not Done Inline ActionsI'd like to not have a m_Result name in case of void. You just shouldn't have a way to use/get addres of m_Result for void. vladislavbelov: I'd like to not have a `m_Result` name in case of `void`. You just shouldn't have a way to… | ||||||||||||
* | ||||||||||||
* The destructor is never blocking. The promise may still be running on destruction. | ||||||||||||
* TODO: | ||||||||||||
* - Handle exceptions. | ||||||||||||
*/ | ||||||||||||
template<typename ResultType> | ||||||||||||
class Future | ||||||||||||
{ | ||||||||||||
template<typename T> | ||||||||||||
friend class PackagedTask; | ||||||||||||
static constexpr bool VoidResult = std::is_same_v<ResultType, void>; | ||||||||||||
using Status = FutureSharedStateDetail::Status; | ||||||||||||
using SharedState = FutureSharedStateDetail::SharedState<ResultType>; | ||||||||||||
public: | ||||||||||||
Not Done Inline ActionsSeems a hack or should be implemented properly. vladislavbelov: Seems a hack or should be implemented properly. | ||||||||||||
Done Inline ActionsSeems I don't need this in the current iteration of the diff, so removed. wraitii: Seems I don't need this in the current iteration of the diff, so removed. | ||||||||||||
Future() {}; | ||||||||||||
Future(const Future& o) = delete; | ||||||||||||
Future(Future&&) = default; | ||||||||||||
Future& operator=(Future&&) = default; | ||||||||||||
~Future() {} | ||||||||||||
/** | ||||||||||||
* Make the future wait for the result of @a func. | ||||||||||||
*/ | ||||||||||||
template<typename T> | ||||||||||||
PackagedTask<ResultType> Wrap(T&& func); | ||||||||||||
class BadFutureAccess : public std::exception | ||||||||||||
{ | ||||||||||||
virtual const char* what() const noexcept | ||||||||||||
{ | ||||||||||||
return "Tried to access the result of a future that was never wrapped or a cancelled future."; | ||||||||||||
} | ||||||||||||
}; | ||||||||||||
/** | ||||||||||||
* Move the result out of the future, and invalidate the future. | ||||||||||||
*/ | ||||||||||||
template<typename _ResultType = ResultType> | ||||||||||||
vladislavbelovUnsubmitted Not Done Inline ActionsStarting with _ isn't good even in a non-global scope. vladislavbelov: Starting with `_` isn't good even in a non-global scope. | ||||||||||||
std::enable_if_t<!std::is_same_v<_ResultType, void>, ResultType> Get() | ||||||||||||
vladislavbelovUnsubmitted Not Done Inline ActionsGet doesn't mean that it can wait. And the comment doesn't state that. vladislavbelov: `Get` doesn't mean that it can wait. And the comment doesn't state that. | ||||||||||||
wraitiiAuthorUnsubmitted Done Inline ActionsLike Wait, this matches the std::future name/behaviour, which seemed better. I'll update the comment. wraitii: Like `Wait`, this matches the std::future name/behaviour, which seemed better.
I'll update the… | ||||||||||||
{ | ||||||||||||
if (!m_SharedState) | ||||||||||||
throw BadFutureAccess(); | ||||||||||||
Wait(); | ||||||||||||
if constexpr (VoidResult) | ||||||||||||
return; | ||||||||||||
else | ||||||||||||
{ | ||||||||||||
if (m_SharedState->m_Status == Status::CANCELED) | ||||||||||||
{ | ||||||||||||
// We were cancelled or never wrapped, throw. | ||||||||||||
throw BadFutureAccess(); | ||||||||||||
Not Done Inline ActionsMaybe ESNURE, it will be more readable. vladislavbelov: Maybe `ESNURE`, it will be more readable. | ||||||||||||
Not Done Inline ActionsAlso it will give a proper callstack. Stan: Also it will give a proper callstack. | ||||||||||||
Done Inline ActionsBut it can't be tested... wraitii: But it can't be tested... | ||||||||||||
Done Inline ActionsRight l97 of tests TS_ASSERT_THROWS(future.Get(), const Future<NonDef>::BadFutureAccess&); Stan: Right l97 of tests
```
TS_ASSERT_THROWS(future.Get(), const Future<NonDef>… | ||||||||||||
} | ||||||||||||
// This mark the state invalid - can't call Get again. | ||||||||||||
return m_SharedState->GetResult(); | ||||||||||||
} | ||||||||||||
Not Done Inline ActionsThe function shouldn't present at all for void. vladislavbelov: The function shouldn't present at all for `void`. | ||||||||||||
Done Inline ActionsIt is present in the C++ experimental one from what I can tell, and I don't think it really harms much. wraitii: It is present in the C++ experimental one from what I can tell, and I don't think it really… | ||||||||||||
Not Done Inline ActionsI think we need to avoid it. Because else IDE autocompletion will suggest to use Get and a compiler might generate an additional code for that. vladislavbelov: I think we need to avoid it. Because else IDE autocompletion will suggest to use Get and a… | ||||||||||||
} | ||||||||||||
/** | ||||||||||||
* @return true if the shared state is valid and has a result (i.e. Get can be called). | ||||||||||||
*/ | ||||||||||||
bool IsReady() const | ||||||||||||
{ | ||||||||||||
return !!m_SharedState && m_SharedState->m_Status == Status::DONE; | ||||||||||||
} | ||||||||||||
/** | ||||||||||||
* @return true if the future has a shared state and it's not been invalidated, ie. pending, started or done. | ||||||||||||
*/ | ||||||||||||
bool Valid() const | ||||||||||||
Not Done Inline Actions
Stan: | ||||||||||||
{ | ||||||||||||
return !!m_SharedState && m_SharedState->m_Status != Status::CANCELED; | ||||||||||||
} | ||||||||||||
void Wait() | ||||||||||||
{ | ||||||||||||
if (Valid()) | ||||||||||||
m_SharedState->Wait(); | ||||||||||||
} | ||||||||||||
/** | ||||||||||||
* Cancels the task, waiting if the task is currently started. | ||||||||||||
* Use this function over Cancel() if you need to ensure determinism (i.e. in the simulation). | ||||||||||||
Not Done Inline ActionsConsider m_SharedState->Wait(); that you have already checked Valid() in this function. Polakrity: Consider `m_SharedState->Wait();` that you have already checked `Valid()` in this function.
| ||||||||||||
Not Done Inline ActionsSeems to work. Stan: Seems to work. | ||||||||||||
* @see Cancel. | ||||||||||||
*/ | ||||||||||||
void CancelOrWait() | ||||||||||||
{ | ||||||||||||
if (!Valid()) | ||||||||||||
return; | ||||||||||||
if (!m_SharedState->Cancel()) | ||||||||||||
Not Done Inline ActionsDon't need the else since you return? Stan: Don't need the else since you return? | ||||||||||||
Wait(); | ||||||||||||
m_SharedState.reset(); | ||||||||||||
} | ||||||||||||
/** | ||||||||||||
* Cancels the task (without waiting). | ||||||||||||
* The result is always invalid, even if the task had completed before. | ||||||||||||
* Note that this cannot stop started tasks. | ||||||||||||
*/ | ||||||||||||
void Cancel() | ||||||||||||
{ | ||||||||||||
if (m_SharedState) | ||||||||||||
Not Done Inline ActionsCould call Valid() not sure if that has perf consideration Stan: Could call Valid() not sure if that has perf consideration | ||||||||||||
m_SharedState->Cancel(); | ||||||||||||
m_SharedState.reset(); | ||||||||||||
} | ||||||||||||
protected: | ||||||||||||
std::shared_ptr<SharedState> m_SharedState; | ||||||||||||
}; | ||||||||||||
/** | ||||||||||||
* Corresponds somewhat to std::packaged_task. | ||||||||||||
* Like packaged_task, this holds a function acting as a promise. | ||||||||||||
* This type is mostly just the shared state and the call operator, | ||||||||||||
* handling the promise & continuation logic. | ||||||||||||
*/ | ||||||||||||
template<typename ResultType> | ||||||||||||
class PackagedTask | ||||||||||||
{ | ||||||||||||
static constexpr bool VoidResult = std::is_same_v<ResultType, void>; | ||||||||||||
public: | ||||||||||||
PackagedTask() = delete; | ||||||||||||
Not Done Inline ActionsIn the worst case you check three times for Valid() Stan: In the worst case you check three times for Valid() | ||||||||||||
PackagedTask(const std::shared_ptr<typename Future<ResultType>::SharedState>& ss) : m_SharedState(ss) {} | ||||||||||||
void operator()() | ||||||||||||
{ | ||||||||||||
typename Future<ResultType>::Status expected = Future<ResultType>::Status::PENDING; | ||||||||||||
if (!m_SharedState->m_Status.compare_exchange_strong(expected, Future<ResultType>::Status::STARTED)) | ||||||||||||
return; | ||||||||||||
if constexpr (VoidResult) | ||||||||||||
m_SharedState->m_Func(); | ||||||||||||
else | ||||||||||||
{ | ||||||||||||
// To avoid UB, explicitly placement-new the value. | ||||||||||||
new (&m_SharedState->m_Result) ResultType{std::move(m_SharedState->m_Func())}; | ||||||||||||
m_SharedState->m_HasResult = true; | ||||||||||||
} | ||||||||||||
// Because we might have threads waiting on us, we need to make sure that they either: | ||||||||||||
// - don't wait on our condition variable | ||||||||||||
// - receive the notification when we're done. | ||||||||||||
// This requires locking the mutex (@see Wait). | ||||||||||||
{ | ||||||||||||
std::lock_guard<std::mutex> lock(m_SharedState->m_Mutex); | ||||||||||||
m_SharedState->m_Status = Future<ResultType>::Status::DONE; | ||||||||||||
} | ||||||||||||
m_SharedState->m_ConditionVariable.notify_all(); | ||||||||||||
// We no longer need the shared state, drop it immediately. | ||||||||||||
m_SharedState.reset(); | ||||||||||||
} | ||||||||||||
void Cancel() | ||||||||||||
{ | ||||||||||||
m_SharedState->Cancel(); | ||||||||||||
m_SharedState.reset(); | ||||||||||||
} | ||||||||||||
protected: | ||||||||||||
std::shared_ptr<typename Future<ResultType>::SharedState> m_SharedState; | ||||||||||||
}; | ||||||||||||
template<typename ResultType> | ||||||||||||
template<typename T> | ||||||||||||
PackagedTask<ResultType> Future<ResultType>::Wrap(T&& func) | ||||||||||||
{ | ||||||||||||
static_assert(std::is_convertible_v<std::invoke_result_t<T>, ResultType>, "The return type of the wrapped function cannot be converted to the type of the Future."); | ||||||||||||
m_SharedState = std::make_shared<SharedState>(std::move(func)); | ||||||||||||
return PackagedTask<ResultType>(m_SharedState); | ||||||||||||
} | ||||||||||||
#endif // INCLUDED_FUTURE | ||||||||||||
Not Done Inline ActionsToo complicated for our tasks. vladislavbelov: Too complicated for our tasks. | ||||||||||||
Done Inline ActionsThis is one of the finer points on which I'd like more information. What would you do instead? Just skip executors entirely and use the task manager directly? With an interface like "PushTask", "PushLowPriorityTask" and passing thread affinity as arguments? wraitii: This is one of the finer points on which I'd like more information.
What would you do instead? | ||||||||||||
Not Done Inline ActionsYes, PushTask is enough. You don't need a special name for a lower task, just an argument. vladislavbelov: Yes, `PushTask` is enough. You don't need a special name for a lower task, just an argument. |
#include <memory>