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 <atomic> | ||||||||||||
#include <condition_variable> | ||||||||||||
#include <functional> | ||||||||||||
#include <mutex> | ||||||||||||
#include <type_traits> | ||||||||||||
template<typename T> | ||||||||||||
Stan: #include <memory> | ||||||||||||
class Future; | ||||||||||||
/** | ||||||||||||
* Equivalent to std::packaged_task. | ||||||||||||
* Like packaged_task, this holds a function acting as a promise. | ||||||||||||
* Unlike packaged_task, this can be cancelled. | ||||||||||||
* It also can be created from a Future (so this can be untemplated, @see Future). | ||||||||||||
* which is convenient to store it in a queue (typically in the ThreadPool::Pool queue). | ||||||||||||
* PackagedTask is blocking if the wrapped function has started processing | ||||||||||||
* when it is destroyed, non-blocking otherwise. | ||||||||||||
*/ | ||||||||||||
class PackagedTask | ||||||||||||
{ | ||||||||||||
template<typename T> | ||||||||||||
friend class Future; | ||||||||||||
protected: | ||||||||||||
/** | ||||||||||||
* Status and SharedState are shared with Future, but it's more convenient header-wise to define them here. | ||||||||||||
*/ | ||||||||||||
enum Status | ||||||||||||
{ | ||||||||||||
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. | ||||||||||||
PENDING, | ||||||||||||
STARTED, | ||||||||||||
DONE | ||||||||||||
}; | ||||||||||||
/** | ||||||||||||
* Shared state between Future and PackagedTask. | ||||||||||||
* Equivalent to what the c++ standard refers to as "shared state" between an std::future, std::promise and std::packaged_task. | ||||||||||||
*/ | ||||||||||||
class SharedState | ||||||||||||
{ | ||||||||||||
public: | ||||||||||||
void Wait() | ||||||||||||
{ | ||||||||||||
// Fast path: we're already done. | ||||||||||||
if (m_Status == DONE) | ||||||||||||
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 m_Status == DONE; }); | ||||||||||||
} | ||||||||||||
/** | ||||||||||||
* Mark the task as done. | ||||||||||||
* @return true if the task was indeed cancelled, false if Cancel() had to wait on it to end or it was already done/cancelled. | ||||||||||||
*/ | ||||||||||||
bool Cancel() | ||||||||||||
{ | ||||||||||||
Status expected = PENDING; | ||||||||||||
// If we're pending, try atomically setting to done. | ||||||||||||
if (m_Status.compare_exchange_strong(expected, DONE)) | ||||||||||||
return true; | ||||||||||||
// That failed - we'll need to wait until we're done. | ||||||||||||
Wait(); | ||||||||||||
return false; | ||||||||||||
} | ||||||||||||
std::atomic<Status> m_Status = PENDING; | ||||||||||||
std::mutex m_Mutex; | ||||||||||||
std::condition_variable m_ConditionVariable; | ||||||||||||
}; | ||||||||||||
public: | ||||||||||||
/** | ||||||||||||
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. | ||||||||||||
* Standalone constructor. Wraps the function. | ||||||||||||
*/ | ||||||||||||
PackagedTask(std::function<void()>&& func) | ||||||||||||
{ | ||||||||||||
m_SharedState = std::make_shared<SharedState>(); | ||||||||||||
m_Func = func; | ||||||||||||
} | ||||||||||||
/** | ||||||||||||
* Constructor from an existing future - @a func will | ||||||||||||
* set the value of the future. | ||||||||||||
*/ | ||||||||||||
Not Done Inline ActionsWait for? vladislavbelov: Wait for? | ||||||||||||
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. | ||||||||||||
Not Done Inline ActionsI mean the name could be more detailed. vladislavbelov: I mean the name could be more detailed. | ||||||||||||
template<typename T> | ||||||||||||
PackagedTask(const Future<T>& future, std::function<void()>&& func) | ||||||||||||
{ | ||||||||||||
m_SharedState = future.m_SharedState; | ||||||||||||
m_Func = func; | ||||||||||||
} | ||||||||||||
PackagedTask(PackagedTask&&) = default; | ||||||||||||
PackagedTask(const PackagedTask&) = delete; | ||||||||||||
~PackagedTask() | ||||||||||||
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 | ||||||||||||
{ | ||||||||||||
// Wait on started task completion, but not on pending ones (auto-cancelled). | ||||||||||||
Not Done Inline ActionsThe comment isn't more accurate: "as cancelled" or nothing? Polakrity: The comment isn't more accurate: `"as cancelled"` or nothing? | ||||||||||||
if (m_SharedState) | ||||||||||||
m_SharedState->Cancel(); | ||||||||||||
} | ||||||||||||
/** | ||||||||||||
* Start the task - if it was cancelled, do nothing. | ||||||||||||
* (this also prevents starting a task twice). | ||||||||||||
*/ | ||||||||||||
void operator()() | ||||||||||||
{ | ||||||||||||
PackagedTask::Status expected = PENDING; | ||||||||||||
if (m_SharedState->m_Status.compare_exchange_strong(expected, PackagedTask::STARTED)) | ||||||||||||
{ | ||||||||||||
m_Func(); | ||||||||||||
// 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. | ||||||||||||
Not Done Inline Actionsearly return? Stan: early return? | ||||||||||||
// This requires locking the mutex (@see Wait). | ||||||||||||
{ | ||||||||||||
std::unique_lock<std::mutex> lock(m_SharedState->m_Mutex); | ||||||||||||
m_SharedState->m_Status = DONE; | ||||||||||||
} | ||||||||||||
m_SharedState->m_ConditionVariable.notify_all(); | ||||||||||||
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… | ||||||||||||
} | ||||||||||||
} | ||||||||||||
protected: | ||||||||||||
std::function<void()> m_Func; | ||||||||||||
std::shared_ptr<SharedState> m_SharedState; | ||||||||||||
}; | ||||||||||||
/** | ||||||||||||
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. | ||||||||||||
* ThreadPool equivalent of std::future. | ||||||||||||
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. | ||||||||||||
* 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. | ||||||||||||
* | ||||||||||||
* Note that currently Future auto-cancels the wrapped task on destruction. | ||||||||||||
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… | ||||||||||||
* TODO: | ||||||||||||
* - Make the above behaviour optional. | ||||||||||||
* - Handle exceptions. | ||||||||||||
*/ | ||||||||||||
template<typename Ret> | ||||||||||||
class Future | ||||||||||||
{ | ||||||||||||
friend class PackagedTask; | ||||||||||||
static constexpr bool VoidReturn = std::is_same_v<Ret, void>; | ||||||||||||
public: | ||||||||||||
Future() {} | ||||||||||||
Future(const Future&) = delete; | ||||||||||||
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… | ||||||||||||
Future(Future&& o) = default; | ||||||||||||
~Future() | ||||||||||||
{ | ||||||||||||
// Since the future holds the result, | ||||||||||||
// we need to make sure the function doesn't outlive it | ||||||||||||
// in a non-cancelled state anyways. | ||||||||||||
Cancel(); | ||||||||||||
} | ||||||||||||
Future& operator=(Future&& o) | ||||||||||||
{ | ||||||||||||
Cancel(); | ||||||||||||
m_Result = std::move(o.m_Result); | ||||||||||||
m_SharedState = std::move(o.m_SharedState); | ||||||||||||
return *this; | ||||||||||||
} | ||||||||||||
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. | ||||||||||||
/** | ||||||||||||
* Make the future wait for the result of @a func. | ||||||||||||
* @return a (cancellable) PackagedTask. | ||||||||||||
* This is the other way around from C++, where std::packaged_task outputs the std::future, | ||||||||||||
* because that lets PackagedTask be untemplated (convenient for storage). | ||||||||||||
*/ | ||||||||||||
template<typename T> | ||||||||||||
PackagedTask Wrap(T&& func) | ||||||||||||
{ | ||||||||||||
static_assert(std::is_convertible_v<std::invoke_result_t<T>, Ret>, "The return type of the wrapped function cannot be converted to the type of the Future."); | ||||||||||||
m_SharedState = std::make_shared<PackagedTask::SharedState>(); | ||||||||||||
if constexpr (VoidReturn) | ||||||||||||
return PackagedTask(*this, std::move(func)); | ||||||||||||
else | ||||||||||||
{ | ||||||||||||
// Allocate the memory space for the result (via the bytes member). | ||||||||||||
m_Result = std::make_unique<Result>(); | ||||||||||||
return PackagedTask(*this, [resultPtr = &m_Result->m_Result, func=std::move(func)]() { | ||||||||||||
// This is safe - the function passed to PackagedTask | ||||||||||||
// is not executed if the task was cancelled, | ||||||||||||
// and Future cancels the task when it is destroyed, | ||||||||||||
// so m_Result will exist at this point. | ||||||||||||
// To avoid UB, explicitly placement-new the value. | ||||||||||||
new (resultPtr) Ret{func()}; | ||||||||||||
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. | ||||||||||||
}); | ||||||||||||
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. | ||||||||||||
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… | ||||||||||||
} | ||||||||||||
} | ||||||||||||
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."; | ||||||||||||
} | ||||||||||||
}; | ||||||||||||
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>… | ||||||||||||
Ret Get() | ||||||||||||
{ | ||||||||||||
Wait(); | ||||||||||||
if constexpr (VoidReturn) | ||||||||||||
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; | ||||||||||||
else | ||||||||||||
{ | ||||||||||||
if (!m_Result) | ||||||||||||
{ | ||||||||||||
// We were never wrapped/cancelled, throw. | ||||||||||||
throw BadFutureAccess(); | ||||||||||||
} | ||||||||||||
return m_Result->m_Result; | ||||||||||||
} | ||||||||||||
} | ||||||||||||
bool Valid() const | ||||||||||||
{ | ||||||||||||
Not Done Inline Actions
Stan: | ||||||||||||
return !!m_SharedState; | ||||||||||||
} | ||||||||||||
void Wait() | ||||||||||||
{ | ||||||||||||
if (Valid()) | ||||||||||||
m_SharedState->Wait(); | ||||||||||||
} | ||||||||||||
void Cancel() | ||||||||||||
{ | ||||||||||||
if (Valid() && m_SharedState->Cancel()) | ||||||||||||
if constexpr (!VoidReturn) | ||||||||||||
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. | ||||||||||||
// If we've managed to cancel the task, we can delete the result storage. | ||||||||||||
// This acts as the boolean to know, in DONE state, if we actually ran or were cancelled. | ||||||||||||
m_Result.reset(); | ||||||||||||
} | ||||||||||||
protected: | ||||||||||||
std::shared_ptr<PackagedTask::SharedState> m_SharedState; | ||||||||||||
Not Done Inline ActionsDon't need the else since you return? Stan: Don't need the else since you return? | ||||||||||||
struct Empty {}; | ||||||||||||
union Result | ||||||||||||
{ | ||||||||||||
std::aligned_storage_t<sizeof(Ret), alignof(Ret)> m_Bytes; | ||||||||||||
Ret m_Result; | ||||||||||||
Result() : m_Bytes() {}; | ||||||||||||
}; | ||||||||||||
// TODO C++20: [[no_unique_address]] this for a minor memory optimisation. | ||||||||||||
// We could use std::optional, except that the value needs a stable address | ||||||||||||
// or the wrapped function won't know where to write, | ||||||||||||
// so m_Result can't be moved, and the Future ought be movable | ||||||||||||
// (or using it becomes un-necessarily annoying). | ||||||||||||
Not Done Inline ActionsCould call Valid() not sure if that has perf consideration Stan: Could call Valid() not sure if that has perf consideration | ||||||||||||
// And we _could_ just use unique_ptr<Ret>, but then Ret needs to be | ||||||||||||
// default constructible, which is also annoying. | ||||||||||||
std::conditional_t<VoidReturn, Empty, std::unique_ptr<Result>> m_Result; | ||||||||||||
}; | ||||||||||||
#endif // INCLUDED_FUTURE | ||||||||||||
Not Done Inline ActionsIn the worst case you check three times for Valid() Stan: In the worst case you check three times for Valid() | ||||||||||||
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>