Эффективность без Boost Pool O (n) или O (1) - PullRequest
Новая
       58

Эффективность без Boost Pool O (n) или O (1)

3 голосов
/ 13 марта 2011

Недавно я обнаружил библиотеку Boos Pool и начал адаптировать ее к своему коду.Одна вещь, о которой в библиотеке упоминалось, что она отсутствовала, - это базовый класс, который переопределяет операторы new / delete для любого класса и использует пул для управления памятью.Я написал свою собственную реализацию, и с некоторым программированием на основе мета-шаблонов он действительно выглядел очень прилично (поддерживая любой класс размером от 1 до 1024 байт, просто производный от базового класса)

Я упомянул эти вещи, потому чтодо сих пор это было действительно круто и захватывающе, и затем я нашел это сообщение из списка рассылки Boost .Похоже, некоторые люди действительно бьют библиотеку Pool и особенно указывают на неэффективность метода free (), который, по их словам, выполняется за O (n) раз.Я прошел по коду и обнаружил, что это реализация этого метода: 

void free(void * const chunk)
{
  nextof(chunk) = first;
  first = chunk;
}

Для меня это выглядит как O (1), и я действительно не вижу неэффективности, о которой они говорят.Одна вещь, которую я заметил, это то, что если вы используете несколько экземпляров singleton_pool (то есть разные теги и / или размеры выделения), они все используют один и тот же мьютекс (критический раздел, если быть более точным), и это можно немного оптимизировать.Но если бы вы использовали обычные операции с кучей, они использовали бы ту же форму синхронизации.

Так кто-нибудь еще считает библиотеку пула неэффективной и устаревшей?

1 Ответ

5 голосов
/ 13 марта 2011

Эта бесплатная уверенность выглядит для меня постоянным временем.Возможно, автор поста имел в виду order_free, который имеет такую ​​реализацию: 

void ordered_free(void * const chunk)
{
  // This (slower) implementation of 'free' places the memory
  //  back in the list in its proper order.

  // Find where "chunk" goes in the free list
  void * const loc = find_prev(chunk);

  // Place either at beginning or in middle/end
  if (loc == 0)
    (free)(chunk);
  else
  {
    nextof(chunk) = nextof(loc);
    nextof(loc) = chunk;
  }
}

Где find_prev выглядит следующим образом 

template <typename SizeType>
void * simple_segregated_storage<SizeType>::find_prev(void * const ptr)
{
  // Handle border case
  if (first == 0 || std::greater<void *>()(first, ptr))
    return 0;

  void * iter = first;
  while (true)
  {
    // if we're about to hit the end or
    //  if we've found where "ptr" goes
    if (nextof(iter) == 0 || std::greater<void *>()(nextof(iter), ptr))
      return iter;

    iter = nextof(iter);
  }
}
...