стратегия размещения / освобождения множества мелких объектов - PullRequest
Новая
       42

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

7 голосов
/ 13 марта 2010

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

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

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

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

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

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

Ответы [ 3 ]

6 голосов
/ 13 марта 2010

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

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

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

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

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

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

1 голос
/ 13 марта 2010

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

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

0 голосов
/ 13 марта 2010

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

РЕДАКТИРОВАТЬ: вот пример Бьярна Страуструпа Язык программирования 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);
  }
};
...