`std::string` распределения - мое текущее узкое место - как я могу оптимизировать с помощью настраиваемого распределителя?

Ответ 1

По умолчанию std::string выделяет память по мере необходимости из той же кучи, что и все, что вы выделяете с помощью malloc или new. Чтобы получить прирост производительности от предоставления собственного пользовательского распределителя, вам нужно будет управлять своим "куском" памяти таким образом, чтобы ваш распределитель мог обрабатывать объемы памяти, которые ваши строки запрашивают быстрее, чем malloc., Менеджер памяти будет делать относительно немного вызовов malloc (или new, в зависимости от вашего подхода) под капотом, запрашивая сразу "большие" объемы памяти, затем обрабатывать разделы этого (этого) блока памяти ( s) через пользовательский распределитель. Чтобы добиться лучшей производительности, чем malloc, ваш менеджер памяти, как правило, должен быть настроен на основе известных шаблонов распределения ваших случаев использования.

Подобные вещи часто сводятся к вековой борьбе с использованием памяти и скорости исполнения. Например: если у вас есть известная верхняя граница ваших размеров строк на практике, вы можете тянуть трюки с избыточным распределением, чтобы всегда вмещать самый большой случай. Хотя это расточительно относится к ресурсам вашей памяти, это может облегчить накладные расходы на производительность, с которыми сталкивается более обобщенное распределение, с фрагментацией памяти. Как и любые вызовы realloc по существу постоянного времени для ваших целей.

@sehe точно верно. Существует много способов.

EDIT:

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

Например:

class myalloc : public std::allocator<char>{};
myalloc customAllocator;

int main(void)
{
  std::string mystring(customAllocator);
  std::string regularString = "test string";
  mystring = regularString;
  std::cout << mystring;

  return 0;
}

Это довольно глупый пример и, конечно же, использует тот же код рабочей лошади под капотом. Тем не менее, он показывает назначение между строками с использованием классов-распределителей "разных типов". Реализация полезного распределителя, который обеспечивает полный интерфейс, требуемый STL, без маскировки значения по умолчанию std::allocator не так тривиально. Это, похоже, достойная запись, охватывающая вовлеченные концепции. Ключ к тому, почему это работает, в контексте вашего вопроса, по крайней мере, заключается в том, что использование разных распределителей не приводит к тому, что строки имеют разный тип. Обратите внимание, что пользовательский распределитель задается в качестве аргумента конструктору, а не параметром шаблона. STL по-прежнему делает забавные вещи с шаблонами (такими как rebind и Traits) для гомогенизации интерфейсов распределителя и отслеживания.

Ответ 2

Думаю, вам лучше всего воспользоваться, прочитав EASTL

В нем есть раздел о распределителях, и вы можете найти fixed_string полезным.

Ответ 3

Пользовательские распределители могут помочь, поскольку большинство реализаций malloc()/new разработаны для максимальной гибкости, обеспечения безопасности потоков и пуленепробиваемой работы. Например, они должны изящно обрабатывать случай, когда один поток продолжает выделять память, отправляя указатели на другой поток, который освобождает их. Такие вещи трудно обрабатывать по-настоящему и управлять стоимостью вызовов malloc().

Однако, если вы знаете, что некоторые вещи не могут произойти в вашем приложении (например, один поток, освобождающий другой выделенный ресурс и т.д.), вы можете оптимизировать свой распределитель дальше стандартной реализации. Это может дать значительные результаты, особенно если вам не нужна безопасность потока.

Кроме того, стандартная реализация не обязательно хорошо оптимизирована: реализация void* operator new(size_t size) и void operator delete(void* pointer) путем простого вызова malloc() и free() дает среднее увеличение производительности на 100 процессоров на моей машине, что доказывает, что реализация по умолчанию является неоптимальной.

Ответ 4

То, что часто помогает, - это создание GlobalStringTable.

Посмотрите, можете ли вы найти части старой библиотеки NiMain из ныне не существующего стека программного обеспечения NetImmerse. Он содержит пример реализации.

Lifetime

Важно отметить, что эта таблица строк должна быть доступна между различными пространствами DLL и что она не является статическим объектом. Р. Мартиньо Фернандес уже предупреждал, что объект должен быть создан, когда приложение или поток DLL создается/прикрепляется и удаляется, когда поток уничтожается или dll отделяется, и предпочтительно перед тем, как какой-либо строковый объект фактически используется. Это звучит проще, чем на самом деле.

Распределение памяти

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

Размещение нового

Что-то, что часто работает хорошо, называется оператором new() размещения, где вы можете указать, где в памяти должен быть выделен ваш новый строковый объект. Однако вместо распределения оператор может просто захватить место памяти, которое передается в качестве аргумента, нуль памяти в этом месте и вернуть его. Вы также можете отслеживать распределение, фактический размер строки и т.д. В объекте Globalstringtable.

SOA

Обработка фактического планирования памяти - это то, что вам нужно, но есть много возможных способов приблизиться к этому. Часто выделенное пространство разбивается на несколько областей, так что у вас есть несколько блоков на возможный размер строки. Блок для строк <= 4 байта, один для <= 8 байтов и т.д. Это называется Small Object Allocator и может быть реализовано для любого типа и буфера.

Если вы ожидаете много строковых операций, когда маленькие строки будут увеличиваться несколько раз, вы можете изменить свою стратегию и распределить большие буферы с самого начала, чтобы количество операций memmove было уменьшено. Или вы можете выбрать другой подход и использовать потоки строк для них.

Строковые операции

Неплохая идея состоит из std:: basic_str, так что большая часть операций все еще работает, но внутренняя память фактически находится в GlobalStringTable, так что вы можете продолжать использовать те же соглашения stl. Таким образом, вы также убедитесь, что все распределения находятся в пределах одной DLL, так что не может быть никакого кучного повреждения, связывая различные типы строк между разными библиотеками, поскольку все операции выделения по существу находятся в вашей DLL (и перенаправляются на объект GlobalStringTable)

Ответ 5

Лучший способ избежать выделения памяти - это не делать! НО, если я правильно помню JSON, все значения readStr либо используются в качестве ключей, либо как идентификаторы, поэтому вам придется выделять их в конечном итоге, std:: strings move semantics должны гарантировать, что выделенный массив не будет скопирован, а повторно использован до его окончательного использования. По умолчанию NRVO/RVO/Move должен уменьшать любое копирование данных, если не в самом заголовке строки.

Способ 1:
Передайте результат в виде ссылки от вызывающего, который зарезервировал символы SomeResonableLargeValue, а затем очистит его в начале readStr. Это можно использовать только в том случае, если вызывающий объект может повторно использовать строку.

Способ 2:
Используйте стек.

// Reserve memory for the string (BOTTLENECK)
if (end - idx < SomeReasonableValue) { // 32?
  char result[SomeReasonableValue] = {0};  // feel free to use std::array if you want bounds checking, but the preceding "if" should insure its not a problem.
  int ridx = 0;

  for(; idx < end; ++idx) {
    // Not an escape sequence
    if(!isC('\\')) { result[ridx++] = getC(); continue; }
    // Escape sequence: skip '\'
    ++idx;
    // Convert escape sequence
    result[ridx++] = getEscapeSequence(getC());
  }

  // Skip closing '"'
  ++idx;
  result[ridx] = 0; // 0-terminated.
  // optional assert here to insure nothing went wrong.
  return result; // the bottleneck might now move here as the data is copied to the receiving string.
}
// fallback code only if the string is long.
// Your original code here

Способ 3:
Если ваша строка по умолчанию может выделить некоторый размер для заполнения границы 32/64 байта, вы можете попытаться использовать это, постройте result, как это, вместо этого, если конструктор может его оптимизировать.

Str result(end - idx, 0);

Способ 4:
В большинстве систем уже есть оптимизированный распределитель, похожий на конкретные размеры блоков, 16,32,64 и т.д.

siz = ((end - idx)&~0xf)+16; // if the allocator has chunks of 16 bytes already.
Str result(siz);

Способ 5:
Используйте либо распределитель, созданный google, либо facebook, как глобальную замену new/delete.

Ответ 6

Чтобы понять, как может помочь пользовательский распределитель, вам нужно понять, что делает malloc и куча, и почему он довольно медленный по сравнению со стеком.

Стек

Стек представляет собой большой блок памяти, выделенный для вашей текущей области. Вы можете думать об этом как о

([] означает байт памяти)

[Р] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []

(P - указатель, указывающий на конкретный байт памяти, в этом случае его указание на первый байт)

Таким образом, стек представляет собой блок с 1 указателем. Когда вы выделяете память, что она делает, она выполняет арифметику указателя на P, которая принимает постоянное время. Итак, объявляя int я = 0; означало бы это,

P + sizeof (int).

[I] [I] [I] [I] [P] [] [] [] [] [] [] [] [] [] [] [], (i в [] - блок памяти, занятый целым числом)

Это быстро вспыхивает, и как только вы выходите из области видимости, весь фрагмент памяти опустошается просто, перемещая P обратно в первую позицию.

Куча

Куча выделяет память из зарезервированного пула байтов, зарезервированного компилятором С++ во время выполнения, когда вы вызываете malloc, куча находит длину непрерывной памяти, которая соответствует вашим требованиям к malloc, маркирует ее как используемую, поэтому ничто не может ее использовать, и возвращает это вам как пустоту *.

Итак, теоретическая куча с небольшой оптимизацией, вызывающей new (sizeof (int)), сделает это.

Куча кучи

Сначала: [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []

Выделить 4 байта (sizeof (int)): Указатель идет через каждый байт памяти, находит тот, который имеет правильную длину, и возвращает вам указатель. После: [i] [i] [i] [i] [] [] []] [] [] [] [] [] [] [] [] []] [] [] [] [] [] [] []

Это не точное представление кучи, но из этого вы уже видите множество причин быть медленными относительно стека.

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

• Куча требуется для циклического перемещения всех байтов, чтобы найти тот, который соответствует вашей длине.

• Куча может пострадать от фрагментации, так как она никогда не будет полностью очищена, если вы ее не укажете. Поэтому, если вы выделили int, a char и еще один int, ваша куча будет выглядеть так:

[I] [I] [I] [I] [с] [i2] [i2] [i2] [i2]

(i обозначает байты, занятые int, а c обозначает байты, занятые char. Когда вы выделите char, он будет выглядеть следующим образом.

[я] [я] [я] [я] [пусто] [i2] [i2] [i2] [i2]

Поэтому, когда вы хотите выделить другой объект в кучу,

[я] [я] [я] [я] [пусто] [i2] [i2] [i2] [i2] [i3] [i3] [i3] [i3]

если размер объекта не равен 1 char, общий размер кучи для этого распределения уменьшается на 1 байт. В более сложных программах с миллионами ассигнований и освобождения от ответственности проблема фрагментации становится серьезной, и программа станет неустойчивой.

4. Беспокоиться о таких случаях, как безопасность потоков (кто-то еще сказал это уже).

Custom Heap/Allocator

Таким образом, пользовательский распределитель обычно должен решать эти проблемы, предоставляя преимущества кучи, такие как персонализированное управление памятью и постоянство объекта.

Обычно они выполняются с помощью специализированных распределителей. Если вы знаете, что вам не нужно беспокоиться о безопасности потоков, или вы точно знаете, как долго будет ваша строка, или предсказуемый шаблон использования, вы можете сделать свой распределитель быстрее, чем malloc и новый довольно много.

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

например

typedef char* buffer;
//Super simple example that probably doesnt work.
struct StackAllocator:public Allocator{
     buffer stack;
     char* pointer;
     StackAllocator(int expectedSize){ stack = new char[expectedSize];pointer = stack;}
     allocate(int size){ char* returnedPointer = pointer; pointer += size; return returnedPointer}
     empty() {pointer = stack;}

};

Получить ожидаемый размер, получить кусок памяти из кучи.

Назначьте указатель на начало.

[P] [] [] [] [] [] [] [] [] []..... [].

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

Для строк вы можете попробовать распределитель блоков. Для каждого распределения распределитель предоставляет набор блоков памяти.

Совместимость

Совместимость с другими строками почти гарантирована. Пока вы выделяете непрерывный кусок памяти и не позволяете чему-либо еще использовать этот блок памяти, он будет работать.