Оптимизация избыточного выделения строк в C ++

У меня довольно сложный компонент C ++, производительность которого стала проблемой. Профилирование показывает, что большая часть времени выполнения просто тратится на выделение памяти для std::strings.

Я знаю, что среди этих строк много избыточности. Горстка значений повторяется очень часто, но есть также много уникальных значений. Строки, как правило, довольно короткие.

Сейчас я просто думаю, имеет ли смысл каким-то образом повторно использовать эти частые распределения. Вместо 1000 указателей на 1000 различных значений «foobar» я мог бы иметь 1000 указателей на одно значение «foobar». Тот факт, что это будет более эффективно использовать память, является хорошим бонусом, но я в основном обеспокоен задержками.

Я предполагаю, что одним из вариантов было бы поддерживать какой-то реестр с уже распределенными значениями, но возможно ли вообще сделать поиск в реестре быстрее, чем избыточные выделения памяти? Это жизнеспособный подход?

Я полагаюсь на интернированные строки, как предлагает Басиле, где поиск строки преобразуется в 32-битный индекс для хранения и сравнения. Это полезно в моем случае, так как у меня иногда есть сотни тысяч или миллионы компонентов со свойством с именем «x», например, которое все еще должно быть удобным для пользователя строковым именем, так как к нему часто обращаются сценарии по имени.

Я использую три для поиска (экспериментировал также с, unordered_mapно моя настроенная трия, поддерживаемая пулами памяти, по крайней мере, начала работать лучше, а также была проще сделать поточно-безопасным, не блокируя каждый раз при обращении к структуре), но это не так быстро для строительства, как создание std::string. Суть в том, чтобы ускорить последующие операции, такие как проверка на равенство строк, что в моем случае сводится к проверке на равенство двух целых чисел и радикальному сокращению использования памяти.

Я предполагаю, что одним из вариантов было бы поддерживать какой-то реестр с уже распределенными значениями, но возможно ли вообще сделать поиск в реестре быстрее, чем избыточные выделения памяти?

Это будет трудно сделать поиск по структуре данных намного быстрее, чем один mallocНапример, если у вас есть случай, когда вы читаете множество строк из внешнего ввода, например, из файла, то у меня будет соблазн использовать последовательный распределитель, если это возможно. Это связано с тем недостатком, что вы не можете освободить память отдельной строки. Вся память, объединенная распределителем, должна быть освобождена сразу или не освобождена вовсе. Но последовательный распределитель может быть полезен в тех случаях, когда вам просто нужно выделить кучу крошечных кусков памяти переменного размера прямым последовательным образом, только чтобы потом отбросить все это позже. Я не знаю, применимо ли это к вашему случаю или нет, но когда это применимо, это может быть простой способ исправить горячую точку, связанную с частым выделением памяти для подростка (которая может быть больше связана с промахами кэша и ошибками страницы, чем с основной алгоритм, используемый, скажем, malloc).

Выделения фиксированного размера легче ускорить без ограничений последовательного выделения, которые не позволяют освободить определенные куски памяти для последующего повторного использования. Но сделать распределение с переменным размером быстрее, чем распределитель по умолчанию, довольно сложно. По сути, создание любого вида распределителя памяти быстрее, чем mallocобычно, чрезвычайно сложно, если вы не применяете ограничения, которые сужают его применимость. Одно из решений состоит в том, чтобы использовать распределитель фиксированного размера, скажем, для всех строк размером 8 байт или менее, если у вас есть их загрузка, а более длинные строки - редкий случай (для которого вы можете просто использовать распределитель по умолчанию). Это означает, что 7 байтов тратятся на однобайтовые строки, но это должно исключить связанные с выделением точки доступа, если, скажем, в 95% случаев ваши строки очень короткие.

Другое решение, которое только что пришло мне в голову, - это использовать развернутые связанные списки, которые могут показаться странными, но выслушать меня.

Идея здесь состоит в том, чтобы сделать каждый развернутый узел фиксированным размером вместо переменного размера. Когда вы это сделаете, вы сможете использовать чрезвычайно быстрый распределитель чанков фиксированного размера, который объединяет память, выделяя чанки фиксированного размера для строк переменного размера, связанных вместе. Это не уменьшит использование памяти, оно будет увеличиваться из-за стоимости ссылок, но вы можете поиграть с развернутым размером, чтобы найти баланс, подходящий для ваших нужд. Это своего рода дурацкая идея, но она должна исключить связанные с памятью горячие точки, поскольку теперь вы можете эффективно объединять память, уже распределенную в громоздких смежных блоках, и при этом иметь преимущества освобождения строк по отдельности. Вот простой старый фиксированный распределитель, который я написал (иллюстративный, который я сделал для кого-то другого, без пуха, связанного с производством), который вы можете свободно использовать:

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

Возможно, вы захотите иметь несколько машин с внутренними строками (но строки должны быть неизменяемыми, поэтому используйте const std::string-s). Вы могли бы хотеть некоторые символы . Вы можете посмотреть на умные указатели (например, std :: shared_ptr ). Или даже std :: string_view в C ++ 17.

Когда-то в построении компилятора мы использовали нечто, называемое data-chair (вместо data-bank, разговорный немецкий перевод для БД). Это просто создало хеш для строки и использовало его для выделения. Таким образом, любая строка была не частью памяти в куче / стеке, а хеш-кодом в этом кресле данных. Вы могли бы заменить Stringна такой класс. Тем не менее, нуждается в некоторой переработке кода. И, конечно, это можно использовать только для строк ввода / вывода.

Обратите внимание, как распределение памяти и используемая память связаны с низкой производительностью:

Стоимость фактического выделения памяти, конечно, очень высока. Поэтому std :: string может уже использовать размещение на месте для небольших строк, и поэтому количество фактических выделений может быть меньше, чем вы могли бы сначала предположить. Если размер этого буфера недостаточно велик, вас может вдохновить, например, класс строки Facebook ( https://github.com/facebook/folly/blob/master/folly/FBString.h ), который использует 23 символа внутренне перед распределением.

Стоит также отметить стоимость использования большого количества памяти. Возможно, это самое серьезное нарушение: у вас может быть достаточно оперативной памяти на вашем компьютере, однако размеры кэша по-прежнему достаточно малы, что ухудшит производительность при доступе к памяти, которая еще не кэширована. Вы можете прочитать об этом здесь: https://en.wikipedia.org/wiki/Locality_of_reference

Вместо ускорения строковых операций, другой подход заключается в сокращении числа строковых операций. Можно ли заменить строки с перечислением, например?

Другой подход, который может быть полезен, используется в Какао: есть случаи, когда у вас есть сотни или тысячи словарей, все с главным образом одним и тем же ключом. Таким образом, они позволяют вам создать объект, который представляет собой набор ключей словаря, и есть конструктор словаря, который принимает такой объект в качестве аргумента. Словарь ведет себя так же, как и любой другой словарь, но когда вы добавляете пару ключ / значение с ключом в этот набор ключей, ключ не дублируется, а просто указатель на ключ в наборе ключей сохраняется. Таким образом, эти тысячи словарей нуждаются только в одной копии каждой ключевой строки в этом наборе.