更好地理解LRU算法-Java 学习之路

我需要在3D渲染器中实现LRU算法以进行纹理缓存 . 我在Linux上用C编写代码 .

在我的情况下，我将使用纹理缓存来存储"tiles"的图像数据（16x16像素块） . 现在假设我在缓存中进行查找，获得命中（tile在缓存中） . 如何将该条目的"cache"的内容返回给函数调用者？我解释 . 我想，当我在高速缓冲存储器中加载一个磁贴时，我分配内存来存储16x16像素，然后加载该磁贴的图像数据 . 现在有两种解决方案可以将缓存条目的内容传递给函数调用者：
1）作为指向图块数据的指针（快速，内存效率），

TileData *tileData = cache->lookup(tileId); // not safe?

2）或者我需要在函数调用者分配的内存空间中重新复制来自缓存的tile数据（复制可能很慢） .

void Cache::lookup(int tileId, float *&tileData)
{
   // find tile in cache, if not in cache load from disk add to cache, ...
   ...
   // now copy tile data, safe but ins't that slow?
   memcpy((char*)tileData, tileDataFromCache, sizeof(float) * 3 * 16 * 16);
}
float *tileData = new float[3 * 16 * 16]; // need to allocate the memory for that tile
// get tile data from cache, requires a copy
cache->lookup(tileId, tileData);

我会选择1）但问题是，如果在查找之后从缓存中删除了tile，并且该函数尝试使用返回指针访问数据会发生什么？我看到的唯一解决方案是使用一种引用计数（auto_ptr）的形式，其中数据实际上只在不再使用时才被删除？

应用程序可能访问多个纹理 . 我似乎无法找到一种创建每个纹理和纹理的每个图块独有的键的方法 . 例如，我可能在缓存中有来自file1的tile 1和来自file2的tile1，所以在tildId = 1上进行搜索是不够的......但我似乎无法找到一种方法来创建解释该文件的密钥name和tileID . 我可以构建一个包含文件名和tileID（FILENAME_TILEID）的字符串，但是用作键的字符串不会比整数慢得多吗？
最后我有一个关于时间戳的问题 . 许多论文建议使用时间戳来对缓存中的条目进行排序 . 使用时间戳有什么好功能？ time（）函数，clock（）？有比使用时间戳更好的方法吗？

对不起，我意识到这是一个非常长的消息，但LRU似乎并不像听起来那么简单 .

3 回答

您的问题的答案：

1）返回一个shared_ptr（或逻辑上等同于它的东西） . 然后所有“什么时候安全删除这个对象”的问题几乎消失了 .

2）我首先使用一个字符串作为键，看看它实际上是否太慢 . 如果字符串不是太长（例如你的文件名不是太长），那么你可能会发现它比你预期的要快 . 如果你确实发现字符串键不够有效，你可以尝试类似于为字符串计算哈希码并向其添加tile ID ...这可能会在实践中起作用，尽管总是有可能哈希冲突 . 但是你可以在启动时运行一个碰撞检查例程来生成所有可能的文件名tileID组合，并在映射到相同的键值时提醒你，这样至少你在测试时会立即知道出现问题并且可以对此做些什么（例如通过调整文件名和/或哈希码算法） . 当然，这假设所有文件名和磁贴ID都将事先知道 .

3）我不建议使用时间戳，这是不必要的和脆弱的 . 相反，尝试这样的事情（伪代码）：

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

linked_list<TileDataPtr> linkedList;
hash_map<data_key_t, TileDataPtr> hashMap;

// This is the method the calling code would call to get its tile data for a given key
TileDataPtr GetData(data_key_t theKey)
{
   if (hashMap.contains_key(theKey))
   {
      // The desired data is already in the cache, great!  Just move it to the head
      // of the LRU list (to reflect its popularity) and then return it.
      TileDataPtr ret = hashMap.get(theKey);
      linkedList.remove(ret);     // move this item to the head
      linkedList.push_front(ret); // of the linked list -- this is O(1)/fast
      return ret;
   }
   else
   {
      // Oops, the requested object was not in our cache, load it from disk or whatever
      TileDataPtr ret = LoadDataFromDisk(theKey);
      linkedList.push_front(ret);
      hashMap.put(theKey, ret);

      // Don't let our cache get too large -- delete
      // the least-recently-used item if necessary
      if (linkedList.size() > MAX_LRU_CACHE_SIZE)
      {
         TileDataPtr dropMe = linkedList.tail();
         hashMap.remove(dropMe->GetKey());
         linkedList.remove(dropMe);
      }
      return ret;
   }
}

回复于 2024-05-02T09:09:16+08:00

0
与您的问题顺序相同：
- 从性能角度来看，复制纹理日期似乎不合理 . 只要您可以安全地编码它，参考计数声音就会好得多 . 数据存储器一旦未被渲染器使用或者存储在缓存中就会被释放 .
- 我假设您将使用某种hash table作为您所描述内容的查找部分 . 您的问题的常见解决方案有两个部分：
- 使用合并多个值的合适散列函数，例如纹理文件名和图块ID . 基本上，您创建一个被视为一个实体的复合键 . 散列函数可以是所有基本组件的散列的XOR运算，或者更复杂的东西 .
选择合适的散列函数对于性能原因至关重要 - 如果所述函数不够随机，则会有很多hash collisions .
- 使用合适的复合相等性检查来处理哈希冲突的情况 .
这样你就可以查找所有属性的组合对单个哈希表查找感兴趣 .
- 使用时间戳这是行不通的 - 期间 . 关于缓存的大多数来源通常在考虑网络资源缓存（例如HTTP缓存）时描述所讨论的算法 . 由于三个原因，这在这里不起作用：
- 使用自然时间只是意味着您打算实施将其考虑在内的缓存策略，例如10分钟后删除缓存条目 . 除非你做了一件非常奇怪的事情，否则在3D渲染器中没有任何意义 .
- 即使使用高精度计时器，时间戳的实际分辨率也相对较低 . 大多数定时器源具有大约1ms的精度，这对于处理器来说是非常长的时间 - 在那个时候你的渲染器将通过几个纹理条目工作 .
- 你知道定时器通话有多贵吗？像这样滥用它们甚至可能使你的系统比没有任何缓存更糟糕...
这个问题的通常解决方案是根本不使用计时器 . LRU算法只需要知道两件事：
- 允许的最大条目数 .
- 现有条目的顺序w.r.t.他们最后一次访问
项目（1）来自系统的配置，并且通常取决于可用的存储空间 . 项（2）通常意味着使用组合链表/散列表数据结构，其中散列表部分提供快速访问，并且链表保留访问顺序 . 每次访问一个条目时，它都会放在列表的末尾，而旧的条目会从其开头删除 .

使用组合数据结构而不是两个单独的数据结构允许从哈希表中删除条目，而无需通过查找操作 . 这提高了整体性能，但并非绝对必要 .
回复于 2024-05-02T09:09:16+08:00

正如所承诺的那样，我发布了我的代码 . 如果我犯了错误或者我可以进一步改进，请告诉我 . 我现在要研究如何在多线程环境中工作 . 再次感谢Jeremy和Thkala的帮助（对不起，代码不适合评论栏） .

#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;
}

回复于 2024-05-02T09:09:16+08:00

更好地理解LRU算法

3 回答

相关问题