Как разработать класс, подходящий для миллионов выделений?

Главное - минимизировать использование new и delete, сохраняя использованные объекты в пуле и повторно используя их. Не беспокойтесь о виртуальных функциях. Накладные расходы на их вызов обычно тривиальны по отношению ко всему остальному, что происходит в вашей программе.

Просто уточню один момент по поводу пользовательских аллокаторов.

Используя new по умолчанию, вы, скорее всего, получите довольно много накладных расходов, то есть дополнительной памяти, выделенной поверх sizeof(Foo). На самом деле вы хотите распределить эти накладные расходы по многим Foos.

Идея заключается в том, чтобы выполнить один вызов new для выделения одного блока байтов, достаточно большого, чтобы вместить 100 или 1000 (или больше?) смежных Foos, а затем выделить из него отдельные Foos.

Если вы держите пул предварительно выделенных Foos, вы все равно будете нести затраты памяти на каждый экземпляр, даже если он быстрее.

В книге The C++pl2e Строуструп говорит о байтах "на моей машине", поэтому вам придется провести эксперименты самостоятельно: Сколько памяти на самом деле занимает выделение одного Foo с помощью new?

Поищите аллокаторы пулов (например, Boost) или аллокаторы малых объектов (например, Loki).

Другие уже упоминали шаблон Flyweight, но поскольку вы отметили это для C++, я бы рассмотрел Boost.Flyweight. Его дизайн соответствует вашим потребностям, и если вам нужно изобрести колесо, вы всегда можете посмотреть его исходный текст для получения подробной информации.

Что касается выделения объектов вашего класса, посмотрите на библиотеку boost Pool, которая может быть более эффективной для многих выделений небольших объектов, чем обычное new/delete через системный аллокатор. Она также может располагать их ближе друг к другу в памяти. fast_pool_allocator очень удобен как реализация аллокатора на C++, которую вы можете легко вставить в свое приложение, чтобы оценить преимущества. Я бы посоветовал использовать аллокаторы в любом случае, так как это облегчит сравнение различных схем распределения.

Еще одна вещь, которую следует рассмотреть, это когда будут создаваться объекты - например, знаете ли вы заранее, сколько их понадобится (и поэтому система объединения/переиспользования, описанная другими, была бы полезной), или вы просто знаете, что их потребуется O(1m) в разные моменты времени. Создание большого количества за один раз должно быть намного быстрее, чем выделение большого количества по отдельности. В своей собственной работе я часто обнаруживал, что повторное выделение памяти для множества мелких объектов показывает себя как большое узкое место при профилировании.

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

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

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

Если это кажется странным, подумайте об объекте String в Python . Как и во многих современных языках, String неизменяемы в Python . Конечно, объект, которым вы управляете, может измениться, но реальная String - нет: ваш дескриптор просто перемещается.

Конечно, Python имеет автоматическую сборку мусора, которая значительно упрощает эту задачу, но она может сработать и для вас. Вот набросок:

class FooImpl;

class Foo
{
public:
  explicit Foo(int i): mImpl(FooImpl::Build(i)) {}

  int foo() const { return mImpl->foo(); }

  void foo(int i) { mImpl = mImpl->foo(i); }

private:
  const FooImpl* mImpl;
}; // class Foo

class FooImpl
{
public:
  static const FooImpl* Build(int i)
  { 
    typedef std::unordered_set<FooImpl> foos_type;
    FooImpl tmp(i);
    foos_type::iterator it = gFooImplCollection.insert(tmp);
    return &(*it);
  }

  int foo() const { return mFoo; }

  const FooImpl* foo(int i) const
  {
    return Build(i);
  }

  // Useful thingy
  bool operator==(const FooImpl& rhs) const { return mFoo == rhs.mFoo; }
  size_t hash() const { return mFoo; }

private:
  explicit FooImpl(int i): mFoo(i) {}

  int mFoo;
};

std::unordered_set< FooImpl > gFooImplCollection;

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

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

И теперь, когда вы нашли время прочитать, у Boost есть это: Boost.Flyweight :)

Примечание:

Кажется важным уточнить, потому что Foo должен выделяться (в стеке) миллионы раз, его размер должен оставаться как можно ближе к указателю. Это достигается за счет использования Intrusive ссылки couting (я надеюсь, что это то, что делает Boost).Кроме того, нет необходимости иметь виртуальных методов в Foo , виртуальных в FooImpl и Build фактически может вызвать AbstractFactory за кулисами.

Таким образом, поскольку Foo :

• не имеет базового класса,
• не имеет виртуальных методов
• имеет только один атрибут (указатель)

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

Посмотрите на шаблон Flyweight. Книга GoF объясняет паттерн гораздо лучше, чем Википедия.

Я не думаю, что можно много сказать о проектировании вашего класса для миллионов распределений. Да, есть очевидный предел памяти, поэтому, если у вас есть фиксированный объем памяти, это может быть для вас настоящей проблемой, иначе вы всегда рискуете нехватить памяти. Указатель на виртуальную таблицу - это просто указатель (4 или 8 байтов в 32- или 64-битной архитектуре), не уверен, что это так в случае множественного наследования. Вызов виртуальных функций имеет накладные расходы на виртуальный поиск (и лишний пропуск кеша, если вы не использовали его в последнее время), но только для виртуальных функций, и они могут никогда не быть встроенными.

Если имеется много повторяющихся значений, вы можете также рассмотреть возможность создания отдельной структуры данных (шаблон-легковес). А для эффективности убедитесь, что у вас есть облегченный (встроенный) конструктор и операторы присваивания, особенно если вы собираетесь использовать векторы stl и т.п.

Это все довольно простые вещи, так что теперь мое настоящее предложение:

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

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

Точнее, эффективен или неэффективен код. Виртуальные вызовы, вероятно, требуют дополнительных затрат на вызовы, но сколько раз вызывается каждая функция-член, зависит от вызывающего кода, а не от класса. В любом случае встраивание - это то место, где наблюдается большой выигрыш в скорости, а виртуальные функции - это лишь один из способов помешать конкретному сайту вызова, извлекающему выгоду из встраивания. Если ваш дизайн упрощен за счет наличия 27 виртуальных функций-членов, каждая из которых вызывается один раз в месяц, но при этом гарантируется, что 2 функции, которые вызываются миллионы раз в секунду, могут быть встроены вызывающим, тогда нет необходимости избегать виртуальных функций. .

Базовые классы стоят примерно столько же, сколько объект-член того же типа. При множественном наследовании static_cast может перестать быть запретной операцией, как это обычно бывает при одиночном наследовании, но, вероятно, об этом не стоит беспокоиться. Виртуальное наследование и dynamic_cast могут быть интересны с точки зрения объема работы, выполняемой во время выполнения, но только в масштабе, аналогичном виртуальным функциям-членам.

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

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