стратегия распределения/освобождения множества мелких объектов

Question

Я играюсь с определенным алгоритмом кэширования, который несколько сложен.По сути, ему необходимо выделить множество небольших объектов (двойные массивы, от 1 до 256 элементов), причем объекты доступны через сопоставленное значение, map[key] = array.время инициализации массива может быть довольно большим, обычно более 10 тысяч циклов процессора.

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

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

Я использую C++, поэтому могу использовать new и malloc.Спасибо.

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

моя платформа разработки — Intel Xeon, операционная система Linux.В идеале я бы хотел поработать и на PPC Linux, но для меня это не самое главное.

Answer 1

Создайте слотовый распределитель:

Распределитель создается с множеством страниц памяти, каждая из которых имеет одинаковый размер (512 КБ, 256 КБ, размер должен быть настроен для вашего использования).

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

Фрагментация предотвращается, поскольку все слоты имеют одинаковый размер и могут быть заполнены при последующих выделениях.Эффективность сохраняется (в некоторых случаях повышается), поскольку для каждого выделения нет заголовка memheader (что имеет большое значение, когда выделения малы; как только выделения становятся большими, распределитель начинает тратить почти 50% доступной памяти).

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

Редактировать:Этот ответ немного длинный.По-прежнему способствовать росту имеет твою спину.

Answer 2

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

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

Answer 3

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

РЕДАКТИРОВАТЬ:вот отрывок из книги Бьярна Страуструпа Язык программирования C++, 3-е издание:

class Pool
{
private:
  struct Link
    { Link * next; };

  struct Chunk
  {
    enum {size = 8*1024-16};

    Chunk * next;
    char mem[size];
  };

private:
  Chunk * chunks;
  const unsigned int esize;
  Link * head;

private:
  Pool (const Pool &) { }      // copy protection
  void operator = (Pool &) { } // copy protection

public:
  // sz is the size of elements
  Pool(unsigned int sz)
    : esize(sz < sizeof(Link*) ? sizeof(Link*) : sz),
      head(0), chunks(0)
    { }

  ~Pool()
  {
    Chunk * n = chunks;

    while(n)
    {
      Chunk * p = n;
      n = n->next;
      delete p;
    }
  }


public:

  // allocate one element
  void * alloc()
  {
    if(head == 0)
      grow();

    Link * p = head;
    head = p->next;

    return p;
  }

  // put an element back into the pool
  void free(void * b)
  {
    Link * p = static_cast<Link*>(b);
    p->next = head; //put b back as first element
    head = p;
  }

private:
  // make pool larger
  void grow()
  {
    Chunk* n = new Chunk;
    n->next = chunks;
    chunks = n;

    const int nelem = Chunk::size / esize;
    char * start = n->mem;
    char * last = &start [ (nelem - 1) * esize ];

    for(char * p = start; p < last; p += esize) // assume sizeof(Link) <= esize
      reinterpret_cast<Link>(p)->next = reinterpret_cast<Link *>(p + esize);

    reinterpret_cast<Link *>(last)->next = 0;
    head = reinterpret_cast<Link *>(start);
  }
};