C ++ дизайн: как кешировать последние использованные

Question

У нас есть приложение на C ++, для которого мы пытаемся улучшить производительность. Мы определили, что поиск данных занимает много времени, и мы хотим кешировать данные. Мы не можем хранить все данные в памяти, поскольку они огромны. Мы хотим хранить до 1000 предметов в памяти. Этот элемент может быть проиндексирован клавишей long. Однако, когда размер кэша превышает 1000, мы хотим удалить элемент, к которому не обращались в течение самого длительного времени, поскольку мы предполагаем некоторую «локальность ссылок», то есть мы предполагаем, что элементы в кэше, к которому недавно обращались вероятно, снова будет доступен.

Можете ли вы предложить способ ее реализации?

Моя первоначальная реализация состояла в том, чтобы иметь map<long, CacheEntry> для хранения кэша и добавить accessStamp член к CacheEntry, для которого будет установлен увеличивающийся счетчик при создании или доступе к записи. Когда кэш заполнен и требуется новая запись, код отсканирует всю карту кэша, найдет запись с самым низким значением accessStamp и удалит ее. Проблема в том, что после заполнения кеша каждая вставка требует полного сканирования кеша.

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

Можете ли вы предложить лучший подход?

спасибо
splintor * * 1018

Answer 1

У вас есть map<long,CacheEntry>, но вместо отметки времени доступа в CacheEntry вставьте две ссылки на другие CacheEntry объекты, чтобы записи образовали двусвязный список. При каждом доступе к записи перемещайте ее в начало списка (это операция с постоянным временем). Таким образом, вы оба легко найдете запись в кэше, поскольку к ней обращаются с карты, и можете удалить наименее использованную запись, поскольку она находится в конце списка (я предпочитаю делать списки с двойной связью круглыми таким образом, указатель на голову также достаточен для быстрого доступа к хвосту). Также не забудьте вставить ключ, который вы использовали на карте, в CacheEntry, чтобы вы могли удалить запись с карты, когда она будет удалена из кэша.

Answer 2

Сканирование карты из 1000 элементов займет очень мало времени, и сканирование будет выполняться только в том случае, если элемент не находится в кеше, который, если ваше местоположение эталонных идей правильное, должен составлять небольшую часть времени. Конечно, если ваши идеи ошибочны, кэш, вероятно, в любом случае является пустой тратой времени.

Answer 3

В моем подходе необходимо иметь хеш-таблицу для быстрого поиска сохраненных объектов и связанный список для поддержания последовательности последнего использования.

Когда объект запрашивается. 1) попробуйте найти объект из хеш-таблицы 2.yes) если найдено (значение имеет указатель на объект в связанном списке), переместите объект в связанном списке в верхнюю часть связанного списка. 2.no) если нет, удалите последний объект из связанного списка и удалите данные также из хеш-таблицы, затем поместите объект в хеш-таблицу и верхнюю часть связанного списка.

Например Допустим, у нас есть кэш-память только на 3 объекта.

Последовательность запроса: 1 3 2 1 4.

1) Хеш-таблица: [1] Связанный список: [1]

2) Хеш-таблица: [1, 3] Связанный список: [3, 1]

3) Хеш-таблица: [1,2,3] Связанный список: [2,3,1]

4) Хеш-таблица: [1,2,3] Связанный список: [1,2,3]

5) Хеш-таблица: [1,2,4] Связанный список: [4,1,2] => 3 из

Answer 4

Альтернативная реализация, которая могла бы упростить «старение» элементов, но за счет более низкой производительности поиска, состояла бы в том, чтобы хранить ваши элементы CacheEntry в std :: list (или использовать std::pair<long, CacheEntry>. Самый новый элемент получает добавлены в начале списка, чтобы они «мигрировали» к концу списка по мере их старения. Когда вы проверяете, присутствует ли элемент в кэше, вы сканируете список (который по общему признанию является операцией O (n) как вместо того, чтобы быть операцией O (log n) на карте.) Если вы найдете ее, вы удалите ее из ее текущего местоположения и вставите заново в начало списка. Если длина списка превышает 1000 элементов, вы удаляете ее. необходимое количество элементов в конце списка, чтобы обрезать его ниже 1000 элементов.

Answer 5

Обновление: я получил это сейчас ...

Это должно быть достаточно быстро. Предупреждение, некоторый псевдокод вперед.

// accesses contains a list of id's. The latest used id is in front(),
// the oldest id is in back().
std::vector<id> accesses;
std::map<id, CachedItem*> cache;

CachedItem* get(long id) {
    if (cache.has_key(id)) {
         // In cache.
         // Move id to front of accesses.
         std::vector<id>::iterator pos = find(accesses.begin(), accesses.end(), id);
         if (pos != accesses.begin()) {
             accesses.erase(pos);
             accesses.insert(0, id);
         }
         return cache[id];
    }

    // Not in cache, fetch and add it.
    CachedItem* item = noncached_fetch(id);
    accesses.insert(0, id);
    cache[id] = item;
    if (accesses.size() > 1000)
    {
        // Remove dead item.
        std::vector<id>::iterator back_it = accesses.back();
        cache.erase(*back_it);
        accesses.pop_back();
    }
    return item;
}

Вставки и удаления могут быть немного дорогими, но также могут быть не слишком плохими, учитывая локальность (мало промахов кэша) В любом случае, если они станут большой проблемой, можно перейти на std :: list.

Answer 6

Создайте std: priority_queue

:: iterator> с компаратором для метки доступа. Для вставки сначала вытолкните последний элемент из очереди и удалите его с карты. Затем вставьте новый элемент в карту и, наконец, поместите его итератор в очередь.

Answer 7

Другим вариантом может быть использование boost :: multi_index . Он предназначен для отделения индекса от данных и тем самым позволяет использовать несколько индексов для одних и тех же данных.

Я не уверен, что это действительно будет быстрее, чем сканировать 1000 предметов. Это может использовать больше памяти, чем хорошо. Или замедлить поиск и / или вставить / удалить.

Answer 8

Я считаю, что это хороший кандидат на трепы . Приоритетом будет время (виртуальное или иное) в порядке возрастания (более старое в корне) и long в качестве ключа.

Существует также алгоритм второго шанса , который хорош для кэшей. Хотя вы теряете возможность поиска, это не окажет большого влияния, если у вас будет только 1000 предметов.

Наивным методом было бы иметь карту, связанную с приоритетной очередью, заключенную в класс. Вы используете карту для поиска и очередь для удаления (сначала удалите из очереди, захватите элемент, а затем удалите по ключу с карты).

Answer 9

Я согласен с Нилом, сканирование 1000 элементов вообще не занимает много времени.

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

Answer 10

В качестве более простой альтернативы вы можете создать карту, которая растет бесконечно и очищается каждые 10 минут или около того (настройте время для ожидаемого трафика).

Вы также можете регистрировать некоторые очень интересные статистические данные таким образом.