Régions, régions d'objets et plus encore !

Premature optimization is the root of all evil [...] in programming.

— Donald Knuth, Conférence du Prix Turing 1974

Gérer la mémoire est probablement le sport — extrême — le plus pratiqué par les programmeurs C/C++. Quiconque a programmé dans un langage possédant un garbage collector — poétiquement appelé ramasse-miettes en français — est d'autant plus conscient de cet état de fait et des douleurs qui y sont associées.

N'empêche que le contrôle manuel de l'allocation de mémoire ouvre la porte à une kyrielle d'optimisations. En particulier, il devient possible de tirer partie des comportements particuliers qu'exhibe une application en ce qui a trait à l'allocation de mémoire pour en accélérer significativement l'exécution.

Région

Les régions se révèlent très efficaces lorsqu'une application alloue une grande quantité de petits objets qui sont par la suite libérés simultanément.

Le principe de fonctionnement — très simple — consiste à allouer un grand bloc de mémoire à partir duquel les requêtes subséquentes, de petite taille, seront satisfaites. Obtenir quelques octets de mémoire se résume alors à incrémenter un pointeur dans le bloc de mémoire de grande taille.

Lorsqu'un bloc de mémoire de grande taille est épuisé, il s'agit simplement d'en allouer un nouveau. Comme le montre la figure ci-dessous, les blocs de mémoire forment alors une liste chaîné:

Trois pointeurs doivent être maintenus:

Le code ci-dessous montre une implantation de base des régions en C++. L'implantation des régions livrée glibc représente très certainement une référence de qualité supérieure (obstack.h, obstack.c).

class Region {
private:
    struct Block {
        Block(size_t size) : prev(NULL), memory(NULL) {
            memory = new uint8_t[size];
        }

        ~Block() {
            delete [] memory;
        }

        Block* prev;
        uint8_t* memory;
    };

public:
    static const int alignment = 4;

    Region(size_t block_size = 4096) : current(NULL),
        block_size(block_size), limit(NULL), pos(NULL) {
        assert(block_size > 0);
        expand();
    }

    ~Region() {
        while (current) {
            Block* block = current;
            current = current->prev;
            delete block;
        }
    }

    void* allocate(size_t size) {

        if (size > block_size) {
            return NULL;
        }

        if (size == 0) {
            return NULL;
        }

        // Make sure to account for the alignment when checking if
        // an expansion is required. Otherwise, aligned address may
        // overflow the buffer limit. Notice that we are sure that
        // the alignment won't overflow on a mallocated block since
        // malloc must return memory suitably aligned for any kind
        // of variable (the pool alignment is certainly smaller).
        if ((pos + size + (alignment - 1)) > limit) {
            expand();
        }

        uintptr_t adr = reinterpret_cast<uintptr_t>(pos);
        adr = (adr + (alignment - 1)) & ~(alignment - 1);
        pos = reinterpret_cast<uint8_t*>(adr + size);

        return reinterpret_cast<void*>(adr);
    }

private:
    void expand() {
        Block* block = new Block(block_size);
        block->prev = current;
        current = block;

        // The new position is at the beginning of the
        // allocated block while the new limit is at its end.
        pos = block->memory;
        limit = pos + block_size;
    }

    Block* current;
    size_t block_size;
    uint8_t* limit; // One past the end of the current block data.
    uint8_t* pos;   // Position in the current block data.
};

Le gain de performance attribuable à l'utilisation des régions dépend de plusieurs facteurs. La taille des allocations est un de ceux-ci. De manière générale, plus les objets alloués sont de grande taille, moins le gain de performance est intéressant.

Le graphique ci-dessous compare les temps d'allocation d'un million d'objets, dont les tailles varient de 4 à 128 octets, entre ptmalloc et une région configurée avec des blocs de 4096 octets — les résultats sont similaires pour une région configurée avec des blocs de 8192 octets.

Temps d'exécution en fonction de la taille des allocations.

Comme le montre le graphique ci-dessous, le gain de performance par rapport à ptmalloc décroît rapidement lorsque la taille des objets alloués augmente.

Gain de performance en fonction de la taille des allocations.

La taille des blocs alloués par la région constitue un autre facteur devant être considéré.

Sans surprise, comme le montre le graphique ci-dessous, plus les blocs alloués sont de grande taille et plus le gain de performance est intéressant. Néanmoins, il importe de garder à l'esprit que cette amélioration est effectuée au prix d'une utilisation de mémoire plus importante.

Temps d'exécution en fonction de la taille des blocs.

Fait intéressant, tel qu'illustré par le graphique ci-dessous, le gain de performance n'est pas, comme nous aurions pu nous y attendre, linéaire en fonction de la taille des blocs. Ce comportement dépend toutefois de l'allocateur générique sous-jacent — ptmalloc dans ce cas-ci.

Gain de performance en fonction de la taile des blocs.

Région d'objets

Lorsque les objets alloués sont tous du même type, il est possible de simplifier quelque peu l'implantation présentée précédemment. Évidemment, cela suppose que les objets alloués sont des plain old data structures. Généralement, il ne s'agit pas d'une exigence trop contraignante.

template <typename T, size_t BlockSize = 512>
class RegionOf {
private:
    struct Block {
        Block() : prev(NULL) {}

        Block* prev;
        T objects[BlockSize];
    };

public:
    RegionOf() : current(NULL), index(0) {
        expand();
    }

    ~RegionOf() {
        while (current) {
            Block* block = current;
            current = current->prev;
            delete block;
        }
    }

    T* allocate() {
        if (index == BlockSize)
            expand();

        return &current->objects[index++];
    }

private:
    void expand() {
        Block* block = new Block;
        block->prev = current;
        current = block;
        index = 0;
    }

    Block* current;
    int index;
};

Les performances de cette solution sont équivalentes à celles des régions.

Object pool

Un object pool peut être vu comme l'évolution naturelle des régions d'objets. Une opération additionnelle est supportée: la libération d'objets. Pour ce faire, une liste d'objets libres, la freelist, est entretenue. Lorsqu'un bloc de mémoire est alloué par le pool, les objets le composant sont chaînés entre eux puis ajoutés à la freelist.

Bloc de mémoire dont les objets sont chaînés entre eux.
Liste des objets libres.

Allouer un objet se résume à retirer le premier nœud de la freelist et retourner son adresse à l'appelant. De même, lorsqu'un objet est libéré, ce dernier est simplement ajouté à la freelist. Ces deux opérations, réalisées en temps constant, sont évidemment très rapides.

template <typename Type, size_t BlockSize = 128>
class ObjectPool {
private:
    union Node {
        Node* next;
        Type type;
    };

    struct Block {
        Block* next;
        Node nodes[BlockSize];
    };

public:
    ObjectPool() :
        blocks(NULL), freelist(NULL) {
        expand();
    }

    ~ObjectPool() {
        while (blocks) {
            Block* block = blocks;
            blocks = blocks->next;
            delete block;
        }
    }

    Type* allocate() {
        if (!freelist) expand();
        Node* node = freelist;
        freelist = freelist->next;
        return reinterpret_cast<Type*>(node);
    }

    void free(Type* t) {
        Node* node = reinterpret_cast<Node*>(t);
        node->next = freelist;
        freelist = node;
    }

private:
    void expand() {
        Block* block = new Block;

        // Link block's nodes together.
        for (size_t i = 0; i < (BlockSize - 1); i++)
            block->nodes[i].next = &block->nodes[i + 1];

        // Link new nodes to the free list.
        block->nodes[BlockSize - 1].next = freelist;
        freelist = block->nodes;

        // Add the new block to the blocks list.
        block->next = blocks;
        blocks = block;
    }

    Block* blocks;
    Node* freelist;
};

Conclusion

Si ces trois techniques permettent généralement d'obtenir des gains de performance significatifs par rapport à un allocateur générique, il importe de garder à l'esprit que ces dernières possèdent des domaines d'application restreints.

En outre, dans le contexte d'une application de grande taille, les gains de performance offerts par ces techniques ne sont pas toujours au rendez-vous. Cela est d'autant plus remarquable dans le contexte d'applications concurrentes, tel que le laisse entrevoir cet article sur le sujet.

Les mesures empiriques demeurent donc le seul moyen permettant de déterminer si l'utilisation de ces techniques offre véritablement des gains de performance significatifs dans un contexte donné.

Bref, comme le dirait sans doute Fred Brooks, there is no silver bullet.