Optymalizacja alokacji nadmiarowych ciągów w C ++

Mam dość złożony komponent C ++, którego wydajność stała się problemem. Profilowanie pokazuje, że większość czasu wykonywania jest po prostu poświęcana na przydzielanie pamięci dla std::strings.

Wiem, że wśród tych ciągów jest dużo redundancji. Garść wartości powtarza się bardzo często, ale istnieje również wiele unikalnych wartości. Ciągi są zazwyczaj dość krótkie.

Zastanawiam się teraz, czy sensowne byłoby ponowne wykorzystanie tych częstych przydziałów. Zamiast 1000 wskaźników do 1000 różnych wartości „foobar”, mógłbym mieć 1000 wskaźników do jednej wartości „foobar”. Fakt, że byłoby to bardziej wydajne pod względem pamięci, jest fajną zaletą, ale najbardziej martwię się tutaj o opóźnienia.

Wydaje mi się, że jedną z opcji byłoby utrzymywanie pewnego rodzaju rejestru już przydzielonych wartości, ale czy jest nawet możliwe, aby wyszukiwanie rejestru było szybsze niż nadmiarowe przydziały pamięci? Czy to realne podejście?

Opieram się mocno na internowanych ciągach, jak sugeruje Basile, gdzie wyszukiwanie ciągów przekłada się na 32-bitowy indeks do przechowywania i porównywania. Jest to przydatne w moim przypadku, ponieważ czasami mam setki tysięcy do milionów komponentów z właściwością o nazwie „x”, np. Która wciąż musi być przyjazną dla użytkownika nazwą ciągu, ponieważ jest często dostępna dla skrypterów według nazwy.

Używam trie do wyszukiwania (eksperymentowałem również z, unordered_mapale mój tuning trie wspierany przez pule pamięci przynajmniej zaczął działać lepiej i łatwiej było też zabezpieczyć wątek bez blokowania przy każdym dostępie do struktury), ale nie jest tak szybki do budowy jako tworzenie std::string. Chodzi o to, aby przyspieszyć kolejne operacje, takie jak sprawdzanie równości ciągów, co w moim przypadku sprowadza się do sprawdzenia dwóch liczb całkowitych pod kątem równości i drastycznego zmniejszenia zużycia pamięci.

Wydaje mi się, że jedną z opcji byłoby utrzymywanie pewnego rodzaju rejestru już przydzielonych wartości, ale czy jest nawet możliwe, aby wyszukiwanie rejestru było szybsze niż nadmiarowe przydziały pamięci?

Trudno będzie przeszukać strukturę danych znacznie szybciej niż pojedynczy malloc, np. jeśli masz przypadek, w którym odczytujesz ładunek ciągów znaków z zewnętrznego wejścia, na przykład pliku, wtedy moją pokusą byłoby użycie sekwencyjnego alokatora, jeśli to możliwe. Ma to tę wadę, że nie można zwolnić pamięci pojedynczego łańcucha. Cała pamięć zgromadzona przez alokator musi zostać uwolniona od razu lub wcale. Ale sekwencyjny alokator może być przydatny w przypadkach, w których po prostu musisz przydzielić ładunek niewielkich fragmentów pamięci o zmiennej wielkości w prosty sekwencyjny sposób, tylko po to, aby później to wszystko wyrzucić. Nie wiem, czy ma to zastosowanie w twoim przypadku, czy nie, ale w stosownych przypadkach może to być prosty sposób na naprawienie hotspotu związanego z częstymi alokacjami pamięci (które mogą mieć więcej wspólnego z błędami pamięci podręcznej i błędami strony niż z bazowymi algorytm używany, powiedzmy, malloc).

Przydziały o stałej wielkości są łatwiejsze do przyspieszenia bez ograniczeń sekwencyjnych, które uniemożliwiają zwolnienie określonych fragmentów pamięci do ponownego wykorzystania. Jednak szybsze przydzielanie przydziałów o zmiennej wielkości niż domyślny jest dość trudne. Zasadniczo tworzenie dowolnego rodzaju alokatora pamięci, który jest szybszy niż mallocjest ogólnie wyjątkowo trudny, jeśli nie zastosujesz ograniczeń ograniczających jego zastosowanie. Jednym z rozwiązań jest użycie dzielnika o stałej wielkości, powiedzmy, dla wszystkich ciągów, które mają 8 bajtów lub mniej, jeśli masz ich ładunek, a dłuższe ciągi są rzadkim przypadkiem (dla którego możesz po prostu użyć domyślnego przydziału). Oznacza to, że 7 bajtów jest marnowanych na łańcuchy 1-bajtowe, ale powinno to wyeliminować hotspoty związane z alokacją, jeśli, powiedzmy, w 95% przypadków, twoje łańcuchy są bardzo krótkie.

Innym rozwiązaniem, które właśnie mi przyszło do głowy, jest użycie rozwiniętych połączonych list, które mogą wydawać się szalone, ale mnie wysłuchaj.

Chodzi o to, aby każdy rozwinięty węzeł miał stały rozmiar zamiast zmiennej wielkości. Gdy to zrobisz, możesz użyć niezwykle szybkiego przydziału porcji o stałej wielkości, który gromadzi pamięć, przydzielając porcje o stałej wielkości do połączonych ze sobą łańcuchów o zmiennej wielkości. Nie zmniejszy to zużycia pamięci, będzie się do niej dodawać ze względu na koszt linków, ale możesz grać z rozwiniętym rozmiarem, aby znaleźć równowagę odpowiednią dla twoich potrzeb. Jest to trochę zwariowany pomysł, ale powinien wyeliminować hotspoty związane z pamięcią, ponieważ możesz teraz skutecznie grupować pamięć już przydzieloną w dużych, ciągłych blokach i nadal mieć korzyści z indywidualnego uwalniania ciągów. Oto prosty stary ustalony alokator (ilustracyjny, który zrobiłem dla kogoś innego, pozbawiony puchu związanego z produkcją), z którego możesz swobodnie korzystać:

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

Możesz chcieć mieć wewnętrzną maszynerię ciągów (ale ciągi powinny być niezmienne, więc użyj const std::string-s). Możesz chcieć symboli . Możesz spojrzeć na inteligentne wskaźniki (np. Std :: shared_ptr ). Lub nawet std :: string_view w C ++ 17.

Dawno, dawno temu w budowie kompilatora używaliśmy czegoś, co nazywa się krzesłem danych (zamiast banku danych, potocznym tłumaczeniem języka niemieckiego na DB). To po prostu utworzyło skrót dla ciągu i wykorzystało go do alokacji. Więc żaden ciąg nie był jakimś fragmentem pamięci na stercie / stosie, ale kodem skrótu w tym krześle danych. Możesz zastąpić Stringtaką klasą. Jednak wymaga sporo przeróbek kodu. I oczywiście jest to użyteczne tylko dla ciągów r / o.

Zauważ, że zarówno przydział pamięci, jak i faktyczna pamięć są powiązane ze słabą wydajnością:

Koszt faktycznej alokacji pamięci jest oczywiście bardzo wysoki. Dlatego też std :: string może już używać alokacji w miejscu dla małych łańcuchów, a zatem liczba faktycznych alokacji może być niższa niż można się było spodziewać. Jeśli rozmiar tego bufora nie jest wystarczająco duży, możesz zainspirować się np. Klasą ciągów znaków Facebooka ( https://github.com/facebook/folly/blob/master/folly/FBString.h ), która używa 23 znaków wewnętrznie przed alokacją.

Warto również zwrócić uwagę na koszt użycia dużej ilości pamięci. Jest to być może największy przestępca: możesz mieć dużo pamięci RAM w swoim komputerze, jednak rozmiary pamięci podręcznej są wciąż wystarczająco małe, aby obniżyć wydajność podczas uzyskiwania dostępu do pamięci, która nie jest jeszcze buforowana. Możesz przeczytać o tym tutaj: https://en.wikipedia.org/wiki/Locality_of_reference

Zamiast przyspieszyć operacje na łańcuchach, innym podejściem jest zmniejszenie liczby operacji na łańcuchach. Czy na przykład byłoby możliwe zastąpienie ciągów znakiem wyliczeniem?

Inne podejście, które może być przydatne, jest stosowane w kakao: Istnieją przypadki, w których masz setki lub tysiące słowników, z których większość ma ten sam klucz. Pozwalają więc stworzyć obiekt, który jest zestawem kluczy słownikowych, i istnieje konstruktor słownikowy, który przyjmuje taki obiekt jako argument. Słownik zachowuje się tak samo, jak każdy inny słownik, ale po dodaniu pary klucz / wartość z kluczem w tym zestawie kluczy klucz nie jest duplikowany, ale przechowywany jest tylko wskaźnik do klucza w zestawie kluczy. Te tysiące słowników potrzebują tylko jednej kopii każdego ciągu klucza w tym zestawie.