В заметке о двенадцати эффективных методах оптимизации программ мемоизация была названа в качестве одного из эффективных методов. Сегодня совместными усилиями мы напишем небольшую библиотеку на 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
