Corrutinas en C (2000)

• Cuando el código productor y el consumidor intercambian datos, si uno de los dos se reescribe invertido como callee, la estructura del algoritmo que antes era visible puede quedar enterrada en transiciones de estado
• Las corrutinas al estilo Knuth son un modelo en el que dos rutinas guardan su posición de ejecución y se pasan el control, pero en la estructura de llamadas basada en pila de C es difícil implementarlas directamente de forma portable
• El truco central de este texto consiste en usar la sintaxis de C que permite poner case dentro de subbloques de un switch, junto con la macro __LINE__, para crear una máquina de estados implícita que reingresa en la posición posterior a un return
• Con las macros crBegin, crReturn y crFinish se puede conservar la estructura original de bucles de un descompresor y un parser, pero las variables locales que deban preservarse deben ser static, y crReturn no debe colocarse dentro de un switch explícito ni dos veces en la misma línea
• En código real, por restricciones de reentrancia y multithreading, se necesita una versión mejorada que pase una estructura de contexto; coroutine.h ofrece tanto macros simples scr como macros reentrantes ccr

---

El problema estructural al conectar productores y consumidores

• En programas grandes, es común que un código produzca datos y otro los consuma; en ese caso, decidir cuál será el caller y cuál el callee complica el diseño
• El ejemplo consta de dos rutinas pequeñas
  • El código de descompresión run-length lee la entrada con getchar() y emite caracteres uno por uno con emit()
  • El código del parser lee caracteres con getchar() y trata las secuencias alfabéticas como WORD, y los demás caracteres como PUNCT
• Vistas por separado, ambas rutinas son naturales, pero para que la salida emit() del descompresor alimente directamente la entrada getchar() del parser, hace falta una estructura que las conecte
• También se puede resolver con un pipe entre dos procesos o dos threads
  • El emit() del descompresor escribe en el pipe, y el getchar() del parser lee del otro extremo
  • Este enfoque es simple y robusto, pero pesado y poco portable, por lo que a menudo no se quiere dividir en threads una tarea sencilla

Pérdida de legibilidad por reescritura de funciones

• La solución tradicional es reescribir un extremo del canal de comunicación como una función invocable
• Si el descompresor se convierte en una función que devuelve un carácter en cada llamada, el parser existente puede llamar a decompressor() en lugar de getchar()
• A la inversa, si el parser se convierte en una función que se llama cada vez que recibe un carácter, el código de descompresión existente puede llamar a parser() en lugar de emit()
• No hace falta cambiar ambos: con modificar solo un lado ya se pueden conectar, pero el código reescrito se vuelve mucho más difícil de leer que el original
  • En el descompresor y el parser originales, el flujo del algoritmo aparece de forma natural dentro de los bucles
  • La forma reescrita depende de variables de estado static y transiciones de estado con switch, lo que dificulta leer en el código el formato de compresión o la gramática del parser
• El objetivo es conectar ambos sin invertir ninguno como una máquina de estados explícita

Corrutinas al estilo Knuth y los límites de C

• La solución con corrutinas de Donald Knuth descarta la distinción entre caller y callee, y trata los dos procesos como entidades cooperativas en igualdad de condiciones
• El principio de llamada de este modelo difiere de una llamada de función común
  • La posición de ejecución actual se guarda en un lugar separado, no en la pila
  • Se salta a la posición de ejecución que la otra rutina guardó por última vez
  • Cuando el descompresor emite un carácter, guarda su propio contador de programa y se mueve a la posición guardada del parser
  • Cuando el parser necesita el siguiente carácter, guarda su propio contador de programa y se mueve a la posición guardada del descompresor
• El control va y viene entre las dos rutinas tantas veces como sea necesario
• Este enfoque es bueno en teoría, pero en la práctica solo es posible en ensamblador
• Los lenguajes de alto nivel como C dependen de una estructura basada en pila, así que al transferir control entre funciones una parte debe ser caller y la otra callee
• En código C portable, el enfoque de corrutinas puras es tan poco práctico como la solución con pipes de Unix

Simular “return and continue” en C

• En C, el comportamiento necesario es que una función callee haga return y, en la siguiente llamada, continúe ejecutándose justo después de ese return: return and continue
• Por ejemplo, sería ideal que una función de la forma for (i = 0; i < 10; i++) return i;, al llamarse 10 veces, devolviera en orden los valores de 0 a 9
• La primera implementación usa una variable de estado y goto
  • Se colocan labels al inicio de la función y después de cada return
  • Una variable state que se conserva entre llamadas apunta al siguiente label de reanudación
  • Al inicio de la función, switch(state) salta al label adecuado
  • Justo antes del return, se guarda en state el label al que se volverá en la próxima llamada
• Este enfoque funciona, pero administrar labels manualmente carga el mantenimiento
  • Cada vez que se agrega un return, hay que crear un nuevo label y sumarlo también al switch inicial
  • Al quitar un return, también hay que quitar su label correspondiente
  • Hay que mantener sincronizados todo el tiempo el cuerpo de la función y la lista del switch

Una máquina de estados oculta con Duff’s device

• El famoso Duff’s device de C aprovecha la sintaxis que permite colocar sentencias case correspondientes a un switch también dentro de sus subbloques
• Si esta propiedad se aplica al truco de corrutinas, en vez de que el switch elija qué goto ejecutar, el propio switch funciona como un salto de reingreso
• La forma básica es la siguiente
  • static int state guarda el siguiente punto de reanudación
  • Al inicio de la función se entra con switch(state) { case 0: ... }
  • Justo antes del return, se guarda el siguiente valor de case en state
  • Justo después del return, se coloca ese label case
• Si se envuelve esto en macros, queda una interfaz que parece una corrutina
  • crBegin: oculta static int state=0; switch(state) { case 0:
  • crReturn: guarda state, devuelve un valor y luego coloca un label case en la misma posición
  • crFinish: cierra el bloque abierto
• crReturn está envuelta en do ... while(0), así que incluso si se usa sin llaves entre un if y un else, no causa problemas de sintaxis
• Al principio hay que pasar explícitamente el número de estado, como en crReturn(1, i), pero usando la macro __LINE__ de ANSI C se puede usar el número de línea actual del código fuente como valor de estado
• Después de esta mejora, basta con escribir crReturn(x), pero se agrega la regla de no poner dos crReturn en una misma línea

Reglas de uso de las macros y ejemplos

• Las corrutinas basadas en macros asumen algunas reglas
  • Envolver el cuerpo de la función con crBegin y crFinish
  • Declarar como static las variables locales que deban preservarse más allá de un crReturn
  • Nunca poner crReturn dentro de una sentencia switch explícita
  • En la implementación basada en __LINE__, no poner dos crReturn en la misma línea
• El ejemplo del descompresor conserva la estructura original de bucles y, al emitir un carácter, usa crReturn(c) en lugar de emit(c)
• El ejemplo del parser vuelve al caller con crReturn() cuando necesita un nuevo carácter, y en la siguiente llamada continúa ejecutándose con el nuevo carácter ya recibido en el parámetro c
• En el parser hay un pequeño cambio estructural
  • Como el primer carácter ya está en c al entrar en la función, el crReturn correspondiente al getchar() del inicio del bucle original se mueve al final del bucle
  • Si se quiere, también se puede definir que el parser necesite una llamada de inicialización
• No hace falta convertir ambas rutinas a macros de corrutina; se puede cambiar solo una y dejar la otra como caller
• En definitiva, combinando ANSI C, el preprocesador y una sintaxis poco usada de switch, se maneja el paso de datos entre productor y consumidor sin reescribirlos como máquinas de estados explícitas

Conflicto entre estándares de código y claridad del algoritmo

• Esta técnica viola fuertemente los estándares de codificación habituales
  • Dentro de las macros hay llaves que no encajan entre sí
  • Usa case dentro de subbloques
  • crReturn oculta switch, return y case dentro de una sola macro
• Desde el punto de vista de los estándares de codificación, las macros que ocultan la estructura sintáctica pueden considerarse perjudiciales para la claridad
• Sin embargo, una función reescrita como máquina de estados explícita también se compone de pequeños bloques case STATE y transiciones de estado, y su estructura visual no difiere mucho de una función que enumera bloques con labels goto
• Cuanto más larga es la función, más daña la reescritura como máquina de estados la estructura original del algoritmo
• Esta técnica es un compromiso que oculta parte de la estructura sintáctica para exponer mejor la estructura del algoritmo

Versión reentrante mejorada y código provisto

• Una implementación simple de juguete depende de variables static, por lo que no es reentrante ni adecuada para multithreading
• En aplicaciones reales, debe ser posible llamar a la misma función desde varios contextos y que cada contexto continúe ejecutándose después de su último return
• La mejora consiste en pasar un puntero a una estructura de contexto como parámetro adicional
  • Tanto el estado local como la variable de estado de la corrutina se guardan como miembros de la estructura
  • Variables como contadores de bucle también deben accederse como ctx->i en lugar de i
  • El código queda un poco más feo, pero elimina el problema de reentrancia y mantiene la estructura general de la rutina
• Los usuarios de C++ pueden convertir la corrutina en un miembro de clase y poner dentro de la clase el estado equivalente a las variables locales, para manejar el scope de forma más natural
• El archivo coroutine.h provisto implementa este truco de corrutinas como un conjunto de macros predefinidas
  • Las macros con prefijo scr son la versión simple que usa variables static
  • Las macros con prefijo ccr son la versión avanzada reentrante
  • La documentación detallada está incluida en los comentarios del archivo header
• Visual C++ 6 rechaza este truco porque con la configuración de debug predeterminada “Program Database for Edit and Continue” trata de forma extraña la macro __LINE__
  • Para compilar un programa que use corrutinas en VC++ 6, hay que desactivar Edit and Continue
  • En la configuración del proyecto, en la pestaña “C/C++”, categoría “General”, opción “Debug info”, hay que elegir una opción que no sea “Program Database for Edit and Continue”
• El header se ofrece bajo licencia MIT

Referencias relacionadas y uso real

• The Art of Computer Programming, Volumen 1, Sección 1.4.2, de Donald Knuth, trata las corrutinas en su forma pura
• La discusión de Tom Duff sobre Duff’s device contiene indicios de que pudo haber concebido de forma independiente un truco de corrutinas similar, y en una actualización del 2005-03-07 Tom Duff lo confirmó en un comentario de blog
• El código del protocolo SSH de PuTTY usa este truco de corrutinas en la práctica
• El caso de PuTTY representa un nivel fuerte de hackeo en C poco común en código serio de producción

[GN⁺]

Comentarios en Hacker News

• Al intentar reducir la complejidad de la API en un proyecto en C, terminé volviendo a esta página varias veces, y me parece excelente la explicación del flujo de control
  También me ayudó a pensar con más claridad sobre cómo se guarda el estado dentro y fuera de la pila, y sobre las diferencias de legibilidad según el enfoque de acceso
  Por ahora, mi conclusión es que lo mejor es que sean los usuarios de la biblioteca quienes decidan si quieren usar corrutinas en C. Por ejemplo, Mongoose(https://github.com/cesanta/mongoose) maneja la asincronía con callbacks de eventos, y para bibliotecas así es mucho más agradable envolverlas con las primitivas nativas de hilos/tareas de cada sistema, en lugar de intentar portarlas a unas corrutinas en C míticamente multiplataforma o, peor aún, a std::thread

  • Este sitio es de Simon Tatham. Es conocido por ser el autor de PuTTY [1] y de la colección de rompecabezas [2]
    [1] https://www.chiark.greenend.org.uk/~sgtatham/putty/
    [2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

• Las corrutinas son un concepto realmente genial, y también es muy entretenido ver videos de corrutinas de C++ en CppCon, sobre todo los presentados por gente de Microsoft. El gancho de “abstracción de costo negativo” también está bastante bueno
  Hace unos años, amigos en Meta empezaron a usar corrutinas de C++, pero me dijeron que al final fue un gran error. Tuvieron que enfrentarse a bugs en la implementación del compilador, y seguramente fue bastante sucio de rastrear. En Google, sigo esperando a que la gente brillante que sabe integrarlas bien en google3/ diga que ya se pueden usar
  Este artículo explica una estrategia para implementar corrutinas en C con goto estructurado basado en macros, usando el dispositivo de Duff [1]. La clave es que puedes poner sentencias case casi en cualquier parte dentro de un bloque switch; entonces envuelves toda la función en un switch, guardas la última posición de retorno de la corrutina en una variable static y etiquetas cada coReturn como un case
  El artículo de Sustrik sobre corrutinas en C también puede ser interesante [2]
  [1] https://en.wikipedia.org/wiki/Duff%27s_device
  [2] https://250bpm.com/blog:48/index.html

  • En los últimos años, al pasar de google3 a fbcode, he visto que tener código asíncrono disperso por todas partes del código C++ con cosas como co_yield, co_return y co_await tiene tanto ventajas como desventajas
    La ventaja frente al enfoque interno de google3 es que, al leer el código, queda claro qué partes son asíncronas. Algunos programadores en Google llegaban a trabajar sin entender el modelo de hilos más allá de una sola rama, y luego terminaban creando bugs serios
    La desventaja es más simple. Como mucho código “puede ser asíncrono”, con el tiempo todo termina volviéndose asíncrono solo porque los programadores escriben en ese modo. Elegir entre un spinlock y un mutex con cesión debería depender del tamaño de la sección crítica y de la situación de hilos en ese momento, pero al intentar mantener legibilidad y consistencia, es fácil que todo el proyecto se incline hacia un solo lado
    Me gustaría conocer más implementaciones de lenguajes con threading que no fijen un valor predeterminado hacia ninguno de los dos lados, sino que optimicen mejor la siguiente ejecución según el perfil de las anteriores, sin cambios de código ni bugs
  • Como alternativa, se puede usar la función de GCC de labels as values. Puedes obtener la dirección de una etiqueta y saltar ahí después. En 2005 contribuí con el código que ahora está en lc-addrlabels.h
    También usé la función de etiquetas locales de GCC para evitar por completo el uso de __LINE__, y así incluso se podían poner varios coReturn en una misma línea
  • Probablemente sea cierto que Duff se dio cuenta de que se puede usar case casi en cualquier parte dentro de un bloque switch, pero esa capacidad en sí casi con seguridad fue una función intencional
    Como se menciona al final del artículo, Duff también se dio cuenta de que encima de eso se podían construir corrutinas, pero esa idea le pareció “repugnante”
    Si piensas en el switch de C como una especie de pattern matching poco expresivo, es fácil que el “fallthrough” parezca un bug, pero no lo es. Es algo de la misma familia que el goto calculado de Fortran, y como no requiere que los valores sean contiguos ni que todas las etiquetas estén listadas arriba, resulta más cómodo. Ahora que lo escribo, quizá se parece más a un COMEFROM calculado
  • Ah, el preprocesador de C sigue dando regalos con el paso de los años :-(

• La afirmación de que “los lenguajes de alto nivel de uso general no soportan corrutinas” pudo haber sido cierta en 2000, pero hoy muchos lenguajes sí las soportan, como C++20, Lua, Python y Ruby

  • Python se creó en 1991, así que imagino que la palabra clave yield apareció por esa época o no mucho después
    La mejora propuesta al final del artículo —“agregar un puntero a una estructura de contexto como argumento adicional de la función, y declarar todo el estado local y las variables de estado de la corrutina como miembros de esa estructura”— se parece a una implementación de closures. Sería como convertir el lado llamado en una lambda y hacer que use variables/contexto/estado externos para decidir qué hacer o con qué valores hacerlo; me pregunto si lo estoy entendiendo bien
  • Como referencia, Simula67 tenía corrutinas. No fue el primero, pero si mal no recuerdo, sí fue el primer lenguaje importante en soportarlas

• El enfoque con switch no es rarísimo, pero normalmente se usa un puntero de estado que se pasa a una función de inicialización y a la función de la corrutina
  Usé mucho este método en proyectos embebidos: una corrutina se encargaba de la aceleración/desaceleración del motor y otra solo indicaba hacia qué dirección ir. También lo usé en una biblioteca de red[1]. Incluso la biblioteca estándar tiene funciones corrutina como strtok()[2]
  Para que sea manejable no hace falta llegar al infierno de macros, pero nunca me ha resultado agradable leer el flujo de switch/case
  [1]: https://github.com/REONTeam/libmobile/blob/master/relay.c#L3...
  [2]: https://manpages.debian.org/bookworm/manpages-dev/strtok.3.e...

• También está Simon Tatham's Portable Puzzle Collection, del mismo autor
  https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

• Si esto te parece magia negra de C, también vale la pena leer el texto del mismo autor sobre cómo crear estructuras de control arbitrarias con macros: https://www.chiark.greenend.org.uk/~sgtatham/mp/

  • El enfoque de prefijo con guion bajo sigue siendo muy vulnerable al ocultamiento de nombres en muchos casos. Para evitarlo hay que hacer un name mangling bastante feo y, a diferencia de las macros parecidas a expresiones/sentencias, en las macros de bloque externo ni siquiera los hacks de macros higiénicas de GNU/C23 pueden evitarlo

• Las corrutinas son interesantes, pero en código real también conviene considerar el uso de hilos reales. Los procesadores modernos tienen muchos núcleos, pero las corrutinas a menudo usan solo un núcleo
  Es un problema real. Hasta hace poco, qemu, que usa muchas corrutinas, enviaba buena parte del I/O de dispositivos de bloque a un solo hilo, y eso causaba problemas de rendimiento. Kevin Wolf y otras personas lo corrigieron durante años, y el qemu moderno ya usa varios hilos para I/O; ese trabajo está previsto para RHEL 9.4

  • La única conexión entre hilos y corrutinas es que algunos runtimes de lenguajes monohilo solo ofrecen corrutinas, así que a veces se terminan usando corrutinas donde un hilo sería una mejor opción
    Las corrutinas son una forma de estructurar la ejecución monohilo, y eso ya es útil por sí mismo. El patrón productor-consumidor del ejemplo principal es un buen caso, y conectar un stream a un parser no es un algoritmo paralelo, así que los hilos no sirven para escribir eso
    Si usas un paradigma monohilo para trabajo que sí puede ejecutarse en paralelo, naturalmente será ineficiente, pero las corrutinas no son paralelismo para pobres sino una estructura de control con valor propio. También pueden combinarse productivamente con hilos, como en un servidor web donde el event loop, junto con el dispatcher, va entretejiendo corrutinas entre varios eventos bloqueantes; y si el runtime lanza un hilo por núcleo para paralelizar, la coordinación entre hilos puede reducirse a revisar la profundidad de cada cola de trabajo y pasar solicitudes a la menos cargada
  • Que las corrutinas normalmente usen un solo núcleo suele ser, en general, el comportamiento deseado. Si se trata de tareas paralelas separadas, lo natural es que trabajen con datos distintos
    La idea de las corrutinas es que tienes algún trabajo local y datos síncronos, y te resulta más fácil expresarlo no con el paradigma funcional donde el llamador “tira” del loop interno, sino con la forma invertida donde la función recorre algo en un loop y “empuja” resultados hacia un consumidor abstraído que está en otra parte
  • Hay un punto bastante bueno para mezclar hilos y corrutinas. Se pone una instancia del planificador de corrutinas por hilo, y se crea un hilo por núcleo
    Luego casi nunca se mueven corrutinas entre planificadores, y también casi nunca se comparten datos entre corrutinas de distintos planificadores
    Las corrutinas, mediante planificación cooperativa, permiten un estilo cómodo de programación concurrente que no necesita locks en absoluto. Normalmente la latencia de planificación es mayor, pero al desaparecer el overhead de operaciones atómicas/locks y al no interrumpirse constantemente la ejecución por temporizadores de planificación preventiva, el throughput puede ser bastante alto
  • El consejo de “considera hilos reales” no suele ser bueno en general. Por ejemplo, si solo quieres hacer un recorrido de nodos de árbol en una colección no plana, no veo por qué habría que ejecutar un hilo aparte
  • Las corrutinas son livianas y la sincronización es muy sencilla. Encajan perfecto en cálculos incrementales pequeños, como iteradores o tokenizadores. Probablemente estabas pensando en green threads

• La versión en C++ de este enfoque: https://www.codeproject.com/Tips/29524/Generators-in-C
  Yo también lo uso en mi Sciter por si acaso, y funciona bastante bien; es cómodo

• La forma modular y segura de lograr esto probablemente sean los manejadores de efectos. Se parecen al yield de Python, pero pueden devolver valores y no están limitados a llamadas de función: capturan el scope como las excepciones. Si no te resultan familiares, este texto da una buena motivación
  Cada función escrita en estilo directo puede realizar un “efecto” cuando el control tiene que pasar a otro lugar. Aquí c=getchar() y emit(c) serían casos así
  Entonces el control pasa al manejador de efectos y, en este caso, probablemente el llamador de las dos funciones decide qué hacer después. Cuando el descompresor emite un carácter, se reanuda el código del parser pasándole ese carácter; se sigue hasta que el parser dice que necesita más, y entonces se reanuda otra vez el descompresor
  Los efectos pueden implementarse eficientemente, en especial si se restringe la continuation para que solo pueda llamarse una vez. Ese es el caso de OCaml. Permiten código en estilo directo junto con seguridad de tipos y de memoria, y además son muy útiles en entornos concurrentes
  Aquí hay un ejemplo: https://effekt-lang.org/docs/casestudies/lexer

• No coincido en absoluto con la parte de “este truco obviamente viola todos los estándares de codificación… yo diría que los estándares de codificación están mal”.
  No está mal que un estándar de codificación rechace este código; este código es solo un truco simpático. La ingeniería de software a gran escala consiste en eliminar sorpresas y en hacer código que también pueda leer alguien falto de sueño, depurando a las 3 de la mañana después de que lo llamaron. No se puede esperar que los programadores recuerden siempre cuatro reglas básicas.
  Tampoco me convence la idea de que, al ocultar elementos importantes como switch, return y case dentro de macros “ofuscadoras”, se haya difuminado la estructura sintáctica pero revelado la estructura algorítmica. Un buen programa debe dejar claras tanto la estructura sintáctica como la estructura algorítmica, y este enfoque no llega a eso. Creo que aquí el modelo debería ser la forma en que Rust crea implícitamente una máquina de estados en las funciones async.

• Esa actitud de rebajar todo indefinidamente “hasta el mínimo común denominador” es la causa de gran parte de la calidad actual del software, o de su ausencia. Si se evita el conocimiento y la formación, al final se termina pagando el precio.

• Al pasar de C a C++, vi que hay una gran diferencia entre ambas comunidades en qué consideran código fácil de leer, es decir, en qué esperan que entienda quien lo lea en el futuro.
  En el mundo de C, hasta el operador condicional ternario parece demasiado provocador, y C99 todavía se trata como si fuera una novedad. En el mundo de C++, la única razón para desalentar la metaprogramación con plantillas es que en el estándar que se use se pueda hacer lo mismo con constexpr.