Написал библиотеку для мемоизации в Erlang

8 мая 2013

В заметке о двенадцати эффективных методах оптимизации программ мемоизация была названа в качестве одного из эффективных методов. Сегодня совместными усилиями мы напишем небольшую библиотеку на Erlang, которая упростит использование этой оптимизации в наших программах. Заодно мы попрактикуемся в использовании ETS.

Идей довольно простая. Если у нас есть чистая функция foo:bar/N, выполнение которой занимает много времени, то вместо:

Result = foo:bar(Alpha, Beta, ...)

… мы можем написать:

Result = erlymemo:call(foo, bar, [Alpha, Beta, ...])

Функция erlymemo:call/3 вычисляет хэш от имени модуля, имени функции и аргументов (поскольку функция должна работать медленно, чтобы мемоизация была эффективна, логично предположить, что она может обрабатывать большие объемы данных), после чего использует этот хэш для поиска в таблице. В роли таблицы будет выступать ETS, поскольку в данном случае нам крайне важна скорость. ETS намного быстрее set’ов и dict’ов, что очень легко проверить:

1> Set = sets:new().
{set,0,16,16,8,80,48,
     {[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]},
     {{[],[],[],[],[],[],[],[],[],[],[],[],[],[],[],[]}}}
2> timer:tc(fun() -> lists:foldl(fun(I, Acc) -> sets:add_element({I,I}, Acc) end, Set, lists:seq(1, 100000)), ok end).
{2293092,ok}
3> ets:new(test_ets, [set, named_table, public]).
test_ets
4> timer:tc(fun() -> [ ets:insert(test_ets, {I, I} ) || I <- lists:seq(1, 100000) ], ok end).
{712618,ok}

Дополнение: Однако следует отметить, что это может быть неверно для больших объемов данных. Чем больше объемы данных, тем больше накладные расходы на их копирование из ETS в локальную кучу процесса.

Если в таблице найден элемент с таким ключом, обновляем время последнего доступа к нему (об этом — ниже) и возвращаем найденный элемент. Иначе вычисляем apply(foo, bar, [Alpha, Beta, ...]), сохраняем результат в таблицу, а затем возвращаем вычисленное значение.

Поскольку память у нас не бесконечная, придется ограничить количество элементов, хранимых в ETS. Мы воспользуемся алгоритмом LRU. Для хранения времени доступа к элементам таблицы, нам придется завести еще одну ETS. Чтобы как-то различать таблицы, пусть первая будет называться memo_ets, а вторая — lru_ets. Все операции над ETS являются атомарными, но когда дело доходит до двух ETS, мы можем получить состояние гонки. Для борьбы с этой проблемой мы заведем gen_server, отвечающий за операции записи в обе ETS. Что интересно, мы можем безопасно читать из memo_ets напрямую, а не через gen_server.

Теперь перейдем к реализации. Вместо того, чтобы приводить код целиком, я обращу внимание лишь на основные моменты.

Состояние gen_server’а описывается следующей записью:

-record(state, {
    lru_ets :: ets:tab(),
    curr_unique_id :: non_neg_integer(),
    free_space :: non_neg_integer()
  }).

Здесь lru_ets — это идентификатор таблицы, используемой для реализации алгоритма LRU. Таблица memo_ets является именованной, поэтому ее идентификатор не хранится в #state{}. Поле curr_unique_id хранит текущее «время», в роли которого выступает обыкновенное целое число. При каждом доступе к memo_ets мы увеличиваем текущее «время» на единицу. Поскольку целые числа в Erlang могут быть сколь угодно большими, это работает почти как erlang:now(), только без блокировок. Мой небольшой опыт реализации целых чисел произвольной длины подсказывает, что инкремент таких чисел должен быть очень быстрой операцией. В поле free_space хранится количество «свободных» ячеек в memo_ets. Как только этот счетчик становится отрицательным, мы удаляем из memo_ets элемент, который дольше всего не использовался, после чего устанавливаем счетчик в ноль.

Инициализация gen_server’а происходит так:

init([]) ->
  ets:new(?MODULE, [set, named_table, protected]),
  {ok, #state{
    lru_ets = ets:new(lru_ets, [ordered_set, private]),
    free_space = config_max_table_size(),
    curr_unique_id = ?START_UNIQUE_ID
  }}.

Сначала мы создаем нашу memo_ets. Таблица является именованной. Это означает, что к таблице можно обращаться по имени, а не сгенерированному числовому идентификатору. В качестве имени таблицы используется имя модуля. Имена модулей в Erlang уникальны, в связи с чем маловероятно, что кто-то воспользуется таким же именем таблицы в рамках одной программы. То, что таблица имеет тип set, означает, что одному ключу может быть поставлено в соответствие только одно значение. Для реализации этого типа ETS используются хэш-таблицы. Protected означает, что любые процессы могут читать из этой таблицы. Но писать в таблицу может только процесс, создавший ее.

Таблица lru_ets устроена несколько иначе. Во-первых, эта ETS не является именованной, поэтому доступ к ней осуществляется только по идентификатору, пришедшему из ets:new/2. Во-вторых, она имеет тип ordered_set. Он аналогичен set, только элементы в таблицах этого типа упорядочены по ключу. Реализован ordered_set на сбалансированных бинарных деревьях. Если верить книге Чезарини и Томпсона, используются АВЛ-деревья. В-третьих, данная таблица является private. Это означает, что доступ к таблице как на чтение, так и на запись, имеет только процесс, создавший ее.

Рассмотрим устройство функции erlymemo:call/3:

call(Module, Function, Args) ->
  MemoKey = erlang:md5(term_to_binary({Module, Function, Args})),
  case ets:lookup(?MODULE, MemoKey) of
    [{_MemoKey, _LruUniqId, Result}] ->
      ok = gen_server:call(?MODULE, {update_lru, MemoKey}),
      Result;
    [] ->
      Result = erlang:apply(Module, Function, Args),
      ok = gen_server:call(?MODULE,
                           {memoize_and_update_lru, MemoKey, Result}),
      Result
    end.

Все в точности по описанной ранее логике. Мы вычисляем ключ, представляющий собой хэш от имени модуля, имени функции и аргументов, после чего ищем в memo_ets элемент по этому ключу. Поскольку таблица является именованной и protected, мы можем читать из нее напрямую. Если элемент найден, мы говорим gen_server’у обновить время последнего доступа к нему. Если не найден, вызываем функцию и говорим gen_server’у сохранить полученное значение.

Обработчики соответствующих сообщений:

handle_call(
    {memoize_and_update_lru, MemoKey, Result}, _From,
    #state{ free_space = FreeSpace } = State) ->
  PrevUniqId =
    case ets:lookup(?MODULE, MemoKey) of
      [{ _MemoKey, Found, _Result }] -> Found;
      [] -> ?INVALID_UNIQUE_ID
    end,
  NewState =
    memoize_and_update_lru(MemoKey, Result, PrevUniqId, State),
  {reply, ok,
    delete_expired(NewState#state{ free_space = FreeSpace - 1 })};

handle_call({update_lru, MemoKey}, _From, State) ->
  NewState =
    case ets:lookup(?MODULE, MemoKey) of
      [{_MemoKey, PrevUniqId, Result}] ->
        memoize_and_update_lru(MemoKey, Result, PrevUniqId, State);
      [] -> % rare case: MemoKey was just deleted from ETS
        State
    end,
  {reply, ok, NewState };

Как видите, все сводится к вызову memoize_and_update_lru/4 с правильными аргументами:

memoize_and_update_lru(
    MemoKey, Result, PrevUniqId,
     #state{
      lru_ets = LruEts,
      curr_unique_id = CurrUniqId
     } = State) ->
  ets:delete(LruEts, PrevUniqId),
  ets:insert(LruEts, { CurrUniqId, MemoKey }),
  ets:insert(?MODULE, { MemoKey, CurrUniqId, Result}),
  State#state{ curr_unique_id = CurrUniqId + 1 }.

Я считаю, тут все самоочевидно. Наконец, рассмотрим delete_expired/1:

delete_expired(#state{ free_space = FreeSpace } = State)
    when FreeSpace >= 0 ->
  State;

delete_expired(#state{ lru_ets = LruEts } = State) ->
  LruKey = ets:first(LruEts),
  [{_LruKey, MemoKey}] = ets:lookup(LruEts, LruKey),
  ets:delete(LruEts, LruKey),
  ets:delete(?MODULE, MemoKey),
  State#state{ free_space = 0 }.

Если количество элементов в memo_ets не превышает указанного предела, ничего не делаем. Иначе находим первую пару ключ-значение в lru_ets. Поскольку элементы в этой таблице упорядочены, а «время» доступа к элементам memo_ets строго возрастает, в значении будет хранится ключ элемента memo_ets, который дольше всего не использовался. Затем найденный ключ используется для удаление элемента из lru_ets, а значение — для удаления из memo_ets.

Код библиотеки вы найдете на GitHub. Помимо рассмотренного в данной заметке функционала, в нем вы найдете еще несколько полезных функций, а также спеки для dialyzer и набор тестов. Если у вас есть идеи, как улучшить библиотеку, я буду рад с ними ознакомиться. Например, я не могу решить, имеет ли смысл прикручивать опциональный сбор статистики процента случаев попаданий в кэш, версию функции erlymemo:call/3 с асинхронными обращениями к gen_server’у, а также возможность выбора между алгоритмами LRU и MRU. Как вы считаете?

Дополнение: Очереди заданий и пулы процессов в Erlang

Метки: , , .

Понравился пост? Узнайте, как можно поддержать развитие этого блога.

Также подпишитесь на RSS, Facebook, ВКонтакте, Twitter или Telegram.