Ponto V!

Contêineres Intrusivos Escrito por Bruno Crivelari Sanches

Os contêineres da STL são estruturas de dados não intrusivas, ou seja, não precisamos alterar ou implementar qualquer tipo de interface para armazenarmos um dado nestes contêineres, mas, para que estes funcionem a STL muitas vezes precisa alocar um objeto extra para qualquer dado inserido, ocasionando uma alocação de memória que pode ser custosa demais em alguns casos, vamos conhecer neste artigo então uma maneira de contornar esse problema.

Revendo os Contêineres Não Intrusivos

Os Contêineres não intrusivos são aquelas estruturas de dados no estilo da STL, onde não é preciso modificar o tipo que vai ser armazenado pelos contêineres. Por simplicidade, este artigo vai focar na list, mas os conceitos se aplicam a maioria das estruturas de dados da STL.

Toda vez que um elemento é inserido numa std::list ela precisa alocar um novo nó que irá ser inserido na lista, por exemplo:

#include <list>
class GameObject
{
};

int main(int, char **)
{
    GameObject monster;
    GameObject elevator;
    GameObject player;

    std::list<GameObject *> lstObjectsToUpdate;

    lstObjectsToUpdate.push_back(&monster);
    lstObjectsToUpdate.push_back(&elevator);
    lstObjectsToUpdate.push_back(&player);

    return 0;
}

No exemplo acima temos uma classe chamada GameObject e precisamos inserir ela em uma std::list, como não desejamos que novas instancias sejam criadas usamos uma lista de ponteiros e é nesse ponto que os problemas começam: toda vez que um novo objeto é inserido na lista a std::list aloca um objeto (algo do tipo: std::list_node) que é usado para armazenar o novo elemento, dessa forma, o layout da std::list na memória deve ser algo semelhante com a figura abaixo:

No diagrama de colaboração acima podemos perceber então o custo oculto que estes contêineres podem trazer, este tipo de problema pode ser minimizado ou até resolvido usando outras técnicas, como, por exemplo, o uso de pools de memória, mas vamos estudar aqui uma outra maneira de se obter um ganho semelhante com algumas vantagens extras.

Usando Contêineres Intrusivos

Para utilizar um contêiner intrusivo é preciso que a classe do objeto a ser inserido no contêiner possua um atributo “gancho” (hook) que é usado como nó do contêiner, assim o uso destes contêineres fica restrito a apenas os objetos do qual temos o código e podemos modificar para inserir os ganchos, outro detalhe é que a inserção do objeto fica restrita a contêineres que aceitem o mesmo tipo de gancho que o objeto possui e o gancho só pode ser usado por um contêiner de cada vez.

Como exemplo vamos utilizar a biblioteca de Contêineres Intrusivos da Boost, a documentação pode ser acessada clicando-se no link: Boost Intrusive. A biblioteca da Boost permite o uso dos ganchos de duas formas, como atributos ou por herança. Vamos ver primeiramente como podemos criar a classe GameObject usando o gancho por herança:

#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

class GameObject: public list_base_hook<>
{ 
    /**/ 
};

Neste caso estamos apenas utilizando a versão básica do gancho com as opções padrão, existem varias opções para o gabarito (template), como tags, modo seguro, modo inseguro e auto-desconexão, não vamos explorar todos aqui, para maiores detalhes de todos as opções consulte a documentação.

Agora que o GameObject já possui um gancho, podemos utilizar ele em uma lista intrusiva, desta forma podemos modificar o código principal para:

#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

class GameObject: public list_base_hook<>
{ 
    /**/ 
};

int main(int, char **)
{
    GameObject monster;
    GameObject elevator;
    GameObject player;

    list<GameObject> lstObjectsToUpdate;

    lstObjectsToUpdate.push_back(monster);
    lstObjectsToUpdate.push_back(elevator);
    lstObjectsToUpdate.push_back(player);

    return 0;
}

Os contêineres intrusivos da Boost possuem uma interface e nomes equivalentes aos mesmos contêineres da STL, o que facilita muito o aprendizado, note que a função main sofreu apenas uma alteração para não inserir o endereço dos objetos na lista e sim o objeto em si, pois como esta é uma lista intrusiva são inseridas apenas referências utilizando-se o gancho. As mudanças no código ocorrem mesmo é no inicio, onde é feito o include do arquivo de cabeçalho da Boost (ao invés do list da std) e a classe GameObject foi modificada para herdar o gancho padrão.

As diferenças no código são bem sutis, mas nos bastidores as mudanças são significativas, o layout da memória deve ficar semelhante ao do diagrama abaixo:

Podemos ver claramente que houve uma bela redução nas alocações de memória, pois como o gancho faz parte do GameObject não foi mais preciso alocar um objeto extra para inserir cada um na lista. A diferença no consumo de memória não deve ser significativo se compararmos o tamanho de um gancho e o tamanho de um nó da std::list, mas se levarmos em conta o custo da alocação de memória do nó, a memória gasta para gerenciar a alocação e a redução da fragmentação da memória temos bons ganhos, principalmente em situações extremas.

Utilizando Ganchos Como Atributos

Não é necessário herdar os ganchos em todas as classes que vão fazer parte de algum contêiner intrusivo, pode-se criar um atributo (que na maioria das vezes vai ser publico) que faça o trabalho do gancho. A vantagem de utilizar esta técnica é que na minha opinião é muito mais simples criar vários ganchos atributos do que usar herança múltipla e o sistema de tags que a Boost oferece.

Vamos então modificar a class GameObject para utilizar um gancho como atributo:

#include <boost/intrusive/list.hpp>

class GameObject
{
    public:
        boost::intrusive::list_member_hook<> hookUpdateList;
    /**/
};

A mudança é bem simples e nomeamos o gancho com base no tipo de lista que ele deva ser utilizado, o interessante é que fica bem simples criar vários ganchos para diferentes listas, o único porém é que a declaração da lista precisa ser modificada para que o gancho membro seja utilizado, vamos ver então o código final:

#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

class GameObject
{ 
    public:
        list_member_hook<> hookUpdateList;
    /**/ 
};

typedef member_hook<GameObject, list_member_hook<>, &GameObject::hookUpdateList> GameObjectMemberHookOption;

int main(int argc, char **argv)
{
    GameObject monster;
    GameObject elevator;
    GameObject player;

    boost::intrusive::list<GameObject, GameObjectMemberHookOption> lstObjectsToUpdate;

    lstObjectsToUpdate.push_back(monster);
    lstObjectsToUpdate.push_back(elevator);
    lstObjectsToUpdate.push_back(player);

    return 0;
}

O GameObject continua o mesmo, mas como estamos utilizando um atributo como gancho, precisamos dizer isso na criação da lista, então primeiramente é feito um typedef (para simplificar) com a opção de gancho membro, depois criamos a lista utilizando esta opção e pronto, já podemos inserir objetos na nova lista.

Auto Desconexão

Uma grande vantagem dos contêineres intrusivos é que fica simples remover automaticamente um objeto do contêiner quando este é destruído, ação que em um contêiner “comum” não é tão simples. Para melhor ilustrar, vamos modificar o primeiro exemplo:

#include <iostream>
#include <list>
#include <string>

using namespace std;

class GameObject
{
    public:
        GameObject(const string &name): 
          strName(name)
        {
        }

        string strName;
};

int main(int, char **)
{
    GameObject *monster = new GameObject("monster");
    GameObject *elevator = new GameObject("elevator");
    GameObject *player = new GameObject("player");

    typedef list<GameObject *> UpdateList_t;
    UpdateList_t lstObjectsToUpdate;

    lstObjectsToUpdate.push_back(monster);
    lstObjectsToUpdate.push_back(elevator);
    lstObjectsToUpdate.push_back(player);

    //Supondo que o monstro foi morto:
    delete monster;

    //Agora vamos listar os objetos:
    for(UpdateList_t::iterator it = lstObjectsToUpdate.begin(), end = lstObjectsToUpdate.end(); it != end; ++it)
        cout << "Object: " << (*it)->strName << endl;

    delete elevator;
    delete player;    

    return 0;
}

O código aumentou um pouco: para começar incluímos um atributo chamado strName na classe GameObject onde colocamos o nome de cada objeto, depois passamos a alocar os objetos dinamicamente (apenas para simplificar o problema), inserimos todos na lista e simulamos a morte do monstro “matando” (usando o delete) o monstro e esquecendo (propositalmente nesse caso) de remover ele da lista. Como não existe meio algum da lista saber que o objeto foi destruído, quando percorremos a lista acessamos um Dangling Pointer e a partir deste ponto tudo pode acontecer.

Utilizando um contêiner intrusivo é simples evitar esse tipo de problema e no caso da Boost ela já possui um gancho especifico que lida com essa situação, vamos então modificar o código novamente para utilizar a lista intrusiva com um gancho que se auto-desconecta (note aqui que por padrão os contêineres intrusivos da Boost vão conter ponteiros inválidos caso um gancho comum seja usado):

#include <iostream>
#include <boost/intrusive/list.hpp>
#include <string>

using namespace std;
using namespace boost::intrusive;

typedef list_base_hook<link_mode<auto_unlink> > auto_unlink_hook;

class GameObject: public auto_unlink_hook
{
    public:
        GameObject(const string &name): 
          strName(name)
        {
        }

        string strName;
};

int main(int, char **)
{
    GameObject *monster = new GameObject("monster");
    GameObject *elevator = new GameObject("elevator");
    GameObject *player = new GameObject("player");

    typedef list<GameObject, constant_time_size<false> > UpdateList_t;
    UpdateList_t lstObjectsToUpdate;

    lstObjectsToUpdate.push_back(*monster);
    lstObjectsToUpdate.push_back(*elevator);
    lstObjectsToUpdate.push_back(*player);

    //Supondo que o monstro foi morto:
    delete monster;

    //Agora vamos listar os objetos:
    for(UpdateList_t::iterator it = lstObjectsToUpdate.begin(), end = lstObjectsToUpdate.end(); it != end; ++it)
        cout << "Object: " << (*it).strName << endl;

    delete elevator;
    delete player;    

    return 0;
}

No código acima o GameObject herda um gancho que é declarado utilizando a opção de auto desconexão (link_mode), já no código principal a lista é criada com um novo parâmetro:constant_time_size. Este parâmetro liga ou desliga (no exemplo acima desligou) a opção que força o método size (que diz quantos elementos um contêiner possui) executar em tempo constante. Isso significa que quando size é chamado e esta opção esta desligada ele vai ter um tempo de execução variável (pois certamente vai percorrer a lista toda para contar os elementos). Quando o tempo constante esta ligado é criada uma variável que conta a quantidade de elementos do contêiner, mas esta opção é incompatível com ganchos automáticos.

Voltando ao código, a inserção dos elementos sofreu uma pequena modificação, pois na lista intrusiva não inserimos mais os ponteiros e sim os objetos diretamente. Outra pequena mudança é o uso de “.” ao invés de “->” na hora de imprimir os nomes. Por fim, a principal mudança é invisível no código e ocorrer quando o monstro é “morto”, pois quando isso ocorre o destrutor do gancho o remove automaticamente da lista, assim os nomes são impressos corretamente e não temos mais o perigo de um ponteiro invalido na lista.

Conclusão

Os contêineres intrusivos são um pouco mais trabalhosos que os contêineres tradicionais da STD durante o uso, principalmente devido as mudanças que os objetos a serem armazenados precisam sofrer, mas em casos onde existe pouca memória ou listas de objetos muito grandes o seu uso pode ser vantajoso e pode-se ter um belo ganho de uma maneira relativamente simples. Já o uso da auto desconexão por si só pode ser o fator decisivo que leve um desenvolvedor a utilizar estes contêineres, pois a estes ajudam em muito a tornar o desenvolvimento do software muito mais simples e menos sucetivel a falhas de programação.