Дизайн C++: Как кэшироваться новый используемый

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

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

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

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

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

Спасибо
осколок

7
задан splintor 20 December 2009 в 19:41
поделиться

9 ответов

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

16
ответ дан 6 December 2019 в 05:38
поделиться

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

11
ответ дан 6 December 2019 в 05:38
поделиться

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

вы просматриваете список (который, по общему признанию, является операцией O (n), а не операцией O (log n) на карте). Если вы найдете его, вы удалите его из текущего местоположения и снова вставите в начало списка. Если длина списка превышает 1000 элементов, вы удаляете необходимое количество элементов из конца списка, чтобы уменьшить его до менее 1000 элементов.

вы просматриваете список (который, по общему признанию, является операцией O (n), а не операцией O (log n) на карте). Если вы найдете его, вы удалите его из текущего местоположения и снова вставите в начало списка. Если длина списка превышает 1000 элементов, вы удаляете необходимое количество элементов из конца списка, чтобы уменьшить его до менее 1000 элементов.

2
ответ дан 6 December 2019 в 05:38
поделиться

Обновление: я понял ...

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

// 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.

2
ответ дан 6 December 2019 в 05:38
поделиться

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

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

0
ответ дан 6 December 2019 в 05:38
поделиться

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

1
ответ дан 6 December 2019 в 05:38
поделиться

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

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

0
ответ дан 6 December 2019 в 05:38
поделиться

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

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

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

0
ответ дан 6 December 2019 в 05:38
поделиться

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

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

0
ответ дан 6 December 2019 в 05:38
поделиться
Другие вопросы по тегам:

Похожие вопросы: