Corrotinas em C (2000)

• Quando código produtor e consumidor trocam dados entre si, reescrever um dos lados na forma de callee tende a enterrar a estrutura algorítmica original em transições de estado
• Corrotinas no estilo de Knuth são um modelo em que duas rotinas salvam seu ponto de execução e passam o controle uma à outra, mas na estrutura de chamadas baseada em pilha do C é difícil implementá-las diretamente de forma portável
• O truque central deste texto é usar a sintaxe de C que permite colocar case dentro de sub-blocos de switch junto com a macro __LINE__, para criar uma máquina de estados implícita que reentra no ponto após o return
• Com as macros crBegin, crReturn e crFinish, é possível manter a estrutura original dos loops de um descompressor e de um parser, mas as variáveis locais que precisam ser preservadas devem ser static, e crReturn não pode ser colocado dentro de um switch explícito nem na mesma linha que outro crReturn
• Em código real, por causa das limitações de reentrância e multithread, é necessária uma versão aprimorada que receba uma struct de contexto, e coroutine.h fornece tanto macros simples scr quanto macros reentrantes ccr

---

Problemas de estrutura ao conectar produtores e consumidores

• Em programas grandes, é comum que um código produza dados e outro os consuma, e nesse ponto decidir qual lado será o caller e qual será o callee torna o design mais difícil
• O exemplo é composto por duas pequenas rotinas
  • O código de descompressão por run-length lê a entrada com getchar() e emite caracteres um a um com emit()
  • O código do parser lê caracteres com getchar() e trata sequências contínuas de letras como WORD, e os demais caracteres como PUNCT
• Cada rotina, isoladamente, é natural, mas para que a saída de emit() do descompressor alimente diretamente a entrada de getchar() do parser, é preciso uma estrutura para conectá-las
• Também dá para resolver com um pipe entre dois processos ou duas threads
  • O emit() do descompressor escreve no pipe, e o getchar() do parser lê da outra ponta
  • Esse método é simples e robusto, mas pesado e pouco portátil, então muitas vezes não se quer dividir threads para uma tarefa simples

Perda de legibilidade ao reescrever funções

• A solução tradicional é reescrever uma das pontas do canal de comunicação na forma de uma função chamável
• Se o descompressor for transformado em uma função que retorna um caractere por chamada, o parser original pode chamar decompressor() no lugar de getchar()
• Por outro lado, se o parser for transformado em uma função chamada a cada caractere recebido, o código original do descompressor pode chamar parser() no lugar de emit()
• Não é necessário mudar os dois; mudar apenas um lado já permite a conexão, mas o código reescrito fica muito mais difícil de ler do que o original
  • No descompressor e no parser originais, o fluxo do algoritmo aparece naturalmente dentro dos loops
  • Na forma reescrita, tudo passa a depender de variáveis de estado static e de transições de estado com switch, dificultando ler no código o formato de compressão ou a gramática do parser
• O objetivo é conectá-los sem virar nenhum dos dois do avesso como uma máquina de estados explícita

Corrotinas no estilo de Knuth e os limites do C

• A solução de corrotinas de Donald Knuth abandona a distinção entre caller e callee e trata os dois processos como entidades cooperativas em pé de igualdade
• O princípio de chamada nesse modelo é diferente de uma chamada de função comum
  • O ponto de execução atual é salvo em um lugar separado, e não na pilha
  • A execução salta para o ponto que a outra rotina havia salvo por último
  • Quando o descompressor emite um caractere, ele salva seu contador de programa e vai para a posição salva do parser
  • Quando o parser precisa do próximo caractere, ele salva seu contador de programa e vai para a posição salva do descompressor
• O controle vai e volta entre as duas rotinas quantas vezes forem necessárias
• Em teoria, essa abordagem é ótima, mas na prática só é viável em assembly
• Linguagens de alto nível como C dependem de uma estrutura baseada em pilha, então ao transferir controle entre funções um lado precisa ser o caller e o outro o callee
• Em C portável, a abordagem de corrotina pura acaba sendo tão pouco prática quanto a solução com pipes Unix

Imitando “return and continue” em C

• O comportamento necessário em C é que uma função callee execute return e, na chamada seguinte, continue a partir do ponto logo após aquele return: return and continue
• Por exemplo, seria ideal que uma função na forma for (i = 0; i < 10; i++) return i; retornasse de 0 a 9 em ordem ao ser chamada dez vezes
• A primeira implementação usa uma variável de estado e goto
  • Há labels no início da função e após cada return
  • A variável state, preservada entre chamadas, aponta para o próximo label de retomada
  • No início da função, switch(state) desvia para o label apropriado
  • Logo antes do return, o código salva em state o label ao qual deverá voltar na próxima chamada
• Funciona, mas manter os labels manualmente traz um custo alto de manutenção
  • Cada novo return exige um novo label e também uma nova entrada no switch inicial
  • Quando um return é removido, o label correspondente também precisa ser removido
  • É preciso manter continuamente a consistência entre o corpo da função e a lista do switch

A máquina de estados escondida com Duff’s device

• O famoso Duff’s device em C explora a sintaxe que permite colocar instruções case correspondentes a um switch também dentro de seus sub-blocos
• Aplicando essa propriedade ao truque de corrotina, o switch deixa de apenas escolher qual goto executar e passa a funcionar ele próprio como um salto de reentrada
• A forma básica é a seguinte
  • Um static int state guarda o próximo ponto de retomada
  • A função entra por switch(state) { case 0: ... }
  • Antes do return, o código grava em state o valor do próximo case
  • Logo após o return, é colocado o label case correspondente
• Quando isso é encapsulado em macros, a interface passa a parecer uma corrotina
  • crBegin: esconde static int state=0; switch(state) { case 0:
  • crReturn: salva state, retorna o valor e, no mesmo ponto, posiciona o label case
  • crFinish: fecha o bloco aberto
• crReturn é envolvido em do ... while(0), então pode ser usado entre if e else sem chaves sem causar problemas de sintaxe
• No início, era preciso informar manualmente o número do estado, como em crReturn(1, i), mas com a macro __LINE__ do ANSI C dá para usar o número da linha atual do fonte como valor de estado
• Depois dessa melhoria, basta usar crReturn(x), mas surge a regra de que não se pode colocar dois crReturn na mesma linha

Regras de uso das macros e exemplos

• As corrotinas baseadas em macros assumem algumas regras
  • O corpo da função deve ser envolvido por crBegin e crFinish
  • Variáveis locais que precisem sobreviver além de um crReturn devem ser declaradas como static
  • Nunca se deve colocar crReturn dentro de um switch explícito
  • Na implementação baseada em __LINE__, não se deve colocar dois crReturn na mesma linha
• No exemplo do descompressor, a estrutura original do loop é preservada, e ao emitir um caractere usa-se crReturn(c) no lugar de emit(c)
• No exemplo do parser, quando um novo caractere é necessário, usa-se crReturn() para voltar ao caller e, na chamada seguinte, a execução continua já com o novo caractere recebido no parâmetro c
• Há uma pequena mudança estrutural no parser
  • Como o primeiro caractere já chega em c na entrada da função, o crReturn equivalente ao getchar() do início do loop original é movido para o fim do loop
  • Se quiser, também é possível definir que o parser exige uma chamada inicial de inicialização
• Não é necessário converter as duas rotinas para macros de corrotina; basta converter uma delas e deixar a outra como caller
• No fim, a ideia combina ANSI C, o pré-processador e uma sintaxe menos usada do switch para passar dados entre produtor e consumidor sem reescrever explicitamente o código como máquina de estados

O choque entre padrões de código e clareza algorítmica

• Essa técnica viola fortemente padrões de código convencionais
  • Há chaves desbalanceadas dentro das macros
  • São usados case dentro de sub-blocos
  • crReturn esconde switch, return e case dentro de uma única macro
• Do ponto de vista de padrões de código, macros que escondem a estrutura sintática podem ser vistas como prejudiciais à clareza
• Mas funções reescritas como máquinas de estado explícitas também acabam compostas por pequenos blocos case STATE e transições de estado, sem uma estrutura visual tão diferente de uma função com uma lista de blocos marcados por goto
• Quanto maior a função, mais a reescrita como máquina de estados danifica a estrutura algorítmica original
• Essa técnica é um compromisso: ela esconde parte da estrutura sintática para expor melhor a estrutura algorítmica

Versão reentrante aprimorada e código fornecido

• A implementação simples, de brinquedo, depende de variáveis static, portanto não é reentrante e não é adequada para multithread
• Em aplicações reais, a mesma função pode ser chamada em vários contextos, e cada contexto precisa poder continuar após o último return
• A melhoria consiste em passar um ponteiro para uma struct de contexto como parâmetro adicional
  • Tanto o estado local quanto a variável de estado da corrotina ficam como membros da struct
  • Variáveis como contador de loop também passam a ser acessadas como ctx->i em vez de i
  • O código fica um pouco mais feio, mas elimina o problema de reentrância preservando a estrutura geral da rotina
• Usuários de C++ podem transformar a corrotina em membro de classe e colocar dentro da classe o estado correspondente às variáveis locais, tratando o escopo de forma mais natural
• O arquivo coroutine.h implementa esse truque de corrotina em um conjunto de macros já definidas
  • As macros com prefixo scr são a versão simples com variáveis static
  • As macros com prefixo ccr são a versão avançada e reentrante
  • A documentação detalhada está incluída nos comentários do arquivo de cabeçalho
• O Visual C++ 6 não gosta desse truque porque lida de forma estranha com a macro __LINE__ na configuração padrão de debug, “Program Database for Edit and Continue”
  • Para compilar programas que usam corrotinas no VC++ 6, é preciso desativar o Edit and Continue
  • Na aba “C/C++” das configurações do projeto, na categoria “General”, escolha em “Debug info” uma opção diferente de “Program Database for Edit and Continue”
• O arquivo de cabeçalho é fornecido sob licença MIT

Referências relacionadas e uso real

• Donald Knuth, em The Art of Computer Programming, Volume 1, Seção 1.4.2, trata das corrotinas em sua forma pura
• A discussão de Tom Duff sobre Duff’s device sugere que ele pode ter chegado independentemente a um truque de corrotina parecido, e uma atualização de 2005-03-07 informa que Tom Duff confirmou isso em um comentário de blog
• O código do protocolo SSH do PuTTY usa esse truque de corrotina na prática
• O caso do PuTTY mostra um nível forte de hack em C raro de ver em código de produção sério

[GN⁺]

Comentários do Hacker News

• Ao tentar reduzir a complexidade da API em um projeto em C, acabei voltando a esta página várias vezes, e acho excelente a explicação sobre fluxo de controle.
  Também ajudou a pensar com mais clareza sobre o armazenamento de estado dentro e fora da pilha e sobre as diferenças de legibilidade entre as abordagens.
  Minha conclusão agora é que é melhor deixar para o usuário da biblioteca decidir se vai usar corrotinas em C. Por exemplo, o Mongoose (https://github.com/cesanta/mongoose) trata assíncrono com callbacks de eventos; para bibliotecas assim, é muito mais agradável envolvê-las com os primitivos de threads/tarefas de cada sistema do que tentar portá-las para alguma corrotina C multiplataforma mítica, ou, pior, para std::thread.

  • Este site é de Simon Tatham. Ele é conhecido como autor do PuTTY [1] e de uma coleção de quebra-cabeças [2].
    [1] https://www.chiark.greenend.org.uk/~sgtatham/putty/
    [2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

• Corrotinas são um conceito realmente muito legal, e também é divertido assistir aos vídeos sobre corrotinas em C++ da CppCon, apresentados principalmente pelo pessoal da Microsoft. O gancho de “abstração de custo negativo” também é bem bom.
  Alguns anos atrás, amigos da Meta começaram a usar corrotinas em C++, e me disseram que acabou sendo um grande erro. Tiveram de lidar com bugs de implementação do compilador, que devem ter sido bem complicados de rastrear. No Google, estou esperando que as pessoas excelentes que as integrem corretamente ao google3/ avisem que agora já dá para usar.
  Este texto explica, por meio do dispositivo de Duff [1], uma forma de goto estruturado baseado em macros como estratégia para implementar corrotinas em C. A ideia central é que dá para colocar instruções case em quase qualquer lugar dentro de um bloco switch; então você envolve a função inteira em um switch, salva a última posição de retorno da corrotina em uma variável static e rotula cada coReturn com um case.
  O texto de Sustrik sobre corrotinas em C também pode ser interessante [2].
  [1] https://en.wikipedia.org/wiki/Duff%27s_device
  [2] https://250bpm.com/blog:48/index.html

  • Tendo me mudado do google3 para o fbcode nos últimos anos, vejo prós e contras no fato de haver código assíncrono como co_yield, co_return e co_await espalhado por toda parte no código C++.
    A vantagem, em comparação com a forma interna do google3, é que, ao ler o código, a assincronicidade de cada parte fica clara. Alguns programadores do Google passavam sem conhecer o modelo de threading além do nível de cada branch, e depois acabavam criando bugs graves.
    A desvantagem é mais simples. Como muito código “pode ser assíncrono”, com o tempo tudo vai se tornando assíncrono só porque os programadores escrevem nesse modo. A escolha entre usar um spinlock ou um mutex que cede a execução deveria depender do tamanho da seção crítica e da situação de threading naquele momento, mas, ao tentar manter legibilidade e consistência, é fácil o projeto inteiro pender para um lado.
    Eu gostaria de conhecer mais implementações de linguagens com threading que não coloquem nenhum dos lados como padrão e que, com base no perfil de uma execução anterior, otimizem melhor a execução seguinte, mas sem mudanças de código nem bugs.
  • Como alternativa, é possível usar o recurso labels as values do GCC. Dá para obter o endereço de um rótulo e pular para lá depois. Em 2005, contribuí com o código que hoje está em lc-addrlabels.h.
    Também usei o recurso de rótulos locais do GCC para evitar completamente o uso de __LINE__, e era possível ter vários coReturn na mesma linha.
  • Provavelmente é verdade que Duff percebeu que se podia usar instruções case em quase qualquer lugar dentro de um bloco switch, mas esse recurso em si quase certamente era intencional.
    Como também aparece no fim do texto, Duff percebeu que dava para construir corrotinas sobre isso, mas considerou a ideia “repugnante”.
    Se você pensar no switch de C como uma espécie de pattern matching pouco expressivo, o “fallthrough” pode facilmente parecer um bug, mas não é. Ele é da mesma família do goto calculado, como o do Fortran, e é mais conveniente porque os valores não precisam ser consecutivos e os rótulos não precisam ficar todos listados no topo. Escrevendo assim, talvez ele pareça até mais próximo de um COMEFROM calculado.
  • Ah, o pré-processador C continua dando presentes mesmo depois de tantos anos :-(

• A afirmação de que “nenhuma linguagem de alto nível amplamente usada oferece suporte a corrotinas” talvez fosse verdadeira em 2000, mas hoje muitas linguagens oferecem, como C++20, Lua, Python e Ruby.

  • Python foi criado em 1991, então eu imaginaria que a palavra-chave yield tenha surgido naquela época ou não muito tempo depois.
    A melhoria sugerida no fim do texto — “ter um ponteiro para uma estrutura de contexto como argumento adicional da função e declarar todo o estado local e as variáveis de estado da corrotina como elementos dessa estrutura” — parece uma implementação de closures. Seria como transformar o lado chamado em uma lambda e usar variáveis externas/contexto/estado para decidir o que fazer ou com qual valor fazer; fico curioso se entendi corretamente.
  • Para referência, Simula67 tinha corrotinas. Não foi a primeira, mas, pelo que me lembro, foi a primeira linguagem importante com suporte a corrotinas.

• O método com switch não é exatamente raríssimo, mas normalmente se usa um ponteiro de estado passado para a função de inicialização e para a função da corrotina
  Usei bastante esse método em projetos embarcados; uma corrotina cuidava da aceleração/desaceleração do motor, enquanto outra apenas informava em qual direção ir. Também já usei em uma biblioteca de rede[1]. A biblioteca padrão também tem funções de corrotina, como strtok()[2]
  Para deixar isso gerenciável, não é preciso chegar a um inferno de macros, mas nunca achei prazeroso ler o fluxo switch/case
  [1]: https://github.com/REONTeam/libmobile/blob/master/relay.c#L3...
  [2]: https://manpages.debian.org/bookworm/manpages-dev/strtok.3.e...

• Há também a Simon Tatham's Portable Puzzle Collection, do mesmo autor
  https://www.chiark.greenend.org.uk/~sgtatham/puzzles/

• Se isso parece magia negra em C, vale a pena ler também o texto do mesmo autor sobre criar estruturas de controle arbitrárias com macros: https://www.chiark.greenend.org.uk/~sgtatham/mp/

  • O método de prefixo com sublinhado ainda é muitas vezes vulnerável a sombreamento de nomes. Para evitar isso, é preciso fazer um name mangling bem feio; e, diferentemente de macros próximas de expressões/instruções, em macros de bloco externo nem os hacks de macros higiênicas do GNU/C23 conseguem evitar o problema

• Corrotinas são interessantes, mas em código real também vale considerar o uso de threads de verdade. Processadores modernos têm muitos núcleos, enquanto corrotinas frequentemente usam apenas um único núcleo
  Isso também é um problema real. Até recentemente, o qemu, que usa muitas corrotinas, enviava boa parte do I/O de dispositivos de bloco para uma única thread, o que causava problemas de desempenho. Kevin Wolf e outras pessoas corrigiram isso ao longo de vários anos, e o qemu moderno passou a usar várias threads para I/O; esse trabalho deve entrar no RHEL 9.4

  • A única conexão entre threads e corrotinas é que alguns runtimes de linguagens single-thread só oferecem corrotinas, o que às vezes leva ao uso de corrotinas em lugares onde threads seriam uma escolha melhor
    Corrotinas são uma forma de estruturar a execução em uma única thread, e são úteis por si só. O padrão produtor-consumidor do exemplo do texto é um bom caso: conectar um stream a um parser não é um algoritmo paralelo, portanto threads não ajudam a escrevê-lo
    Usar um paradigma single-thread para tarefas que podem ser executadas em paralelo é naturalmente ineficiente, mas corrotinas não são o paralelismo dos pobres; são uma estrutura de controle com significado independente. Elas também podem ser combinadas produtivamente com threads, como quando, em um servidor web, um loop de eventos costura corrotinas entre vários eventos bloqueantes junto com um dispatcher; se o runtime paraleliza iniciando uma thread por núcleo, a coordenação entre threads se reduz a algo como verificar a profundidade de cada fila de tarefas e encaminhar a requisição para a menos congestionada
  • O fato de corrotinas normalmente usarem apenas um único núcleo é, em geral, o comportamento desejado. Se forem tarefas paralelas separadas, elas naturalmente lidarão com dados diferentes
    A ideia das corrotinas é usá-las quando há algum trabalho local e dados síncronos, e é mais fácil expressar isso de forma invertida — uma função fazendo um loop e “empurrando” resultados para algum consumidor abstrato em outro lugar — do que no paradigma funcional em que o chamador “puxa” o loop interno
  • Há um ponto bem interessante em misturar threads e corrotinas: ter uma instância de escalonador de corrotinas por thread e criar uma thread por núcleo
    Depois disso, quase nunca se movem corrotinas entre escalonadores, e quase nunca se compartilham dados entre corrotinas de escalonadores diferentes
    Corrotinas permitem, via escalonamento cooperativo, um estilo conveniente de programação concorrente sem nenhuma necessidade de locks. Normalmente a latência de escalonamento aumenta, mas o throughput pode ficar bem alto, porque desaparece a sobrecarga de operações atômicas/locks e um temporizador não fica interrompendo constantemente a execução para o escalonamento preemptivo
  • O conselho “considere threads de verdade” não é bom em geral. Por exemplo, se tudo que quero é percorrer nós de uma árvore, uma coleção não plana, não vejo por que deveria rodar uma thread separada
  • Corrotinas são leves e a sincronização é muito fácil. São perfeitas para pequenos cálculos incrementais, como iteradores ou tokenizers. Talvez você esteja pensando em green threads

• Versão em C++ dessa abordagem: https://www.codeproject.com/Tips/29524/Generators-in-C
  Também uso no meu Sciter, por via das dúvidas, e funciona muito bem, além de ser conveniente

• A forma modular e segura de conseguir isso provavelmente seria com handlers de efeitos. É parecido com o yield do Python, mas pode retornar valores e, em vez de ficar restrito a chamadas de função, tem escopo como exceções. Se você não conhece o conceito, este texto serve como uma boa motivação
  Cada função escrita em estilo direto pode executar um “efeito” quando o controle precisa ir para outro lugar. Aqui, c=getchar() e emit(c) são esses casos
  Então o controle vai para o handler de efeitos e, neste caso, provavelmente o chamador das duas funções decide o que fazer a seguir. Quando o descompressor emite um caractere, ele o passa ao código do parser e retoma a execução; segue assim até o parser dizer que precisa de mais, e então retoma o descompressor novamente
  Efeitos podem ser implementados de forma eficiente, especialmente se a continuation for restringida para poder ser chamada apenas uma vez. O OCaml é assim. Isso permite código em estilo direto junto com segurança de tipos/memória, e também é muito útil em ambientes concorrentes
  Há um exemplo aqui: https://effekt-lang.org/docs/casestudies/lexer

• Não concordo de forma alguma com a parte que diz: “Este truque obviamente viola todos os padrões de codificação… eu diria que os padrões de codificação estão errados”
  Não é errado que os padrões de codificação rejeitem esse código; ele é apenas um truque bonitinho. Engenharia de software em larga escala é sobre eliminar surpresas e criar código que também seja legível para alguém sem dormir, chamado às 3 da manhã para depurar. Não dá para esperar que programadores sempre se lembrem das quatro regras básicas
  Também é difícil aceitar a afirmação de que, ao esconder elementos importantes como switch, return e case dentro de macros de “ofuscação”, a estrutura sintática ficou obscurecida, mas a estrutura algorítmica foi revelada. Um bom programa precisa ter estrutura sintática e estrutura algorítmica claras, e essa abordagem não chega lá. Acho que o modo como Rust cria uma máquina de estados implícita em funções async deveria servir de modelo aqui

  • A postura de “rebaixar ao nível mais burro” sem parar, nivelando pelo menor denominador comum, é o que produziu a maior parte da qualidade — ou da falta dela — do software de hoje. Quando se evita conhecimento e educação, no fim a conta chega
  • Ao passar de C para C++, percebi que há uma grande diferença entre as duas comunidades quanto ao que se considera código legível, isto é, quanto ao que se espera que o leitor do futuro entenda
    No mundo C, até o operador condicional ternário é estímulo demais, e C99 é tratado como novidade moderna. No mundo C++, o único motivo para desestimular metaprogramação com templates é que, no padrão que se está usando, dá para fazer a mesma coisa com constexpr