LRU-кэш это популярная структура данных, хранящая пары ключ-значение, но в отличие от обычной "мэпы", ограниченная по размеру - более старые (Least-Recently-Used) записи "вытряхиваются" при переполнении. Он популярен как в повседневной работе так и на собеседованиях (видимо в качестве альтернативы заезженным алгоритмам сортировок). Собственно под влиянием небольшого спора с интервьюером и родилась эта заметка :)
Огорчает, что обычно подразумевают конкретно "классическую" реализацию с мэпой и двухсвязным списком. В некоторых языках (Java) даже в стандартную либу входит такая комбинация (LinkedHashMap).
А на деле способов реализации можно найти или придумать много - в этом смысле задачка тем и хороша что простор для "пошевелить мозгами" очень большой. Я собираюсь здесь показать как от "классического" способа прийти к более простым вариантам (без списка - с таймстемпами или с поколениями). Как в инженерной практике так и на собеседовании - чем проще, тем лучше - правда? И мы проанализируем и проверим, проседает ли быстродействие (а может наоборот улучшается?)
Суть задачи
Мы хотим иметь структуру для кэша - хранилище "ключ-значение", имеющую ограниченный размер. Когда элементов становится много, наиболее "старые" могут удаляться.
Под старыми подразумеваются те, которые мы читали или записывали давнее других.
Например, представим себе кэш на тысячу элементов, куда записали полторы тысячи челове�� с фамилией в качестве ключа, от Абрикосова до Яблокова, в алфавитном порядке. Но где-то в середине процесса записи "дёрнули" Арбузова чтобы посмотреть какие-то подробности о нём.
Получится что к моменту окончания записи Абрикосов, Бананов, Вареников уже выпали из кэша (предположим, что по буквам фамилии распределены более-менее равномерно) - но Арбузов всё ещё присутствует, потому что когда его прочли (скажем, в кэше тогда было уже 700-800 записей) - он "переместился наверх".
При этом естественно мы хотим уметь искать в кэше или добавлять в него - быстро. Обычно речь идёт о доступе за O(1) в среднем.
Способ #1 - классический, с двухсвязным списком
Этот вариант популярен и потому что это в принципе "наиболее строгая" реализация такого кэша (например в сравнении с двумя описанными дальше) - и потому, наверное, что манипуляции со списками это тема которую все любят на собеседованиях - т.к. легко запутаться с присваиванием указателей - или с одновременным обновлением обеих частей структуры :)
Впрочем справедливости ради - и в реальной практике списки порой могут всплывать (в основном зависит от языка и библиотеки, которыми вы пользуетесь).
Эту реализацию мы рассматриваем в основном для того, чтобы от неё перейти к следующим путём упрощения!
Идея проста, устроим комбинированную структуру из двух компонент:
поскольку нужно уметь "вытащить из середины и поставить в начало" - очевидно что внутри должна быть "линейная" структура типа списка - которая позволяет быстро удалять элементы из произвольного места
а поскольку нам ещё надо уметь быстро отыскать элемент (не бегая по всему списку) то будем также хранить и мэпу, в которой ключи ссылаются на элементы списка.
Код для примера будет на Go (на нём было собеседование) - но без специфики, так что познания этого языка не требуются. Мы ведь хотим обсудить вещи не зависящие от языка. Для простоты ключи и значения имеют строковый тип (не будем засорять пример дженериками).
Начнём с описания основных структур и их методов:
type Elem struct { value string next *Elem prev *Elem } type Cache struct { head *Elem kv map[string]*Elem max int } func NewCache(size int) *Cache { return nil } func (cache *Cache) Put(key, value string) { } func (cache *Cache) Get(key string) string { return "" }
Итак для работы с кэшом у нас будет NewCache в качестве "конструктора" и два метода Put и Get чтобы добавить или найти запись.
В структуре описывающей сам кэш у нас head указывает на голову списка, kv содержит мэпу для поиска элементов по ключу, а поля cur и max позволяют следить за размером.
Как будет видно дальше, это не все поля которые нам нужны.
Базовая реализация методов Put и Get основывается на поиске элемента с помощью мэпы, после чего используются вспомогательные приватные функции promote для переноса в начало и detach для изъятия из списка:
func (cache *Cache) Put(key, value string) { elem, ok := cache.kv[key] if !ok { elem = &Elem{value: value} // если элемент не нашли, создадим новый } else { cache.kv[key].value = value // а если нашли, просто подставим значение } cache.promote(elem) // и перенесем (вставим) его в начало } func (cache *Cache) Get(key string) string { elem, ok := cache.kv[key] if !ok { // если элемент не нашли, то и делать ничего не надо return "" } cache.promote(elem) // а если нашли то перед возвратом тоже переносим в начало return elem.value }
Здесь пока нет некоторых важных подробностей - например, удаления старого элемента при достижении максимального размера. Это мы в окончательном варианте добавим.
Реализация функций promote и detach - это в первую очередь типичные манипуляции на списке:
func (cache *Cache) promote(elem *Elem) { if elem.prev != nil { // если это не вновь созданный элемент detach(elem) // то сперва извлечем его из списка } elem.next = cache.head.next elem.prev = cache.head elem.next.prev = elem elem.prev.next = elem } func detach(elem *Elem) { prev := elem.prev next := elem.next prev.next = next next.prev = prev }
У нас не было в описании структуры Elem поля с ключом - но оказывается оно нужно в одном единственном месте - чтобы удалить последний элемент не только из списка но и из мэпы. Добавим поле key.
Подобным же образом в структуре Cache нам на самом деле понадобится не только указатель на начало списка, но и на конец - иначе как мы будем удалять что-то с конца :) Добавим поле tail.
Теперь функция создания кэша (конструктор) - тут есть важная маленькая деталь:
func NewCache(size int) *Cache { cache := &Cache{ max: size, kv: map[string]*Elem{}, head: &Elem{}, tail: &Elem{}, } cache.head.next = cache.tail cache.tail.prev = cache.head return cache }
Мы в список добавляем "головной" и "хвостовой" элементы, которые не будут участвовать собственно в алгоритме (их нет в мэпе, у них нет ни ключа, ни значения) - всё ради того чтобы не делать дальше в коде проверок на nil в указателях на предыдущий и следующий у "живых" элементов - они таким образом всегда будут не-nil-овыми! (конечно это некритичная деталь - просто чуть меньше вероятность ошибиться)
Осталось только добавить проверку на размер кэша при добавлении:
func (cache *Cache) Put(key, value string) { elem, ok := cache.kv[key] if !ok { elem = &Elem{key: key, value: value} if len(cache.kv) == cache.max { delete(cache.kv, cache.tail.prev.key) detach(cache.tail.prev) } cache.kv[key] = elem } else { cache.kv[key].value = value } cache.promote(elem) }
Целиком этот код можно посмотреть и поиграть в плейграунде (https://go.dev/play/p/Z0hWIdtnF7z) а пока сделаем простую проверку на небольшом кэше. Здесь мы в кэш размером 4 добавляем 6 записей, причем 1 раз перезаписываем элемент и 2 раза пробуем читать. Для удобства можно добавить распечатку состояния списка после каждой операции (всё это можно найти в функции main по ссылке) - результат выглядит так:
set Abrikos -> ABR ABR set Bananas -> BAN BAN ABR set Cucumba -> CUC CUC BAN ABR search Abrikos -> ABR ABR CUC BAN set Durian -> DUR DUR ABR CUC BAN set Eggplant -> EGG EGG DUR ABR CUC set Durian -> DUN DUN EGG ABR CUC set Fig -> FIG FIG DUN EGG ABR search Bananas -> FIG DUN EGG ABR
Видно что "Дуриан" при записи переехал в начало, как и "Абрикос" - а вот "Бананам" не повезло.
Анализируя этот вариант отмечаем:
быстродействие вставки и поиска в данном случае O(1), при условии что используется хэш-мэпа (а не tree-map) - не зависит от объёма данных.
реализация доступна даже при базовом знании структур данных, однако требует внимания, как при манипуляциях с указателями в списке, так и в том что обновлять нужно обе структуры (и счетчик).
объём данных несколько избыточный - ключи приходится хранить в обеих суб-структурах, да ещё по 4 указателя на каждую запись.
возможны дальнейшие улучшения этой идеи - например можно "промоутить" элемент не каждый раз (а завести счетчик или использовать вероятностный подход) - для часто используемых элементов это актуально.
В качестве упражнения можете добавить метод удаления записи - а также навесить мьютексы для синхронизации доступа.
Способ #2 - Наивный, без списка но с таймстемпами
В предыдущем способе у нас две структуры под капотом - мэпа и список. Что будет если удалить одну из них?
удалив мэпу мы останемся со списком - поиск в нём будет O(N) и это звучит слишком драматично для кэша - а поиск нам нужен и при чтении и при записи
а вот если мы удалим список - поиск и запись останутся при своих O(1) - даже ускорятся немного, т.к. нет операций на списке каждый раз. Сложность увеличится только при удалении.
Рассмотрим внимательнее второй вариант. Нам нужно будет всё же как-то отмечать какие элементы старше, какие моложе. Можно записывать таймстемп или завести сквозной счетчик обращений к структуре. Для общности мы используем счётчик но называем его stamp.
Когда кэш переполняется и пора удалять старые, нам придётся пройти циклом по всей мэпе и найти самый старый элемент - и его выкинуть. Давайте запишем это в коде и обсудим насколько это плохо.
Вот определения структур - и конструктор к ним:
type Elem struct { value string stamp int } type Cache struct { kv map[string]*Elem opcnt int max int } func NewCache(size int) *Cache { return &Cache{kv: map[string]*Elem{}, max: size} }
Структура Elem остаётся всё равно т.к. в мэпе нужно хранить и значение и счетчик (или таймстемп) - но всё-таки получается явно компактнее.
Методы Put и Get без удаления можно написать так:
func (cache *Cache) Put(key, value string) { cache.opcnt++ elem, ok := cache.kv[key] if !ok { elem = &Elem{} cache.kv[key] = elem } elem.value = value elem.stamp = cache.opcnt } func (cache *Cache) Get(key string) string { elem, ok := cache.kv[key] if !ok { return "" } cache.opcnt++ elem.stamp = cache.opcnt return elem.value }
Здесь всё так просто что кажется и комментировать нечего. Счётчик opcnt увеличивается при каждой операции - и он же записывается в элемент, над которым операция произведена. Если инты маленькие то лучше использовать таймстемпы.
Осталось добавить удаление - тоже в виде метода evict и небольшой вставки в Put:
func (cache *Cache) Put(key, value string) { // ... if !ok { if len(cache.kv) == cache.max { cache.evict() } // ... } // ... } func (cache *Cache) evict() { oldestKey := "" oldestVal := cache.opcnt for k, v := range cache.kv { if v.stamp < oldestVal { oldestVal = v.stamp oldestKey = k } } delete(cache.kv, oldestKey) }
Тут тоже никакого "рокет-сайенса" - удаление вызывается если при добавлении выясняем что это новый элемент - и достигнут предельный размер кэша. В самой функции удаления - банальный поиск минимального (самого старого) значения перебором по всей мэпе.
Вот код целиком: https://go.dev/play/p/QY1IEDA5I5r и результат его запуска на том же примере выглядит так (с распечаткой "стемпов") - можно убедиться что наполнение кэша остаётся тем же:
set Abrikos -> ABR ABR:1 set Bananas -> BAN ABR:1 BAN:2 set Cucumba -> CUC ABR:1 BAN:2 CUC:3 search Abrikos -> ABR CUC:3 ABR:4 BAN:2 set Durian -> DUR ABR:4 BAN:2 CUC:3 DUR:5 set Eggplant -> EGG evicting Bananas EGG:6 CUC:3 DUR:5 ABR:4 set Durian -> DUN DUN:7 ABR:4 EGG:6 CUC:3 set Fig -> FIG evicting Cucumba ABR:4 EGG:6 FIG:8 DUN:7 search Bananas -> EGG:6 FIG:8 DUN:7 ABR:4
Конечно здесь очевидный недостаток - если удаление вызывается часто то быстродействие деградирует в сторону O(N) для операций записи. Нужно что-то придумать!
Способ #2.5 - те же таймстемпы, но с групповым удалением
Очевидное решение - удалять больше чем один элемент. Таким образом мы высвободим место для нескольких последующих вставок - либо какое-то константное количество (десять, сто и т.п.) - либо какой-то процент от общего объёма.
Таким образом можно получить "амортизированное" O(1) на записи (а поскольку используется мэпа, оно у нас и так "амортизированное", даже в случае со списком).
К сожалению поиск подмножества "крайних" элементов (K минимальных) - задача хотя не архисложная, но всё-таки её реализация несколько "затмевает" простоту подхода. На практике есть разные пути для этого:
либо "точный" способ основанный на алгоритме выбора - он позволит нам выделить и выкинуть ровно желаемое количество элементов - к сожалению он требует O(N) памяти либо работает хуже чем за O(N)
либо "приближённый" - возьмём несколько произвольных записей из мэпы и на их основе оценим каким должно быть "пороговое" значение чтобы отбросить такую-то часть коллекции; это похоже на ситуацию с выбором ключевого элемента в "быстрой" сортировке
Для целей сравнения алгоритмов (в конце этой заметки) я реализовал именно второй вариант который отбрасывает примерно треть элементов каждый раз:
func (cache *Cache) evict() { stamps := make([]int, 13) // массив для "случайной выборки" i := 0 for _, v := range cache.kv { // заполним его произвольными значениями из мэпы s := v.stamp j := i for j > 0 && stamps[j-1] > s { // на ходу сортируя "вставками" stamps[j] = stamps[j-1] j-- } stamps[j] = s i++ if i == len(stamps) { break } } threshold := stamps[len(stamps)/4] // берем пороговое значение for k, v := range cache.kv { // итерируем по мэпе if v.stamp <= threshold { // и всё что старше - удаляем delete(cache.kv, k) } } }
Результаты тестирования этого способа приведены вместе с остальными в конце.
Способ #3 - разделение на два поколения
Заключительное предложение из предыдущего варианта приводило к тому что размер кэша при достижении лимита сбрасывается "скачком" - высвобождается сразу целая группа записей так что на последующие сколько-то операций повторение evict-а не потребуется. Это не похоже на ситуацию с "классическим" способом где размер кэша поддерживается "идеально ровным" при достижении лимита.
Но так ли нам важно поддерживать этот размер постоянным? :) конечно, нет.
Это похоже на работу "сборщика мусора" - он вызывается периодически и высвобождает "запас пространства" на некоторое время вперед.
Ведь задача в общем-то в том чтобы не давать кэшу разрастаться, а не в том чтобы он был "строго столько-то записей". Негативным моментом является лишь то что мы потенциально теряем несколько процентов эффективности кэша (в случаях когда вот понадобится запись которая была именно среди старых, вытряхнутых "скопом" - но как раз поскольку она старая, вероятность её появления не так велика как для более часто используемых, поэтому можно не слишком переживать на счёт этих процентов. Мы ведь что-то выигрываем на том чтобы не возиться с указателями и пр.
Разовьём эту идею чуть дальше. Представим что в предыдущем варианте мы хотим "высвобождать" ровно 50% записей. А заодно выкинем из нашей мэпы таймстемпы/счётчики :)
Как же тогда помнить какая запись моложе, а какая старше?
Будем использовать две одинаковых мэпы, назовём их новым и старым поколениями:
при добавлении записей в кэш они попадают в "новое" поколение
при вычитывании мы ищем сначала в мэпе "нового" поколения, а если не нашли то в мэпе "старого" поколения;
если запись нашлась (при чтении или записи) в "старом" поколении, забираем её оттуда (и по необходимости переносим в "новое").
когда размер мэпы "нового" поколения достигает предела осуществляем "сдвиг поколений" - новая пустая мэпа становится "новым" поколением, а прежнее "новое" становится "старым" (само же прежнее "старое" мы выкидываем).
Вот и всё! Описывать дольше чем писать код :) Старое поколение при этом никогда не растёт, только уменьшается - поэтому мы контролируем суммарный размер. Итак, запишем.
type Cache struct { fresh map[string]string old map[string]string max int } func NewCache(size int) *Cache { return &Cache{ fresh: map[string]string{}, old: map[string]string{}, max: size, } } func (cache *Cache) Put(key, value string) { sz := len(cache.fresh) cache.fresh[key] = value if sz < len(cache.fresh) { // элемента не было в "новом" до вставки cache.deleteFromOldAndFlush(key) } } func (cache *Cache) Get(key string) string { if value, ok := cache.fresh[key]; ok { return value } else if value, ok := cache.old[key]; ok { cache.fresh[key] = value cache.deleteFromOldAndFlush(key) return value } return "" } func (cache *Cache) deleteFromOldAndFlush(key string) { delete(cache.old, key) if len(cache.fresh) == cache.max { cache.old = cache.fresh cache.fresh = make(map[string]string, cache.max) } }
Добавив метод для печати элементов в обоих поколениях "подебажим" их на тех же элементах, какие добавляли испытывая первый способ (со списком) - только зададим размер поменьше (3) поскольку здесь он относится к размеру поколения (вот код https://go.dev/play/p/Q58tD7d2hGb) - здесь в каждой строке вертикальной чертой разделены элементы в новом и старом поколениях:
set Abrikos -> ABR ABR | set Bananas -> BAN ABR BAN | set Cucumba -> CUC | ABR BAN CUC search Abrikos -> ABR ABR | BAN CUC set Durian -> DUR ABR DUR | BAN CUC set Eggplant -> EGG | ABR DUR EGG set Durian -> DUN DUN | ABR EGG set Fig -> FIG DUN FIG | ABR EGG search Bananas -> DUN FIG | EGG ABR
Результат практически тот же (отчасти это удачное совпадение) - хотя понятно что наш новый кэш ведёт себя иначе - распухнув до предела он мгновенно "схлопывается" - в худшем случае вдвое.
Знатоки Java (и не только) скажут что это опять же напоминает Garbage Collection построенный "по поколениям" - ну да, идея "поколений" давно используется на практике!
Идею можно экстраполировать на больше чем 2 поколения - допустим на 3 - тогда объём "схлопывания" будет в пределах трети от общего. Однако из-за обращения в 3 мэпы операции замедлятся чуть больше - да и код уже лучше будет изменить так чтобы оперировать небольшим массивом поколений и итерироваться по нему - и в общем-то нет необходимости так поступать.
Можно даже наоборот - использовать вырожденный вариант с 1 поколением - когда мэпа заполняется целиком - она просто очищается. Интуитивно кажется что этот вариант хуже - но ведь мы тогда можем использовать вдвое больший размер мэпы при том же потреблении памяти. Оставим этот вариант на проверку энтузиастам.
Анализируя этот способ подметим следующее:
операция Get обращается в две мэпы для старых или отсутствующих элементов, но для "хороших" (то есть недавних) нужно только одно обращение
операция Put тоже может обращаться в две мэпы, но может довольствоваться и только одной - для "хороших", недавних элементов
значит если "хорошие" элементы попадаются статистически ощутимо чаще плохих (а это и есть актуальный случай использования кэша - то количество обращений в мэпы отнюдь не возрастает вдвое (по сравнению с "классическим" способом со списком)
в способе со списком расходуется больше памяти: при одинаковом ограничении
maxмы будем иметь два поколения, каждое размером доmax- то есть до2*maxзаписей - при сравнимых затратах памяти (здесь мы храним две мэпы - а там мэпу и список со всеми ключами и значениями - в общем, зависит от размераvalue- если оно меньше чем 3 указателя, то мы точно экономим)отсюда же следует что при сравнимом расходе памяти мы чаще "попадаем" в сохранённые в кэше значения (просто потому что их больше) - а от этого улучшается производительность (ведь основное "торможение" не от количества обращений в мэпы, а от количества "промахов" и необходимости загрузки из нижележащего медленного хранилища).
"схлопывание" происходит отнюдь не после каждых
Nопераций записи - поскольку не все из них окажутся "старыми" или "отсутствующими".
Замечание о смысле "размера" кэша
В отличие от классического варианта, этот кэш после "наполнения" не обязательно остаётся постоянным в размере - он может уменьшиться после нескольких Get-операций (об этом - следующее замечание). Размер который мы задаём при создании - это минимальное количество записей которые он всё-таки гарантированно будет "удерживать". В нашей реализации это значение совпадает с максимальным размером "старого" поколения и на единицу больше максимального размера "нового". Эти частности можно варьировать переставляя строки или меняя строгие и нестрогие неравенства - но это непринципиально.
Замечание �� "схлопывании" из-за операций чтения
Нежелательной может казаться та особенность поведения, что кэш может уменьшаться от Get операций, представим например такой код:
c := NewCache(3) c.Put("one", "один") c.Put("two", "два") c.Put("three", "три") c.Put("four", "четыре") c.Put("five", "пять") println(c.Get("one"), c.Get("two"), c.Get("three"), c.Get("four"), c.Get("five"))
Он напечатает один четыре пять - хотя понятно что после пяти Put-ов были доступны все элементы. Однако two и three пропали когда c.Get("one") триггернул очистку старого поколения (в котором они находились).
В этом поведении нет никакой ошибки или обмана - мы, как пояснено выше, и создавали кэш для гарантированного размера 3. Тем не менее интересно, нельзя ли как-то эффективнее использовать "старое" поколение и на операциях Get по крайней мере не терять элементы.
Простейшим вариантом, конечно, было бы не "промоутить" элементы при Get операции. Но это несколько противоречит задаче LRU-кэша.
Вместо этого можно поступать так - если элемент "промоутится" из старого поколения в новое, нужно "взамен" более старый элемент из нового выкинуть в старый. К сожалению эта идея упирается в то что мы не знаем какой из элементов нового поколения самый старый! Эдак нвому поколению понадобится собственный кэш!
Здесь возможны также разные подходы - либо действительно пытаться как-то определять более старые элементы в новом поколении (может использовать способ с таймстемпами описанный выше) - либо перемещать случайно выбранный элемент. Способ с удалением случайных элементов хотя и кажется сперва нелепым, но на самом деле широко используется, например, в кэшах процессоров.
Мы однако не будем углубляться в этот эксперимент - с одной стороны поскольку в Go нет красивого способа взят поистинне рандомный элемент из мэпы - с другой, поскольку такой кэш уже станет все-таки не чисто LRU (есть шанс что рандомный более свежий элемент окажется удалён раньше чем какой-то более давно использованный, хотя в среднем все же будут удаляться более старые.
Тестирование на большем объёме
Это не очень простая задача по смыслу - потому что невозможно предсказать точно какого характера данные будут в "реальной" задаче, как часто кэш будет "попадать" и "промахиваться". Тем не менее какую-то оценку хочется получить поэтому попробуем сгенерировать данные, распределённые не очень равномерно, и варьируя размер кэша получим разные отношения hit/miss.
Используем такой код чтобы сгенерировать 20 миллионов 6-значных чисел, распределенных не очень равномерно (за счет возведения числа из диапазона [0..1) в квадрат).
func main() { r := rand.New(rand.NewSource(17)) sz, _ := strconv.ParseInt(os.Args[1], 10, 64) cache := NewCache(int(sz)) hit := 0 miss := 0 for i := 0; i < 20000000; i++ { rnd := r.Float64() key := fmt.Sprintf("%06d", int(rnd*rnd*1000000)) if cache.Get(key) == "" { cache.Put(key, key) miss++ } else { hit++ } } println("hit:", hit, "miss:", miss) }
Запустим его на трёх наших алгоритмах для размеров кэша (задаваемых параметром командной строки) в 100, 300 и 500 тысяч записей.
Здесь деликатный момент - строго говоря кэши нужно сравнивать не по количеству записей, а по занимаемой памяти. Исходя из этого соображения "размер" для кэша "с поколениями" означает размер одного поколения - в таком случае его объём будет близок к объёму кэша с мэпой и списком (как обсуждалось выше). Для варианта "с таймстемпами" такой поправки не сделано - но вы можете поэкспериментировать самостоятельно.
размер кэша | |||
100000 | 300000 | 500000 | |
Со списком | |||
-- время | 5.8 сек | 7.4 сек | 8.5 сек |
-- попад / промах | 3.7 млн / 16.3 млн | 8.5 млн / 11.5 млн | 12.3 млн / 7.7 млн |
С таймстемпами | |||
-- время | 5.8 сек | 7.1 сек | 7.3 сек |
-- попад / промах | 3.3 млн / 16.7 млн | 7.5 млн / 12.5 млн | 11.0 млн / 9.0 млн |
С поколениями | |||
-- время | 4.1 сек | 5.6 сек | 6.3 сек |
-- попад / промах | 4.9 млн / 15.1 млн | 10.5 млн / 9.5 млн | 14.3 млн / 5.7 млн |
По этим цифрам не следует делать скоропалительных выводов - главное что можно заметить - все три способа весьма близки, о чём и говорилось выше - то есть отказ от списка не ведёт к каким-то драматическим эффектам.
Конечно, приятно что наш "самый упрощённый" способ немного но заметно выигрывает в скорости. При этом помним - в данном тесте "промах" не влечёт какой-то задержки по времени (как в реальной системе). Разница получается только за счет исключения операций на списке.
В реальной же ситуации "торможение на промахах" тоже сыграет на руку нашему "упрощённому" варианту, поскольку как видим промахов он даёт меньше (что вполне объяснимо - ведь как говорилось, мы фактически используем мэпу большего размера за счет того что высвободили память занятую списком).
Что касается способа "с таймстемпами" - заметно что и он не хуже, впрочем тут можно дополнительно пробовать варианты с разными процентами удаляемых записей. Для справедливости стоит заметить что он занимает меньше памяти чем два других способа, так что "по-честному" следовало бы ему задавать бОльший размер кэша.
Заключение
Уверен что знатоки могут припомнить в комментариях ещё кучу способов реализации LRU-кэша, с деревьями, в том числе декартовыми, кучами или какой-нибудь ещё более диковинной магией. Но наша цель была в том чтобы найти по возможности более простые подходы (KISS - принцип) - ведь проревьюить и протестировать даже такой небольшой алгоритм - уже требуется и время и внимание.
Простота - вещь относительная - но можно примерно оценить по количеству строк в исходниках:
реализация со списком растянулась примерно на 64 строки
реализация с таймстемпами (и "продвинутым" удалением) - тоже около 60 строк
реализация с поколениями - около 30 строк
О том что алгоритм "с поколениями" может оказаться выгоднее - этого я до написания примеров к статье не знал. Ну и конечно это от реализации хэштаблиц в языке зависит.
Пока я составлял и отлаживал примеры и тесты для этой статьи, конечно, неизбежно обнаруживал ошибки и в собственной реализации (особенно по классическому способу, что неудивительно). Примеры и ссылки на плейграунд приходилось менять - и есть шанс что в этом процессе могла вкрасться какая-либо неконсистентность. Если обнаружите подобное - не ломайте голову и не ругайте автора - а смело пишите - и постараемся поскорее исправить.
P.S. для удобства желающих потестировать и поэкспериментировать на гитхабе размещён более "практичный" вариант двух кэшей - с дженериками и мьютексами - и в виде библиотеки которую можно включить в проект: https://github.com/rodiongork/lrucache
