Диспетчер кучи для объектов одного размера

Автор: Сергей Парунов

Динамическое размещение объектов (не только экземпляров классов, а вообще) в куче имеет неоспоримые преимущества: гибкость, простота... Но у такого подхода есть недостаток, проистекающий от всеядности стандартного диспетчера кучи языка (Delphi), который и выбирает, откуда "отщипнуть" кусочек памяти. Уж очень много самых разных блоков выделяется-освобождается в куче, и она превращается в швейцарский сыр. Отсюда вытекают две неприятности. Во-первых, когда выделяется блок памяти, диспетчер вынужден запомнить его размер и прочие параметры в пропадающем зря 4-байтном (чаще всего) заголовке (для освобождения). Во-вторых, уж очень медленен этот процесс - надо перестроить дерево... в общем, тактов 200 на одно выделение/освобождение на процессоре Пентиум 3 обеспечено.

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

Данный класс реализует упрощенный диспетчер кучи для объектов одного размера (назовём его экземпляр кучей), который можно применять вместо стандартного, получая с маленькими объектами существенно большую скорость, а часто и экономию памяти, за счёт реализации старого татаро-монгольского принципа: "меньше чем по десять тысяч мы даже в гости не ходим" ((c) Александр Борянский, Сергей Козлов).

with psnFixSzMemMgr.Create(16) do
begin // куча создана
  Ptr := FixNew; // Выделяем блок в 16 байт.
  ... // Делаем всё, что нам надо.
  FixDsp(Ptr); // Блок, указуемый Ptr, возвращён в кучу. Вообще-то
  // этот шаг перед самым разрушением кучи
  // необязателен, это стоит делать, только когда
  // есть надежда на повторное использование блока.
  Destroy; // Куча разрушена.
end;

Статистика: с 8-12-байтными блоками втрое обгоняет стандартный, с возрастанием блока до 48 байт практически сравнивается с ним. Экономия памяти при хорошем наполнении составляет почти 4 байта на блок.

У него есть недостаток, вытекающий из назначения. Рассмотрим в общих чертах его работу. Он выделяет большой массив памяти, нарезает его блоками и скармливает нам, пока он не кончится, выделяет следующий и т.д. Но определением того факта, что в массиве уже нет ни одного используемого блока, и освобождением массива этот диспетчер кучи не занимается по соображениям скорости. Иными словами, грубо говоря, если Вы выделили 1024 блока памяти по 16 байт, а затем все их освободили, пропадёт 16 кБ памяти до освобождения либо заполнения заново этой кучи.

Но динамические структуры чаще всего применяются однократно или не уменьшаются так резко в ходе работы. Не проблема и реализовать несколько замедленный вариант диспетчера кучи с автоосвобождением. Более того, если идёт интенсивная работа с мелкими блоками, вероятность того, что полностью освободится целый массив, невелика. А если не смущает некоторая замедленность работы, то для блоков произвольного размера можно воспользоваться API (LocalAlloc, HeapCreate и пр.), позволяющими реализовать отдельную кучу.

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

Я обнаружил, что запрошенная посредством VirtualAlloc (как делает "настоящий" диспетчер памяти) память в окне CPU Delphi 5 отображается как мусор: изменить память там можно, а посмотреть - нет (с всплывающей подсказкой в редакторе кода всё нормально). Так что диспетчер реализован как надстройка над стандартным, что, конечно, несколько снижает скорость, но зато позволяет уменьшить потери памяти на фрагментацию для небольших объёмов (VirtualAlloc не размещает память меньше чем по странице - 4 кБ на процессорах линии IA32).

type

  psnFixSzMemMgr = class
  private
    FLastCommit, {указатель на последний выделенный массив, в начале которого -
    указатель на предпоследний...}
    FEmptyBlock: Pointer; {указатель на последний пустой блок из списка, в
    начале которого - указатель на предпоследний...}
    FBlockSize, FCommitSize, FFillCycles: Integer;
  public
    constructor Create(
      const BlockSize: Integer; {Размер выделяемых блоков памяти. Реально
      округляется в большую сторону до величины, кратной 4.}
      const CommitBlocks: Integer = 127 {Количество блоков в выделяемых
      массивах. Должно быть больше 1 (иначе зачем огород городить?), а для
      скорости желательно не меньше 31. Реально увеличивается до ближайшего
      сверху нечётного значения (алгоритм требует это для высокой скорости).}
      );
    function FixNew: Pointer; {Выделяет блок памяти размера BlockSize и
    возвращает ссылку на эту память. Выполнено в виде функции во избежание
    обязательного преобразования типов параметра, передаваемого по ссылке.}
    procedure FixDsp(const Ptr: Pointer); {Освобождает блок памяти, выделенный
    ранее в данном экземпляре класса, указуемый параметром Ptr.}
    destructor Destroy; override;
  end;

implementation

constructor psnFixSzMemMgr.Create(const BlockSize, CommitBlocks: Integer);
begin
  FBlockSize := (BlockSize + 3) and $7FFFFFFC;
  FCommitSize := (CommitBlocks and $7FFFFFFE + 1) * FBlockSize + 4;
  FFillCycles := CommitBlocks shr 1 - 1; {заполняем в один присест два блока, и
  цикл оформим от нуля: for I:= 0 to FFillCycles, быстрее будет}
end;

function psnFixSzMemMgr.FixNew: Pointer;
var
  P, P2: Pointer;
  I, DBlockSize: Integer;
begin
  if not Assigned(FEmptyBlock) then
  begin {выделим массив}
    GetMem(P, FCommitSize);
    Pointer(P^) := FLastCommit;
    FLastCommit := P;
    Inc(PChar(P), 4);
    Pointer(P^) := nil;
    P2 := Pointer(Integer(P) + FBlockSize);
    DBlockSize := FBlockSize shl 1;
    for I := 0 to FFillCycles do
    begin {надо сделать список пустых блоков}
      Pointer(P2^) := P;
      Inc(PChar(P), DBlockSize);
      Pointer(P^) := P2;
      Inc(PChar(P2), DBlockSize);
    end;
    FEmptyBlock := P;
  end;
  Result := FEmptyBlock;
  FEmptyBlock := Pointer(Result^);
end;

procedure psnFixSzMemMgr.FixDsp(const Ptr: Pointer);
begin
  Pointer(Ptr^) := FEmptyBlock;
  FEmptyBlock := Ptr;
end;

destructor psnFixSzMemMgr.Destroy;
var
  P: Pointer;
begin
  while Assigned(FLastCommit) do
  begin
    P := FLastCommit;
    FLastCommit := Pointer(P^);
    FreeMem(P, FCommitSize);
  end;
  inherited;
end;