Написал библиотеку для мемоизации в Erlang
8 мая 2013
В заметке о двенадцати эффективных методах оптимизации программ мемоизация была названа в качестве одного из эффективных методов. Сегодня совместными усилиями мы напишем небольшую библиотеку на Erlang, которая упростит использование этой оптимизации в наших программах. Заодно мы попрактикуемся в использовании ETS.
Идей довольно простая. Если у нас есть чистая функция foo:bar/N, выполнение которой занимает много времени, то вместо:
… мы можем написать:
Функция erlymemo:call/3 вычисляет хэш от имени модуля, имени функции и аргументов (поскольку функция должна работать медленно, чтобы мемоизация была эффективна, логично предположить, что она может обрабатывать большие объемы данных), после чего использует этот хэш для поиска в таблице. В роли таблицы будет выступать ETS, поскольку в данном случае нам крайне важна скорость. ETS намного быстрее set’ов и dict’ов, что очень легко проверить:
{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’а описывается следующей записью:
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’а происходит так:
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:
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’у сохранить полученное значение.
Обработчики соответствующих сообщений:
{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 с правильными аргументами:
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:
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
Метки: Erlang, Оптимизация, Функциональное программирование.
Вы можете прислать свой комментарий мне на почту, или воспользоваться комментариями в Telegram-группе.