Optimisation des allocations de chaînes redondantes en C ++

J'ai un composant C ++ assez complexe dont les performances sont devenues un problème. Le profilage montre que la majeure partie du temps d'exécution est simplement consacrée à l'allocation de mémoire pour std::strings.

Je sais qu'il y a beaucoup de redondance entre ces chaînes. Une poignée de valeurs se répètent très fréquemment, mais il existe également de nombreuses valeurs uniques. Les cordes sont généralement assez courtes.

Je me demande maintenant s'il serait judicieux de réutiliser ces allocations fréquentes. Au lieu de 1000 pointeurs pour 1000 valeurs "foobar" distinctes, je pourrais avoir 1000 pointeurs pour une valeur "foobar". Le fait que ce soit plus efficace en mémoire est un bon bonus, mais je suis surtout préoccupé par la latence ici.

Je suppose qu'une option serait de maintenir une sorte de registre de valeurs déjà allouées, mais est-il même possible de rendre les recherches de registre plus rapides que les allocations de mémoire redondantes? Est-ce une approche viable?

Je m'appuie fortement sur les chaînes internes comme le suggère Basile, où une recherche de chaîne se traduit par un index 32 bits à stocker et à comparer. C'est utile dans mon cas car j'ai parfois des centaines de milliers à des millions de composants avec une propriété nommée "x", par exemple, qui doit toujours être un nom de chaîne convivial car il est souvent accédé par les scripteurs par leur nom.

J'utilise un trie pour la recherche (expérimenté également unordered_mapmais mon tri réglé soutenu par des pools de mémoire a au moins commencé à mieux fonctionner et était également plus facile à rendre thread-safe sans simplement verrouiller chaque fois que la structure était consultée) mais ce n'est pas aussi rapide pour la construction comme la création std::string. Le but est plus d'accélérer les opérations suivantes comme la vérification de l'égalité des chaînes qui, dans mon cas, se résume à vérifier l'égalité de deux entiers et de réduire considérablement l'utilisation de la mémoire.

Je suppose qu'une option serait de maintenir une sorte de registre de valeurs déjà allouées, mais est-il même possible de rendre les recherches de registre plus rapides que les allocations de mémoire redondantes?

Cela va être difficile de faire une recherche dans une structure de données beaucoup plus rapidement qu'un seul mallocPar exemple, si vous avez un cas où vous lisez un bateau chargé de chaînes à partir d'une entrée externe comme un fichier, par exemple, alors ma tentation serait d'utiliser un allocateur séquentiel si possible. Cela a pour inconvénient que vous ne pouvez pas libérer la mémoire d'une chaîne individuelle. Toute la mémoire mise en commun par l'allocateur doit être libérée en une seule fois ou pas du tout. Mais un allocateur séquentiel peut être pratique dans les cas où vous avez juste besoin d'allouer une cargaison de petits morceaux de mémoire de taille variable d'une manière séquentielle droite, pour ensuite tout jeter plus tard. Je ne sais pas si cela s'applique dans votre cas ou non, mais le cas échéant, cela peut être un moyen facile de corriger un point d'accès lié aux fréquentes allocations de mémoire des adolescents (ce qui pourrait avoir plus à voir avec les échecs de cache et les erreurs de page que le sous-jacent) algorithme utilisé par, disons malloc).

Les allocations de taille fixe sont plus faciles à accélérer sans les contraintes d'allocateur séquentiel qui vous empêchent de libérer des morceaux de mémoire spécifiques pour les réutiliser plus tard. Mais rendre l'allocation de taille variable plus rapide que l'allocateur par défaut est assez difficile. Fondamentalement, rendre tout type d'allocateur de mémoire plus rapide que mallocgénéralement extrêmement difficile si vous n'appliquez pas de contraintes qui restreignent son applicabilité. Une solution consiste à utiliser un allocateur de taille fixe pour, disons, toutes les chaînes de 8 octets ou moins si vous en avez une cargaison et les chaînes plus longues sont un cas rare (pour lequel vous pouvez simplement utiliser l'allocateur par défaut). Cela signifie que 7 octets sont gaspillés pour les chaînes de 1 octet, mais cela devrait éliminer les points chauds liés à l'allocation, si, disons, 95% du temps, vos chaînes sont très courtes.

Une autre solution qui m'est venue à l'esprit est d'utiliser des listes chaînées déroulées qui peuvent sembler folles, mais écoutez-moi.

L'idée ici est de faire de chaque nœud déroulé une taille fixe au lieu d'une taille variable. Lorsque vous faites cela, vous pouvez utiliser un allocateur de blocs de taille fixe extrêmement rapide qui regroupe la mémoire, en allouant des blocs de taille fixe pour les chaînes de taille variable liées entre elles. Cela ne réduira pas l'utilisation de la mémoire, cela aura tendance à y augmenter en raison du coût des liens, mais vous pouvez jouer avec la taille déroulée pour trouver un équilibre adapté à vos besoins. C'est une idée farfelue, mais elle devrait éliminer les points d'accès liés à la mémoire, car vous pouvez désormais regrouper efficacement la mémoire déjà allouée dans des blocs contigus volumineux et avoir toujours les avantages de libérer des chaînes individuellement. Voici un simple allocateur fixe que j'ai écrit (un illustration que j'ai fait pour quelqu'un d'autre, dépourvu de peluches liées à la production) que vous pouvez utiliser librement:

#ifndef FIXED_ALLOCATOR_HPP
#define FIXED_ALLOCATOR_HPP

class FixedAllocator
{
public:
    /// Creates a fixed allocator with the specified type and block size.
    explicit FixedAllocator(int type_size, int block_size = 2048);

    /// Destroys the allocator.
    ~FixedAllocator();

    /// @return A pointer to a newly allocated chunk.
    void* allocate();

    /// Frees the specified chunk.
    void deallocate(void* mem);

private:
    struct Block;
    struct FreeElement;

    FreeElement* free_element;
    Block* head;
    int type_size;
    int num_block_elements;
};

#endif

#include "FixedAllocator.hpp"
#include <cstdlib>

struct FixedAllocator::FreeElement
{
    FreeElement* next_element;
};

struct FixedAllocator::Block
{
    Block* next;
    char* mem;
};

FixedAllocator::FixedAllocator(int type_size, int block_size): free_element(0), head(0)
{
    type_size = type_size > sizeof(FreeElement) ? type_size: sizeof(FreeElement);
    num_block_elements = block_size / type_size;
    if (num_block_elements == 0)
        num_block_elements = 1;
}

FixedAllocator::~FixedAllocator()
{
    // Free each block in the list, popping a block until the stack is empty.
    while (head)
    {
        Block* block = head;
        head = head->next;
        free(block->mem);
        free(block);
    }
    free_element = 0;
}

void* FixedAllocator::allocate()
{
    // Common case: just pop free element and return.
    if (free_element)
    {
        void* mem = free_element;
        free_element = free_element->next_element;
        return mem;
    }

    // Rare case when we're out of free elements.
    // Create new block.
    Block* new_block = static_cast<Block*>(malloc(sizeof(Block)));
    new_block->mem = malloc(type_size * num_block_elements);
    new_block->next = head;
    head = new_block;

    // Push all but one of the new block's elements to the free stack.
    char* mem = new_block->mem;
    for (int j=1; j < num_block_elements; ++j)
    {
        void* ptr = mem + j*type_size;
        FreeElement* element = static_cast<FreeElement*>(ptr);
        element->next_element = free_element;
        free_element = element;
    }
    return mem;
}

void FixedAllocator::deallocate(void* mem)
{
    // Just push a free element to the stack.
    FreeElement* element = static_cast<FreeElement*>(mem);
    element->next_element = free_element;
    free_element = element;
}

Vous voudrez peut-être avoir un mécanisme de chaîne interne (mais les chaînes doivent être immuables, utilisez donc const std::string-s). Vous pourriez vouloir des symboles . Vous pourriez regarder dans les pointeurs intelligents (par exemple std :: shared_ptr ). Ou même std :: string_view en C ++ 17.

Il était une fois dans la construction du compilateur, nous avons utilisé quelque chose appelé data-chair (au lieu de data-bank, une traduction allemande familière pour DB). Cela a simplement créé un hachage pour une chaîne et l'a utilisé pour l'allocation. Donc, n'importe quelle chaîne n'était pas un morceau de mémoire sur le tas / pile mais un code de hachage dans cette chaise de données. Vous pourriez remplacer Stringpar une telle classe. Cependant, il a besoin d'un certain remaniement de code. Et bien sûr, cela n'est utilisable que pour les chaînes R / O.

Remarquez comment l'allocation de mémoire et la mémoire réelle utilisée sont toutes deux liées à de mauvaises performances:

Le coût de l'allocation effective de la mémoire est, bien sûr, très élevé. Par conséquent, std :: string peut déjà utiliser l'allocation sur place pour les petites chaînes, et le montant des allocations réelles peut donc être inférieur à ce que vous pourriez d'abord supposer. Dans le cas où la taille de ce tampon n'est pas assez grande, alors vous pourriez être inspiré par exemple par la classe de chaîne de Facebook ( https://github.com/facebook/folly/blob/master/folly/FBString.h ) qui utilise 23 caractères en interne avant l'allocation.

Il convient également de noter le coût d' utilisation de beaucoup de mémoire. C'est peut-être le plus gros délinquant: vous pouvez avoir beaucoup de RAM dans votre machine, cependant, les tailles de cache sont encore suffisamment petites pour nuire aux performances lors de l'accès à la mémoire qui n'est pas déjà mise en cache. Vous pouvez lire à ce sujet ici: https://en.wikipedia.org/wiki/Locality_of_reference

Au lieu de rendre les opérations de chaîne plus rapides, une autre approche consiste à réduire le nombre d'opérations de chaîne. Serait-il possible de remplacer des chaînes par une énumération, par exemple?

Une autre approche qui pourrait être utile est utilisée dans Cocoa: il existe des cas où vous avez des centaines ou des milliers de dictionnaires, tous avec principalement la même clé. Ils vous permettent donc de créer un objet qui est un ensemble de clés de dictionnaire, et il existe un constructeur de dictionnaire qui prend un tel objet comme argument. Le dictionnaire se comporte de la même manière que tout autre dictionnaire, mais lorsque vous ajoutez une paire clé / valeur avec une clé dans cet ensemble de clés, la clé n'est pas dupliquée mais juste un pointeur vers la clé dans l'ensemble de clés est stocké. Ces milliers de dictionnaires n'ont donc besoin que d'une copie de chaque chaîne de clés de cet ensemble.