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

Question

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

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

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

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

  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)，但问题是，如果在查找之后瓦片被从缓存中删除，并且该函数尝试使用返回指针访问数据，会发生什么？我对此的唯一解决方案是使用引用计数(auto_ptr)的形式，其中数据实际上仅在不再使用时才被删除？

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

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

抱歉，我意识到这是一条很长的消息，但 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;
   }
}