Ottimizzazione delle allocazioni di stringhe ridondanti in C ++

Mi baso molto sulle stringhe internamente, come suggerisce Basile, dove una ricerca di stringhe si traduce in un indice a 32 bit da memorizzare e confrontare. Ciò è utile nel mio caso poiché talvolta ho centinaia di migliaia o milioni di componenti con una proprietà denominata "x", ad esempio, che deve ancora essere un nome di stringa di facile utilizzo poiché è spesso utilizzato dagli sceneggiatori per nome.

Uso un trie per la ricerca (sperimentato anche con unordered_map ma il mio trie sintonizzato supportato da pool di memoria ha iniziato almeno a funzionare meglio ed era anche più facile da rendere thread-safe senza il solo blocco ogni volta che si accede alla struttura) ma non è così veloce per la costruzione quanto creare std::string . Il punto è più di accelerare le operazioni successive come verificare l'uguaglianza delle stringhe che, nel mio caso, si riduce a controllare due interi per l'uguaglianza e ridurre drasticamente l'utilizzo della memoria.

I guess one option would be to maintain some kind of a registry of already allocated values but is it even possible to make the registry lookups faster than redundant memory allocations?

Sarà difficile effettuare una ricerca attraverso una struttura dati molto più veloce di un singolo malloc , ad es. Se si ha un caso in cui si sta leggendo un carico di archi di stringhe da un input esterno come un file, ad esempio, allora la mia tentazione sarebbe quella di utilizzare un allocatore sequenziale se possibile. Ciò comporta uno svantaggio del fatto che non è possibile liberare memoria di una singola stringa. Tutta la memoria messa in comune dall'allocatore deve essere liberata in una volta o per niente. Ma un allocatore sequenziale può essere utile nei casi in cui è sufficiente allocare un carico di piccoli frammenti di memoria di dimensioni variabili in modo sequenziale, per poi gettarli via in un secondo momento. Non so se questo si applica al tuo caso o meno, ma se applicabile, può essere un modo semplice per correggere un hotspot relativo a frequenti allocazioni di memoria teeny (che potrebbero avere più a che fare con errori di cache e errori di pagina rispetto al sottostante algoritmo utilizzato da, diciamo, malloc ).

Le allocazioni di dimensioni fisse sono più facili da accelerare senza i vincoli di allocatore sequenziale che impediscono di riutilizzare blocchi di memoria specifici da riutilizzare in seguito. Ma rendere l'allocazione di dimensioni variabili più veloce dell'allattore predefinito è piuttosto difficile. Fondamentalmente, rendere qualsiasi tipo di allocatore di memoria più veloce di malloc è generalmente estremamente difficile se non si applicano vincoli che ne restringono l'applicabilità. Una soluzione consiste nell'utilizzare un allocatore di dimensioni fisse per, diciamo, tutte le stringhe che sono 8 byte o meno se si dispone di un carico di barca di esse e stringhe più lunghe sono un caso raro (per il quale è sufficiente utilizzare l'allocatore predefinito). Ciò significa che 7 byte vengono sprecati per stringhe da 1 byte, ma dovrebbe eliminare gli hotspot relativi all'allocazione, se, ad esempio, il 95% delle volte le stringhe sono molto brevi.

Un'altra soluzione che mi è appena venuta in mente è quella di usare liste collegate srotolate che potrebbero sembrare pazzesche, ma ascoltami.

L'ideaquièdirendereciascunnodosrotolatounadimensionefissaanzichéunavariabile.Quandosieseguequestaoperazione,èpossibileutilizzareunallocatorediblocchididimensionifisseestremamentevelocecheraggruppalamemoria,allocandoblocchididimensionifisseperstringhedidimensionivariabilicollegateinsieme.Ciònonridurràl'usodellamemoria,matenderàadaggiungerloacausadelcostodeicollegamenti,mapuoigiocareconledimensionisrotolatepertrovareunequilibrioadattoalletueesigenze.Èunaspeciediideastravagante,madovrebbeeliminareglihotspotrelativiallamemoriapoichéoraèpossibileraggruppareinmodoefficacelamemoriagiàallocatainblocchicontiguiingombrantieavereancoraivantaggidiliberarelestringhesingolarmente.Eccounsempliceallocatorefissochehoscritto(unoillustrativochehorealizzatoperqualcunaltro,privodifluffrelativiallaproduzione)chepuoiusareliberamente:

#ifndefFIXED_ALLOCATOR_HPP#defineFIXED_ALLOCATOR_HPPclassFixedAllocator{public:///Createsafixedallocatorwiththespecifiedtypeandblocksize.explicitFixedAllocator(inttype_size,intblock_size=2048);///Destroystheallocator.~FixedAllocator();///@returnApointertoanewlyallocatedchunk.void*allocate();///Freesthespecifiedchunk.voiddeallocate(void*mem);private:structBlock;structFreeElement;FreeElement*free_element;Block*head;inttype_size;intnum_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;
}

Potresti desiderare di avere qualche stringa interna (ma le stringhe devono essere immutabili, quindi usa const std::string - S). Potresti desiderare alcuni simboli . Potresti esaminare punti intelligenti (ad es. std :: shared_ptr ). O anche std :: string_view in C ++ 17.

C'era una volta nella costruzione del compilatore che usavamo qualcosa chiamato data-chair (invece di data-bank, una traduzione tedesca colloquiale per DB). Questo ha semplicemente creato un hash per una stringa e usato quello per l'allocazione. Quindi ogni stringa non era un pezzo di memoria su heap / stack ma un codice hash in questa sedia dati. Puoi sostituire String con tale classe. Ha bisogno di un po 'di rilavorazione del codice, però. E ovviamente questo è utilizzabile solo per le stringhe di r / o.

Si noti come l'allocazione della memoria e la memoria effettiva utilizzate si riferiscono a prestazioni scadenti:

Il costo dell'allocazione effettiva della memoria è, ovviamente, molto alto. Pertanto std :: string potrebbe già utilizzare l'allocazione sul posto per stringhe di piccole dimensioni e l'importo delle allocazioni effettive potrebbe pertanto essere inferiore a quello che si potrebbe supporre. Nel caso in cui la dimensione di questo buffer non sia abbastanza grande, potresti essere ispirato, ad es. La classe di stringa di Facebook ( link ) che utilizza internamente 23 caratteri prima di allocarli.

Vale anche la pena notare il costo di utilizzare molta memoria. Questo è forse il più grande delinquente: si potrebbe avere un sacco di RAM nella macchina, tuttavia, le dimensioni della cache sono ancora abbastanza piccole da compromettere le prestazioni quando si accede alla memoria che non è già memorizzata nella cache. Puoi leggere su questo qui: link

Invece di rendere più veloci le operazioni sulle stringhe, un altro approccio consiste nel ridurre il numero di operazioni sulle stringhe. Sarebbe possibile sostituire stringhe con un enum, per esempio?

Un altro approccio che potrebbe essere utile è usato in Cocoa: ci sono casi in cui hai centinaia o migliaia di dizionari, tutti con la stessa chiave. Così ti permettono di creare un oggetto che è un insieme di chiavi del dizionario, e c'è un costruttore di dizionari che accetta tale oggetto come argomento. Il dizionario si comporta come qualsiasi altro dizionario, ma quando aggiungi una coppia chiave / valore con una chiave in quella serie di chiavi, la chiave non viene duplicata, ma viene memorizzato solo un puntatore alla chiave nella serie di chiavi. Quindi queste migliaia di dizionari hanno bisogno di una sola copia di ogni stringa di chiavi in quel set.