Кэш с плохой политикой - это просто другое имя для утечки памяти

Это перевод A cache with a bad policy is another name for a memory leak. Автор: Реймонд Чен.

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

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

type
  TBufferCache = class
  private
    m_pCache: Pointer;
  public
    destructor Destroy; override;
    function GetBuffer(cb: Cardinal): Pointer;
    procedure ReturnBuffer(p: Pointer);
  end;

destructor TBufferCache.Destroy; 
begin
  LocalFree(Cardinal(m_pCache));

  inherited;
end;

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

function TBufferCache.GetBuffer(cb: Cardinal): Pointer;
begin
  // Может ли кэш удовлетворить этот запрос?
  if Assigned(m_pCache) and (LocalSize(Cardinal(m_pCache)) >= cb) then
  begin
    Result := m_pCache;
    m_pCache := nil;
  end
  else
    Result := Pointer(LocalAlloc(LMEM_FIXED, cb));
end;

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

// Плохой дизайн - см. обсуждение
procedure TBufferCache.ReturnBuffer(p: Pointer);
var
  cb: Cardinal;
begin
  cb := LocalSize(Cardinal(p));
  if (not Assigned(m_pCache)) or (cb > LocalSize(Cardinal(m_pCache))) then
  begin
    // Мы получили больший буфер:
    // Удаляем текущий буфер
    LocalFree(Cardinal(m_pCache));
    m_pCache := p;
  end
  else
    // Возвращаемый буфер меньше кэшированного:
    // Оставляем кэшированный
    LocalFree(Cardinal(p));
end;

Почему этот код неверен? Я даю вам время немного подумать об этом.

Нет, серьёзно - я хочу, чтобы вы подумали.

Вы думаете? Не спешите; я никуда не уйду, пока вы размышляете.

OKэй, поскольку я знаю, что вы, вообще-то, не особенно старались думать и просто ждали, пока я скажу вам ответ, я немного вас подтолкну.

Распределение размеров блоков памяти редко является однородным. Наиболее частое распределение - маленькие буферы являются наиболее популярными, а большие буферы требуются реже. Давайте напишем простую программу, которая распределяет и освобождает память по этому шаблону. Чтобы было проще заметить плохое поведение при первом прогоне, я собираюсь использовать такое распределение: половина буферов будет маленькой, а большие буферы будут становиться всё менее популярными с экспонентным затуханием. На практике кривая затухания намного круче.

program Test;

uses
  Windows,
  SysUtils,
  Classes;

// ...

var
  List: TList;
  B: TBufferCache;
  cb: Cardinal;
  p: Pointer;
  victim: Integer;
begin
  // инициализация генератора случайных чисел здесь не важна

  while True do
  begin
    // Случайное выделение и освобождение памяти
    if (List.Count = 0) or ((Random($7fff) and 1) <> 0) then
    // Выделение
    begin
      cb := 100;
      while (cb < (1024 * 1024)) and ((Random($7fff) and 1) <> 0) do
        cb := cb * 2; // экспоненциальный рост до 1 Мб
      p := B.GetBuffer(cb);
      WriteLn('A', LocalSize(Cardinal(p)), '/', cb);
      List.Add(p);
    end
    else
    // Освобождение
    begin
      victim := Random(List.Count); // выбираем случайно
      WriteLn('F', LocalSize(Cardinal(List[victim])));
      B.ReturnBuffer(List[victim]); // освобождаем
      List.Delete(Victim);
    end;
  end;
end.

Эта короткая программа выделяет и освобождает память, используя кэш и печатая (довольно загадочно) размеры выделяемых и освобождаемых блоков. Когда память выделяется, программа печатает "A1/2", где "1" - это размер выделенного блока, а "2" - запрошенный размер. Когда память освобождается, программа печатает "F3", где "3" - размер блока памяти. Запустите программу и дайте ей поработать, скажем, 10-15 секунд, затем приостановите её и изучите вывод. Я подожду. Если вы слишком ленивы, чтобы запускать программу, я просто покажу вам пример вывода для изучения:

F102400 
A102400/400 
F800 
F200 
A800/100 
A200/200 
A400/400
A400/400 
A200/200 
F1600 
A1600/100 
F100 
F800 
F25600 
A25600/200
F12800 
A12800/200 
F200 
F400 
A400/100 
F200 
A200/100 
A200/200
A100/100 
F200 
F3200
A3200/400 
A200/200 
F51200 
F800 
F25600
F1600 
F1600 
A51200/100 
F100 
A100/100 
F3200 
F200 
F409600 
F100
A409600/400 
A100/100 
F200 
F3200 
A3200/800 
A400/400 
F800 
F3200
F200 
F12800 
A12800/200 
A100/100 
F200 
F25600 
F400 
F6400
A25600/100 
F100 
F200 
F400 
F200 
F800 
F400 
A800/800 
A100/100

Я всё ещё жду вашу догадку.

OKей, может быть, вы это просто не видите. Давайте сделаем эффект ещё более очевидным, переодически печатая статистику. Конечно же, для этого нам её надо отслеживать, так что мы запомним размер запрашиваемого блока (что мы будем делать в самом буфере):

program Test;

uses
  Windows,
  SysUtils,
  Classes;

// ...

var
  List: TList;
  B: TBufferCache;
  cb: Cardinal;
  p: Pointer;
  victim: Integer;
  cbAlloc: Cardinal;
  cbNeeded: Cardinal;
  Count: Cardinal;
begin
  // инициализация генератора случайных чисел здесь не важна

  cbAlloc := 0;
  cbNeeded := 0;
  Count := 0;
  while True do
  begin
    Inc(Count);

    // Случайное выделение и освобождение памяти
    if (List.Count = 0) or ((Random($7fff) and 1) <> 0) then
    // Выделение
    begin
      cb := 100;
      while (cb < (1024 * 1024)) and ((Random($7fff) and 1) <> 0) do
        cb := cb * 2; // экспоненциальный рост до 1 Мб
      p := B.GetBuffer(cb);

      PCardinal(p)^ := cb;
      Inc(cbAlloc, LocalSize(Cardinal(p)));
      Inc(cbNeeded, cb);

      WriteLn('A', LocalSize(Cardinal(p)), '/', cb);
      List.Add(p);
    end
    else
    // Освобождение
    begin
      victim := Random(List.Count); // выбираем случайно

      Dec(cbAlloc, LocalSize(Cardinal(v[victim])));
      Dec(cbNeeded, PCardinal(v[victim])^);

      WriteLn('F', LocalSize(Cardinal(List[victim])));
      B.ReturnBuffer(List[victim]); // освобождаем
      List.Delete(Victim);
    end;
    if (count mod 100) = 0 then
      WriteLn(count, ': ', List.Count, ' buffers, ', cbNeeded, '/', cbAlloc, '=', cbNeeded * 100.0 / cbAlloc, '% used');
  end;
end.

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

0: 1 buffers, 400/400=100% used
100: 7 buffers, 4300/106600=4.03377% used
200: 5 buffers, 1800/103800=1.7341% used
300: 19 buffers, 9800/115800=8.46287% used
400: 13 buffers, 5100/114000=4.47368% used
500: 7 buffers, 2500/28100=8.8968% used
...
37200: 65 buffers, 129000/2097100=6.15135% used
37300: 55 buffers, 18100/2031400=0.891011% used
37400: 35 buffers, 10400/2015800=0.515924% used
37500: 43 buffers, 10700/1869100=0.572468% used
37600: 49 buffers, 17200/1874000=0.917823% used
37700: 75 buffers, 26000/1889900=1.37573% used
37800: 89 buffers, 30300/1903100=1.59214% used
37900: 91 buffers, 29600/1911900=1.5482% used

К этому моменту проблема становится очевидной: мы напрасно тратим ужасное количество памяти. К примеру, после шага 37900 мы выделили 1.8 Мб памяти, хотя нам нужно было только 30 Кб - что приводит к напрасной трате более 98%.

Как же нам удалось создать такой ужасный алгоритм?

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

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

Плохой эффект №1: большие буферы тратятся зря для хранения небольших данных.

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

Плохой эффект №2: большие буферы редко удаляются.

Единственным шансом для большого буфера быть освобождённым - это если в кэше уже есть больший буфер. Если вместо однозаписевого кэша из нашего примера у нас был бы, скажем, кэш на 10 записей, то чтобы освободить большой буфер, вам нужно последовательно вызвать ReturnBuffer 11 раз, каждый раз передавая большой буфер.

Плохой эффект №3: чем "более кэширующим" вы будете делать кэш, тем больше памяти он будет тратить зря!

Более того, когда делается 11-й вызов к ReturnBuffer с большим буфером, то только один из двух больших буферов освобождается. Самый большой буфер остаётся в кэше.

Плохой эффект №4: если вы удаляете большой буфер, то это просто означает, что у вас есть ещё больший буфер!

Следствие: буфер наибольшего размера никогда не освобождается.

Что началось как "очевидное" решение по хранению буфера, теперь превратилось в катастрофу производительности. Предпочитая большие буферы, вы позволили им "отравить" кэш. И чем дольше работает эта система, тем больше происходит выделений памяти, и тем больше оказывается "отравленных" буферов. Не имеет значения, как редки эти большие блоки; рано или поздно вы окажетесь в этом состоянии. Это просто вопрос времени.

Когда команда производительности попыталась объяснить эту проблему людям, многие из них ошибочно решили, что проблема в трате места на кэш. Но посмотрите на наш пример: наш кэш хранит лишь один блок памяти, и тем не менее мы тратим более 90% памяти впустую. Потому что трата памяти не ограничивается только памятью из кэша, наоборот, большая часть потраченной зря памяти находится вне кэша - в тех блоках, что он когда-то выдал (это вроде как похоже на ту сцену в It's a Wonderful Life, где Джордж Бейли объясняет, где все деньги. Они не в банке, они во всех тех местах, которые получили деньги из банка).

Мои рекомендации:

• При проектировании вашего кэша учитывайте характеристики шаблона выделения/освобождения памяти.
• Используйте эту информацию, чтобы выбрать точку отреза, за которой вы просто не используете кэш. Это гарантирует, что большие буферы не появятся в кэше. Выбор этой точки обычно является тривиальной вещью, если вы взглянете на гистограмму выделения памяти вашего приложения.
• Хотя вы удалили большие буферы из рассмотрения, у вас всё ещё остаётся проблема, что размеры небольших блоков будут расти до вашей точки отреза (т.е. у вас всё ещё есть та же самая проблема, только в миниатюре). Поэтому, если кэш полон, то вам нужно просто освободить последний буфер, вне зависимости от его размера.
• Не использовать кэширующий буфер, если трата памяти слишком велика. Вы можете решить использовать несколько "bucket" ("горстей") в кэше - по одной секции на, скажем, буферы до 100 байт, ещё одну на 100-200 байт и так далее. Таким образом, трата памяти никогда не превысит 100 байт на одно выделение.
• Наконец, перепроверьте ваш кэш на предмет возникновения какого-то другого патологического поведения, про которое я не говорил.

Вот новая реализация ReturnBuffer, которая учитывает некоторые из советов выше. Профилирование программы показало, что три четверти выделений памяти являются запросами в диапазоне 100–200 байт, так что давайте установим точку отреза в 200 байт.

procedure TBufferCache.ReturnBuffer(p: Pointer);
begin
  if (not Assigned(m_pCache)) and (LocalSize(Cardinal(m_pCache)) <= 200) then
    m_pCache := p
  else
    LocalFree(Cardinal(p));
end;

С этим, казалось бы, незначительным изменением, наша эффективность не опускается ниже 90%, а иногда даже равна 100%:

0: 1 buffers, 400/400=100% used
100: 7 buffers, 4300/4400=97.7273% used
200: 5 buffers, 1800/1800=100% used
300: 19 buffers, 9800/9800=100% used
400: 13 buffers, 5100/5100=100% used
500: 7 buffers, 2500/2600=96.1538% used
...
37200: 65 buffers, 129000/130100=99.1545% used
37300: 55 buffers, 18100/18700=96.7914% used
37400: 35 buffers, 10400/11000=94.5455% used
37500: 43 buffers, 10700/11000=97.2727% used
37600: 49 buffers, 17200/18000=95.5556% used
37700: 75 buffers, 26000/26800=97.0149% used
37800: 89 buffers, 30300/31900=94.9843% used
37900: 91 buffers, 29600/30600=96.732% used

Не забудьте прочитать напоминание Caching implies Policy от гуру производительности Rico Mariani. Как он объяснял это мне: "Политика кэша - это всё. Так что вам нужно быть железно уверенным в том, что политика работает как вы ожидаете. Кэш с плохой политикой - это просто другое имя для утечки памяти".

См. также: Поиск утечек памяти для бедных.