c++ - 更好的理解LRU算法

Question

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

• 在我的例子中，我将使用纹理缓存来存储图像数据的“图 block ”(16x16 像素 block )。现在想象一下，我在缓存中进行了一次查找，得到了一个结果(图 block 在缓存中)。如何将该条目的“缓存”内容返回给函数调用者？我解释。我想象当我在缓存内存中加载一个图 block 时，我分配内存来存储例如 16x16 像素，然后加载该图 block 的图像数据。现在有两种解决方案可以将缓存条目的内容传递给函数调用者:
  1) 作为指向图 block 数据的指针(快速、内存高效)，

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

  2) 或者我需要从函数调用者分配的内存空间内的缓存中重新复制切片数据(复制可能很慢)。

  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 copycache->lookup(tileId, tileData);

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

• 应用程序可能会访问超过 1 个纹理。我似乎无法找到一种方法来创建对每个纹理和每个纹理图 block 都是唯一的键。例如，我可能在缓存中有来自 file1 的 tile 1 和来自 file2 的 tile1，因此在 tildId=1 上进行搜索是不够的......但我似乎无法找到一种方法来创建占文件的 key 名称和 tileID。我可以构建一个包含文件名和 tileID (FILENAME_TILEID) 的字符串，但用作键的字符串不会比整数慢得多吗？

• 最后我有一个关于时间戳的问题。许多论文建议使用时间戳来对缓存中的条目进行排序。使用时间戳有什么好的功能？时间()函数，时钟()？有没有比使用时间戳更好的方法？

抱歉，我意识到这是一条很长的消息，但 LRU 的实现似乎并不像听起来那么简单。

Answer 1

问题的答案:

1) 返回一个 shared_ptr(或逻辑上等同的东西)。然后，所有“何时可以安全删除此对象”的问题几乎都消失了。

2) 我首先使用一个字符串作为键，看看它是否真的太慢了​​。如果字符串不太长(例如，您的文件名不太长)，那么您可能会发现它比您预期的要快。如果您确实发现字符串键不够有效，您可以尝试诸如计算字符串的哈希码并向其添加图 block ID 之类的方法......这可能在实践中有效，尽管总是有可能哈希冲突。但是你可以在启动时运行一个碰撞检查例程，它会生成所有可能的文件名+tileID 组合，并在映射到相同的键值时提醒你，这样至少你会在测试期间立即知道问题并可以做一些事情(例如通过调整你的文件名和/或你的哈希码算法)。当然，这假设所有文件名和图 block 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;
   }
}