История изменений
Исправление dissident, (текущая версия) :
у корутин нет шедулера,
Поправь меня, пожалуйста, если я что-то неверно понял.
У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер (в случае если он есть и используется).
При этом fiber’ы могут быть симметричные и несимметричные. В случае несимметричных fiber’ов yield возвращает управление вызвавшему fiber трэду, а в случае симметричных они переключаются между друг другом.
(с) https://stackoverflow.com/a/42042904
Но как в случае симметричных, так и даже несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:
queue<fiber_type> fibers;
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
Или это будет, например, цикл с приоритетами:
struct fiber_type {
int prio;
...
void operator()() { ... }
};
struct greater_fib {
bool operator()(const fiber_type& a, const fiber_type& b) const{
return a.prio > b.prio;
}
};
vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...
// sort by priorities
make_heap(fibers.begin(), fibers.end());
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
// sort by priorities to keep fibers sorted in case any of the executed fiber
// adds something to the heap (not effective, but this is just an example)
make_heap(fibers.begin(), fibers.end());
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:
coroutine_type coroutine
{
int a, b;
// do something async
yield();
}
void function()
{
coroutine_type cor coroutine();
cor.resume();
}
await function();
Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.
В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.
Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).
Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).
Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):
future<data_type f = async([]() {
data_type d = long_process();
return d;
});
f.then([](future<data_type> &f) {
data_type d = f.get();
d.use();
};
do_smth_in_parallel_with_long_process();
А придется городить бессмысленный огород как-нибудь так:
future<data_type> f = async([&f]() {
data_type d = long_process();
return d;
});
thread([]() {
data_type d = f.get();
d.use();
});
do_smth_in_parallel_with_long_process();
что проще реализовать вовсе без future:
void callback(data_type &d)
{
d.use();
}
async([&f]() {
data_type d = long_process();
callback(d);
});
do_smth_in_parallel_with_long_process();
что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.
Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.
То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.
Исправление dissident, :
у корутин нет шедулера,
Поправь меня, пожалуйста, если я что-то неверно понял.
У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер (в случае если он есть и используется).
При этом fiber’ы могут быть симметричные и несимметричные. В случае несимметричных fiber’ов yield возвращает управление вызвавшему fiber трэду, а в случае симметричных они переключаются между друг другом.
(с) https://stackoverflow.com/a/42042904
Но как в случае симметричных, так и даже несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:
queue<fiber_type> fibers;
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
Или это будет, например, цикл с приоритетами:
struct fiber_type {
int prio;
...
void operator()() { ... }
};
struct greater_fib {
bool operator()(const fiber_type& a, const fiber_type& b) const{
return a.prio > b.prio;
}
};
vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...
// sort by priorities
make_heap(fibers.begin(), fibers.end());
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
// sort by priorities to keep fibers sorted in case any of the executed fiber
// adds something to the heap (not effective, but this is just an example)
make_heap(fibers.begin(), fibers.end());
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:
coroutine_type coroutine
{
int a, b;
// do something async
yield();
}
void function()
{
coroutine_type cor coroutine();
cor.resume();
}
await function();
Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.
В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.
Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).
Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).
Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):
futuredata_type f = async([]() {
data_type d = long_process();
return d;
});
f.then([](future<data_type> &f) {
data_type d = f.get();
d.use();
};
do_smth_in_parallel_with_long_process();
А придется городить бессмысленный огород как-нибудь так:
future<data_type> f = async([&f]() {
data_type d = long_process();
return d;
});
thread([]() {
data_type d = f.get();
d.use();
});
do_smth_in_parallel_with_long_process();
что проще реализовать вовсе без future:
void callback(data_type &d)
{
d.use();
}
async([&f]() {
data_type d = long_process();
callback(d);
});
do_smth_in_parallel_with_long_process();
что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.
Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.
То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.
Исправление dissident, :
у корутин нет шедулера,
Поправь меня, пожалуйста, если я что-то неверно понял.
У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер (в случае если он есть и используется).
При этом fiber’ы могут быть симметричные и несимметричные. В случае несимметричных fiber’ов yield возвращает управление вызвавшему fiber трэду, а в случае симметричных они переключаются между друг другом.
(с) https://stackoverflow.com/a/42042904
Как в случае симметричных, так и несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:
queue<fiber_type> fibers;
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
Или это будет, например, цикл с приоритетами:
struct fiber_type {
int prio;
...
void operator()() { ... }
};
struct greater_fib {
bool operator()(const fiber_type& a, const fiber_type& b) const{
return a.prio > b.prio;
}
};
vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...
// sort by priorities
make_heap(fibers.begin(), fibers.end());
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
// sort by priorities to keep fibers sorted in case any of the executed fiber
// adds something to the heap (not effective, but this is just an example)
make_heap(fibers.begin(), fibers.end());
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:
coroutine_type coroutine
{
int a, b;
// do something async
yield();
}
void function()
{
coroutine_type cor coroutine();
cor.resume();
}
await function();
Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.
В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.
Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).
Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).
Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):
futuredata_type f = async([]() {
data_type d = long_process();
return d;
});
f.then([](future<data_type> &f) {
data_type d = f.get();
d.use();
};
do_smth_in_parallel_with_long_process();
А придется городить бессмысленный огород как-нибудь так:
future<data_type> f = async([&f]() {
data_type d = long_process();
return d;
});
thread([]() {
data_type d = f.get();
d.use();
});
do_smth_in_parallel_with_long_process();
что проще реализовать вовсе без future:
void callback(data_type &d)
{
d.use();
}
async([&f]() {
data_type d = long_process();
callback(d);
});
do_smth_in_parallel_with_long_process();
что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.
Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.
То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.
Исправление dissident, :
у корутин нет шедулера,
Поправь меня, пожалуйста, если я что-то неверно понял.
У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер.
При этом fiber’ы могут быть симметричные и несимметричные. В случае несимметричных fiber’ов yield возвращает управление вызвавшему fiber трэду, а в случае симметричных они переключаются между друг другом.
(с) https://stackoverflow.com/a/42042904
Как в случае симметричных, так и несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:
queue<fiber_type> fibers;
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
Или это будет, например, цикл с приоритетами:
struct fiber_type {
int prio;
...
void operator()() { ... }
};
struct greater_fib {
bool operator()(const fiber_type& a, const fiber_type& b) const{
return a.prio > b.prio;
}
};
vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...
// sort by priorities
make_heap(fibers.begin(), fibers.end());
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
// sort by priorities to keep fibers sorted in case any of the executed fiber
// adds something to the heap (not effective, but this is just an example)
make_heap(fibers.begin(), fibers.end());
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:
coroutine_type coroutine
{
int a, b;
// do something async
yield();
}
void function()
{
coroutine_type cor coroutine();
cor.resume();
}
await function();
Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.
В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.
Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).
Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).
Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):
futuredata_type f = async([]() {
data_type d = long_process();
return d;
});
f.then([](future<data_type> &f) {
data_type d = f.get();
d.use();
};
do_smth_in_parallel_with_long_process();
А придется городить бессмысленный огород как-нибудь так:
future<data_type> f = async([&f]() {
data_type d = long_process();
return d;
});
thread([]() {
data_type d = f.get();
d.use();
});
do_smth_in_parallel_with_long_process();
что проще реализовать вовсе без future:
void callback(data_type &d)
{
d.use();
}
async([&f]() {
data_type d = long_process();
callback(d);
});
do_smth_in_parallel_with_long_process();
что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.
Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.
То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.
Исправление dissident, :
у корутин нет шедулера,
Поправь меня, пожалуйста, если я где-то неверно понял/
У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер.
При этом fiber’ы могут быть симметричные и несимметричные. В случае несимметричных fiber’ов yield возвращает управление вызвавшему fiber трэду, а в случае симметричных они переключаются между друг другом.
(с) https://stackoverflow.com/a/42042904
Как в случае симметричных, так и несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:
queue<fiber_type> fibers;
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
Или это будет, например, цикл с приоритетами:
struct fiber_type {
int prio;
...
void operator()() { ... }
};
struct greater_fib {
bool operator()(const fiber_type& a, const fiber_type& b) const{
return a.prio > b.prio;
}
};
vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
...
// sort by priorities
make_heap(fibers.begin(), fibers.end());
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
// sort by priorities to keep fibers sorted in case any of the executed fiber
// adds something to the heap (not effective, but this is just an example)
make_heap(fibers.begin(), fibers.end());
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio, см., например, socket_ и buffer_ в примере https://www.boost.org/doc/libs/1_54_0/doc/html/boost_asio/overview/core/coroutine.html). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:
coroutine_type coroutine
{
int a, b;
// do something async
yield();
}
void function()
{
coroutine_type cor coroutine();
cor.resume();
}
await function();
Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата (courotine_type в примере выше) является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызовов функций/корутин.
В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.
Мне кажется, что в случае безстэковых корутин и хитроумного шедулера можно создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).
Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).
Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):
futuredata_type f = async([]() {
data_type d = long_process();
return d;
});
f.then([](future<data_type> &f) {
data_type d = f.get();
d.use();
};
do_smth_in_parallel_with_long_process();
А придется городить бессмысленный огород как-нибудь так:
future<data_type> f = async([&f]() {
data_type d = long_process();
return d;
});
thread([]() {
data_type d = f.get();
d.use();
});
do_smth_in_parallel_with_long_process();
что проще реализовать вовсе без future:
void callback(data_type &d)
{
d.use();
}
async([&f]() {
data_type d = long_process();
callback(d);
});
do_smth_in_parallel_with_long_process();
что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.
Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO относительно шедулера у безстэковых корутин, см. вопрос выше про осмысленность шедулера для них и про deadlock), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, иначе стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую корутину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.
То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд (см. https://stackoverflow.com/a/19486183 наример), в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции), а значит, как как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.
Исходная версия dissident, :
у корутин нет шедулера,
Поправь меня, пожалуйста, если я где-то неверно понял/
У fiber’ов может быть шедулер (как и у безстэковых корутин, твоего «оксюморона», но это IMHO не имеет смысла, см. ниже), например, https://www.boost.org/doc/libs/1_65_1/libs/fiber/doc/html/fiber/scheduling.html. Имеется ввиду не то, что шедулер определяет, когда прервать fiber, что было бы вытесняющей многозадачностью (это определяет сам fiber, в точках вызова yield, что является кооперативной многозадачностью), а в том, что fiber’ы не нужно вручную «возобновлять» при помощи resume - их «возобновляет» шедулер.
При этом fiber’ы могут быть симметричные и несимметричные. В случае несимметричных fiber’ов yield возвращает управление вызвавшему fiber трэду, а в случае симметричных они переключаются между друг другом.
(с) https://stackoverflow.com/a/42042904
Как в случае симметричных, так и несимметричных fiber’ов можно реализовать шедулер. Например в случае несимметричных корутин (тех, которые возвращают управление вызвавшему трэду) шедулер будет "resume"ить fiber’ы согласно какому-нибудь алгоритму в этом самом трэде, который можно будет выбрать, например, в простейшем случае это будет просто цикл:
queue<fiber_type> fibers;
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
Или это будет, например, цикл с приоритетами:
struct fiber_type {
int prio;
...
void operator()() { ... }
};
struct greater_fib {
bool operator()(const fiber_type& a, const fiber_type& b) const{
return a.prio > b.prio;
}
};
vector<fiber_type> fibers;
fibers.push_back(...);
fibers.push_back(...);
// sort by priorities
make_heap(fibers.begin(), fibers.end());
...;
while (!finished)
{
while (fibers.empty() && !fibers)
{
co_yield();
}
// sort by priorities to keep fibers sorted in case any of
// the executed fiber adds something to the heap (not
// effective, but this is just an example)
make_heap(fibers.begin(), fibers.end());
if (!finished)
{
fiber_type f = fibers.front();
fibers.pop();
f.resume();
}
}
В случае безстэковых корутин компилятор при создании каждой корутины генерирует и создает при помощи new структуру (где хранятся, например, значения переменных в данный момент) для корутины (в принципе, не обязательно компилятор эту структуру генерирует, безстэковые корутины могут быть реализованы в качестве библиотеки, правда в этом случае необходимо будет вручную задать какие переменные в корутине нужно «запомнить» в структуре корутины и вручную реализовывать всю эту механику с их «запоминанием», так, например, безстэковые корутины реализованы в boost::asio). При этом, поскольку структура для корутины одна, то нельзя сделать как-нибудь так:
coroutine_type coroutine
{
int a, b;
// do something async
yield();
}
void function()
{
coroutine_type cor coroutine();
cor.resume();
}
await function();
Т.е. нельзя ожидать корутины на уровне выше, чем ее вызов, так как у безстэковых корутин тип возвращаемого результата является частью декларации корутины (в отличие от стэковой корутины) и при ее вызове динамически создается структура, содержащая в примере выше a и b, которая одна для всей корутины и не поддерживает стэка вызова функций/корутин.
В Unity (как и в C++ STL!) именно такие безстэковые корутины. К ним можно прилепить шедулер (например простой цикл для данного трэда, который будет их сам вызывать (см. выше пример с queue и heap)), но у такой реализации ограниченные возможности именно потому, что передать управление «наверх» можно только из самой корутины, а не из промежуточной функции/функций.
Мне кажется, что в случае безстэковых корутин и хитроумного шедулера легко создать deadlock, даже несмотря на то, что трэд один, например трэд делает await cor1 и следом await cor2, обе cor1 и cor2 делают await cor3, которая делает await cor1 и await cor2. Такое вообще возможно? Я в ту сторону думаю? Ну т.е. мой вопрос: имеет ли право на существование шедулер для безстэковых корутин (повторюсь, под шедулером, я имею ввиду не выбор точек переключения (это задает программист вручную вставляя куда нужно yield()), а алгоритм выбора следующей корутины для «возобновления» (resume), например «простой цикл», «цикл с приоритетами» и т.п.).
Стэковые же корутины (они же fiber’ы) позволяют иметь граф вызовов функций, в котором фукнции где-то «внизу» вызывают корутины, а трэд, который «начинает» этот граф, может ждать не только на уровне вызова fiber’ов, но и выше. В такой реализации (стэковые корутины, они же fiber’ы) шедулер имеет смысл. Такие корутины (или правильнее fiber’ы или lightweight threads) реализованы например в boost::coroutine и boost::courotine2 (которые отличаются, например, тем, что в boost::coroutine2 нету симметричных корутин, но при этом обе эти библиотеки реализуют стэковые корутины, они же fiber’ы, они же lightweight threads).
Тот факт, что в C++ корутины безстэковые ограничивает их полезность. Так же, как, например, отсутствие then() у future сильно ограничивает применение future, т.е., например, нельзя написать так (этот пример с future не имеет отношение к корутинам, просто показывает, насколько в C++ то, что появляется - появляется поздно и не доделано по-человечески, как future’ы, так и корутины):
futuredata_type f = async([]() {
data_type d = long_process();
return d;
});
f.then([](future<data_type> &f) {
data_type d = f.get();
d.use();
};
do_smth_in_parallel_with_long_process();
А придется городить бессмысленный огород как-нибудь так:
future<data_type> f = async([&f]() {
data_type d = long_process();
return d;
});
thread([]() {
data_type d = f.get();
d.use();
});
do_smth_in_parallel_with_long_process();
что проще реализовать вовсе без future:
void callback(data_type &d)
{
d.use();
}
async([&f]() {
data_type d = long_process();
callback(d);
});
do_smth_in_parallel_with_long_process();
что делает future практически бесполезными, так же и то, что корутины в C++ безстэковые тоже делает их использование просто синтактическим сахаром.
Так или иначе шедулер у корутин может быть, как у стэковых, так и у безстэковых (IMHO, см. вопрос выше про осмысленность шедулера для безстэковых корутин), правда во-втором случае смысла в нем мало (IMHO). Стэковые же корутины иначе называются fiber’ами, иначе lightweight thread’ами, иначе, например, goroutine’ами (в Go), отсюда и путаница в терминах. То, что ты называешь трэдами, может быть как полноценными трэдами (или процессами), которые могут выполняться каждый своим CPU, так и fiber’ами, иначе lightweight thread’ами, т.е. стэковыми корутинами, которые выполняются в том же трэде (и тем же CPU), но при этом обеспечивают кооперативную многозадачность в точках yield, при этом позволяют иметь шедулер, решающий какую коротину следующую возобновлять при помощи resume(), при этом позволяют иметь любой уровень вложенности функций/корутин) и делают использование шедулера для них чем-то, что имеет смысл.
То, что объединяет безстэковые и стэковые корутины - это то, что они выполняются в том же самом трэде (ну, в отличие, разве что от gotoutines в Go, которые могут быть «перенесены» в другой трэд https://stackoverflow.com/a/19486183, наример, в случае вызова какой-нибудь goroutine’ой блокирующей I/O операции)), а значит, как в случае безстэковых так и стэковых корутин синхронизация (мутексы, семафоры и т.д.) не нужна.