¿Son un problema las corutinas C++ 20 sin pila?

asynchronous c++20

Question

Según lo siguiente, parece que las corutinas en C ++ 20 serán apiladas.

https://en.cppreference.com/w/cpp/language/coroutines

Estoy preocupado por muchas razones:

1. En los sistemas integrados, la asignación de almacenamiento dinámico a menudo no es aceptable.
2. Cuando está en un código de bajo nivel, sería útil anidar co_await (no creo que las rutinas sin pila lo permitan).

Con una rutina sin pila, solo se puede suspender la rutina de nivel superior. Cualquier rutina llamada por esa rutina de nivel superior puede no suspenderse. Esto prohíbe proporcionar operaciones de suspensión / reanudación en rutinas dentro de una biblioteca de uso general.

https://www.boost.org/doc/libs/1_57_0/libs/coroutine/doc/html/coroutine/intro.html#coroutine.intro.stackfulness

3. Código más detallado debido a la necesidad de asignadores personalizados y agrupación de memoria.

4. Más lento si la tarea espera a que el sistema operativo le asigne algo de memoria (sin agrupación de memoria).

Dadas estas razones, realmente espero estar muy equivocado acerca de cuáles son las corutinas actuales.

La pregunta tiene tres partes:

1. ¿Por qué elegiría C ++ usar corutinas sin pila?
2. En cuanto a las asignaciones para guardar el estado en las rutinas apiladas. ¿Puedo usar alloca () para evitar cualquier asignación de montón que normalmente se usaría para la creación de rutina.

El estado de la rutina se asigna en el montón a través del operador no matriz nuevo. https://en.cppreference.com/w/cpp/language/coroutines

3. ¿Están equivocados mis supuestos sobre las corutinas de c ++, por qué?

EDITAR:

Estoy revisando las conversaciones de cppcon para las corutinas ahora, si encuentro alguna respuesta a mi propia pregunta la publicaré (nada hasta ahora).

CppCon 2014: Gor Nishanov "aguarda 2.0: Funciones reanudables sin apilamiento"

https://www.youtube.com/watch?v=KUhSjfSbINE

CppCon 2016: James McNellis "Introducción a las corutinas C ++"

https://www.youtube.com/watch?v=ZTqHjjm86Bw

Answer 1

Adelante: cuando esta publicación dice simplemente "corutinas", me refiero al concepto de una rutina, no a la característica específica de C ++ 20. Al hablar sobre esta característica, me referiré a ella como " co_await " o "co_await coroutines".

En asignación dinámica

Cppreference a veces usa una terminología más flexible que la estándar. co_await como característica "requiere" asignación dinámica; si esta asignación proviene del montón o de un bloque estático de memoria o lo que sea que sea asunto del proveedor de la asignación. Dichas asignaciones se pueden eludir en circunstancias arbitrarias, pero dado que el estándar no las detalla, aún debe suponer que cualquier rutina de co_await puede asignar memoria de forma dinámica.

co_await coroutines tienen mecanismos para que los usuarios proporcionen la asignación para el estado de la corutina. Por lo tanto, puede sustituir la asignación de almacenamiento dinámico / libre por cualquier grupo particular de memoria que prefiera.

co_await como característica está bien diseñada para eliminar la verbosidad desde el punto de uso de cualquier objeto y funcionalidad co_await. La maquinaria co_await es increíblemente complicada e intrincada, con muchas interacciones entre objetos de varios tipos. Pero en el punto de suspensión / reanudación, siempre se ve como co_await <some expression> . Agregar soporte de asignador a sus objetos y promesas esperadas requiere un poco de verbosidad, pero esa verbosidad vive fuera del lugar donde se usan esas cosas.

Usar alloca para una rutina sería ... muy inapropiado para la mayoría de los usos de co_await . Si bien la discusión sobre esta característica intenta ocultarla, el hecho es que co_await como característica está diseñada para uso asíncrono. Ese es su propósito: detener la ejecución de una función y programar la reanudación de esa función en potencialmente otro subproceso, luego pastorear cualquier valor eventualmente generado a algún código de recepción que pueda estar algo alejado del código que invocó la rutina.

alloca no es apropiado para ese caso de uso particular, ya que la persona que llama a la rutina puede hacer todo lo posible para que el valor pueda ser generado por algún otro hilo. Por lo tanto, el espacio asignado por alloca ya no existiría, y eso es algo malo para la rutina que vive en él.

También tenga en cuenta que el rendimiento de la asignación en tal escenario generalmente se verá eclipsado por otras consideraciones: la programación de subprocesos, mutexes y otras cosas a menudo se necesitarán para programar adecuadamente la reanudación de la rutina, sin mencionar el tiempo que toma obtener el valor de lo que sea asincrónico El proceso lo está proporcionando. Por lo tanto, el hecho de que se necesite una asignación dinámica no es realmente una consideración sustancial en este caso.

Ahora, hay circunstancias en las que la asignación in situ sería apropiada. Los casos de uso del generador son para cuando esencialmente desea pausar una función y devolver un valor, luego retomar donde la función se detuvo y potencialmente devolver un nuevo valor. En estos escenarios, la pila para la función que invoca la rutina seguramente seguirá existiendo.

co_await admite tales escenarios (aunque co_yield ), pero lo hace de una manera menos que óptima, al menos en términos del estándar. Debido a que la característica está diseñada para una suspensión total, convertirla en una rutina de suspensión tiene el efecto de tener esta asignación dinámica que no necesita ser dinámica.

Es por esto que el estándar no requiere asignación dinámica; Si un compilador es lo suficientemente inteligente como para detectar un patrón de uso del generador, puede eliminar la asignación dinámica y simplemente asignar el espacio en la pila local. Pero, de nuevo, esto es lo que un compilador puede hacer, no debe hacer.

En este caso, la asignación basada en alloca sería apropiada.

Cómo se metió en el estándar

La versión corta es que entró en el estándar porque las personas detrás de él pusieron el trabajo, y las personas detrás de las alternativas no lo hicieron.

Cualquier idea de rutina es complicada, y siempre habrá preguntas sobre la implementabilidad con respecto a ellas. Por ejemplo, las propuestas de " funciones reanudables " se veían geniales, y me hubiera encantado verlas en el estándar. Pero en realidad nadie lo implementó en un compilador. Así que nadie podría probar que en realidad era algo que tú podrías hacer. Claro, suena implementable, pero eso no significa que sea implementable.

Recuerde lo que sucedió la última vez que se utilizó "sonidos implementables" como base para adoptar una función.

No desea estandarizar algo si no sabe que se puede implementar. Y no desea estandarizar algo si no sabe si realmente resuelve el problema deseado.

Gor Nishanov y su equipo de Microsoft se pusieron a trabajar para implementar co_await . Lo hicieron durante años , refinando su implementación y similares. Otras personas utilizaron su implementación en el código de producción real y parecían bastante satisfechos con su funcionalidad. Clang incluso lo implementó. Por mucho que personalmente no me guste, es innegable que co_await es una característica madura .

Por el contrario, las alternativas de "corutinas centrales" que surgieron hace un año como ideas en competencia con co_await no lograron ganar tracción en parte porque eran difíciles de implementar . Es por co_await se adoptó co_await : porque era una herramienta comprobada, madura y sólida que la gente quería y tenía la capacidad demostrada de mejorar su código.

co_await no es para todos. Personalmente, es probable que no lo use mucho, ya que las fibras funcionan mucho mejor para mis casos de uso. Pero es muy bueno para su caso de uso específico: suspensión completa.

Answer 2

Utilizo rutinas sin pila en objetivos ARM Cortex-M0 pequeños y en tiempo real, con 32kb de RAM, donde no hay ningún asignador de montón presente: toda la memoria está preasignada estáticamente. Las rutinas apiladas son un factor decisivo, y las corutinas apiladas que había usado anteriormente eran difíciles de entender, y esencialmente eran un truco basado completamente en el comportamiento específico de la implementación. Pasar de ese desastre a C ++ portátil y compatible con los estándares fue maravilloso. Me estremezco al pensar que alguien podría sugerir volver.

• Las corutinas apiladas no implican el uso del montón: tiene control total sobre cómo se asigna el marco de la rutina (a través del miembro void * operator new(size_t) en el tipo de promesa).

• co_await se puede anidar bien , de hecho, es un caso de uso común.

• Las corutinas apiladas también tienen que asignar esas pilas en algún lugar, y quizás sea irónico que no puedan usar la pila primaria del hilo para eso . Estas pilas se asignan en el montón, tal vez a través de un asignador de grupo que obtiene un bloque del montón y luego lo subdivide.

• Las implementaciones de rutina sin apilamiento pueden eludir la asignación de trama, de modo que el operator new la promesa no se llama en absoluto, mientras que las corutinas apiladas siempre asignan el apilamiento para la rutina, ya sea necesario o no, porque el compilador no puede ayudar al tiempo de ejecución de la rutina con eludirlo ( al menos no en C / C ++).

• Las asignaciones se pueden eludir con precisión utilizando la pila donde el compilador puede demostrar que la vida de la rutina no se sale del alcance de la persona que llama. Y esa es la única forma en que puede usar alloca . Entonces, el compilador ya se encarga de ti. ¡Cuan genial es eso!

  Ahora, no es necesario que los compiladores realmente hagan esta elisión, pero AFAIK todas las implementaciones por ahí lo hacen, con algunos límites razonables sobre cuán compleja puede ser esa "prueba", en algunos casos no es un problema decidible (IIRC). Además, es fácil verificar si el compilador hizo lo que esperaba: si sabe que todas las corutinas con un tipo de promesa particular son solo anidadas (¡razonables en pequeños proyectos integrados pero no solo!), Puede declarar al operator new en el tipo de promesa pero no lo defina, y luego el código no se vinculará si el compilador "engañó".

  Se podría agregar un pragma a una implementación particular del compilador para declarar que un marco de rutina particular no se escapa incluso si el compilador no es lo suficientemente inteligente como para probarlo; no verifiqué si alguien se molestó en escribirlos todavía, porque mi uso los casos son lo suficientemente razonables como para que el compilador siempre haga lo correcto.

  La memoria asignada con alloca no se puede usar después de regresar de la persona que llama. El caso de uso de alloca , en la práctica, es ser una forma ligeramente más portátil de expresar la extensión de matriz automática de tamaño variable de gcc.

Básicamente, en todas las implementaciones de rutinas apiladas en lenguajes tipo C, el único y supuesto "beneficio" de la pila llena es que se accede al marco utilizando el direccionamiento relativo de puntero base habitual, y push y pop cuando sea apropiado, así que " El código C simple puede ejecutarse en esta pila inventada, sin cambios en el generador de código. Sin embargo, no hay puntos de referencia que respalden este modo de pensar, si tiene muchas corutinas activas: es una buena estrategia si hay un número limitado de ellas y tiene la memoria para desperdiciar para empezar.

La pila tiene que ser sobreasignada, disminuyendo la localidad de referencia: una rutina de pila típica usa una página completa para la pila como mínimo, y el costo de hacer que esta página esté disponible no se comparte con nada más: la única rutina tiene que soportarlo todo. Es por eso que valió la pena desarrollar Python sin pila para servidores de juegos multijugador.

Si solo hay un par de couroutines, no hay problema. Si tiene miles de solicitudes de red, todas manejadas por rutinas apiladas, con una pila de red ligera que no impone una sobrecarga que monopoliza el rendimiento, los contadores de rendimiento por fallas de caché lo harán llorar. Como Nicol ha declarado en la otra respuesta, esto se vuelve algo menos relevante a medida que hay más capas entre la rutina y cualquier operación asincrónica que esté manejando.

Ha pasado mucho tiempo desde que cualquier CPU de más de 32 bits tuvo beneficios de rendimiento inherentes al acceso a la memoria a través de cualquier modo de direccionamiento particular. Lo que importa son los patrones de acceso amigables con el caché y el aprovechamiento de la captación previa, la predicción de ramificaciones y la ejecución especulativa. La memoria paginada y su almacén de respaldo son solo dos niveles más de caché (L4 y L5 en las CPU de escritorio).

1. ¿Por qué elegiría C ++ usar corutinas sin pila? Porque se desempeñan mejor y no peor. Por el lado del rendimiento, solo puede haber beneficios para ellos. Por lo tanto, es obvio, en cuanto al rendimiento, solo usarlos.

2. ¿Puedo usar alloca () para evitar cualquier asignación de montón que normalmente se usaría para la creación de rutina. No. Sería una solución a un problema inexistente. Las rutinas apiladas en realidad no se asignan en la pila existente: crean nuevas pilas, y esas se asignan en el montón de forma predeterminada, tal como lo serían los marcos de corutina C ++ (de forma predeterminada).

3. ¿Están equivocados mis supuestos sobre las corutinas de c ++, por qué? Véase más arriba.

4. Código más detallado debido a la necesidad de asignadores personalizados y agrupación de memoria. Si desea que las rutinas apiladas funcionen bien, estará haciendo lo mismo para administrar las áreas de memoria para las pilas, y resulta que es aún más difícil. Debe minimizar el desperdicio de memoria y, por lo tanto, debe sobreasignar mínimamente la pila para el caso de uso del 99.9%, y tratar de alguna manera con las rutinas que agotan esta pila.

   Una forma de tratarlo en C ++ fue haciendo comprobaciones de la pila en los puntos de ramificación donde el análisis de código indica que se puede necesitar más pila, luego, si la pila se desborda, se produce una excepción, el trabajo de la rutina se deshace (el diseño del sistema tenía para apoyarlo!), y luego el trabajo se reinicia con más pila. Es una manera fácil de perder rápidamente los beneficios de los paquetes apilados. Ah, y tuve que proporcionar mi propia __cxa_allocate_exception para que eso funcione. Diversión, ¿eh?

Una anécdota más: estoy jugando con el uso de corutinas dentro de los controladores de modo kernel de Windows, y allí la falta de apilamiento es importante, en la medida en que si el hardware lo permite, puede asignar el búfer de paquetes y el marco de la rutina juntos, y estas páginas son anclado cuando se envían al hardware de red para su ejecución. Cuando el controlador de interrupciones reanuda la rutina, la página está allí y, si la tarjeta de red lo permite, incluso podría capturarla de antemano para que quede en el caché. Así que eso funciona bien, es solo un caso de uso, pero como querías incrustar, he incrustado :).

Quizás no sea común pensar en los controladores en las plataformas de escritorio como código "incrustado", pero veo muchas similitudes y se necesita una mentalidad integrada. Lo último que desea es el código del núcleo que asigna demasiado, especialmente si agregaría una sobrecarga por subproceso. Una PC de escritorio típica tiene algunos miles de subprocesos presentes, y muchos de ellos están ahí para manejar E / S. Ahora imagine un sistema sin disco que utiliza almacenamiento iSCSI. En dicho sistema, todo lo relacionado con E / S que no esté vinculado a USB o GPU estará vinculado al hardware de la red y a la pila de red.

Finalmente: ¡Confíe en los puntos de referencia, no en mí, y lea la respuesta de Nicol también! . Mi perspectiva está determinada por mis casos de uso: puedo generalizar, pero afirmo que no tengo experiencia de primera mano con las rutinas en el código "generalista" donde el rendimiento es menos preocupante. Las asignaciones de montón para las rutinas apiladas casi nunca se notan en las trazas de rendimiento. En el código de aplicación de uso general, rara vez será un problema. Se vuelve "interesante" en el código de la biblioteca, y se deben desarrollar algunos patrones para permitir que el usuario de la biblioteca personalice este comportamiento. Estos patrones se encontrarán y popularizarán a medida que más bibliotecas usen corutinas C ++.

Answer 3

corutinas apiladas

• Las rutinas sin pila (C ++ 20) hacen la transformación de código (máquina de estado)
• sin pila en este caso significa que la pila de la aplicación no se usa para almacenar variables locales (por ejemplo, variables en su algoritmo)
• de lo contrario, las variables locales de la rutina sin pila se sobrescribirán mediante invocaciones de funciones ordinarias después de suspender la rutina sin pila
• las rutinas sin pila también necesitan memoria para almacenar variables locales, especialmente si la rutina se suspende, las variables locales deben preservarse
• para este tipo de coropas apiladas, apile y use un llamado registro de activación (equivalente a un marco de pila)
• el registro de activación no debe residir en la pila primaria del hilo
• la suspensión de una pila de llamadas profundas solo es posible si todas las funciones intermedias son también rutinas sin pila ( viral ; de lo contrario, obtendría una pila corrupta )
• una rutina sin apilamiento no puede sobrevivir a la persona que llama / creador
• algunos desarrolladores de clang son escépticos de que siempre se pueda aplicar la Optimización de eLision de asignación de montón (HALO)

pila de corutinas

• en su esencia, una rutina apilada simplemente cambia la pila y el puntero de instrucción
• asignar una pila lateral que funcione como una pila normal (almacenar variables locales, avanzar el puntero de la pila para las funciones llamadas)
• la pila lateral debe asignarse solo una vez (también se puede agrupar) y todas las llamadas de funciones posteriores son rápidas (porque solo avanza el puntero de la pila)
• cada rutina sin pila requiere su propio registro de activación -> llamado en una cadena de llamadas profunda se deben crear / asignar muchos registros de activación
• las rutinas apiladas permiten suspender desde una cadena de llamadas profunda mientras que las funciones intermedias pueden ser funciones normales ( no virales )
• una rutina completa puede sobrevivir a la persona que llama o al creador
• Una versión de los puntos de referencia de Skynet genera 1 millón de corutinas apiladas y muestra que las corutiens apiladas son muy eficientes (la versión de rendimiento superior utiliza hilos)
• Todavía no se implementó una versión de la prueba de referencia de Skynet con coroutiens sin pila
• boost.context representa la pila primaria del hilo como una rutina / fibra apilada, incluso en ARM
• boost.context admite pilas crecientes bajo demanda (pilas divididas GCC)