Чем сопрограммы без стеков отличаются от сопрограмм со стеками?

Question

Фон:

Я спрашиваю об этом, потому что в настоящее время у меня есть приложение со многими (от сотен до тысяч) потоков. Большинство из этих потоков простаивают большую часть времени, ожидая, пока рабочие элементы будут помещены в очередь. Когда рабочий элемент становится доступным, он обрабатывается путем вызова некоторого произвольно сложного существующего кода. В некоторых конфигурациях операционной системы приложение сталкивается с параметрами ядра, определяющими максимальное количество пользовательских процессов, поэтому я хотел бы поэкспериментировать со средствами для уменьшения количества рабочих потоков.

Мое предлагаемое решение:

Кажется, что подход на основе сопрограмм, где я заменяю каждый рабочий поток сопрограммой, помог бы достичь этого. Затем я могу создать рабочую очередь, которая будет поддержана пулом реальных рабочих потоков (ядра). Когда элемент помещается в очередь определенной подпрограммы для обработки, запись помещается в очередь пула потоков. Затем он возобновит соответствующую сопрограмму, обработает данные в очереди, а затем снова приостановит их, освободив рабочий поток для выполнения другой работы.

Детали реализации:

Размышляя о том, как я это сделаю, у меня возникают проблемы с пониманием функциональных различий между сопрограммами без стеков и со стеками. У меня есть некоторый опыт использования стека сопрограмм с использованием библиотеки Boost.Coroutine. Я считаю, что это довольно легко понять с концептуального уровня: для каждой сопрограммы она сохраняет копию контекста и стека ЦП, а когда вы переключаетесь на сопрограмму, она переключается на этот сохраненный контекст (как планировщик режима ядра).).

Что менее ясно для меня, так это то, как сопрограмма без стеков отличается от этого. В моем приложении очень важна сумма накладных расходов, связанных с описанными выше очередями рабочих элементов. Большинство реализаций, которые я видел, например, новая библиотека CO2, предполагают, что сопрограммы без стеков обеспечивают намного более низкие издержки переключения контекста.

Поэтому я бы хотел более четко понять функциональные различия между сопрограммами без стеков и стеков. В частности, я думаю об этих вопросах:

• Ссылки, подобные этой, предполагают, что различие заключается в том, где вы можете получить / возобновить в сопрограмме против стека и без стека. Это тот случай? Есть ли простой пример того, что я могу сделать в стопке сопрограмм, но не в стеке?

• Существуют ли какие-либо ограничения на использование автоматических переменных хранения (т. Е. Переменных "в стеке")?

• Есть ли какие-то ограничения на то, какие функции я могу вызывать из сопрограммы без стеков?

• Если нет никакого сохранения стекового контекста для сопрограммы без стека, куда переходят автоматические переменные хранения при выполнении сопрограммы?

Answer 1

Во-первых, спасибо, что взглянули на CO2:)

Документ Boost.Coroutine хорошо описывает преимущество стекируемой сопрограммы:

stackfulness

В отличие от сопрограммы без стеков сложенная сопрограмма может быть приостановлена ​​из вложенного стекового фрейма. Выполнение возобновляется в той же точке кода, где оно было приостановлено ранее. С сопрограммой без стеков, только подпрограмма верхнего уровня может быть приостановлена. Любая процедура, вызываемая этой процедурой верхнего уровня, сама по себе не может быть приостановлена. Это запрещает предоставлять операции приостановки / возобновления в подпрограммах в библиотеке общего назначения.

первоклассное продолжение

Первоклассное продолжение может быть передано в качестве аргумента, возвращено функцией и сохранено в структуре данных для последующего использования. В некоторых реализациях (например, C# yield) к продолжению нельзя получить прямой доступ или манипулировать напрямую.

Без использования стека и первоклассной семантики некоторые полезные потоки управления выполнением не могут поддерживаться (например, совместная многозадачность или контрольные точки).

Что это значит для вас? например, представьте, что у вас есть функция, которая принимает посетителя:

template<class Visitor>
void f(Visitor& v);

Вы хотите преобразовать его в итератор, с помощью стека сопрограммы вы можете:

asymmetric_coroutine<T>::pull_type pull_from([](asymmetric_coroutine<T>::push_type& yield)
{
    f(yield);
});

Но с сопрограммой без стека это сделать невозможно:

generator<T> pull_from()
{
    // yield can only be used here, cannot pass to f
    f(???);
}

В общем случае стековая сопрограмма является более мощной, чем сопрограмма без стеков. Итак, почему мы хотим сопрограмму без стеков? краткий ответ: эффективность.

Стабильная сопрограмма, как правило, должна выделять определенный объем памяти для размещения своего стека времени выполнения (должен быть достаточно большим), а переключение контекста обходится дороже, чем переключение без стеков, например, Boost.Coroutine занимает 40 циклов, а CO2 - всего 7. в среднем на моей машине циклы, потому что единственное, что нужно восстановить без стекового сопрограммы - это счетчик программ.

Тем не менее, при поддержке языка, вероятно, стековая сопрограмма может также использовать преимущества вычисляемого компилятором максимального размера для стека, если в сопрограмме нет рекурсии, поэтому использование памяти также может быть улучшено.

Говоря о сопрограмме без стеков, имейте в виду, что это вовсе не означает, что стек времени выполнения вообще отсутствует, это означает лишь то, что он использует тот же стек времени выполнения, что и на стороне хоста, так что вы также можете вызывать рекурсивные функции, только это все рекурсии будут происходить в стеке времени выполнения хоста. Напротив, при использовании стековой сопрограммы, когда вы вызываете рекурсивные функции, рекурсии будут происходить из собственного стека сопрограммы.

Чтобы ответить на вопросы:

• Существуют ли какие-либо ограничения на использование автоматических переменных хранения (т. Е. Переменных "в стеке")?

Нет. Это ограничение эмуляции CO2. При поддержке языка переменные автоматического хранения, видимые для сопрограммы, будут помещены во внутреннюю память сопрограммы. Обратите внимание на мой акцент на "видимом для сопрограммы", если сопрограмма вызывает функцию, которая использует внутренние переменные автоматического хранения, то эти переменные будут помещены в стек времени выполнения. В частности, сопрограмма без стеков должна сохранять только те переменные / временные значения, которые могут быть использованы после возобновления.

Для ясности, вы также можете использовать автоматические переменные хранения в теле сопрограммы CO2:

auto f() CO2_RET(co2::task<>, ())
{
    int a = 1; // not ok
    CO2_AWAIT(co2::suspend_always{});
    {
        int b = 2; // ok
        doSomething(b);
    }
    CO2_AWAIT(co2::suspend_always{});
    int c = 3; // ok
    doSomething(c);
} CO2_END

Пока определение не предшествует await,

• Есть ли какие-то ограничения на то, какие функции я могу вызывать из сопрограммы без стеков?

Нет.

• Если нет никакого сохранения стекового контекста для сопрограммы без стека, куда переходят автоматические переменные хранения при выполнении сопрограммы?

В ответе выше сопрограмма без стека не заботится об автоматических переменных хранения, используемых в вызываемых функциях, они просто помещаются в обычный стек времени выполнения.

Если у вас есть какие-либо сомнения, просто проверьте исходный код CO2, это может помочь вам понять механику под капотом;)

Answer 2

То, что вы хотите, это пользовательские потоки / волокна - обычно вы хотите приостановить свой код (работающий в волокне) в глубоком вложенном стеке вызовов (например, при анализе сообщений из TCP-соединения). В этом случае вы не можете использовать переключение контекста без стека (стек приложения распределяется между сопрограммами без стека -> кадры стека вызываемых подпрограмм будут перезаписаны).

Вы можете использовать что-то вроде boost.fiber, который реализует пользовательские потоки / волокна на основе boost.context.