Лучшее понимание алгоритма LRU

В том же порядке, что и ваши вопросы:

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

• Я предполагаю, что вы собираетесь использовать какой-то хеш-таблица для поисковой части того, что вы описываете. Общее решение вашей проблемы состоит из двух частей:

  • Использование подходящей функции хеширования, которая объединяет несколько значений, например имя файла текстуры и идентификатор плитки. По сути вы создаете составной ключ это рассматривается как одно целое. Функция хеширования может быть операцией XOR хэшей всех элементарных компонентов или чем-то более сложным.

    Выбор подходящей хеш-функции имеет решающее значение с точки зрения производительности — если указанная функция не является достаточно случайной, у вас будет много хэш столкновения.

  • Использование подходящей составной проверки равенства для обработки случая хеш-столкновений.

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

• Использование временных меток для этого не иду на работу — период. В большинстве источников, касающихся кеширования, обычно описываются рассматриваемые алгоритмы с учетом кеширования сетевых ресурсов (например, кеширования HTTP). Это не сработает здесь по трем причинам:

  1. Использование естественного времени имеет смысл только в том случае, если вы намерены внедрять политики кэширования, которые учитывают его, например, сброс записи в кеш через 10 минут. Если вы не делаете что-то очень странное что-то подобное не имеет смысла в 3D-рендерере.

  2. Метки времени имеют относительно низкое фактическое разрешение, даже если вы используете высокоточные таймеры. Большинство источников таймера имеют точность около 1 мс, что является очень долгое время для процессора — за это время ваш рендерер проработал бы несколько текстурных записей.

  3. Ты хоть представляешь, сколько стоят таймерные звонки? Такое злоупотребление ими может даже заставить вашу систему работать хуже чем не иметь кеша вообще …

  Обычное решение этой проблемы — вообще не использовать таймер. Алгоритм LRU должен знать только две вещи:

  1. Максимально допустимое количество записей.

  2. Порядок существующих записей w.r.t. их последний доступ.

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

  Использование комбинированной структуры данных, а не двух отдельных, позволяет удалять записи из хеш-таблицы без необходимости выполнять операцию поиска. Это улучшает общую производительность, но это не является абсолютно необходимым.

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

#include <cstdlib>
#include <cstdio>
#include <memory>
#include <list>
#include <unordered_map>

#include <cstdint>
#include <iostream>

typedef uint32_t data_key_t;

class TileData
{
public:
TileData(const data_key_t &key) : theKey(key) {}
data_key_t theKey;
~TileData() { std::cerr << "delete " << theKey << std::endl; }
};

typedef std::shared_ptr<TileData> TileDataPtr;   // automatic memory management!

TileDataPtr loadDataFromDisk(const data_key_t &theKey)
{
return std::shared_ptr<TileData>(new TileData(theKey));
}

class CacheLRU
{
public:
// the linked list keeps track of the order in which the data was accessed
std::list<TileDataPtr> linkedList;
// the hash map (unordered_map is part of c++0x while hash_map isn't?) gives quick access to the data
std::unordered_map<data_key_t, TileDataPtr> hashMap;
CacheLRU() : cacheHit(0), cacheMiss(0) {}
TileDataPtr getData(data_key_t theKey)
{
std::unordered_map<data_key_t, TileDataPtr>::const_iterator iter = hashMap.find(theKey);
if (iter != hashMap.end()) {
TileDataPtr ret = iter->second;
linkedList.remove(ret);
linkedList.push_front(ret);
++cacheHit;
return ret;
}
else {
++cacheMiss;
TileDataPtr ret = loadDataFromDisk(theKey);
linkedList.push_front(ret);
hashMap.insert(std::make_pair<data_key_t, TileDataPtr>(theKey, ret));
if (linkedList.size() > MAX_LRU_CACHE_SIZE) {
const TileDataPtr dropMe = linkedList.back();
hashMap.erase(dropMe->theKey);
linkedList.remove(dropMe);
}
return ret;
}
}
static const uint32_t MAX_LRU_CACHE_SIZE = 8;
uint32_t cacheMiss, cacheHit;
};

int main(int argc, char **argv)
{
CacheLRU cache;
for (uint32_t i = 0; i < 238; ++i) {
int key = random() % 32;
TileDataPtr tileDataPtr = cache.getData(key);
}
std::cerr << "Cache hit: " << cache.cacheHit << ", cache miss: " << cache.cacheMiss << std::endl;
return 0;
}