Tag Archive | C++

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.

Showtime: library to be proposed as Boost.Http!

It’s been two months already since my last post on this blog. All this time (and more), I’ve been (among other tasks) working on my 2014 GSoC project, an HTTP server proposal to Boost. I’ve finally reached a point where I feel it’s ready for major review/feedback.

If you’re a C++ programmer, a native speaker or an HTTP researcher (or just a little of everything) and you want to help, I’d like to ask you to review the project (interface-wise) and give me feedback.

You can find all the documentation and code at github.

Experience

This isn’t my first time on GSoC, but the experience was very different. The communities, development model, targeted audience, knowledge domain, to name a few, were completely different. Also, this year’s project wasn’t as challenging as the last one (although this is very subjective).

I improved as a programmer, but this is limiting. Once you become able to write algorithms for turing-machine compatible devices, there isn’t much room for improvement and you need to hunt other skills to continue improving (e.g. security, parallelism…). Coding for the sake of coding solves no problems. I decided to take a break (not exactly now, but in a few weeks) to make a shift and start to increase the efforts I dedicate to my academic skills.

Next step

I aim to integrate this library into Boost, so I still want to invest effort in this project.

Arquivos portáveis, protocolos portáveis… em C!

Um hábito que me faz desprezar imediatamente TODAS as habilidades que um programador afirme ter, é ele fazer um formato de arquivo ou protocolo binário que não é portável, então resolvi fazer esse artigo para ajudar a diminuir essa prática, expondo os seus perigos.

Mas antes, lembro que na época que eu usava Flash Player, eu era um usuário burro e aceitava cegamente a desculpa das versões de diferentes sistemas operacionais serem dessincronizadas (sistema operacional X recebe versão nova antes de Y e Z, em vez de lançamento simultâneo). Isso é um ato que eu até consigo entender tendo em mente os objetivos da empresa, mas outro lugar onde a dessincronização de versões ocorria era em arquiteturas diferentes (32bit e 64bit). E o único fator para justificar isso é pura incompetência dos programadores, que ganharam para sempre o meu desprezo. Dito isso, não acompanho ou uso mais o Flash Player e não sei se esse problema já foi corrigido.

Para não comentarem que sou extremista e só exponho os erros técnicos de softwares proprietários, aqui e aqui você vai encontrar um erro que pode ocasionar o mesmo problema, no futuro, mas é completamente ignorado, no projeto Enlightenment, que é software livre. Aliás, eu nem posso afirmar que expus erros técnicos do software Flash Player, pois é assim que funciona com software proprietário, você simplesmente não sabe.

Citando, para motivos de reflexão, antes do começar a parte séria do texto, a frase de alguns padrões da IETF, em tradução livre: “seja liberal no que você aceita, mas conservador no que você produz”.

Fluxos de bytes binários

O computador trabalha usando binários, mas esse fato é abstraído na linguagem de programação e esquecemos isso enquanto estamos focando no problema que queremos resolver de verdade, em vez de ficarmos nos preocupando com o opcode da instrução da arquitetura do processador que é necessária para implementar várias camadas de algoritmos até chegar no problema que realmente queremos resolver. Entretanto, quando é hora de fazer o programa se comunicar com o mundo externo, através de arquivos ou sockets, é hora de nos preocuparmos com a representação interna das estruturas do programa, pois nesse momento elas importam.

<stdint.h> e <inttypes.h>

Começando pelo mais simples, C não exige/garante que os tipos short, int, long, long long tenham a mesma quantidade de bits para todas implementações, ou mesmo que o tipo char tenha sinal. Isso significa que se você fizer um programa que leia um long de um arquivo ou da rede, você está errado. Quando você compilar o seu programa em uma implementação que usa um long de 32 bits, ele não se comunicará adequadamente com o mesmo programa compilado em uma implementação que usa um long de 64 bits, pois a estrutura de fluxo de bytes que ele gera não é definida e varia de implementação para implementação.

A solução para esse problema é você usar tipos para os quais existe a garantia de tamanho específico, independente de implementação. Se um compilador não cumprir com esse requisito, ele não é um compilador da linguagem C, pois ele não cumpre com a especificação da linguagem. Esses inteiros estão disponíveis nos cabeçalhos <stdint.h> e <inttypes.h>. O cabeçalho <stdint.h> possui todos os nomes necessário para declarar inteiros de tamanho fixo, enquanto o <inttypes.h>, além dos nomes introduzidos pelo <stdint.h>, introduz nomes para ajudar a trabalhar com printf, scanf e conversões entre strings e inteiros de tamanho fixo.

Mais uma coisa a aprender é que o padrão mais comum para representar números negativos usando binários é o complemento de 2, mas a especificação da linguagem não exige/garante o padrão por trás do mesmo e, inclusive, define integer overflow como undefined behaviour. Mas nada tema, pois o padrão exige que os inteiros com sinal declarados no cabeçalho <stdint.h> sejam armazenados usando complemento de dois. Então se você está seguindo as soluções até aqui, você já se livrou do problema.

Uma última nota que tenho a adicionar é: só use inteiros de tamanho fixo quando eles forem necessários.

Ordem dos bytes

Outro problema que atinge a portabilidade do fluxo de bytes é que não há garantias em relação a ordem dos bytes que compõem um mesmo inteiro. Isto é, em 16 bits, é legal representar 16 bits como 0000’0001’0000’0000 ou 0000’0000’0000’0001. As duas ordenações que costumamos encontrar são Little Endian e Big Endian (também conhecido com Network Byte Order).

Não há solução embutida na especificação da linguagem C para esse problema, então você vai ter que implementar suas funções ou usar alguma biblioteca externa como essa ou essa.

EBML/Matroska

Um formato que eu quero citar brevemente, pois possui uma característica que eu acho bem legal, é o EBML. O EBML é binário e possui uma representação eficiente, sendo usado, por exemplo, no formato de arquivo Matroska. Mas o EBML é também extensível, o que me dá confiança para acreditar que não seria surpresa continuarmos a utilizar esse formato por, sei lá, mais 20 anos.

Imagine que lhe seja dada a tarefa de criar uma representação binária para datas. Você decide especificar a quantidade de bits necessários para dias (que variam entre 1 e 31) e meses, mas chega então no problema de especificar a representação para armazenar o ano. Você sente a vontade de especificar um tamanho fixo grande o suficiente para que o problema não seja exposto enquanto você estiver vivo, mas algo dentro de você grita para que você lute e acabe com o problema. Esse algo dentro de você, gritando para que você resolva o problema, se chama competência. Você decide usar caracteres ASCII no topo do formato binário, para usar texto e ter uma quantidade infinita de caracteres, que pode ser usada para representar qualquer data, mas surge a questão de como definir o tamanho para armazenar essa cadeia de caracteres. Se você especificar um inteiro de 32 bits ou qualquer outro tamanho no começo da sequência, a representação continuará limitada.

A linguagem C define cadeias de caracteres de tamanho arbitrários (na verdade, ainda limitados pelo intervalo enumerável dos ponteiros) através de um delimitador no final da sequência. A mesma solução de usar um delimitador pode ser trazida ao universo dos inteiros binários e, de fato, é usada no formato EBML. Vale ressaltar que o EBML não sofre o gargalo e ineficiência de usar caracteres ASCII convertidos lexicalmente (no sentido do lexical_cast existente na Boost) para inteiros em sua representação.

Baseado em texto puro (legível por humanos)

Não, seus problemas não acabam com você indo para texto puro! Mas nada tema, pois você usa uma linguagem que requer a presença de acentos, está usando um locale diferente do padrão e já possui vantagem sobre outros programadores, detectando mais cedo qualquer quebra de internacionalização!

Se o fluxo de bytes que você está definindo é baseado em texto puro, você deve responder algumas perguntas como “o conjunto de caracteres ASCII é suficiente?”, “como adicionar estrutura de uma forma extensível?” e “dados binários serão suficientes?”.

O primeiro problema a resolver é que, caso abra um arquivo em modo de texto, em C, o final de linha será interceptado e convertido, a depender do sistema operacional (“\n” no sistema pai, o Unix, “\r\n” no Windows e “\r” no sistema da empresa que gosta de quebrar padrões para eventualmente causar dependência). Então, ou você escolhe e usa apenas uma dessas opções (como acontece com o HTTP), ou se prepara para tratar todas elas (como acontece com o gcc e editores de texto decentes). Mas um comportamento deve ser definido (assim como suas consequências refletidas) e a implementação deve cumprir com tal.

Se eventualmente for necessário adicionar suporte a dados binários, pesquise pelos padrões base64 e base91 e faça preparativos para que não haja conflitos de caracteres especiais sendo utilizados em áreas diferentes das planejadas.

Se o conjunto de caracteres ASCII não for suficiente, use Unicode. Vou apenas lhe informar para começar por aqui.

Problemas em XML e arquivos estruturados em geral

O XML é um formato de arquivo que carrega a palavra extensibilidade em seu nome (eXtensible Markup Language) e ele é bastante usado em alguns locais onde manter interoperabilidade é um requisito importante. Os problemas que podem aparecer aqui não são de baixo nível, específicos de arquitetura de computadores ou da linguagem C, mas já que comecei a comentar sobre interoperabilidade, decidi estender o texto e fugir do escopo inicial só um pouco.

Um problema que costuma afetar o XML e formatos estruturados como um todo, é que algumas implementações, não-conformantes, costumam usar a estratégia ingênua de mapear o arquivo para suas próprias estruturas e trabalhar daí, em vez de manipular o arquivo original. Acontece que normalmente essa estratégia ingênua irá descartar todos os atributos, tags, elementos e por aí vai do arquivo original, que não forem reconhecidas pela implementação. Isso aconteceu com algumas implementações do ODF e houve até a teoria conspiratória que a infratora tentava minar o padrão.

Mesmo que você argumente em optar pela abordagem ingênua, por sua implementação suportar todos os nomes definidos na especificação, você deve ter em mente que formatos evoluem e extensões são adicionadas no topo do formato original (isso acontece com o OpenGL, com o XML SVG do Inkscape e em tantos outros por aí).

Uma abordagem mais legal do que criar abstrações que retornam o elemento processado (que só contém as propriedades que a implementação conhece), é criar abstrações que realizem operações em cima da representação original, como acontece com a API do MongoDB, onde você só especifica os atributos que devem ser modificados, mas os atributos não-especificados continuam a existir.

Caso você não seja um guerreiro incorruptível e se desvie do caminho correto, pelo menos tenha a decência de explicitamente proibir, na especificação do padrão, o uso de propriedades adicionais. Tal exigência pode ser especificada como “additionalProperties: false” em JSON Schema.

Final

No final do texto eu fiquei com preguiça e passei a só explicar quais deveriam ser suas preocupações, adicionando referências para você pesquisar mais. Foi diferente do começo do texto, onde eu estava com paciência até para explicar os problemas com detalhes.

Se eu esqueci de alguma coisa ou você tem alguma informação relevante a acrescentar, comente!

GSoC 2014/Boost

I was accepted for GSoC 2014 and I’ll be working on the Boost project.

I created a new category on this blog to track the progress, so you’ll be able to have a separate rss feed for these posts. The new category URL is http://vinipsmaker.wordpress.com/category/computacao/gsoc2014-boost/.

Meu erro favorito de C/C++: Falha de segmentação

Resolvi criar esse curto post para comentar sobre qual o meu erro favorito na linguagem de programação C, que na minha universidade é relativamente comum devido a ela ser a linguagem usada para introduzir os alunos ao universo da programação.

O quê?

O erro falha de segmentação acontece, principalmente, quando você desreferencia um ponteiro inválido. Quando uma falha de segmentação acontece, o programa é encerrado imediatamente.

Por quê?

Esse é o meu erro favorito, pois quando esse é o erro com o qual você se depara, provavelmente não irá gastar muito tempo com o mesmo.

Tudo que você precisa para identificar exatamente esse erro é (1) identificar o conjunto de ações que ocasionará a falha de segmentação, (2) executar o programa através de um depurador e (3) fazer o backtrace, que lhe dará toda a corrente de chamadas de funções que provocou a falha de segmentação, apontando exatamente para a linha de código que ocasionou o problema, além de outras informações úteis como o valor de cada variável.

Perspectiva

Talvez ironicamente o meu erro favorito é o que eu menos presencio. Dependendo de como eu veja, isso pode ser algo bom (eu me tornei um programador melhor) ou algo ruim (as coisas que eu gosto vão embora), mas uma informação que contribui para o valor desse post é o provável verdadeiro motivo desse fato: Eu uso C++. Com C++, eu raramente utilizo ponteiros (que normalmente são substituídos por referências e, quando gerenciamento manual de memória torna-se necessário, por smart pointers), eliminando grande parte das falhas de segmentação.

Uma questão de perspectiva também é que para as pessoas que não conhecem um depurador, esse pode ser um dos erros mais chatos, não o favorito (como eu acho que seja).

O contra-ataque!

(essa seção foi adicionada a pedido dos leitores, 2 dias após o artigo ser publicado)

Eu criei o seguinte código-fonte que apresenta um erro. De acordo com o padrão de C++ o seu comportamento é indefinido e o compilador tem a liberdade de fazer elefantes rosas aparecerem na tela do seu computador sem perder o título de “compilador de C++”. Entretanto, o que provavelmente irá ocorrer é uma falha de segmentação. Baixe o código-fonte e siga para a próxima etapa, onde irei mostrar como erros desse tipo podem ser descobertos de forma simples.

EDIT(2014/02/23): Eu sempre achei que o texto abaixo seria confuso, pois não representava precisamente como uma sessão do gdb realmente é, então, devido (1) a isso e (2) a descoberta do asciinema, resolvi adicionar mais esse pequeno texto no artigo. Basicamente, recomendo que você veja esse asciicast no asciinema antes de prosseguir para os detalhes.

O primeiro passo é compilar o programa junto com as informações de depuração. Leia o manual do seu compilador para descobrir como fazer isso. Caso utilize uma IDE ou qualquer outro intermediário para compilar o programa, provavelmente isso pode ser feito escolhendo um perfil de debug. No gcc, a opção que habilita os símbolos de depuração é a opção “-g”:

Após isso você pode executar o programa através de um depurador e ficar brincando com o programa até o erro acontecer. Aqui, utilizo o gdb, sem nenhuma interface:

Após o gdb iniciado, você presenciará sua saída padrão, que é algo parecido com o texto a seguir:

Dentro da interface do gdb, execute o comando “run” e brinque com o programa até o erro acontecer. No meu caso a saída foi essa:

Voltando a interface do gdb, após o programa ter “crashado”, os dois principais comandos para navegar na pilha de execução são “backtrace” e “frame”, que, respectivamente, mostram a pilha de execução e escolhem um frame/instante na pilha/linha-de-execução.

E assim descobrimos, usando o gdb, que o programa travou exatamente na linha 42, após a função ler_clientes ter sido chamada pela função main. Podemos usar o comando “print” para imprimir o valor de variáveis/expressões que sejam válidas no contexto.

E assim descobrimos que há um ponteiro inválido na memória e o programa “crashou” quando tentamos acessá-lo. As duas opções a partir de agora são (1) examinar o código e descobrir que código inseriu um ponteiro inválido em memória ou (2) continuar usando o auxílio do gdb para descobrir a fonte do erro. Como o código é muito simples, é fácil ver que eu “esqueci” de inicializar o ponteiro dos objetos que são inseridos na variável “clientes” (isso, é claro, só é fácil depois que já descobrimos qual é o erro com a ajuda do gdb).

Caso você queira continuar a usar a ajuda do gdb para inspecionar o estado do programa em tempo de execução, os próximos comandos que seriam lhe úteis seriam “watch”, “break”, “step” e “continue”.

Para referência, deixo abaixo o resto de minha sessão do gdb, onde continuo examinando o programa até descobrir que código faz a inserção de um ponteiro inválido. E recomendo que você já tenha executado o gdb nesse momento, ou então irá ver esse monte de texto e não vai entender nada, achando que é algo muito difícil…

Algo que quero destacar é que o código-fonte é de “um programa em desenvolvimento” e, consequentemente, bem curto. Mas reflita sobre o que aconteceria se ele fosse grande (4000 linhas ou algo parecido). Usando o gdb, o processo de encontrar o erro seria o mesmo, bem fácil.

Avaliação curto-circuito

Existem alguns conceitos de linguagens de programação úteis, mas que são tão simples que se tornam um “tabu”. Você não presenciará veteranos discutindo tais assuntos, pois não há nada há se discutir de tão simples que são, mas são conceitos úteis que deveriam ser disseminados para os novatos desse universo. Um desses conceitos é, dentro do pedaço de universo com o qual eu tenho mais contato, o conceito de avaliação curto-circuito.

Esse conceito se refere a propriedade que alguns operadores possuem. Tal propriedade garante uma ordem de avaliação e que, quando for desnecessário continuar a avaliação para descobrir o resultado, ela será interrompida. É chegado o momento… para um exemplo!

A saída da função g, do exemplo anterior, usa o operador lógico binário && (AND) e sua saída independe da propriedade de avaliação curto-circuito. A tabela a seguir resume as saídas possíveis:

a f(b) g(a,b)
false ? false
true ? ?

A partir da tabela anterior é possível perceber que, caso o valor de a seja false, não precisamos avaliar a expressão f(b). Avaliar, avaliar e avaliar é a ideia-chave para entender a avaliação curto-circuito. O que avaliar a expressão f(b) significa? Se a (sub-)expressão não possuir efeitos colaterais, não faz diferença. Que tal refletir sobre o comportamento de código a seguir?

O código do exemplo anterior explora o fato do operador lógico binário && garantir avaliação curto-circuito. Na verdade, esse é um truque bem comum de encontrar em “códigos de verdade”. Graças a avaliação curto-circuito, é garantido que a sub-expressão val->answer != 42 não será avaliada caso val == NULL. Eu tenho bastante confiança de que você já entendeu a importância da avaliação curto-circuito nesse exemplo, mas para o caso de esse texto estar sendo lido por alguém que entrou muito recentemente no mundo da programação (ou no mundo da programação em C), vou explicar mais profundamente: a sub-expressão val->answer faz um desreferenciamento de ponteiro e, caso val == NULL, a expressão irá gerar um erro em tempo de execução (provavelmente a aplicação vai fechar imediatamente), mas isso não ocorrerá graças a avaliação curto-circuito.

Antes de explorar as consequências desse importante conceito no desempenho da aplicação, uma expansão do exemplo anterior para reforçar a ideia:

Desempenho

Essa seção é só um alerta para o caso de você, paranoico por desempenho, ter sido estimulado a preferir (ou o contrário) os operadores que garantem avaliação curto-circuito para atingir o máximo de desempenho.

A primeira observação que podemos fazer é que o caminho de execução no caso desses operadores será diferente, pois algumas vezes ele será mais curto devido a não-necessidade de avaliar algumas sub-expressões. Menos passos de execução significa que o trabalho é feito mais rápido, afinal isso é o básico de análise de algoritmos, certo? Errado! Só porque algo é teoricamente mais rápido, não quer dizer que na prática vai executar mais rápido, pois (1) a teoria que você usou pode não estar modelando todas as partes importantes do sistema ou (2) algumas instruções podem ter custos maiores (acesso a memória, por exemplo). Um fator que deve ser considerado é a predição de qual ramo será executado.

Eu acabo de fazer algo terrível. Eu introduzi outro conceito a um possível leitor maniaco por desempenho que sacrificará legibilidade de código por código possivelmente mais rápido. Caso isso tenha acontecido, sugiro que você cave mais fundo e pesquise pelas instruções cmov. São instruções que condicionalmente movem um valor e livram o programa da necessidade de realizar um pulo condicional. Isso significa que se você cegamente tentar otimizar o código removendo caminhos (e pulos de instruções), é possível que seu código execute mais lento que um código limpo e claro escrito por alguém que não está preocupado com desempenho.

Uma última observação é que o compilador (e não você!), quando possuir acesso a todos os códigos necessários, saberá qual a melhor decisão a tomar. Sempre use um profiler (coisa que eu deveria estar fazendo)!

OFF-TOPIC

Bom, já que se foi discutido sobre a (não) avaliação de expressões, vou citar uma proposta legal para o próximo padrão do C++ que permitiria eliminar a reavaliação de (mais algumas) sub-expressões comuns: http://isocpp.org/files/papers/n3744.pdf

C++’s best feature

Vinipsmaker:

I think I could make a beautiful XML construction code exploring this feature. I wish some scripting language adopt this feature.

Postado originalmente em Andrzej's C++ blog:

C++, if you want to learn all of it, is big, difficult and tricky. If you look at what some people do with it, you might get scared. New features are being added. It takes years to learn every corner of the language.

But you do not need to learn all of it. Effective use of C++ requires only the knowledge of a couple of its essential features. In this post, I am going to write about one C++ feature that I consider one of the most important. The one that makes me choose C++ rather than other popular programming languages.

Ver original 2.062 mais palavras

%d blogueiros gostam disto: