Arquivo de Tag | C++

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

Splines extraction on Kopf-Lischinski algorithm, part 0

Introduction

This post is a continuation of “Splines extraction on Kopf-Lischinski algorithm, part 1“. The title contains “part 0″, because the algorithm step described here should be executed before the algorithm step described in “part 1″.

This blog post is kind of unstructured, but don’t worry, because I’m aware of that and is intentional.

Generalized Voronoi diagram generation

The algorithm described in this section was kind of documented already, but the documentation wasn’t good enough to be part of a post, then it was keep as a private home-made PDF.

Well, a Voronoi diagram is a black box where you put some points (the seeds) and you get some polygons (the cells). Each polygon contains all points that are closer to its seed than any other seed. There is a good article on Wikipédia and I won’t explain any further.

Kopf-Lischinski algorithm executes a bunch of operations on a graph and it uses a Voronoi diagrams to extract a visual representation from this graph. The simplest form of a Voronoi diagram works with 2D points-seeds, but we have higher-dimentional Voronoi diagrams, Voronoi diagrams using different distance functions and even Voronoi diagrams using complex non-points seeds. We are interested in these Voronoi diagrams using complex non-points seeds.

The below image has a representation of the output graph of the Kopf-Lischinski algorithm and its Voronoi diagram representation. The graph nodes are represented by circles, where nodes with the same color are similar and usually are connected. The connections of the nodes are represented by green lines.

An accurate generalized Voronoi diagram

An accurate generalized Voronoi diagram

The generalized Voronoi diagram is visual, then there is no special meaning to explain it in the previous image. The seeds of this diagram aren’t points, they are line segments. You just need to break a green line in two and add each half to its containing cell. You can note that some polygons aren’t convex.

The graph used as input has certain constraints that enable us to use some simple and fast operations instead of a full-featured and complex algorithm.

If a Voronoi cell is a polygon containing all points that are closer to its seed than any other seed, we can determine the edge of a Voronoi cell by the midpoint of two adjacent seeds. If we generate a vertex for each of its 8 directions, we will get an accurate Voronoi diagram.

A simplified generalized Voronoi diagram

A simplified generalized Voronoi diagram

We can get a simplified Voronoi diagram by forgetting about the top, bottom, left and right vertices (if we just generate the diagonal vertices). The simplified version doesn’t contain concave polygons.

The act of generating diagonal vertices is more complex than the act of generating the other vertices. We need to check if there is a connection with the other cell and, if this connection exists, generate two vertices. If the connection doesn’t exist, we generate a single vertex, but its position depends on the existence of a connection between its neighbors. Look the following figure.

A simplified generalized Voronoi diagram (detailed)

A simplified generalized Voronoi diagram (detailed)

All information we need to generate the Voronoi diagram is located within its neighbors and the only extra tool we need to generate the points is the midpoint procedure. This is old news and it was already implemented in libdepixelize.

Metadata extraction

When we generate B-Splines using Kopf-Lischinski algorithm we need a way to separate points that create sharp corners and smooth points. The Kopf-Lischinski algorithm has techniques just to handle this issue. In libdepixelize, I decided to merge the point smoothness computation and Voronoi generation in one single phase. This is the phase where we can gather lot of info about the graph and we can propagate the smoothness data to later phases.

One note about the algorithm of this “metadata extraction” section is that some points will disappear during polygon union and we don’t care if the metadata about these points are accurate, then we can simplify the algorithm exploring this property. The below image will be citated all time during this time to how explain this algorithm:

Vertex types

Vertex types

There are two types of vertices generated in this special Voronoi diagram:

  • White type: The type of the one labelled with “#1″. Node “#1″ is contained by three cells, one purple and two yellows. The two yellow cells will be merged during polygon-union. There are two possibilities for the remaining cell in this kind of node:
    • When it has the same color. Then the node will disappear during polygon-union and we don’t care about its “smoothness” attribute.
    • When it has a different color. Then we say it is a valence-2 node.
  • Cyan type: The type of the one labelled with “#2″. This type of node can appear in the border of the image and isn’t smooth or in the center of 4 cells and its smoothness isn’t predictable in advance. If it appears in center of four cells, then:
    • It can be in the middle of 4-connected cells and we don’t care about its “smoothness” attribute, because this node will disappear.
    • It can be in the middle of a valence-2 node and will be smooth.
    • It can be a valence-3 node and things start to get complex. After the polygon union, this node will be part of three different polygon and only two of these three nodes will share the same value for the “smoothness” attribute.

Problem explained, it’s time to algorithm! The algorithm is kind of repetitive (if we iterate the bottom-right node, compare with bottom and right nodes, then do all it again, but use nodes of different directions…), but the principle is the same for all “repetitive” code, then I’m only going to put the important parts and you’ll be able to see the full algorithm implemented in libdepixelize within a few hours. Lastly, this isn’t the first algorithm I came up with and I made a lot of iteractions already (lots of crumpled paper on my room’s floor), but I think the result can perform pretty fast and I’m content. This post is kind of a documentation and it will help me to not forget what I wanted to do in the code.

layout

The above image represents the analysed data in the following code example, except for the fact that we don’t know what are the colors of the cells. We are iterating on the middle point of the image and the current iterated cell is cell A. The algorithm also uses the concept of “shading edge” and “contour edge” described in Kopf-Lischinski algorithm paper.

All images in this post were created using Inkscape and its awesome alignment tools.

Palestra sobre o Tufão no FISL14

Tive uma palestra aceita no FISL14 e o tema da palestra é a framework Tufão.

Espero mostrar rapidamente o histórico do projeto e usar o tempo restante para a motivação, reservando 10 minutos ao final para perguntas. A motivação deve incluir uma pequena explicação de como funciona a web e seus principais pontos, comparações, becnhmarks (esse é um item mais difícil), limitações, exemplos e um “tutorial”.

Devo preparar uma nova aplicação de exemplo que explora características presentes no Tufão.

Tufão 1.0.0

After a long time developing Tufão, it finally reached 1.0 version some hours ago. I’ve spent a lot of time cleaning up the API and exploring the features provided by C++11 and Qt5 to release this version.

This is the first Tufão release that:

  • … breaks config files, so you’ll need to update your config files to use them with the new version
  • … breaks ABI, so you’ll need to recompile your projects to use the new version
  • … breaks API, so you’ll need to change your source code to be able to recompile your previous code and use the new version
  • … breaks previous documented behaviour, so you’ll need to change the way you use features that were available before. But don’t worry, because the list of these changes are really small and are well documented below.

Porting to Tufão 1.0

From now on, you should link against tufao1 instead of tufao. The PKGCONFIG, qmake and CMake files were renamed also, so you can have different Tufão libraries in the same system if their major version differs.

The list of behavioural changes are:

  • Headers are being stored using a Hash-table, so you can’t easily predict (and shouldn’t) the order of the headers anymore. I hope this change will improve the performance.
  • HttpServerRequest::ready signal auto-disconnects all slots connected to the HttpServerRequest::data and HttpServerRequest::end slots before being emitted.
  • HttpFileServer can automatically detect the mime type from the served files, so if you had your own code logic to handle the mimes, you should throw it away and enjoy a lesser code base to maintain.

Most of the errors related to API changes are caught at compile-time and you can use the Qt5′s new connection syntax and C++11′s override keyword to catch the remaining errors.

News

The list of changes:

  • The project finally have a logo (made by me in Inkscape)
  • Deprecated API was removed
  • Url and QueryString removed in favor of QUrl
  • Headers refactored to inherit from QMultiHash instead of QMultiMap
  • HttpServerResponse
    • Constructor’s options argument is optional now
    • setOptions method added
    • Constructor takes a reference to a QIODevice instead a pointer
  • HttpServerRequest
    • Constructor takes a reference to a QAbstractSocket instead a pointer
    • socket method returns a reference instead a pointer
    • url returns a QUrl
    • data signal was changed and you must use readBody method to access body’s content
    • the upgrade’s head data is accessed from the request body from now on
    • now the object auto-disconnects slots from data and end signals right before emit ready
    • setCustomData and customData methods added
      • Now HttpServerRequestRouter use these methods to pass the list of captured texts
  • HttpServer uses reference instead of pointers in several places
  • AbstractHttpServerRequestRouter refactored to explore lambdas features
  • Tufão’s plugin system fully refactored
    • It’s using JSON files as configuration
  • AbstractHttpServerRequestHandler::handleRequest
    • It uses references instead pointers
    • It receives 2 arguments instead of 3
  • One more abstraction to sessions created to explore lambdas
  • WebSocket
    • startServerHandshake is taking references instead pointers
  • LESS POINTERS and MORE REFERENCES
    • This change exposes a model more predictive and natural
    • I’m caring less about Qt style and more about C++ style
      • But don’t worry, I’ll maintain a balance
  • Using scoped enums
  • HttpFileServer uses/sends mime info
  • Interfaces don’t inherit from QObject anymore, so you can use multiple inheritance to make the same class implement many interfaces
  • HttpUpgradeRouter introduced
    • HttpServer::setUpgradeHandler also
  • Updated QtCreator plugin to work with QtCreator 2.7.0 and Qt 5

The future

I want to improve the Tufão’s stability and performance, so now I’ll focus on a minor relase with unit testing and some minor changes.

After Tufão 1.0.1, I’ll focus on BlowThemAll.

Bonus

You can see a visualization video based on the history of commits below.

This release deserves a wallpaper, so I made one. See it below:

Tufão wallpaper

You can download the source of the previous wallpaper here.

What are you still doing here? Go download the new version right now!

Gerenciamento de recursos em linguagens de programação

É época de carnaval e provavelmente muito menos pessoas irão ler esse texto, mas, ainda… eu irei digitar, pois há essa necessidade estranha que eu tenho de me agarrar a essa pequena impressão de que o tempo está me tornando melhor, de alguma forma…

Pois bem, gerenciar recursos é um dos maiores desafios presentes em linguagens de programação e, dois indícios fortes que posso citar para sustentar esse argumento fraco é a existência do Buffer Overflow, um dos tipos de ataques mais explorados na história da computação que torna-se possível devido ao mau gerenciamento de memória, e a quantidade de recursos que investimos em ferramentas como a Valgrind.

Pretendo, nesse post, demonstrar o problema, apresentar conceitos simples e, logo após, analisar duas formas de gerenciamento de memória bem comuns, RAIIGarbage Collection.

E no princípio, tínhamos ponteiros…

Um ambiente familiar cria conforto para algumas pessoas, incluindo a mim e, sendo assim, começarei essa parte do texto com algo que me é familiar, um código-fonte:

Os programas que criamos gerenciam recursos e, no princípio, sequer existiam abstrações para procedimentos. O que dizer sobre abstrações para gerenciamento de recursos, então? O código anterior exemplifica o problema de lidar com recursos.

No exemplo, mesmo havendo apenas dois recursos a se gerenciar, torna-se evidente que esse modelo de programação torna o código mais complexo, dificulta a leitura e nos distancia do problema que queremos resolver, nos forçando a pensar em como os recursos se comportam e sendo fácil cometer erros como esquecer de liberar algum recurso ou liberá-los na ordem errada.

Sempre que inicializarmos um novo recurso, devemos verificar se a inicialização falhou, caso em que devemos liberar os recursos que haviam sido adquiridos antes de usar alguma construção da linguagem para quebrar o fluxo de instruções. É importante também analisar cuidadosamente o fluxo de instruções e detectar em quais momentos qualquer um dos recursos pode tornar-se inacessível, ponto em que devemos inserir mais código, redundante, de limpeza. Por último, e não menos importante, é uma boa prática liberar os recursos na ordem contrária em que eles foram adquiridos, para evitar referências inválidas, caso no qual um recurso referencia um outro recurso que já foi liberado.

Como eu chamaria toda essa bagunça, confusão, sujeira, desordem, porcaria, trapalhada, barafunda, balbúrdia, embaraço… que esse modelo de programação está criando? Código espaguete?

Formalizando…

Há o gerenciamento errôneo de um recurso quando:

  • Um recurso é destruído antes de ser usado. Nesse caso referências inválidas para o recurso irão existir e o uso dessas referências pode criar um comportamento imprevisível cuja origem será difícil de rastrear ou o encerramento da aplicação.
  • O recurso não é destruído após ser utilizado. Nesse caso chamamos o erro de vazamento de recurso e isso impede que poder computacional seja reciclado para outra tarefa.

Podemos evitar o primeiro problema deixando de fazer a limpeza de recursos manualmente, mas com as técnicas que (não) discutimos, essa decisão implica o segundo problema.

Há três definições diferentes que podemos usar para nos referir a vazamento de recursos.

A definição do usuário

Do ponto de vista do usuário:

Um recurso vazado é qualquer recurso que não pode ser possivelmente utilizado para qualquer propósito útil.

A definição poderia ser simplificada para “qualquer recurso que eu, como usuário, não estou interessado”, mas essa definição incluiria o uso de cache, por exemplo, o que seria inutilizável na nossa pesquisa.

A definição do desenvolvedor

Do ponto de vista do desenvolvedor:

Um recurso vazado é qualquer recurso que não é alcançável.

Um recurso alcançável é qualquer recurso para o qual exista uma referência, também alcançável, que você possa utilizar para acessá-lo. Deve-se notar que essa é uma definição recursiva e, quando o recurso observado é memória, podemos quebrar essa recursão afirmando que qualquer objeto alocado na stack é alcançável.

Essa é uma definição bem mais formal e, como consequência, é mais fácil criar uma ferramenta para detectar vazamentos de recursos quando utilizamos essa definição.

Entretanto, ela é menos abrangente que a definição do ponto de vista de usuário e um exemplo simples que, segundo essa definição, não apresenta nenhum vazamento de recursos, mas, de acordo com a definição do ponto de vista de usuário, possui um vazamento de recurso, segue:

No exemplo anterior, a variável buffer contém referência a um recurso que não é mais útil quando o fluxo de repetição presente é quebrado, mas, ainda assim, o recurso é alcançável. Essa situação exemplifica a diferença entre as duas definições.

É garantido que um objeto inalcançável não será usado novamente, mas o contrário não é verdade. Algumas pessoas sugerem que essa definição seja uma forma de “aproximação”.

A definição do depurador

Do ponto de vista do depurador:

Um recurso vazado é um recurso que não foi destruído durante o encerramento da aplicação.

Essa é uma definição muito usada em programas de detecção de vazamentos de memória, como Valgrind ou Visual Studio.

Uma situação onde essa definição se distingue da definição do ponto de vista do usuário é a mesma situação demonstrada anteriormente.

Outra situação onde ela se distingue é quando um recurso é utilizado até o final da aplicação, mas não é destruído. Caso o recurso em questão seja memória, isso não costuma ser um problema, pois sistemas operacionais modernos irão lidar com essa situação. Além disso, o objetivo do programa é solucionar um problema do usuário e, assim, a definição do usuário deveria ter precedência caso não haja outras questões envolvidas (como manutenção de código, desempenho, …).

Garbage Collection

Uma das soluções que foi sugerida para resolver esse problema é chamada de Garbage Collection. A premissa é que o desenvolvedor não deveria se preocupar com o gerenciamento de recursos e alguma outra ferramenta, como o compilador ou o interpretador da máquina virtual, é que devia lidar com essa tarefa. Essa técnica depende de uma estratégia e um algoritmo e é a solução que linguagens como Java adotam.

Para automatizar o gerenciamento de memória, a definição do ponto de vista do programador é utilizada. Então a pergunta que resta para solucionar o problema é “como podemos saber que um objeto nunca mais será usado novamente?”.

Estratégias de Garbage Collection decidem quando a limpeza de recursos não utilizados deve ocorrer e podem ser eventos como “quando a memória acabar” ou “a cada 5 minutos”. Alguns algoritmos serão discutidos isoladamente a seguir, mas eles não deveriam depender de uma estratégia específica. Uma forma de conseguir um algoritmo de Garbage Collection desacoplado da estratégia é projetando um algoritmo in situ.

Mark and Sweep

Mark and Sweep é um algoritmo de Garbage Collection que obriga que todos os objetos tenham o campo mark bit e cujo funcionamento acontece em duas fases, mark e sweep.

Na fase mark, o algoritmo deve identificar os objetos alcançáveis, marcando-os através do campo mark bit. Um pseudocódigo para essa fase segue:

No pseudocódigo anterior, root é a variável que contém os objetos raízes, que são objetos localizados na stack.

Na fase sweep, todos os objetos devem ser vasculhados. Os que tiverem o campo mark bit com o valor falso devem ser destruídos e os objetos restantes devem ter o campo mark bit atribuídos ao valor falso. Um pseudocódigo segue:

O algoritmo apresentado não é in situ, como observado, pela recursão que acontece na fase mark. É possível remover essa recursão usando uma lista, mas a lista em si faz com que o algoritmo não seja in situ. Um truque usado para transformar o algoritmo mark and sweep em um algoritmo in situ é inverter os ponteiros quando nós os seguimos, fazendo o objeto observado apontar para o objeto pai. Dessa forma, podemos armazenar a trajetória de quais objetos foram observados sem usar qualquer espaço extra quando o algoritmo é executado.

Stop and Copy

No algoritmo Stop and Copy, a região de memória é dividida em duas metades, uma reservada para a aplicação e outra reservada para o Garbage Collector. Quando o algoritmo é executado, ele começa a rastrear os objetos alcançáveis e, sempre que um novo objeto alcançável é encontrado, ele é movido para a região de memória reservada para o Garbage Collector e toda referência para esse objeto é atualizada. Ao final do processo, a região de memória reservada ao Garbage Collector passa a ser a região de memória reservada a aplicação e vice-versa.

Uma forma de atualizar as referências aos objetos é, no momento em que um objeto for copiado, utilizar a região na qual ele residia para armazenar um ponteiro que aponta para sua nova região.

Garantir a propriedade de algoritmo in situ nesse caso é bem mais fácil e uma forma de se fazer isso seria dividir a região reservada ao Garbage Collector em 3 partes, sendo a primeira a de objetos analisados e copiados, a segunda apenas de copiados e a terceira a região livre. Tudo que é necessário para manter esse modelo de memória são dois ponteiros, além do ponteiro que aponta para o começo da região de memória.

Exceptions

Exceções formam uma técnica de tratamento de erros que visa diminuir o número de erros e melhorar a manutenção de código. Um assunto interessante, de fato, porém, não é um objetivo desse texto explicá-las. É um objetivo, entretanto, explicar que elas impõem novas restrições nas soluções de gerenciamento de recursos. Considere o seguinte código:

No exemplo anterior, o que acontece quando uma exceção é lançada antes do arquivo ser fechado? A linguagem Java permite que objetos tenham destrutores, métodos que executam instruções quando a máquina virtual destruir o objeto. Nada impede que a classe FileReader implemente um destrutor que chame o método close, mas, por outro lado, não há garantias de quando, ou mesmo se, o objeto será destruído. O comportamento não é determinístico.

A falta de determinismo pode parecer um problema pequeno a olhos desatentos, mas é um problema tão sério que o tratamento de exceções de linguagens como Java tem uma palavra-chave extra, a palavra-chave finally.

Considere o caso em que o programa fica aberto por bastante tempo ou trata uma quantidade de arquivos razoavelmente grande. Vários sistemas operacionais seguros costumam impor limites configuráveis aos processos e há um limite também para o número de arquivos abertos. O limite de arquivos abertos por processo, por exemplo, no sistema que estou usando nesse momento, é 1024. Recursos são finitos e não é desejável desperdiçá-los.

O bloco finally sempre será executado, independente se uma exceção foi lançada ou não.

Eu não quero discutir aqui, nesse momento, os impactos na performance introduzidos pelo uso de Garbage Collection, mas Garbage Collection, de fato, resolve o problema de gerenciar memória. Entretanto, esse texto é sobre gerenciamento de recursos, um problema mais geral e, por outro lado, o principal foco das técnicas de Garbage Collection é o gerenciamento de memória.

RAII

Agora que você já conhece a proposta Garbage Collection, é chegado o momento de conhecer a técnica Resource Acquisition Is Intialization, ou RAII, para economizar. A técnica, em contraste com Garbage Collection, assume que a responsabilidade de gerenciar os recursos do programa não é inteiramente do compilador/interpretador. Essa é a solução adotada por linguagens como C++.

A ideia é que todos os objetos tenham um construtor e um destrutor, sejam eles fornecidos por você ou pelo compilador. Quando um objeto entra em escopo, ele é construído, e quando sai de escopo, ele é destruído, havendo assim um gerenciamento de recursos automático e determinístico.

Como mostra o exemplo anterior, você não precisa criar seus próprios construtores e destrutores para se beneficiar dessa técnica. Por ser determinístico, a técnica RAII pode ser utilizada onde a técnica GC não seria, sozinha, o suficiente, o que exigiria o uso de finally. Um uso é demonstrado no exemplo a seguir:

O código anterior mostra a simplicidade e elegância da técnica RAII. O RAII exige que você encapsule cada tipo de recurso em sua própria classe, o que poderia significar uma quantidade maior de código, porém, apesar de serem ambos comuns, aquisições de recursos são bem mais comuns que recursos personalizados que precisam de comportamento especializado. Um fato que ajuda ainda mais a aumentar a produtividade é a presença de abstrações genéricas como unique_ptr e shared_ptr que encapsulam comportamentos comuns e podem ser usadas para qualquer classe.

Referências

Além da experiência de memórias profundas cuja origem não é mais rastreável, esse post foi baseado, principalmente, nas aulas sobre Garbage Collection do Alex Aiken disponíveis no Coursera e em alguns artigos das edições 106 e 107 da revista Overload.

Esse texto não traz nenhuma contribuição nova para a área e o único diferencial entre ele e as referências citadas é o conteúdo em português. Entretanto, esse texto pode ajudar a divulgar conhecimento útil e alimentar a discussão sobre o tema. Além disso, até onde lembro, não é plágio se você citar as referências, então minha consciência permanece limpa, caso ela exista.

Quero aprender C++, e agora?

Ao longo dos últimos 2 anos eu conquistei um conhecimento razoável de C++ e resolvi fazer esse post para ajudar outros desenvolvedores que tenham o mesmo objetivo. O objetivo dessa postagem não é ser um “livro” que o ensine a programar, mas, sim, atuar como um “mapa” que você vai usar para encontrar os principais “livros”. Ele está organizado em 3 partes, sendo elas “por que aprender C++?”, “entendendo a linguagem” e “o percurso”. Os 3 “capítulos” são independentes e você pode lê-los em qualquer ordem.

O número de referências que usei nesse post me faz pensar naquela frase, “…sobre os ombros de gigantes“.

Por que aprender C++?

Acho que motivação é um fator importante ao adquirir novos conhecimentos, e, assim, a primeira parte desse texto é sobre motivação. Destaquei em negrito as frases que espero que você tenha em mente após terminar o texto.

Um motivo para aprender C++ é a ortogonalidade. Se a linguagem fornece algum recurso para ser utilizado, muito provavelmente permitirá que você implemente esse mesmo recurso ou um parecido usando as facilidades que ela própria fornece. Aqui, um pequeno exemplo do que seria (e é) uma quebra de ortogonalidade.

C++ é extensivamente suportada e você vai encontrar bibliotecas para resolver seus problemas nas mais diversas áreas, seja desenvolvimento de jogos, processamento de imagens, visão computacional, inteligência artificial, robótica, processamento numérico, servidor web de alta performance ou outra. Existe até suporte para novos paradigmas de programação para C++.

C++ é flexível. Se você achava que C era flexível, porque pessoas conseguiam sobreusar suas funcionalidades para implementar tratamento de exceções usando try…catch, ficaria surpreso com os códigos que a comunidade faz com C++. Se você possui necessidades incomuns, vai ficar muito contente quando examinar o design da STL, biblioteca padrão de templates de C++.

Uma característica é que a linguagem é estaticamente tipada e grande parte dos erros são capturados em tempo de compilação. Não me entenda errado, pois linguagens dinamicamente tipadas são úteis. Se uma linguagem fortemente tipada é mais adequada ao seu projeto, use C++.

Projeto com múltiplas linguagens? C++ possui conectividade com a grande maioria das linguagens existentes, chegando ao ponto onde eu tenho a ousadia de afirmar que, se uma linguagem não possui alguma forma de conectividade com C++, ela não é relevante. E mesmo nos casos extremos, você ainda terá a possibilidade de usar RPC.

Você gosta de C? Você gosta de C pelo acesso a baixo nível ou pelo desempenho? Algumas pessoas confundem desempenho e código de baixo nível. Acontece que, quando você omite os detalhes de algum comportamento, a implementação fica livre para usar a decisão mais eficiente. Um exemplo disso é a palavra-chave register, que costumava significar “coloque essa variável em um registrador” e passou a significar “por favor, coloque essa variável no lugar de acesso mais rápido”.

Outro exemplo da afirmação anterior é o canvas, um conceito usado em interfaces gráficas para permitir operações de desenho arbitrárias. Existente de forma primitiva em bibliotecas como Allegro, SDL e GTK+, e usando uma abstração de alto nível em bibliotecas como Edje e Qt. Bem, no caso da abstração de alto nível, as implementações conseguem utilizar as melhores estruturas de dados com o objetivo de diminuir o poder computacional necessário para apresentar o resultado, permitindo que, com muito menos código, você possa usar efeitos avançados de forma mais eficiente.

Um último exemplo é o sort, que em C++ é mais rápido, mesmo quando as duas implementações usam o mesmo algoritmo de ordenação. Quer usar baixo-nível para não adicionar gargalo nenhum? É a mesma coisa!

Você gosta de C e quer usar orientação a objetos? É possível usar o paradigma de orientação a objetos em C e não há problemas nisso. Há problema, entretanto, em relação a quanto de orientação a objetos você precisa. Dependendo desse fator, caso escolha C, você acabará cometendo o mesmo ato infeliz que vários outros programadores de C comentem, chegando quase ao ponto de criar uma nova linguagem em cima de C e fazendo centenas de outros programadores desprezarem o seu projeto.

Alguns outros motivos para usar C++ incluem uma carreira profissional, poder modificar o que já existe, entender melhor a tecnologia e melhorar a comunicação com pessoas da área.

Entendendo a linguagem

Um passo importante para entender uma ferramenta é entender os princípios sob os quais ela foi construída. Ao concluir esse passo, você irá adquirir a capacidade de responder sobre as características da mesma e esse “capítulo” é dedicado a lhe ajudar a entender esses princípios. Destaquei em negrito as frases que espero que você tenha em mente após terminar o texto.

Primeiramente, a linguagem não é desenvolvida por uma empresa ou um pequeno grupo com o objetivo de resolver seus próprios problemas e ignorar as consequências de suas decisões em outras áreas. A linguagem é desenvolvida por pessoas preocupadas com flexibilidade, segurança, desempenho, facilidade de uso e qualquer característica que afete sua vida, seja no desenvolvimento de um jogo de última geração, um simulador de navio, um programa de controle de avião ou qualquer outra atividade. A especificação da linguagem é publicada pela ISO e sofre um processo rigoroso antes de ser publicada. Você não ficará preso as decisões arbitrárias de uma organização com a capacidade de estregar tudo optando por C++, pois há implementações de diversas origens que lhe permitirão programar nos mais diversos locais e você não precisará pagar patentes ou algo do tipo para materializar seus conhecimentos.

Em qualquer linguagem existe a possibilidade de reutilizar pedaços de código-fonte úteis que outros programadores criaram no seu projeto. A forma mais rudimentar de reaproveitamento seria copiar e colar o código sempre que ele precisar ser reutilizado. Entretanto, as linguagens de programação sérias permitem uma forma melhor de importar código-fonte. Um dos nomes que utilizamos para citar essa características é o nome biblioteca. Geralmente uma linguagem é composta por uma biblioteca padrão e a própria linguagem. Como podemos criar nossas próprias bibliotecas, nem todas as soluções algorítmicas desenvolvidas pela espécie humana precisam fazer parte da biblioteca padrão e isso é importante.

Antes de virar código-fonte, o algoritmo existe de forma abstrata, nas nossas mentes, e a linguagem de programação escolhida impõe limitações que precisamos superar com nossas criatividades para conseguirmos o resultado (software) desejado. Quanto mais paradigmas uma linguagem suportar, menos são as limitações. Uma frase que eu li em algum lugar era algo como “o programador comum sabe o que escrever, o bom programador sabe o que reescrever”. Em resumo, reaproveitar código é o que fazemos, mas a linguagem pode ajudar (ou prejudicar) bastante essa função.

C++ nasceu como uma linguagem que adicionava orientação a objetos na linguagem C e, de fato, a saída de seu compilador, era um código-fonte C, que depois era compilado para código de máquina. Com o passar do tempo mais abstrações foram adicionadas na linguagem, até chegar ao ponto em que ela ganhou tamanha importância que começou a ter influência no desenvolvimento da linguagem da qual ela nasceu, a linguagem C. Desse primeiro pedaço, podemos entender que uma das motivações da linguagem é poder de abstração.

Com mais poder de abstração, você consegue mais produtividade e menos erros. Entretanto, se a abstração errada for escolhida, você irá perder bastante flexibilidade (dentre outras implicações) e é muito importante encontrar a decisão certa. Esse é outro princípio sob o qual a linguagem é desenvolvida. A biblioteca padrão só deve conter abstrações “corretas” e isso pode significar uma biblioteca padrão minimalista. Veja o caso de Java, por exemplo, onde a documentação contém dezenas de classes obsoletas e várias classes que tentam resolver o mesmo problema. Ou veja também o caso de Python, que se tornou “outra linguagem” na versão 3, já que perdeu compatibilidade com vários códigos escritos para Python 2, e até hoje, bibliotecas muito populares como Django ainda não foram portadas para Python 3. No caso de C++, demorou 13 anos para vermos outra especificação/versão e quase nenhuma funcionalidade antiga foi eliminada/desencorajada (de cabeça lembro de auto_ptr e excpetion especification).

Objective-C também nasceu na época do C++, então qual a diferença entre eles? C++ é bem mais do que apenas “C com classes” e possui diversas outras características (meta-programação com templates, sobrecarga de operadores, …), além do suporte ao paradigma OO. Mas esse ainda não é o ponto. Um dos princípios que guiou e continua guiando o desenvolvimento da linguagem C++ é que você só paga pelo que você usa. Isso influencia bastante sobre a decisão de quais são os comportamentos padrões no caso de ambiguidades. O polimorfismo, por exemplo, que não é habilitado por padrão e deve ser habilitado explicitamente para cada função-membro que deve possuir o comportamento polimórfico e que na versão nova possui um meio de restringir o mesmo para permitir que o compilador faça otimizações em certas situações.

Isso é tudo que vou citar nesse “capítulo”, mas vale ressaltar que a linguagem é uma evolução da linguagem C e grande parte do que vale para C, também vale para C++, como controle (acesso direto ao hardware), portabilidade e eficiência.

O percurso!

Esse é o “capítulo” que você usa para seguir até os locais que distribuem conhecimento em C++. E não esqueça de usar o seu conhecimento para o bem. Sempre que desanimar, veja uma foto minha e isso irá lhe inspirar.

Uma pequena lista de hábitos importantes que você deve desenvolver segue:

  • Você deve usar a linguagem. Use C++ em seus próximos projetos. Depois convoque seus amigos para ajudá-lo. Quem sabe não acaba criando um projeto de sucesso?
  • Ensine C++. Crie um blog, faça apresentações, responda perguntas ou faça um livro. Escolha o caminho que lhe agradar mais, pois essa tarefa irá exigir dedicação, mas, irá lhe fornecer, em troca, bastante conhecimento, caso se dedique da forma correta.
  • Siga outros programadores de C++. Provavelmente eles terão algo a lhe ensinar e você se sentirá mais motivado.
  • Perca o preconceito de aprender inglês. É importante eliminar essa barreira que lhe impede de entrar em contato com um número maior de pessoas interessantes.

E como dicas são indignas da filosofia Chuck Norris de vida nem todo mundo gosta de dicas, deixo a lista de dicas separadas da lista anterior:

  • Crie uma pasta para programas simples (converter temperatura, mostrar código ASCII de um caractere, somar vários números…) que você irá criar durante seu aprendizado
  • Aprenda a utilizar um depurador, pois essa ferramenta lhe auxiliará não somente na tarefa de encontrar erros, mas também a compreender melhor o comportamento do seu código-fonte
  • É importante que você não utilize uma IDE no começo, pois assim terá uma compreensão maior do que acontece quando você compila um projeto.
  • Use um VCS pelo menos para um de seus projetos, pois esse é o modo de trabalhar em grupo. Você pode usar o Google code para hospedar seus projetos open source.
  • Documente pelo menos um de seus projetos, pois essa é uma experiência importante
  • Arquitete pelo menos um de seus projetos, pois essa é outra experiência importante
  • Crie testes para pelo menos um de seus projetos, pois essa é mais outra experiência importante
  • Não siga todas as dicas anteriores simultaneamente, pois isso lhe fará perder tempo
  • Use build systems multiplataformas em seus projetos que tem o objetivo de ser mais do que “apenas um projeto de aprendizado”
  • Em algum momento você vai precisar desenvolver códigos mais complexos e a biblioteca-padrão não mais irá lhe satisfazer. É para isso que bibliotecas como a boost e a Qt estão aí.

As minhas fontes de conhecimento de C++ estão organizadas em duas categorias principais. A categoria “morta”, que é composta por fontes que, caso você tenha memória boa o suficiente, só precisa consultar uma vez, e a categoria “viva”, composta por fontes que estão constantemente evoluindo. Considero importante manter um contanto com a comunidade e evoluir com ela e isso é para o que as fontes “vivas” existem.

A fonte morta

Livros são uma ótima forma de se aprender a programar, pois eles costumam agrupar os principais conhecimentos da linguagem, códigos de exemplo, exercícios, curiosidades interessantes e perguntas intrigantes. Entretanto, a linguagem que um autor utiliza para passar conhecimento pode ser boa para mim e ruim para você, então é importante que você não compre um livro antes de conhecê-lo. Antes da compra, use bibliotecas ou mesmo baixe alguns capítulos do mesmo. Quando chegar o momento em que um livro não mais lhe serve, abandone-o e tente outro.

Como C++ é um superconjunto da linguagem C, alguns livros sobre C também podem ser utilizados. O problema com essa abordagem é que eles podem lhe fazer perder tempo utilizando técnicas obsoletas e que em C++ há um jeito mais fácil de fazer que ainda fornece mais segurança e desempenho.

Alguns materiais memoráveis com os quais tive contato (ou não):

  • cppreference.com: Durante seu aprendizado você vai precisar de uma referência a consultar. Essa é a melhor referência com a qual já tive contato.
  • Curso de Linguagem C: Eu aprendi a programar com essa apostila. Uma característica notável da mesma é que ela esconde poucos detalhes da linguagem, deixando menos dúvidas na sua mente.
  • C++ Black Book: Esse não é um livro tão bom, mas permitiu-me ter conhecimento que não consegui de outras formas, principalmente, porque ele tem o que falta em alguns livros, exemplos de código-fonte.
  • Accelerated C++: Practical Programming by Example: Um livro com uma abordagem de ensino “inovadora”, ensinando a usar facilidades de alto-nível antes de ensinar como elas funcionam.
  • Programming – Principles and Practice Using C++: Esse é um dos melhores livros ensinando programação dos quais eu tive acesso (obrigado ao professor Alcino da UFAL, por ter me emprestado ele por um tempo). Acabei encontrando esse livro num momento em que estava insatisfeito com a falta de exercícios propostos nos livros de programação.
  • The C++ Programming Language: Apesar de ser um livro que consegue reunir explicações para boa parte da linguagem, ele não possui uma ordem muito didática, tornando-se uma péssima escolha para uma primeira leitura.
  • C Completo e Total: Aborda um pouco de “magia negra” tópicos avançados  na linguagem, sendo uma boa escolha depois que você tiver dominado o básico da linguagem e estiver à procura de novos desafios.
  • https://en.wikipedia.org/wiki/C++11: Eu sei que nenhuma página da wikipedia está livre de futuras revisões, mas essa página, em especial, está bem estável e é uma ótima leitura para entender as mudanças do novo padrão de C++.
  • Modern C++ Design: Esse é um livro que eu ainda não tive a chance de ler, porém parece ser bem popular entre os magos desenvolvedores da boost e as palestras do Andrei Alexandrescu possuem informações interessantes.
  • Effective C++: Outro livro que ainda não tive a oportunidade de ler, mas também possui vários indícios que o faz parecer promissor.
  • Guia Foca GNU/Linux: Apesar de não ter relação direta com C++, foi com essa apostila que aprendi bastante sobre computadores e por isso recebe menção honrosa.

A fonte viva

É importante participar de uma comunidade durante o processo (eterno?) de aprendizado. Sem mais enrolação, segue uma lista:

  • Lista de C & C++ Brasil: Dentre as dezenas de listas de emails das quais faço parte, essa é uma das mais respeitosas. Vez ou outra você irá encontrar algo de interessante na lista, além de ter um lugar para discutir sobre C++.
  • reddit: Sempre disponibilizando um link a mais para me ajudar a ser um programador melhor.
  • The home of Standard C++ on the web: É o mais próximo que temos de “site oficial” da linguagem.
  • Channel 9: Um lugar onde você pode assistir vídeos de eventos de C++. Há material bastante interessante que você não deveria subestimar. Usuários do reddit costumam postar os links para novos vídeos que aparecem aqui.
  • cppreference.com: Esse é um link tão importante que merece menção dupla no mesmo post.
  • C++ Quiz: Um quiz de C++ onde você vê o código-fonte de um programa e tenta adivinhar a saída (ou se compila ou provoca UB).

E assim como eu recomendei que você seguisse outros programadores de C++, eu também o faço:

EDIT:

Em uma parte do texto eu comentei que C++ era ortogonal, mas depois de algum tempo pensando eu mudei de ideia em relação ao texto. Primeiro, há vários pontos de vista e um deles é que todas as linguagens são ortogonais, mas algumas são muito ortogonais e outras são pouco ortogonais, então informar que C++ é ortogonal é uma frase inútil que não vale nem os bytes que são usados para armazená-la. Segundo, eu realmente não me importo com isso, mas eu me importo com o fato de você, como projetista da linguagem, definir abstrações que usem conceitos úteis e me impeça, como usuário da linguagem, de criar abstrações que usem esses mesmos conceitos. Essa foi uma parte do texto que ninguém comentou, mas continua algo importante para mim.

%d blogueiros gostam disto: