Optimización de asignaciones de cadenas redundantes en C ++

Tengo un componente C ++ bastante complejo cuyo rendimiento se ha convertido en un problema. La creación de perfiles muestra que la mayor parte del tiempo de ejecución se dedica simplemente a asignar memoria para std::strings.

Sé que hay mucha redundancia entre esas cadenas. Un puñado de valores se repite con mucha frecuencia, pero también hay muchos valores únicos. Las cadenas suelen ser bastante cortas.

Ahora solo estoy pensando si tendría sentido reutilizar de alguna manera esas asignaciones frecuentes. En lugar de 1000 punteros a 1000 valores "foobar" distintos, podría tener 1000 punteros a un valor "foobar". El hecho de que esto sea más eficiente en la memoria es una buena ventaja, pero aquí estoy más preocupado por la latencia.

Supongo que una opción sería mantener algún tipo de registro de valores ya asignados, pero ¿es incluso posible hacer que las búsquedas en el registro sean más rápidas que las asignaciones de memoria redundantes? ¿Es este un enfoque viable?

Me baso mucho en las cadenas internas como sugiere Basile, donde una búsqueda de cadenas se traduce en un índice de 32 bits para almacenar y comparar. Eso es útil en mi caso, ya que a veces tengo cientos de miles a millones de componentes con una propiedad llamada "x", por ejemplo, que todavía debe ser un nombre de cadena fácil de usar, ya que a menudo los scripters acceden a él por nombre.

Utilizo un trie para la búsqueda (también experimenté, unordered_mappero mi trie sintonizado respaldado por grupos de memoria al menos comenzó a funcionar mejor y también fue más fácil de hacer que sea seguro para subprocesos sin solo bloquear cada vez que se accedió a la estructura) pero no es tan Rápido para la construcción como la creación std::string. El objetivo es más para acelerar las operaciones posteriores, como verificar la igualdad de la cadena que, en mi caso, se reduce a verificar la igualdad de dos enteros y reducir drásticamente el uso de la memoria.

Supongo que una opción sería mantener algún tipo de registro de valores ya asignados, pero ¿es incluso posible hacer que las búsquedas en el registro sean más rápidas que las asignaciones de memoria redundantes?

Será difícil hacer una búsqueda a través de una estructura de datos mucho más rápido que una sola malloc, por ejemplo, si tiene un caso en el que está leyendo un montón de cadenas de una entrada externa como un archivo, por ejemplo, entonces mi tentación sería usar un asignador secuencial si es posible. Eso viene con la desventaja de que no puede liberar memoria de una cadena individual. Toda la memoria agrupada por el asignador debe ser liberada de una vez o nunca. Pero un asignador secuencial puede ser útil en casos en los que solo necesita asignar un bote de pequeños trozos de memoria de tamaño variable de forma secuencial, solo para luego tirarlo todo más tarde. No sé si eso se aplica en su caso o no, pero cuando corresponda, puede ser una manera fácil de arreglar un punto de acceso relacionado con asignaciones frecuentes de memoria (que podrían tener más que ver con errores de caché y fallas de página que el subyacente algoritmo utilizado por, digamos, malloc).

Las asignaciones de tamaño fijo son más fáciles de acelerar sin las restricciones secuenciales del asignador que le impiden liberar fragmentos específicos de memoria para reutilizarlos más tarde. Pero hacer una asignación de tamaño variable más rápido que el asignador predeterminado es bastante difícil. Básicamente, hacer cualquier tipo de asignador de memoria que sea más rápido que mallocgeneralmente es extremadamente difícil si no aplica restricciones que reducen su aplicabilidad. Una solución es usar un asignador de tamaño fijo para, por ejemplo, todas las cadenas que son de 8 bytes o menos si tiene una gran cantidad de ellas y las cadenas más largas son un caso raro (para el cual solo puede usar el asignador predeterminado). Eso significa que se desperdician 7 bytes para cadenas de 1 byte, pero debería eliminar los puntos calientes relacionados con la asignación, si, digamos, el 95% del tiempo, sus cadenas son muy cortas.

Otra solución que se me acaba de ocurrir es usar listas enlazadas desenrolladas que pueden sonar locas pero escucharme.

La idea aquí es hacer que cada nodo desenrollado tenga un tamaño fijo en lugar de un tamaño variable. Cuando hace eso, puede usar un asignador de fragmentos de tamaño fijo extremadamente rápido que agrupa la memoria, asignando fragmentos de tamaño fijo para cadenas de tamaño variable unidas entre sí. Eso no reducirá el uso de memoria, tenderá a aumentar debido al costo de los enlaces, pero puede jugar con el tamaño desenrollado para encontrar un equilibrio adecuado para sus necesidades. Es una idea un poco loca, pero debería eliminar los puntos calientes relacionados con la memoria, ya que ahora puede agrupar efectivamente la memoria ya asignada en bloques contiguos voluminosos y aún tener los beneficios de liberar cadenas individualmente. Aquí hay un simple asignador fijo antiguo que escribí (uno ilustrativo que hice para otra persona, desprovisto de pelusa relacionada con la producción) que puede usar libremente:

#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;
}

Es posible que desee tener algo de maquinaria de cadena interna (pero las cadenas deben ser inmutables, así que use const std::string-s). Podrías querer algunos símbolos . Puede buscar punteros inteligentes (por ejemplo, std :: shared_ptr ). O incluso std :: string_view en C ++ 17.

Érase una vez en la construcción del compilador que usamos algo llamado silla de datos (en lugar de banco de datos, una traducción coloquial al alemán para DB). Esto simplemente creó un hash para una cadena y lo usó para la asignación. Entonces, cualquier cadena no era una pieza de memoria en el montón / pila, sino un código hash en esta silla de datos. Podrías reemplazarlo Stringpor tal clase. Sin embargo, necesita bastante retrabajo del código. Y, por supuesto, esto solo se puede usar para cadenas r / o.

Observe cómo la asignación de memoria y la memoria real utilizada se relacionan con un bajo rendimiento:

El costo de asignar realmente la memoria es, por supuesto, muy alto. Por lo tanto, std :: string ya podría usar la asignación en el lugar para cadenas pequeñas, y la cantidad de asignaciones reales podría ser más baja de lo que podría suponer primero. En caso de que el tamaño de este búfer no sea lo suficientemente grande, entonces podría inspirarse, por ejemplo, en la clase de cadena de Facebook ( https://github.com/facebook/folly/blob/master/folly/FBString.h ) que usa 23 caracteres internamente antes de asignar.

También vale la pena señalar el costo de usar mucha memoria. Este es quizás el mayor delincuente: es posible que tenga mucha RAM en su máquina, sin embargo, los tamaños de caché siguen siendo lo suficientemente pequeños como para dañar el rendimiento al acceder a la memoria que aún no está en caché. Puede leer sobre esto aquí: https://en.wikipedia.org/wiki/Locality_of_reference

En lugar de acelerar las operaciones de cadena, otro enfoque es reducir el número de operaciones de cadena. ¿Sería posible reemplazar cadenas con una enumeración, por ejemplo?

Otro enfoque que podría ser útil se usa en Cocoa: hay casos en los que tiene cientos o miles de diccionarios, todos con la misma clave. Entonces te permiten crear un objeto que es un conjunto de claves de diccionario, y hay un constructor de diccionario que toma un objeto como argumento. El diccionario se comporta igual que cualquier otro diccionario, pero cuando agrega un par clave / valor con una clave en ese conjunto de claves, la clave no se duplica sino que solo se almacena un puntero a la clave en el conjunto de claves. Por lo tanto, estos miles de diccionarios necesitan solo una copia de cada cadena clave en ese conjunto.