Optimieren redundanter Zeichenfolgenzuordnungen in C ++

Ich habe eine ziemlich komplexe C ++ - Komponente, deren Leistung zu einem Problem geworden ist. Die Profilerstellung zeigt, dass der größte Teil der Ausführungszeit lediglich für die Zuweisung von Speicher für std::strings aufgewendet wird .

Ich weiß, dass diese Zeichenfolgen sehr redundant sind. Eine Handvoll Werte wiederholen sich sehr häufig, aber es gibt auch viele eindeutige Werte. Die Saiten sind normalerweise ziemlich kurz.

Ich denke jetzt nur, ob es Sinn machen würde, diese häufigen Zuweisungen irgendwie wiederzuverwenden. Anstelle von 1000 Zeigern auf 1000 verschiedene "foobar" -Werte könnte ich 1000 Zeiger auf einen "foobar" -Wert haben. Die Tatsache, dass dies speichereffizienter wäre, ist ein schöner Bonus, aber ich mache mir hier hauptsächlich Sorgen um die Latenz.

Ich denke, eine Option wäre, eine Art Registrierung mit bereits zugewiesenen Werten zu verwalten, aber ist es überhaupt möglich, die Registrierung schneller zu suchen als redundante Speicherzuweisungen? Ist das ein praktikabler Ansatz?

Ich stütze mich stark auf internierte Zeichenfolgen, wie Basile vorschlägt, wo eine Zeichenfolgensuche in einen 32-Bit-Index übersetzt wird, um sie zu speichern und zu vergleichen. Dies ist in meinem Fall nützlich, da ich manchmal Hunderttausende bis Millionen von Komponenten mit einer Eigenschaft namens "x" habe, z. B. die immer noch ein benutzerfreundlicher Zeichenfolgenname sein muss, da Skripter häufig namentlich darauf zugreifen.

Ich verwende einen Trie für die Suche (experimentiert auch mit, unordered_mapaber mein optimierter Trie, der von Speicherpools unterstützt wird, zeigte zumindest eine bessere Leistung und war auch einfacher, Thread-sicher zu machen, ohne jedes Mal, wenn auf die Struktur zugegriffen wurde, nur zu sperren), aber es ist nicht so schnell zum bauen als schaffen std::string. Es geht mehr darum, die nachfolgenden Vorgänge wie das Überprüfen der Zeichenfolgengleichheit zu beschleunigen, was in meinem Fall nur darauf hinausläuft, zwei Ganzzahlen auf Gleichheit zu überprüfen und die Speichernutzung drastisch zu reduzieren.

Ich denke, eine Option wäre, eine Art Registrierung mit bereits zugewiesenen Werten zu verwalten, aber ist es überhaupt möglich, die Registrierung schneller zu suchen als redundante Speicherzuweisungen?

Es wird schwierig sein, eine Datenstruktur viel schneller als eine einzelne zu durchsuchen mallocWenn Sie beispielsweise einen Fall haben, in dem Sie eine Schiffsladung von Zeichenfolgen von einer externen Eingabe wie beispielsweise einer Datei lesen, besteht meine Versuchung darin, wenn möglich einen sequentiellen Allokator zu verwenden. Das hat den Nachteil, dass Sie den Speicher einer einzelnen Zeichenfolge nicht freigeben können. Der gesamte vom Allokator gepoolte Speicher muss sofort oder gar nicht freigegeben werden. Ein sequentieller Allokator kann jedoch nützlich sein, wenn Sie nur eine Schiffsladung winziger Speicherblöcke variabler Größe direkt sequentiell zuweisen müssen, um sie später wieder wegzuwerfen. Ich weiß nicht, ob dies in Ihrem Fall zutrifft oder nicht, aber wenn zutreffend, kann es eine einfache Möglichkeit sein, einen Hotspot zu beheben, der mit häufigen Speicherzuweisungen für Jugendliche zusammenhängt (was möglicherweise mehr mit Cache-Fehlern und Seitenfehlern als mit dem zugrunde liegenden zu tun hat Algorithmus, der beispielsweise von malloc) verwendet wird.

Zuordnungen mit fester Größe lassen sich ohne die Einschränkungen für sequentielle Zuordnungen, die Sie daran hindern, bestimmte Speicherblöcke für die spätere Wiederverwendung freizugeben, einfacher beschleunigen. Es ist jedoch ziemlich schwierig, die Zuweisung mit variabler Größe schneller als die Standardzuweisung zu machen. Grundsätzlich mallocist es extrem schwierig , einen Speicherzuweiser zu erstellen, der schneller als im Allgemeinen ist, wenn Sie keine Einschränkungen anwenden, die seine Anwendbarkeit einschränken. Eine Lösung besteht darin, einen Allokator mit fester Größe für beispielsweise alle Zeichenfolgen zu verwenden, die 8 Byte oder weniger umfassen, wenn Sie eine Schiffsladung davon haben, und längere Zeichenfolgen sind ein seltener Fall (für den Sie nur den Standardzuweiser verwenden können). Das bedeutet, dass 7 Bytes für 1-Byte-Zeichenfolgen verschwendet werden, aber es sollten allokationsbezogene Hotspots eliminiert werden, wenn Ihre Zeichenfolgen beispielsweise in 95% der Fälle sehr kurz sind.

Eine andere Lösung, die mir gerade eingefallen ist, besteht darin, nicht gerollte verknüpfte Listen zu verwenden, die vielleicht verrückt klingen, mich aber anhören.

Die Idee hier ist, jeden nicht gerollten Knoten zu einer festen Größe anstatt zu einer variablen Größe zu machen. Wenn Sie dies tun, können Sie einen extrem schnellen Chunk-Allokator mit fester Größe verwenden, der Speicher bündelt und Chunks mit fester Größe für miteinander verknüpfte Strings mit variabler Größe zuweist. Dadurch wird der Speicherbedarf nicht verringert, sondern aufgrund der Kosten für die Links wird der Wert tendenziell erhöht. Sie können jedoch mit der nicht gerollten Größe spielen, um ein für Ihre Anforderungen geeignetes Gleichgewicht zu finden. Es ist eine verrückte Idee, sollte aber speicherbezogene Hotspots eliminieren, da Sie jetzt bereits in sperrigen zusammenhängenden Blöcken zugewiesenen Speicher effektiv bündeln können und dennoch die Vorteile haben, Zeichenfolgen einzeln freizugeben. Hier ist ein einfacher alter fester Allokator, den ich geschrieben habe (illustrativer Allokator, den ich für jemand anderen gemacht habe, ohne produktionsbedingte Flusen), den Sie frei verwenden können:

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

Möglicherweise möchten Sie eine interne String- Maschinerie haben (aber die Strings sollten unveränderlich sein, verwenden Sie also const std::string-s). Sie könnten einige Symbole wollen . Sie könnten sich mit intelligenten Zeigern befassen (z. B. std :: shared_ptr ). Oder sogar std :: string_view in C ++ 17.

Es war einmal in der Compilerkonstruktion, als wir so etwas wie Data-Chair verwendeten (anstelle von Database, einer umgangssprachlichen deutschen Übersetzung für DB). Dadurch wurde einfach ein Hash für eine Zeichenfolge erstellt und dieser für die Zuweisung verwendet. Jeder String war also kein Stück Speicher auf Heap / Stack, sondern ein Hash-Code in diesem Data-Chair. Sie könnten Stringdurch eine solche Klasse ersetzen . Benötigt jedoch einige Code-Überarbeitungen. Und dies ist natürlich nur für R / O-Strings verwendbar.

Beachten Sie, wie sich die Speicherzuweisung und der tatsächlich verwendete Speicher auf eine schlechte Leistung auswirken:

Die Kosten für die tatsächliche Zuweisung des Speichers sind natürlich sehr hoch. Daher verwendet std :: string möglicherweise bereits eine direkte Zuweisung für kleine Zeichenfolgen, und die Anzahl der tatsächlichen Zuweisungen ist daher möglicherweise geringer, als Sie zunächst annehmen. Falls die Größe dieses Puffers nicht groß genug ist, können Sie sich beispielsweise von der Facebook-Zeichenfolgenklasse ( https://github.com/facebook/folly/blob/master/folly/FBString.h ) inspirieren lassen, die 23 Zeichen verwendet intern vor der Zuteilung.

Erwähnenswert sind auch die Kosten für die Verwendung von viel Speicher. Dies ist möglicherweise der größte Übeltäter: Möglicherweise verfügt Ihr Computer über ausreichend RAM. Die Cache-Größen sind jedoch immer noch so klein, dass die Leistung beim Zugriff auf nicht bereits zwischengespeicherten Speicher beeinträchtigt wird. Sie können dies hier lesen: https://en.wikipedia.org/wiki/Locality_of_reference

Anstatt String-Operationen schneller zu machen, besteht ein anderer Ansatz darin, die Anzahl der String-Operationen zu reduzieren. Wäre es beispielsweise möglich, Zeichenfolgen durch eine Aufzählung zu ersetzen?

Ein anderer Ansatz, der nützlich sein könnte, wird in Cocoa verwendet: Es gibt Fälle, in denen Sie Hunderte oder Tausende von Wörterbüchern haben, die alle meist denselben Schlüssel haben. Sie können also ein Objekt erstellen, das aus einer Reihe von Wörterbuchschlüsseln besteht, und es gibt einen Wörterbuchkonstruktor, der ein solches Objekt als Argument verwendet. Das Wörterbuch verhält sich wie jedes andere Wörterbuch. Wenn Sie jedoch ein Schlüssel / Wert-Paar mit einem Schlüssel in diesem Schlüsselsatz hinzufügen, wird der Schlüssel nicht dupliziert, sondern nur ein Zeiger auf den Schlüssel im Schlüsselsatz gespeichert. Diese Tausenden von Wörterbüchern benötigen also nur eine Kopie jeder Schlüsselzeichenfolge in diesem Satz.