Tag Archive | C++

Boost.Http scheduled for review

February last year, I was writing an email to the Boost user mailing list, asking for feedback on an HTTP server library proposal. Later that year, I got the news that I was to receive funds through Google to work on such proposal. And I had delivered a library by the asked timeframe. However, getting the library into Boost is another game. You must pass through the review process if you want to integrate some library into Boost. And I’d like to announce that my library is finally going to be reviewed starting on Friday.

Some links:

After working on this project for more than a year, I’m pretty glad it finally reached this milestone. And I’m very confident about the review.

I had written about this project so much here and there that when the time to write about it in my own blog comes, I don’t have many words left. It’s a good thing to leave as much info on the documentation itself and don’t spread info everywhere or try to lure users into my blog by providing little information on the documentation.

No tópico de Garbage Collector

Você quer que sua linguagem tenha Garbage Collector. Isso é uma mentira.

Você quer que sua linguagem tenha gerenciamento automático de memória. Isso ainda é uma mentira, mas pelo menos é uma mentira menor.

Você quer que sua linguagem tenha gerenciamento automático de recursos, não importando se eles são memória, file descriptors, socket descriptors ou qualquer outro. Isso NÃO é mentira.

Gerenciamento de memória (e outros recursos) seguro, automático, barato, performático e sem Garbage Collector é possível, como a linguagem Rust vem provando. Rust é a linguagem formidável que realmente se preocupa com performance e é capaz até de detectar race condition em tempo de compilação.

Problemas de usabilidade com Garbage Collector

Garbage Collectors não possuem semânticas fortes o suficiente para permitir destrutores. O mais próximo que existe são os finalizers, que possuem uma lista bem grande de possíveis problemas.

É justamente devido ao Garbage Collector e aos finalizers que você está tendo mais trabalho, tendo que gerenciar blocos finally após cada tratemento de exceção. Na verdade, eu também não acredito em tratamento de erros usando exceções (leia o link para não entender errado!).

Outros problemas com Garbage Collector

O uso de um Garbage Collector diminui a utilidade do seu programa. Se seu programa possuir requisitos de tempo real, baixa latência, sistemas embarcados, uso eficiente de bateria ou alguns outros relacionados, Garbage Collector se torna indesejável.

Uma crítica inicial a Garbage Collector é que seu programa congela aleatoriamente, prejudicando a responsividade, mas esse problema é até mais prejudicial no caso do programa ter requisitos de tempo real, pois nenhuma garantia de tempo máximo gasto com coleta de lixo é oferecida. Foram então, criados algoritmos de GC que rodam em paralelo e algoritmos incrementais de GC, permitindo o uso de GC nesses cenários, mas outros problemas persistem. Primeiro, que uma solução dessas continua a consumir mais recursos.

Outra crítica a GC é que ele é um consumidor exagerado de recursos. Se o algoritmo é paralelo, você já depende de uma segunda thread. A depender do algoritmo adotado, você já vai precisar do dobro de memória RAM que uma versão do programa sem GC. E o programa estará usando mais memória que o que precisa na maior parte do tempo, então não podemos chamá-lo de “leve”. Tudo isso contribuindo para o mal uso da bateria do dispositivo.

Mais uma crítica ao GC é que, quando ele executa, vai caminhar aleatoriamente na RAM, navegando de ponteiro em ponteiro, poluindo a cache da CPU e impedindo que você crie um programa de baixa latência, onde responsividade é importante (i.e. jogos).

Um tweeteiro aleatório me deixou ciente de um diagrama legal que pode facilmente lhe fazer pensar que talvez “C++ sempre vença no desafio de performance”. Acho tal gráfico relevante para o tema:

Conclusão

Eu não tenho nada para concluir de verdade. Só criei essa seção para ter a oportunidade de usar uma frase: C++ foi minha escola.

EDIT:

É legal ver a cara de “WTF” do Alexandrescu ao escutar o Stephan T. Lavavej falar “I don’t think garbage collection can ever solve it”.

Tratamento de erros usando exceções sob a perspectiva de um programador de C++

Um tópico sobre o qual sua compreensão pode evoluir muito com o tempo, pois pouca experiência tem uma grande contribuição para impedir que os conceitos se tornem claros é o tópico de tratamento de erros usando exceções. Em C++, esse é um assunto até mais polêmico que em muitas outras linguagens e eu resolvi compartilhar um pouco de minha compreensão nesse texto.

Eu quero que você se esforce muito para não pensar nas implicações de performance que exceções introduzem no sistema, pelo menos até terminarmos de analisar as outras facetas dessa ideia, pois há muitos argumentos irracionais, que, na minha experiência, vêm principalmente de pessoas que estão falsamente preocupadas com performance. Se esforce para manter em mente as frases “um erro é uma exceção?” e “o que é um caso excepcional?”. Elas vão ajudar a entender motivações e serão discutidas mais adiante no texto.

Exceções – resumo/revisão rápida

Exceções formam um conceito de programação idealizado para tornar difícil o ato de ignorar erros, separar código do fluxo normal do programa do código de tratamento de erros — aumentando a legibilidade, diminuindo erros e melhorando a manutenção do sistema — e transportar tanta informação sobre o erro quanto possível.

A motivação para exceções terem sido idealizadas é inspiradora, principalmente quando se pensa em estilos de notificações de erros alternativos que eram/são comuns, como variáveis globais (errno), valores de retorno onde alguns valores possíveis são reservados para indicar erro (normalmente -1), valores de retorno representando um código de erro, valores de retorno indicando sucesso ou erro e outros. Algumas dessas técnicas alternativas poluem abstrações, como no caso onde o valor de retorno da função torna-se reservado para o erro e a função precisa ser refatorada para enviar o resultado através dos argumentos passados para ela.

Algumas das técnicas alternativas evoluíram para soluções que chegaram a adquirir o meu selo de “minimamente respeitável”, e agora nós temos outras soluções para se levar a sério, como, por exemplo, verificações forçadas estaticamente através do sistema de tipos (veja o exemplo de Rust). Mas, esse texto é sobre exceções, então, a partir de agora, evitarei menções desnecessárias a essas abordagens alternativas.

Uma proposta de “expected” para C++ sugere quatro características importantes para um sistema de tratamento de erros:

  • Visibilidade do erro.
  • Informação nos erros.
  • Código limpo.
  • Erros não intrusivos.

Eu recomendo a leitura da parte inicial da proposta para entender essas quatro características. Elas ajudam a julgar o que é um bom sistema de tratamento de erros, ressaltando indicativos importantes.

Isso é introdução mais que o suficiente para se começar a descrever o que são e como funcionam exceções. Exceções definem construções para o controle de fluxo de execução do programa onde separamos código “normal” de código “excepcional”. E existe a exceção, usada para representar e transportar informações sobre um erro. Quando um erro é detectado e a exceção correspondente é gerada, o fluxo de execução normal é abortado e o fluxo de execução excepcional é iniciado, recebendo a exceção lançada para que se possa fazer a decisão de tratamento de erro apropriada.

Sintaticamente, envolvemos o fluxo de código normal para o qual somos capazes de tratar alguma exceção usando um bloco “try” e, logo em seguida, introduzimos um bloco “catch”, que contém o código para o fluxo excepcional. Um exemplo é dado abaixo:

Bem simples e, para muitos novatos, epifanicamente elegante.

Onde exceções decepcionam

O principal problema de usabilidade com exceções, tal como é implementado na linguagem C++, é que você nunca está certo de que está tratando todas as exceções possíveis. Você chama uma função, verifica a assinatura dela, e não sabe quais possíveis exceções serão lançadas. E se, após uma atualização, a função passar a lançar um novo tipo de exceção, todo o código que a chama vai continuar compilando normalmente, sem nem mesmo um aviso sobre a necessidade de atualizar o código chamador, mas causará um erro em tempo de execução nos piores momentos — que são os momentos quando o programador está confiante que o sistema está pronto para produção.

Em Java, há uma funcionalidade chamada de exceções verificadas, em que as possíveis exceções a serem lançadas por uma função fazem parte de sua assinatura. Ou seja, o sistema de exceções é integrado ao sistema de tipos para aumentar a segurança do sistema. Com tal funcionalidade, se, para uma dada função, não há a declaração de que uma exceção X é possivelmente lançada, e essa possibilidade existe no corpo da função, um erro de compilação é gerado. Ou você trata toda as exceções que podem ser lançadas dentro da própria função, ou informa ao código chamador que é possível que algumas exceções sejam lançadas.

Há quem considere catch(…) com rethrow um devido tratamento de exceção, mas a exceção não está sendo tratada. Você está meramente ignorando toda a informação sobre o erro e transferindo a responsabilidade de tratá-la para algum outro lugar. Esse padrão é útil, no entanto, para fornecer garantias de exceções básicas e fortes, dois conceitos presentes na STL.

Não é possível deferir o tratamento de exceções, situação que já podemos encontrar em casos apenas um pouco mais distantes que os imaginados e idealizados. Em programação concorrente (assíncrona ou paralela), o ponto onde uma operação é iniciada e onde é completada podem ser diferentes. Tais pontos sendo diferentes, a exceção não é retornada para o código que requisitou a realização da operação, e você simplesmente usa outro paradigma para tratamento de erros. É até mais complicado quando se envolve threads — problema para o qual o padrão C++11 adicionou exception_ptr. Um dos paradigmas, o paradigma de futures & promises, restaura o suporte a exceções nesses casos, fazendo com que a operação de desembrulhar o valor, através da função-mebro get, possivelmente lance uma exceção, mas, para funcionar, esse truque se apoia no fato de que as exceções em C++ não são verificadas.

Um ponto final sobre a complexidade que exceções introduzem está relacionada a código de finalização, que sempre precisa ser chamado, independente de uma exceção ter sido lançada ou não. Se a linguagem não suporta RAII, adiciona blocos “finally” para resolver o problema. Se a linguagem suporta RAII, um conjunto de convenções e regras é criado e a possibilidade de se lançar uma exceção enquanto outra já está sendo lançada nasce, o que normalmente provoca o programa a ser terminado.

Basicamente, exceções podem se tornar o novo goto e, elas são até abusadas, para, por exemplo, se implementar sistema de pattern matching em C++.

Performance

Finalmente, o tópico que causa polêmica e que desencoraja o uso de exceções em qualquer caso que não seja excepcional, mas cuja preocupação ajuda a definir o que é um caso excepcional.

A primeira observação a se fazer sobre exceções é que elas não são lentas. Citando outro texto de minha própria autoria:

O documento TR18015 detalha duas abordagens principais para a implementação de suporte a exceções e o que o documento menciona como “abordagem tabela” é muito barata, realizando boa parte do que precisa ser computado em tempo de compilação e estruturando o código de forma que não há penalidade em tempo de execução para o fluxo de execução normal do programa. O custo, nessa abordagem, é que o programa fica maior, mas a parte extra pode ser movida para não interferir negativamente no uso de cache e, em sistemas com suporte a memória virtual, essa parte pode até ficar na swap até que torne-se necessária.

uma resposta no StackOverflow, caso você não queira se dar ao trabalho de passar pelo TR18015. A implementação do suporte a exceções é bem elegante e a discussão deveria deixar de ser se exceções são lentas e passar a ser quando usar exceções.

E cuidado com os benchmarks injustos que alimentem esse mito, assim como o P. alerta.

Então usar exceções pode conduzir a um código até mais rápido do que manualmente verificar se erros ocorreram, mas caso um erro aconteça, haverá uma drástica redução na performance. E, como exceções dependem do mecanismo de RTTI, pode ser que tratar erros usando exceções deixe de ser uma opção em sistemas de tempo real.

A solução para esse problema está em colocar uma linha divisória entre erros e exceções. Ou, mais objetivamente, o que é um caso excepcional. Se você usar exceções apenas em casos excepcionais, não há problema nenhum em utilizá-las devido a alguma degradação de performance, pois você atingiu um caso excepcional de qualquer forma.

Um exemplo de um caso excepcional é quando o seu sistema encontra um erro de lógica, pois continuar executando o programa pode causar corrupção do seu estado interno e ele deveria ser encerrado o mais cedo possível, parando somente para mostrar uma mensagem de erro ao usuário.

Outro exemplo de caso excepcional é um cliente de um jogo online, onde, caso a conexão caia, você não se importa com o tempo gasto para lançar a exceção, pois o sistema não pode fazer nada de útil enquanto o erro não for tratado, e reconectar ao servidor é uma operação que vai custar mais tempo que o tratamento da exceção, de qualquer forma. Esse mesmo exemplo de “queda de conexão”, entretanto, pode virar um caso não excepcional em um contexto diferente. No contexto de um servidor que está servindo milhares de clientes, por exemplo, quedas de conexões são esperadas o tempo todo e você não quer que o gargalo de lançar milhares de exceções diminua a capacidade do seu servidor.

O usuário do reddit @sazzer ilustra mais alguns casos do que é uma situação excepcional.

Conclusão

Responder a pergunta “esse é um caso excepcional?” é uma tarefa complicada, mas, pode se tornar mais fácil, fazendo uso de bom senso, das ferramentas certas e de um bom entendimento de suas implicações.

Além disso, um mesmo erro pode ser excepcional ou não a depender do contexto, então é prefirível que se evite a dependência em exceções.

Aliado a todos os problemas que exceções trazem, eu sugiro que seu uso, em C++, seja reduzido. Entretanto, você simplesmente não pode se livrar de exceções usando C++ idiomático, então compreendê-las é importante.

Um sistema de tratamento de erros unificado é atraente, pois elimina a chance de escolhermos a abordagem errada em algum ponto. Entretanto, um sistema de tratamento de erros unificado deveria ter todas as vantagens que exceções possuem e se livrar de seus problemas mais sérios, inclusive os problemas de performance que impossibilita seu uso em sistemas de tempo real.

Pessoalmente, o sistema de tratamento de erros que eu vejo como ideal é a abordagem que é adotada em Rust, que emprega uso de conceitos como algebraic data types e pattern matching para oferecer um sistema de tratamento de erros bem expressivo e que é difícil de usar erroneamente.

Representação do mundo de jogos Bomberman-like

Existem aqueles problemas não-imediatos como desempenho, elegância ou outros que apenas ficam no caminho para a primeira solução funcional. Há aqueles que condenam a prática de preocupação prévia e insistem em resultados imediatos. Estou trabalhando no desenvolvimento de um jogo similar ao Bomberman e precisei desenvolver uma solução para representar o mapa onde o mundo do jogo é executado. E, é claro, acabei tendo o luxo de escolher a abordagem de desenvolvimento onde a preocupação com problemas não-imediatos ocorre mais cedo que a entrega do produto.

Introdução

Para que o problema não fique muito abstrato, considere a imagem abaixo, retirada do jogo BlowThemAll.

shot-2015-05-09_14-08-52

O mapa do jogo possui uma implementação similar ao conceito de uma matriz, onde os elementos do mapa possuem uma posição <x, y> tal que essa posição não pode ultrapassar os limites da matriz e os índices x e y são números discretos, naturais. Cada posição no mapa é um tile e cada tile pode conter vários elementos.

O mapa contém elementos imóveis, tais como blocos a serem explodidos, e elementos móveis, tais como bombas e avatares. Avatar é um personagem que representa a conexão do jogador com o mundo virtual de BlowThemAll.

Há ainda blocos eternos, que não podem ser explodidos.

No jogo original, Bomberman, uma bomba explode e a explosão tem o alcance baseado em tiles. Itens aparecem somente em tiles específicos. Há muitas observações que sugerem fortemente o uso de uma matriz como uma representação eficiente para o jogo.

Problema

Jogando-se Bomberman é possível observar que um avatar pode estar entre dois tiles, então você não pode representá-los como um elemento em uma sequência que faz parte de algum tile, pois um avatar pode estar entre dois tiles. Logo, o avatar precisa ser independente dessa matriz e não pode ter sua posição representada por números discretos.

Abordagens iniciais

A primeira abordagem para o problema foi utilizar uma lista separada para esses elementos do mapa que podem assumir posições entre dois tiles e armazenar suas respectivas posições usando valores do tipo double (ou parecidos).

Entretanto, eu não me sinto confortável usando valores do tipo double em um jogo em rede. Primeiro, porque o comportamento de doubles não é trivial, e segundo, porque é difícil garantir reprodutibilidade/previsibilidade usando doubles, então  eu não quero lidar com o problema desses números sendo utilizados numa parte principal de um jogo em rede. Lembrando que o double que você está usando pode nem ser o IEEE floating point. É claro que eu iria ler o “what every computer scientist should know about floating point numbers” caso o projeto precisasse, mas eu queria, ao menos, considerar uma abordagem alternativa.

A minha ideia foi usar números discretos para as posições dos elementos não-fixos no mapa, e fazer numa escala diferente (se o mapa era 13×11 tiles, os elementos não-fixos estariam em uma matriz virtual 130×110) para permitir um valor mais granular (que emularia o fato do avatar poder estar entre dois tiles). Essa abordagem não me contentou, pois ela levantava outras perguntas (ex.: quão granular devo permitir a posição para permitir uma experiência de jogo agradável?), não era elegante e tirava a simplicidade que eu tinha na solução inicial, onde, era barata, a operação de encontrar quais os avatares eram atingidos por uma explosão.

Pensando nas restrições

Eu voltei ao problema inicial para pensar nas restrições que ele apresentava. A depender de suas restrições, o algoritmo poderia resolver um problema menor e mais simples. Foi essa a abordagem que me permitiu desenvolver a libdepixelize com menos código e mais rápido, e é isso que decidi também fazer no BlowThemAll, entender melhor o problema.

Daí, percebi algo enquanto jogava bomberman. O avatar pode sim, estar entre duas posições, mas caso ele esteja entre duas posições, ainda há um “tile principal” ao qual ele pertence. Isto é, ele só é atingido por uma explosão caso apenas um dos tiles, o “tile principal”, seja incendiado. Além disso, há a restrição de que ele só pode estar entre dois tiles, não entre quatro tiles. Todas essas informações me inspiraram o suficiente para pensar numa solução alternativa.

Solução final

A ideia-chave da solução que acabei adotando é armazenar os elementos na “matriz”, como estava inicialmente planejado, porém adicionar um atributo “filled”, que representava o quanto  daquele tile o elemento ocupa, e um atributo direção, que representa qual o próximo tile a ser ocupado, quando o elemento atual chegar no limite de desocupação do tile atual.

Conceitualmente, 1 representa o estado onde o elemento está ocupando somente aquele tile, 0 representa o estado onde ele não está ocupando nada daquele tile e temos também todos os valores intermediários (como ocorre em contas de probabilidade). Entretanto, queremos usar valores discretos, então usamos inteiros simples e usamos seus limites (0 e 255) para representar os limites conceituais (0 e 1).

Um elemento é transferido para o próximo tile, quando, conceitualmente, ele desocupa mais da metade do tile atual. Se mapearmos o comportamento conceitual para o comportamento em código, então haverá um desperdício de bits, pois o valor de filled nunca seria inferior a 127. Assim sendo, o valor 255 continua representando o conceitual 1, mas o valor 0 representa o conceitual 1/2.

E a solução ficou bem legal até, mas eu ainda queria mais. Uma granularidade de 256 valores possíveis parecia um desperdício para mim e eu queria usá-los para mais informações. Foi então que eu decidi separar preenchimento/ocupação/”filled” por dimensão. “dir” se transformou nos atributos “is_up” e “is_left”, enquanto “filled” se transformou nos atributos “y_filled” e “x_filled”. Usando campos de bits, consegui armazenar toda essa informação em um único byte.

Os atributos “is_up” e “is_left” podem lembrar o bit de sinal da representação de inteiros por complemento de 1, que desperdiça um valor possível, porém eu quero preservar a simetria, então esse desperdício é aceitável.

Essa separação por dimensão, entretanto, faz com que o objeto sempre assuma uma direção para cada dimensão. Se antes as opções de direção eram norte, sul, leste e oeste, agora as direções são nordeste, noroeste, sudeste, sudoeste. Essa característica não é um problema, mas é preciso manter ela em mente quando for implementar funcionalidades que dependem da direção do personagem (socos, por exemplo).

Outra consequência da separação é que o jogo volta a apresentar a possibilidade inicial onde um personagem pode assumir uma posição de estar entre quatro tiles. Essa é uma característica positiva, pois impõe menos restrições e dá mais liberdade artística aos autores de mapas. Essa possibilidade também está presente no jogo Bomberman Tournament e eu não quero fazer menos que os competidores.

E, assim, eu fiquei satisfeito, e surgiu o código do BlowThemAll para tratar mapas. É claro que eu não acho que usaria essa solução para um jogo estilo “The Legend of Zelda: A Link to the Past“, mas eu acho que ficou bem adequada a um jogo ao estilo de Bomberman. Pode ser que você ache interessante pesquisar também sobre Quadtree Collision detection.

Programação em tempo real

Caso não fosse um jogo em rede e que possui algumas características que eu não detalhei, eu estaria também mantendo a preocupação de fazer uma solução para programação em tempo real, afinal, é um jogo e queremos previsibilidade nos tempos de respostas máximos. Sem essa preocupação, a única modificação que pensei para melhorar a previsibilidade nos tempos de resposta seria usar a função vector::reserve para pré-alocar um pouco de memória para a lista de elementos em cada tile.

Final

E para acabar o post, deixo um vídeo de alguns segundos demonstrando o resultado:

Estilos de multitasking cooperativo, loop de eventos e programação assíncrona

introUm dos assuntos que mais me interessa em programação é programação assíncrona. Esse é um tema ao qual eu fui introduzido desde que comecei a brincar com Qt (framework para criar interfaces gráficas) lá por volta de 2010, mas com o tempo fui tendo experiências em vários “paradigmas” de programação assíncrona, passando, por exemplo, por Node.js e Boost.Asio. O tema muito me interessa e foi, por exemplo, o motivador para eu estudar sistemas operacionais e arquitetura de computadores.

Esse é um trabalho que eu tive a ideia de fazer já faz muito tempo. Passou até ideia de, em vez de fazer um post, evoluir mais a ideia e transformar em contribuição e também a ideia de transformar em episódio de podcast. Acho que evolui muito durante esse tempo, para quem antes não entendia nem o porquê de uma troca de contexto ser lenta.

Motivação

Muitas vezes, nos deparamos com problemas que exigem o tratamento contínuo de várias tarefas, como tratar eventos de rede e manipular arquivos locais, por exemplo. Uma intuição ao encarar esse problema seria o uso de threads, já que há várias tarefas em “paralelo”. Entretanto, nem todos os trabalhos efetuados pelo computador são executados exclusivamente pela CPU.

Há outros componentes além da CPU, mas não programáveis e que não executam seu algoritmo, que costumam ser mais lentos e possuem outras tarefas, como transformar um sinal digital em analógico, por exemplo. Além disso, a comunicação com esses componentes ocorre de forma serial, através do ciclo buscar-decodificar-executar-checar-interrupção. Há uma simplificação nesse argumento, mas o fato é que você não lê dois arquivos em paralelo do mesmo HD. Em suma, usar threads não é uma abstração natural ao problema e só introduz gargalo desnecessário e complexo.

“Para quem só sabe usar martelo, tudo parece um prego.” — velho provérbio Klingon

Outro motivo para evitar o uso de threads como resposta ao problema é que logo você terá mais threads que CPUs/núcleos e irá se deparar com o que é conhecido como problema C10K. Mesmo que não fosse um gargalo absurdo, só o fato de você necessitar de mais threads que CPUs disponíves já torna o seu programa mais restrito, pois ele não mais poderá funcionar em um ambiente bare metal, sem a presença de um sistema operacional moderno ou um scheduler.

E o grande problema de desempenho que threads introduzem decorre do fato de elas exigirem uma troca de contexto com o kernel. É claro que esse não é o único problema, pois há também o custo de criação da thread. O programa estaria realizando a criação de threads, que podem acabar tendo um tempo de vida curto e, além disso, passarem a maior parte de seu tempo de vida dormindo. A própria criação da thread não é completamente escalável, pois requer a alocação de sua própria pilha, porém a memória é um recurso global e já aí temos um ponto de contenção.

O problema de desempenho de uma troca de contexto do sistema operacional lembra o problema de desempenho da convenção de chamada de funções usada por compiladores, mas pior.

Funções são unidades isoladas, encapsuladas, e de tal forma deveriam trabalhar. Ao realizar uma chamada de função, a função atual não tem conhecimento de quais registradores serão usados pela nova função. A função atual não detém a informação de quais registradores terão seus valores sobrescritos pela nova função. Assim, as convenções de chamadas de função exigem dois pontos de processamento extra, um para salvar os valores dos registradores na pilha, e outro para restaurar os valores. É por isso que alguns programadores são tão fissurados em fazer function inlining.

O problema de desempenho da troca de contexto é maior, porque ele deve salvar o valor de todos os registradores e ainda sofre com o gargalo do scheduler e da própria troca de contexto. E se processos estiverem envolvidos, então, ainda tem o gargalo de reconfigurar a unidade de gerenciamento de memória. Esse estilo de processamento multitarefa recebe o nome de multitarefa preemptivo. Você pode aprender mais sobre esses custos estudando arquitetura de computadores e sistemas operacionais.

É possível obter concorrência, que é a propriedade de executar várias tarefas no mesmo período de tempo, sem recorrer a paralelismo real. Para essas tarefas que estão mais atreladas a I/O, é interessante abandonarmos o paralelismo durante o tratamento de I/O para alcançarmos mais escalabilidade, evitando o problema do C10K. E já que um novo design se faz necessário, é bom levar em conta multitarefa cooperativo e obter um resultado até melhor do que o inicialmente planejado.

O loop de eventos

E uma abordagem para o problema de programação, que eu vejo sendo usada mais em jogos do que em qualquer outro lugar, é a abordagem de loop de eventos. Há essas peculiaridades de que em jogos você não manipula arquivos como se fosse um banco de dados, com ambiciosos requisitos de desempenho, e também de desenvolver o jogo para quando completar, não mudar o código nunca mais, sem qualquer compromisso com flexibilidade e manutenção. E é com essa abordagem, a abordagem do loop de eventos, que começamos.

Há uma biblioteca, a biblioteca de baixo nível SDL, que tem como objetivo ser apenas uma camada de abstração multimídia, para suprir o que já não é suprido pela própria especificação da linguagem C, focando no desenvolvedor de jogos. A SDL faz uso de um sistema de eventos para tratar da comunicação entre o processo e o mundo externo (teclado, mouse, janelas, …), que é comumente usada em algum loop que o programador prepara. Essa mesma estrutura é utilizada em vários outros locais, incluindo na Allegro, que foi o maior competidor da SDL, no passado.

A ideia é ter um conjunto de funções que faz a ponte da comunicação entre o processo e o mundo externo. No mundo SDL, eventos são descritos através do tipo não-extensível SDL_Event. Então você usa funções como a SDL_PollEvent para receber os eventos e funções dedicadas para iniciar operações que atuem no mundo externo. O suporte a programação assíncrona na biblioteca SDL é fraco, mas esse mesmo princípio de loop de eventos poderia ser usado em uma biblioteca que fornecesse um suporte mais forte a programação assíncrona. Abaixo você pode ver o exemplo de um código que faz uso de eventos da SDL:

Há as bibliotecas de interface gráfica e widgets, como a GTK+, a EFL e a Qt, que levam essa ideia um passo adiante, abstraindo o loop de eventos, antes escrito e reescrito por você, em um objeto. A Boost.Asio, que não é focada em interface gráficas, mas foca exclusivamente em operações assíncronas, possui uma classe de propósito similar, a classe io_service.

Para que você deixe de fazer o código boilerplate de rotear eventos a ações específicas, essas classes tratam essa parte para você, possivelmente através de callbacks, que é uma abstração antiga. A ideia é que você associe eventos a funções que podem estar interessadas em tratar tais eventos. Toda a lógica de rotear os eventos, agora, passa a fazer parte do objeto “loop de eventos”, em vez de um loop de eventos bruto. Esse estilo de programação assíncrona é um estilo do modelo passivo, pois você só registra os callbacks e cede o controle para a framework.

Agora que estamos em um nível de abstração superior ao do loop de eventos, vamos parar a discussão sobre loop de eventos. E esses objetos que estamos mencionando como objetos “loop de eventos”, serão mencionados, a partir de agora, como executors.

O executor

O executor é um objeto que pode executar unidades de trabalho encapsuladas. Utilizando somente C++11, podemos implementar um executor que gerencie o agendamento de operações relacionadas a espera de alguma duração de tempo. Há o recurso global RTC e, em vez de criar várias e várias threads para a execução de operações bloqueantes como a operação sleep_for, vamos usar um executor, que irá agendar e tratar todos os eventos de tempo que se façam necessário. Abaixo está o código para uma possível implementação de tal executor:

Esse código de exemplo me faz lembrar do sleepsort.

No exemplo, sem o uso de threads, foi possível realizar as várias tarefas concorrentes de espera de tempo. Para tal, ao objeto executor, foi dada a responsabilidade de compartilhar o recurso global RTC. Como a CPU é mais rápida que as tarefas requisitadas, uma única thread foi suficiente e, além disso, mesmo assim houve um período de tempo no qual o programa ficou ocioso.

Há alguns conceitos que já podem ser extraídos desse exemplo. Primeiro, vamos considerar que o executor seja uma abstração padrão, já fornecida de alguma forma e interoperável entre todos os códigos que façam uso de operações assíncronas. Quando o programa deseja fazer a operação assíncrona “esperar”, ele requisita o início da operação a alguma abstração (nesse caso é o próprio executor, mas é mais comum encontrar tais interações através de “objetos I/O”) através da função que inicia a operação. O controle é passado para o executor (através do método run), que continuamente verifica notificações de tarefas concluídas. Quando uma tarefa é concluída, o executor empresta o controle da thread para o código do usuário, executando a função que havia sido registrada para tratar a notificação de finalização da tarefa. Quando não há mais nenhuma tarefa na fila, o executor cede o controle da thread, por completo, para o código do usuário.

Como só existe uma thread de execução, mas várias tarefas a executar, nós temos o problema de compartilhamento de recursos, que nesse caso é a própria CPU/thread. O controle deveria ir e voltar entre alguma abstração e o código do usuário. E aí está o princípio do estilo multitarefa cooperativo. Há pontos de customização de comportamento entre os algoritmos responsáveis por executar as tarefas, fazendo com que eles cedam e emprestem o tempo da CPU para realização de outras tarefas.

O estilo de multitarefa cooperativo tem a vantagem de que os pontos de paradas são bem definidos, pois você sabe exatamente quando o controle passa de uma tarefa a outra. Então não há aquele grande gargalo que vimos com trocas de contextos, onde todos os registradores precisam ser salvos, entre outros. Uma solução mais elegante, eficiente e verde.

O objeto que passamos como último argumento da função add_sleep_for_callback é um callback, também conhecido como completion handler. Reflita sobre o que aconteceria se uma nova operação de espera fosse requisitada dentro de um dos callbacks que registramos. Abaixo há uma versão evoluída do executor que implementamos.

Esse detalhe de implementação me lembra a variável de SHELL SHLVL.

Um caso interessante é o da linguagem JavaScript, que possui um tipo de “executor implícito”, que passa a funcionar quando chega ao fim do seu código. Nesse caso, você não precisa escrever códigos como “while (true) executor.run_one()” ou “executor.run()“, mas apenas registrar os callbacks e se assegurar que não há nenhum loop infinito que impeça que o controle passe ao executor.

Introduzida a motivação, o texto passou a prosseguir reduzindo menções a I/O, por motivos de simplicidade e foco, mas tenha em mente que usamos operações assíncronas, majoritariamente, para realizar interações com o mundo externo. Então muitas das operações são agendadas condicionalmente em resposta a notificação de término de uma tarefa anterior (ex.: se protocolo inválido, feche o socket, do contrário, agende mais uma operação de leitura). Propostas como a N3785 e a N4046 definem executors também para gerenciar thread pools, não somente timeouts dentro de uma única thread. E por último, também é possível implementar executors que agendem a execução de operações de I/O dentro de uma mesma thread.

Algoritmos assíncronos descritos de forma síncrona

O problema com essa abordagem de callbacks é que antes, possuíamos código limpo e legível. O código podia ser lido sequencialmente, pois é isso que o código era, uma sequência de instruções. Entretanto, agora precisamos espalhar a lógica entre múltiplos e múltiplos callbacks. Agora você passa a ter blocos de código relacionados longe uns dos outros. Lambdas ajudam um pouco com o problema, mas não o suficiente. O problema é conhecido como callback/nesting hell e é similar ao problema do espaguete. Não sendo o bastante, o fluxo de execução do código se tornou controvertido pela própria natureza assíncrona das operações e construções como estruturas de condição e repetição e até mesmo código de tratamento de erro ficam representáveis de formas longe do ideal, obscuras e difíceis de ler.

Uma abstração de procedimentos muito importante para programação assíncrona é a corotina. Existe a abstração de procedimentos a qual nos referimos por função, que é uma implementação do conceito de subrotina. E temos a corotina, que é uma generalização do conceito de subrotina. A corotina possui duas operações a mais que a subrotina, sendo elas suspender e resumir.

Quando sua função é uma corotina (possível quando a linguagem dá suporte a corotinas), ela pode suspender antes de chegar ao final de sua execução, possivelmente devolvendo um valor durante essa ação de suspender. Um exemplo de onde corotinas são úteis é na implementação de uma suposta função geradora fibonacci e um programa que use essa função para imprimir os dez primeiros números dessa sequência infinita. O código Python abaixo demonstra uma implementação de tal exemplo, onde se percebe a elegância, legibilidade e reaproveitamento que o conceito de corotina permite quando temos o problema de multitarefa cooperativa:

Esse código aí me lembra das funções setjmp/longjmp.

Uma característica a qual se deve dar atenção caso você não esteja familiarizado com o conceito é que o valor das variáveis locais a função fibonacci foi preservado entre as várias “chamadas”. Mais precisamente, quando a função era resumida, ela possuía a mesma pilha de execução de quando foi suspensa. Essa é a uma implementação “completa” do conceito de corotina, uma corotina com pilha. Há também implementações de corotinas sem pilha de execução, onde somente o “número da linha de código” que estava executando é restaurado.

A proposta N4286 introduz uma nova palavra-chave, await, para identificar um ponto para suspender uma corotina. Fazendo uso de tal funcionalidade, é apresentado o seguinte exemplo, que elegantemente define um algoritmo assíncrono, descrito, na minha humilde opinião, de forma bastante síncrona, e fazendo uso das várias construções da linguagem para controle de fluxo de execução (estrutura de seleção, repetição…).

Corotinas resolvem o problema de complexidade que algoritmos assíncronos demandam. Entretanto, há várias propostas para implementação de corotinas e nenhuma delas foi padronizada ainda. Um caso interessante é o da biblioteca Asio, que, usando macros e um mecanismo similar ao Duff’s device, dá suporte a corotinas que não guardem uma pilha de execução. Dentre todo o trabalho que está sendo investido, o que eu espero que aconteça na comunidade de C++ é que a padronização siga o princípio de “você só paga pelo que usa” e que a especificação permita implementações bem performáticas.

Enquanto a padronização de corotinas não acontece e ficamos sem a solução a nível de linguagem, podemos optar por soluções a nível de biblioteca. Como C++ é uma linguagem que suporta abstrações de baixo nível, você consegue acesso a várias facilidades que podem ser usadas para implementar suporte a corotinas, tipo setjmp e longjmp e até mais coisas indo para o mundo não-portável fora da especificação. Uma biblioteca que parece bem promissora e que espero ver sendo incluída na Boost esse ano é a biblioteca Fiber, que imita a API de threads a qual estamos acostumados para fornecer “threads” agendadas cooperativamente, em espaço de usuário. A biblioteca usa o conceito de fibra, análogo ao conceito de thread, e em uma thread, você pode executar várias fibras. Tal biblioteca fornece a expressividade que precisamos para escrever algoritmos assíncronos de forma síncrona.

Outra solução enquanto você não pode esperar, é não usar corotinas, pois ainda será possível conseguir performance excelente através das técnicas comentadas ao longo do texto. O grande porém vai ser o fluxo embaralhado do código-fonte (ofuscação de código, para quê te quero?).

Completion tokens

E nesse período de tempo incerto quanto a que solução tornará-se o padrão para programação assíncrona na linguagem C++, a Boost.Asio, desde a versão 1.54, adotou um princípio interessante, de implementar uma solução extensível. Tal modelo extensível é muito bem documentado na proposta N4045 e aqui nessa seção há somente um resumo do que está contido em tal proposta.

A proposta é que, dado que o modelo de callbacks é confuso, ele seja evoluído para suportar outros modelos. Então, em vez da função receber como argumento um completion handler (o callback), ela deve receber um completion token, que é a solução de customização/extensibilidade proposta.

A proposta N4045 usa uma abordagem top-down, de primeiro mostrar como a proposta é usada, para depois mostrar como ela é implementada. Abaixo há um código de exemplo retirado da proposta:

No código de exemplo anterior, cada vez que a variável yield é passada a alguma operação assíncrona (ex.: open e read), a função é suspensa até que a operação seja concluída. Quando a operação é concluída, a função é resumida no ponto em que foi suspensa e a função que iniciou a operação assíncrona retorna o resultado da operação. A biblioteca Fiber, mencionada anteriormente, fornece um yield_context para o modelo extensível da Asio, o boost::fibers::asio::yield. Código assíncrono escrito de uma forma síncrona. Entretanto, um modelo extensível é adotado, pois não sabemos qual será o padrão para operações assíncronas, então não podemos forçar o uso da biblioteca Fiber goela abaixo.

Para tornar o modelo extensível, o tipo do retorno da função precisa ser deduzido (a partir do token) e o valor do retorno da função também precisa ser deduzido (também a partir do token). O tipo do retorno da função é deduzido a partir do tipo do token e o valor retornado é criado a partir do objeto token passado como argumento. E você ainda tem o handler, que deve ser chamado quando a operação for concluída. O handler também é extraído a partir do token. O modelo de completion tokens faz uso de type traits para extrair todas essas informações e, caso tais traits não sejam especializados, o comportamento padrão é tratar o token como um handler, tornando a abordagem retrocompatível com o modelo de callbacks.

Vários exemplos de token são dados no documento N4045:

  • use_future
  • boost::fibers::asio::use_future
  • boost::fibers::asio::yield
  • block

A abordagem de usar std::future tem impactos significativos na performance e não é uma abstração legal, como o próprio N4045 explica em suas seções iniciais, então vamos evitá-la. É até por isso que eu nem comentei sobre ela até então nesse texto.

Sinais e slots

Uma alternativa que foi proposta ao modelo de callbacks é a abordagem de “signals & slots”. Essa abordagem é implementada na libsigc++, na Boost, na Qt e em várias outras bibliotecas.

A proposta de usar sinais introduz esse conceito, de sinal, que é usado para notificar algum evento, mas abstrai o processo de entregar as notificações e registrar as funções que tratem o evento. O código que notifica os eventos só precisa se preocupar em emitir o sinal toda vez que o evento acontecer, pois o próprio sinal vai cuidar do conjunto de slots, que são as porções de código a serem executadas para tratar os eventos.

Essa abordagem costuma permitir um grande desacoplamento, em oposição a abordagem verbosa muito usada em Java. Um efeito interessante, também, a depender da implementação, é que você pode conectar um sinal a outro sinal, para evitar o trabalho de escrever você próprio o código que sincronize a emissão de um sinal a emissão de outro sinal. É possível também ter muitos sinais conectados a um único slot, assim como um único sinal conectado a múltiplos slots.

O sinal costuma ser associado a um objeto, e quando tal objeto é destruído, as conexões que haviam sido feitas também o são. Assim como também é possível ter slots como métodos de um objeto, que são desconectados de todos os sinais tão logo o objeto é destruído.

Como os sinais são abstrações independentes e operantes assim que se tornam expostos, é natural ser incentivado a remover o argumento de callback das funções que iniciam operações assíncronas, pois haveria duplicação de esforços. Se você for até mais longe e remover também a própria função que inicie a operação assíncrona, expondo ao usuário apenas os sinais para receber as notificações, sua framework deixará de seguir o modelo ativo para seguir o modelo passivo. Exemplos de tais modelos passivos é o socket da biblioteca Qt, que não possui uma função explícita para iniciar a operação de leitura, e a biblioteca POCO, que não possui uma função explícita para iniciar o recebimento de uma requisição HTTP.

Outro detalhe que temos no caso da ideia de sinais, é o controle de acesso. No caso da biblioteca Qt, sinais são implementados de uma forma que exige a cooperação de um pré-processador, o executor da própria Qt e a classe QObject. No caso da biblioteca Qt, a emissão de sinais segue as regras de controle de acesso de métodos protegidos em C++, onde todas as classes-filha podem realizar a emissão de sinais declaradas nas classes-pai. Enquanto a operação de conectar um sinal a outro sinal ou a um slot segue as mesmas regras de membros públicos, onde todo mundo pode realizar.

No caso das bibliotecas que implementam o conceito de sinais como um tipo, é comum ver um tipo sinal que englobe tanto a operação de emitir o sinal, quanto a operação de conectar o sinal a algum slot (diferente do que vemos na proposta de futures e promises, onde é possível ter um controle de acesso separado para as diferentes responsabilidades/operações/entidades).

A abordagem de sinais é legal, mas ela não resolve o problema de complexidade que é resolvido por corotinas. Eu descrevi essa abordagem com o intuito de facilitar a explicação sobre a diferença entre os modelos ativo e passivo.

Modelo ativo versus passivo

No modelo passivo, você não agenda o início das operações e, apesar de ser mais comum em frameworks de produtividade, há muitas perguntas que esse modelo não responde bem (isso é só uma opinião e não um fato), que acabam exigindo o projeto de bem mais abstrações para contornar o problema.

Fazendo um contraste rápido entre a biblioteca Qt e a Boost.Asio. Em ambas as bibliotecas, você possui classes para abstraírem o conceito de socket, mas, enquanto na Qt você trata o evento readyRead e usa o método readAll para receber o buffer com o conteúdo, na Boost.Asio você inicia a operação async_read_some e passa o buffer a ser utilizado como argumento. A Qt usa o modelo passivo e a Boost.Asio usa o modelo ativo.

O evento readyRead, da Qt, age independente do usuário e requer a alocação do buffer toda vez que ocorre. Como, então, você responde a perguntas como “como eu posso customizar o algoritmo de alocação do buffer?”, “como eu posso customizar a aplicação para fazer reaproveitamento de buffers?”, “como eu faço para usar um buffer pré-alocado na stack?” e outras. Como o modelo passivo não responde a perguntas como essa, você precisa inflar a abstração de socket com mais pontos de customização para que comportamentos como esses sejam possíveis. É uma explosão combinatória que acontece para cada abstração que lide com operações assíncronas. No modelo ativo, fica bem natural. Se há algum recurso que a operação que o programador está prestes a iniciar necessita, só precisa passar o recurso como argumento, pois no modelo ativo, o programador explicitamente inicia as operações. E não é só sobre customizar obtenção de recursos. Mais um exemplo de pergunta que o modelo passivo não responde bem é “como eu decido se vou ou não aceitar uma conexão (ou adiar para depois, durante cenários de sobrecarga do servidor)?”. É um grande poder para aplicações sérias que estão seriamente preocupadas com performance e necessitam de ajustes meticulosos.

Além da questão de performance e ajuste fino, o modelo passivo também é problemático para realizar depuração e testes, pois ele faz uma inversão de controle. Esse é um dos motivos pelos quais, até hoje, eu vejo frameworks e frameworks introduzindo race condition nos testes ao depender de timeout para garantir a “robustez” de suas implementações. Essa solução de timeout não resolve um problema que ocorre somente no modelo passivo, mas no modelo passivo, ele ocorre com muito mais frequência. No modelo ativo, seu callback pode ser chamado mesmo quando o erro acontece. No modelo passivo é tão problemático, que já vi eventos de erro serem declarados como notificações separadas, que podem ser facilmente ignoradas, característica indesejável quando você quer diminuir e evitar os bugs no seu código.

Graças ao modelo ativo, muito da biblioteca que estou desenvolvendo com o intuito de submeter a Boost foi simplificado.

O modelo passivo, no entanto, é ótimo para prototipações rápidas. Felizmente podemos implementar abstrações que introduzam o modelo passivo em termos do modelo ativo e ter o melhor (ou o pior, se você for um projetista de C#) dos dois mundos.

Referências bônus

Uns links aleatórios que também me ajudaram como referência ou podem servir de leitura aprofundada para quem quer mais:

Comentários bônus

Espero ter introduzido você, estimado leitor que não comenta, as principais práticas utilizadas no universo da programação assíncrona. E agora que você já está armado com uma visão geral da “área”, se jogar nesse mar da internet para buscar mais referências e cavar mais fundo é só o segundo passo.

Esses dois meses que não postei nada e fui perdendo acessos/visitantes… valeram a pena, pois estou bastante satisfeito com esse trabalho e esse blog é sobre minha satisfação pessoal, por isso que eu nem coloco propaganda.

Há alguns outros textos separados em minha pasta de rascunho com temas variando desde ideias originais até assuntos “manjados” que eu pretendo usar quando bater aquela preguiça de investir muito tempo para um post só.

Agora que eu finalmente discuti concorrência sem paralelismo nesse blog, eu devia atualizar meu notebook (ou corrigir meu desktop) para ter um hardware suficientemente bom e começar a estudar OpenCL para fazer uns posts sobre paralelismo massivo.

EDIT (2015/3/11):

  • Ressaltar sugestão de estudar arquitetura de computadores e sistemas operacionais na seção de motivação.
  • Menção sobre “executor implícito” que ocorre em JavaScript.
  • Adicionado exemplo de motivação não relacionado a buffers na discussão de modelo ativo versus modelo passivo.

Suggestion: 8+1 languages worth learning

Introduction

Every now and then I have contact with a few programming languages and this is the subset that I believe it would give me a very close insight to the sum of the all languages that I’ve had contact with. Also, this subset is not only based on the choice of ideas that each language aggregate, but also on their usefulness and importance for the general programmer’s toolbox.

Regex

Just about the most awesome way to describe and manipulate words from regular languages. No matter if it’s used as communication purposes within some specification or if it’s used to crawl certain patterns within a large collection of texts. It’s useful even within the programming environment itself. And to contribute to its awesomeness, it’s one of the easiest and fastest things to learn. It’s useful even for non-programmers (think about that time when you want to rename all files from a folder to have better consistency).

You can visualize regex patterns using Regexper or any of its competitors.

MarkDown/CommonMark

Started as a simple tool to pretify common syntax used in text-based email. But now just about almost every major site visited by programmers (e.g. StackOverflow, Reddit, GitHub, Doxygen-generated ones) has some support for MarkDown. Or its recent attempt for a smart standardization to spread good common practices and inspire better interoperability among supporting tools.

You can think of MarkDown as a simple way to describe which parts of the text will be bold or will be the tittle for a subsection and so on. MarkDown is simple! MarkDown is simple enough to be accepted in non-programmer targeted products like blogging platforms (even WordPress) or discussion platforms.

C

A language that appeared in 1972 that is still interesting and it’s still important. Being the “portable Assembly”, operating system’s kernels are still written in C. Pieces of software dealing with low-level are still written in C. Embedded projects are still written in C.

C is not a popular language out of merits. C is just the right abstraction to forget about Assembly, but still have no overhead between your software and the machine. Compilers will do a fantastic job in no time for you.

C is an easy language to learn, adding just a few handful abstractions like subroutines and structures to learn. Of course, C is very low-level and you’re expected to face manual memory management (and memory leaks), bit by bit serialization, pointer to functions (no closures here), architecture and operating system differences and maybe things like varargs, setjmp and mmap. You should be able to understand the implications on performance some decision has. This insight is something C has been a great language at and will hardly be acquired learning another language.

Haskell

Haskell is one of the languages I learnt this year. It’s a typed purely functional language. It’s a great language. It has great concepts to decrease the total number of lines of code you should write (like list comprehensions and pattern matching), a clever syntax and some great concepts you could learn (higher-order functions, currying, lazy evaluation…).

Not all about Haskell was new to me, as I had already learn functional programming through Scheme some years ago, but Haskell does a much better job. I hate Lisp naming conventions (car for the head of the list, seriously) and excessive number of parentheses. You shouldn’t have to follow my path. You should be introduced to functional programming with Haskell.

Also, look at how elegant this QuickSort is:

Ruby

Ruby is another of these languages I learnt this year. It’s a purely object-oriented language. Some cleverness was invested around its syntax and I very much appreciate this. It’s a very dynamic language where every class is open and even things like attr_reader are methods.

Object-oriented programming is one of these must-have skills for a programmer and I think Ruby, being purely object-oriented, is a great language to learn this paradigm. Hide and encapsulate!

I choose to learn Ruby looking for a scripting language to empower a possible game engine that I might code. Ruby really impressed me. Ruby is so dynamic that even if I design a wrong class hierarchy or something, Ruby probably has a way to fix it. I don’t intend to design bad hierarchies, but I don’t know who will use my possible future game engine and this concern then becomes undeniably important.

JavaScript

One of the worst languages I’ve ever seen. But also one of the best languages I’ve ever seen (yep, out there you can find programming languages that would surprise you in the bad way). This language is not what I’d like to be the most popular, but it’s just enough to not be hated. Also, it runs on about every web browser, which is like… everywhere. Importance and interoperability. It’s like you really need to know JavaScript.

JavaScript is like the assembly for the web. You’ll find many tools that translate source code from some language into JavaScript just to enable execution within the browser. Once developed to the browser, JavaScript has grow since and now it’s popular even on the server-side. JavaScript also conquered the smart-side.

Not knowing anything about JavaScript is almost like not knowing how to read in the programming industry. It’s a terrible language full of bad decisions, but it’s the common denominator of the web development.

Learning JavaScript also may help to solidify concepts you should know like asynchronous APIs, JSON and some others.

XML/HTML

Responsible for most of the web traffic, this is a pretty important and simple language to understand how web documents are structured. If you think I’m overestimating web, it’s because it’s one of the greatest things we have. But XML is not only about web, it’s about interoperable documents and protocols and it is used as such. You can find XML in use within vector formats, formats for office applications and even chat protocols. I think learning the basics of XML is a big deal.

LaTeX

I personally think that the LaTeX tools aren’t among the most polished tools. Just look at the Makefile generated by Doxygen to see the run-until-no-more-differences-found loop to work around inconveniences in the LaTeX tools. Or just look at the terrible error messages. Also, the syntax isn’t surprisingly pleasant.

But when you want to focus on the content, forget about the accumulated little formatting details and produce beautiful scientific papers, a book with consistently in-between linked references or even just a few math formulas, LaTeX is probably what you should, at least, consider.

Bonus: bash

Capable to automate the most surprising tasks in a computer, if you are using an Unix variant system. You could automate builds, customize software startup sequences and manage your system. But if you’re using an Unix variant system, you already may be aware of that.

Notes

No Java, C++ or Python in this list. Maybe I’ll do a part 2 of this article containing languages with a lesser chance to be used like SQL, MongoDB, OpenGL, R, GStreamer or some Assembly. Actually, I think Java, C++ and Python have a better chance to be used than Haskell, but if you learn every language in this list, C++, Java and Python will be easy to catch up and the lines of code you write will be more elegant.

Performance em C++

Há várias linguagens que possuem várias abstrações e expõem diferenças de comportamento entre programadores. Se a linguagem for simples o suficiente e não permitir muitas formas de expressar algum algoritmo, então um programador qualquer pode usá-la para se comparar a um programador melhor do que ele, seja em questão de produtividade, segurança, performance, generalismo ou outros. C++ é uma das linguagens que ajuda a destacar os programadores que realmente estão preocupados com performance e essa postagem é sobre conhecimento que eu ganhei no meu aprendizado.

Performance na linguagem C++

Discutir performance em linguagens de programação é uma tarefa fácil de desvirtuar devido a grande quantidade de variáveis que pode interferir na análise. Rodar benchmarks por si só é uma tarefa bem complicada de fazer corretamente, e mesmo assim, os compiladores podem evoluir e invalidar o resultado do benchmark. Analisar o código Assembly gerado pode parecer interessante, pois é “livre de influências externas” (no sentido que outros processos não irão “roubar” tempo de CPU do programa sendo observado), mas as arquiteturas podem evoluir e invalidar o resultado da análise, assim como não existe uma arquitetura definitiva. E caso você ainda não esteja convencido, C++ é só uma especificação e dois compiladores diferentes podem implementar a mesma especificação, mas apresentar resultados diferentes (onde um deles vence uma implementação Java e outro perde). Assim sendo, resta a nós analisar as facilidades que a linguagem fornece para ajudar as implementações a fazer análise do código (onde um código de alto nível que descreve intenção pode resolver o problema de forma mais performática) e facilidades que a linguagem fornece para ajudar o programador a acessar recursos da máquina (onde um código de baixo nível que descreve, por exemplo, padrões de acesso a memória, pode ser mais performático).

Mas antes de continuar, é interessante ressaltar que C++ não é a única linguagem que permite performance. Mesmo linguagens que não são focadas em performance podem incentivar modificações no código-fonte pelo bem da performance. Um exemplo é a diferença entre range e xrange no Python 2. Entretanto, C++ possui um foco bem grande em performance, tendo, por exemplo, o princípio de que “você só paga pelo que você usa”, influenciando em várias decisões da linguagem (métodos não são virtuais/polimórficos por padrão, por exemplo).

Uma característica que foi introduzida para ajudar as implementações a produzir código mais performático é a propriedade Undefined Behaviour (comumente citada somente como UB). A especificação da linguagem C++ define que as implementações são livres para se comportar de qualquer forma em alguns erros de programação específicos (que em alguns casos só podem ser detectados em tempo de execução), como acontece, por exemplo, no caso do índice em vector. Tal liberdade permite que a implementação não gere qualquer código para detecção de erro e gere código ainda mais performático. Isso torna C++ uma das linguagens em que não é encorajado que você aprenda orientado a compilar-e-observar, pois caso esbarre em UB, não há garantias de que o mesmo ocorre em diferentes compiladores (ou mesmo diferentes versões do mesmo compilador!). Torna-se até interessante que você execute os testes unitários sob a análise de “address & memory sanitizers” e talvez usando bibliotecas STL alternativas que foram projetadas para detectar UB. Recomendo ler essa questão no StackOverflow e esse post para saber mais. Esse é um exemplo onde a linguagem ajuda a implementação.

Outro exemplo onde a linguagem ajuda a implementação é a funcionalidade restrict, que é um especificador para ponteiros que informa a implementação que não ocorrerá aliasing para aquele caso. “Banir” aliasing informa que um ponteiro aponta para uma região de memória que não é apontada por nenhum outro ponteiro, então se você modifica uma porção de memória através de um outro ponteiro, não precisa se preocupar com a possibilidade dos dados apontados pelo primeiro ponteiro terem sido alterados. Veja o exemplo de código abaixo, onde, quando é sabido que aliasing não pode ocorrer, o retorno da função pode ser inferido em tempo de compilação e menos instruções Assembly são geradas. Um caso legal é a linguagem Rust, ainda em desenvolvimento, que detecta race conditions em tempo de compilação usando um modelo de estados que captura padrões de acesso/modificação interessantes e “proibe” aliasing.

Confesso que, para mim, a necessidade da palavra-chave restrict demonstra um possível mal planejamento nesse caso extremo, mas C++ é sobre performance, inclusive nos casos extremos. Felizmente linguagens como Rust estão dando um passo à frente. Um outro, dentre esses casos que vejo como “extremos”, mas imensamente mais popular, é a técnica “Empty Base Optimization”. Como essa é uma técnica que merece seu próprio post, me limito a deixar duas referências e informar que essa técnica é um grande justificador para o padrão permitir herança privada.

Há os casos onde a informação necessária para otimização não está disponível no código-fonte. Em tais casos pode-se aplicar JIT ou PGO, mas a informação definitiva ainda pode estar “nas mãos” do programador. Em tais casos onde o programador detém a informação definitiva, há o exemplo do std::vector::reserve, especificado pelo padrão do C++, e o exemplo do likely, extensão extra-oficial. Esse é um exemplo onde a linguagem ajuda o programador, especificando vocabulário para guiar as abstrações a fazerem um trabalho melhor.

“Você só paga pelo que você usa”. Não só decisões são pensadas para levar em conta o caso com menos custo, como novas abstrações são criadas para adicionar pontos de variação que permitem especializar um comportamento de acordo com o seu uso comum. Um exemplo disso é o conceito de allocators, que permite customizar algoritmos de alocação dos containers fornecidos.

E como se tudo isso não fosse o bastante, há ainda a possibilidade de mover uma pequena parte da computação para tempo de compilação através de templates (que são Turing-complete), com o uso de técnicas como “expression template“, por exemplo. Eu já usei templates até para explorar o fato do compilador eliminar código-morto em tempo de compilação (em vez de fornecer duas implementações diferentes, capturava o comportamento comum e passava o argumento booleano como argumento de template, em vez de argumento de função), mas esse é um uso desencorajado.

Você pode fazer várias modificações em código-fonte escrito em outras linguagens pelo bem da performance, mas dificilmente você encontrará um suporte a performance, nas outras linguagens, tão abrangente quanto o disponível em C++. Uma ideia que eu tenho é de usar os critérios que eu coloquei aqui para fazer a análise a fundo (biblioteca padrão, expressões, garantias da especificação que previnem código mais performático) de C++ e umas 3 outras linguagens (provavelmente Lisp e Java estariam nessa lista) para publicar algum paper.

Profiling

As otimizações mais importantes são otimizações no algoritmo, pois elas são universais. Otimizações no próprio código podem ficar “obsoletas”, no sentido que os compiladores e arquiteturas de computadores podem evoluir e deixar a sua “otimização” inútil (ou até pior!). Para acompanhar a evolução, é interessante implementar a versão correta do algoritmo primeiro e compará-la contra suas otimizações. Esse é o papel do profiler, desmistificar “preconceitos” e “superstições” que o programador tenha.

Uma outra utilidade para o profiler é aumentar a eficiência do programador que está interessado em otimizar o código, pois o profiler não só dará informações úteis para realizar as otimizações, como também dará, por exemplo, a informação de que pedaço do código é usado 90% do tempo, ajudando o programador a focar na parte que importa.

Há a palestra Three Optimization Tips for C++, do Andrei Alexandrescu, onde ele usa frases como “measuring gives you a leg up on experts who don’t need to measure” e “you can’t improve what you can’t measure”, além de discutir “dicas/exemplos incomuns”.

Em questão de ferramentas para fazer profiling, há o sempre citado conjunto de ferramentas do projeto Valgrind, a ferramenta pahole e muitas outras. Para tarefas muito simples, pode ser que uma solução feita por você possa funcionar bem, enquanto para algumas outras tarefas, você vai ter que pesquisar até encontrar a esotérica ferramenta capaz de lhe ajudar.

A arte de realizar benchmarks pode não ser óbvia, muitas vezes.

Assembly

Não, você não vai programar em Assembly, mas benchmarks podem ser influenciados por diversos fatores e uma informação que não mente é o código-fonte em Assembly. Você vai querer usar Assembly para saber se há alguma abstração que seu compilador não está otimizando bem, alguma otimização sua que é contraprodutiva ou alguma funcionalidade da arquitetura que está deixando de ser utilizada (como vetorização, por exemplo). Há até os momentos onde o compilador pode ter um bug e a última peça para confirmar a informação está no código-fonte Assembly.

Há a palestra Preparing the GNU/Linux for 64-Bit ARM Processors, onde o Jon “Maddog” Hall comenta o caso dos programadores do X, que conheciam tão bem o compilador GCC, que quando um grupo tentou usar um compilador alternativo, que normalmente gerava código 30% mais eficiente, o ganho foi zero (termo que o Maddog usou).

Eu demorei um tempo para entender Assembly e só acabei aprendendo depois que fiz um curso de compiladores no Coursera. Eu não sou um bom programador de Assembly, mas minha recomendação para quem quiser aprender e ainda não sabe de nada é fazer um curso de compiladores e outro de sistemas operacionais.

Eu deveria ter preparado mais referências para essa seção, mas quando elas primeiro me cruzaram, eu não estava planejando escrever esse texto, então eu as perdi. Caso você tenha algum relato interessante, contribua na seção de comentários.

Branch misprediction

Com a evolução dos computadores, a performance da CPU foi uma das que mais evoluiu, e evoluiu muito mais do que a performance de acesso a memória. Para lidar com o problema, arquiteturas modernas fazem o uso de várias técnicas para continuar alimentando o monstro que é a CPU a todo o momento.

Uma das técnicas utilizadas é o uso de cache (e write buffers) para evitar acesso a memória quando o valor tiver sido recentemente utilizado. Os caches costumam estar próximos a CPU, terem baixa latência para serem acessados e pouco espaço para armazenamento. O termo cache locality é normalmente usado para se mencionar um algoritmo que faça todas as computações com o dado antes de prosseguir para o próximo.

A performance da memória foi evoluindo mais com o aumento da largura de dados do que com a diminuição da latência. Capturar um dado continua sendo caro, mas através de outra técnica, prefetch, que se resume ao sistema tentar prever qual o próximo de bloco de memória que tornar-se-á necessário e requisitá-lo antes do tempo (à lá AOT), esse custo aparece com menos frequência. Essa otimização em arquiteturas de computadores modernas beneficia algoritmos que possuem padrões de acesso a memória mais fáceis de prever.

Esses comportamentos de arquiteturas modernas de computadores são úteis para realizar várias otimizações, mas para essa seção, o efeito que quero comentar é o efeito de branch misprediction.

Não só os próximos blocos de memória para dados são requisitados antes do tempo, como também os próximos blocos de memória contendo instruções também o são. Normalmente as instruções são executadas na ordem em que estão armazenadas, tornando fácil de fazer a previsão. Uma das instruções que quebra essa ordem é o pulo incondicional (para chamada de subrotinas, por exemplo), mas esse também é fácil de prever.

O efeito de branch misprediction torna-se possível quando há um pulo condicional (um loop, um if…). Se das últimas vezes a instrução sempre entrou no “bloco true”, o prefetcher pode escolher pré-carregar o bloco true na próxima oportunidade. Se a predição estiver correta, ótimo. Se o prefetcher prever errado, a CPU vai ter que parar para esperar uma das instruções mais caras terminar de executar: acesso a memória.

Eu já cometi o erro de otimizações contraprodutivas explorando multiplicação por um booleano para evitar branch misprediction. Acontece que existe, para algumas arquiteturas, a instrução CMOV, que condicionalmente move um valor. Não existe pulo de instrução nenhum e o código é mais fácil de ser analisado pelo prefetcher, evitando uma ocorrência de branch misprediction. Então nada de ficar reimplementando as funções max, min e outras em um namespace branchless. Você tem que ficar de olho é em código-fonte cujas ramificações tenham código complexo. Em caso de dúvida sobre o comportamento, verifique o código Assembly gerado.

Há essa grande resposta do StackOverflow sobre branch misprediction para quem ainda quiser saber mais.

Padrão de acesso a memória

Graças a forma como arquiteturas de computadores modernas se comportam, você pode estar interessado em mudar o algoritmo para que ele itere sobre os dados em uma ordem diferente. As ideias por trás das otimizações das arquiteturas modernas são simples de entender, mas o custo de ignorá-las pode parecer muito abstrato e as formas de explorá-las podem acabar sendo bem criativas.

O assunto me lembra padrões de projetos orientado a objetos, onde você pode explicar o básico, mas as pessoas podem continuar se surpreendendo com as formas criativas que são usadas para explorar esses conceitos básicos. Há duas palestras muito boas sobre o tópico para as quais eu não acho que eu seria tão bom quanto tentando expor o assunto. Essas excelentes palestras são:

Assuntos polêmicos

Garbage collection tem desempenho melhor, pois aloca memória em grandes blocos

Costumo encontrar o argumento de que Garbage Collection pode melhorar a performance, evitando alocação e desalocação de vários objetos pequenos com frequência. Bom, se esse argumento for verdade, desde o C++11, é liberado o uso de implementações que façam uso de Garbage Collection, mas vou discutir isso depois, pois a crítica não é a ausência de Garbage Collection, mas sim o algoritmo de alocação.

Normalmente você evita alocar na heap e costuma usar a stack, pois trabalhar na stack se resume, em níveis de implementação, a manipular o ponteiro da stack, que é uma operação muito barata. Normalmente você só usa a heap para (1) objetos cujo tamanho não são conhecidos até que recebam a entrada do mundo externo e (2) para objetos cujo tempo de vida excedem o escopo da função. É comum usar a heap, mas não se costuma usar a heap para objetos pequenos e que têm o tempo de vida limitado ao escopo da função.

Em resposta a quando o problema de desempenho é o algoritmo de alocação, C++ permite, sem recorrer a GC, customizar esse algoritmo usando allocators e até sobrecarregar os operadores new e delete.

Em resposta ao argumento de Garbage Collection (e não algoritmo de alocação) ser mais rápido, no modelo RAII, a implementação já possui a informação de quando um recurso torna-se inválido e pode ser liberado, então como pode ser mais eficiente jogar essa informação fora e, forçadamente em tempo de execução, executar um algoritmo para recuperar a informação que já existia antes? E para aumentar a crítica, os algoritmos de GC costumam não possuir tanta informação sobre o ambiente (daí que vêm os algoritmos conservadores de GC), o que impede que eles possam dar garantia de que sequer os recursos serão liberados (a principal diferença semântica entre destrutores e finalizadores) e pode até dar uma base de dados para computar maior, o que torna a tarefa ainda mais custosa. Parece haver um problema de lógica no argumento, mas para aumentar ainda mais a crítica, o modelo RAII é mais amigável ao cache, pois expõe um modelo que faz objetos que são usados em tempos de uso similares serem alocados próximos uns dos outros.

Um outro argumento a favor de GC é que há o custo de chamada de função. Num mundo GC, vários objetos são coletados com uma chamada de função, mas no mundo RAII, o custo de chamada de função se acumula. Então, seguindo essa lógica, o tempo total (amortizado) para GC seria menor, enquanto que seu tempo de resposta seria pior, pois quando o GC entrasse em ação, muito tempo seria gasto na liberação de recursos. Para melhor discutir esse argumento, precisamos separar os conceitos de alocação e construção de recursos, que se referem a obter uma região de memória para o objeto e colocar o objeto em um estado válido, respectivamente. C++ permite construção (e destrução) barata em vários casos (leia sobre inline e POD), mas no que se refere a alocação, esse argumento está correto. Chamadas de objetos individuais são feitas para a função free. Funções alternativas a malloc/free que aloquem grandes blocos de memória não podem escapar desse comportamento na hora de desalocar.

Daí a questão se torna, “será que o gargalo do algoritmo de GC é mais barato que a soma das várias chamadas extras de funções para desalocação”. Para responder essa questão de forma genérica, muita abstração é necessária, dificultando o trabalho para respondê-la. Mesmo na versão fácil, onde só considerarmos uma comparação direta entre duas implementações específicas, há trabalho que eu não quero fazer para responder uma única pergunta, que nem é objetivo central desse texto. O que eu posso comentar para não fazer esse parágrafo lhe desapontar tanto, é que se você tem um std::vector com 100 elementos, quando ele for destruído, apenas uma chamada a função de desalocação será feita para os 100 elementos. C++ lhe dá o controle, e com ele você pode otimizar. E para você não ficar com a impressão de que eu sou um programador desinformado, quero adicionar que sim, eu sei que o custo de chamada de funções é barato, normalmente negligenciável.

Há também os projetos de embarcados usando microcontroladores, nos quais você não verá o uso de linguagens Garbage Collected com frequência. Usar uma implementação que se apoie unicamente em GC para, por exemplo, reproduzir áudio, pode ser uma ideia colossalmente estúpida.

Exceções são lentas

Os velhos comentam que as primeiras implementações de tratamento de exceções em C++ eram lentas e esse fato contribuiu para a aversão que alguns programadores possam ter em tratar erros usando exceções. O documento TR18015 detalha duas abordagens principais para a implementação de suporte a exceções e o que o documento menciona como “abordagem tabela” é muito barata, realizando boa parte do que precisa ser computado em tempo de compilação e estruturando o código de forma que não há penalidade em tempo de execução para o fluxo de execução normal do programa. O custo, nessa abordagem, é que o programa fica maior, mas a parte extra pode ser movida para não interferir negativamente no uso de cache e, em sistemas com suporte a memória virtual, essa parte pode até ficar na swap até que torne-se necessária.

uma resposta no StackOverflow, caso você não queira se dar ao trabalho de passar pelo TR18015. A implementação do suporte a exceções é bem elegante e a discussão deveria deixar de ser se exceções são lentas e passar a ser quando usar exceções.

E cuidado com os benchmarks injustos que alimentem esse mito, assim como o P. alerta.

Algoritmos

E finalmente, mesmo explorando várias possibilidades disponíveis em C++, que dificilmente você encontrará em outras linguagens, ainda resta a opção de melhorar o próprio algoritmo para fazer seu código-fonte executar mais rápido. Estudando o algoritmo a fundo talvez você encontre meios de eliminar operações devido a características especiais de como as diferentes partes são combinadas, a entrada do programa ou outros. Talvez você encontre um algoritmo que se ajuste melhor ao caso comum da sua entrada.

Em códigos-fonte que escrevi, eu já cheguei a mesclar duas etapas em uma para evitar uma segunda passagem sobre os dados, eliminando o custo de incrementar o iterador uma segunda vez para cada elemento do container (e ao mesmo tempo fazendo melhor uso do cache, ao acessar elementos enquanto ainda estão “quentes”). Um tapa na cara da filosofia UNIX.

Hardwares especiais

C++ é certamente uma ótima linguagem para alcançar uma implementação eficiente de qualquer algoritmo para rodar em sua CPU, mas há hardwares dedicados e de propósito específico para os quais não usamos C++. Para explorarmos um sistema gráfico 3D, possivelmente otimizado por uma GPU, usaremos OpenGL/GLSL. Para explorarmos GPGPUs, usaremos OpenCL (padrão aberto dominante) ou CUDA (padrão proprietário dominante). E há ainda outras tecnologias que você talvez vá precisar aprender tais como FPGA, Verilog e VHDL. Eu não posso estender muito o tópico, pois ainda estou bastante preso na terra do C++, mas talvez em um futuro post eu o faça. Mas ao menos eu já mexi com Arduino, e no Arduino, você ainda vai usar C++.

Eu li em algum lugar que a galera que não pode dispor de um ambiente de computação real time (que inclui o kernel) costuma comprar hardware que implemente a interface MIDI e controlá-lo via software, possivelmente escrito em C++, para criar músicas ao vivo.

Para quem quiser seguir essa estrada, pode ser interessante verificar o laptop Novena.

Comparação com outras linguagens

Se você mostrar o código Assembly para uma função de soma feito na linguagem X, que é tão bom quanto o código Assembly equivalente para C++ e tentar argumentar que isso torna sua linguagem tão performática quanto C++… bom, se nem para esse exemplo, que estressa tão pouco técnicas de performance, a sua linguagem se comparasse a C++, ela seria humilhada em situações mais complexas.

E sua linguagem não ter foco em performance NÃO é ruim. É legal que a implementação da sua linguagem seja rápida ou tão rápida quanto possível dentro de sua proposta, mas se o foco da sua linguagem é segurança, então é sobre a segurança de sua linguagem que você deveria estar fazendo propaganda… não sobre performance. Eu fui teimoso por bastante tempo e demorei a ser mais pragmático.

Conclusão

Se você está seriamente preocupado com performance, você vai precisar aperfeiçoar suas habilidades em múltiplas áreas em vez de ter um falso senso de trabalho bem feito ao aplicar uma única dica que você aprendeu no único texto sobre otimização que leu na vida, otimizando a função que só é chamada uma vez durante toda a vida útil do processo ou aproveitando seus conhecimentos sobre o domínio da aplicação. A chave para o sucesso é a combinação de todas as relevantes áreas.

Esse texto ficou tão grande que eu fico imaginando se há alguém paciente para lê-lo por completo.

%d blogueiros gostam disto: