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

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

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

TileData * tileData =缓存-> lookup(tileId);//不安全？

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

无效的Cache::lookup(int tileId，float *＆tileData)
{
//在缓存中查找图块，如果不在缓存中，则从磁盘加载到缓存中，...
...
//现在复制图块数据，安全但是不会那么慢吗？
memcpy((char *)tileData，tileDataFromCache，sizeof(float)* 3 * 16 * 16);
}
float * tileData =新的float [3 * 16 * 16];//需要为该图块分配内存
//从缓存中获取 slice 数据，需要复制
cache-> lookup(tileId，tileData);

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

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

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

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

最佳答案

您的问题的答案:

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

2)我将从使用字符串作为键开始，看看它实际上是否太慢。如果字符串不太长(例如，文件名不太长)，则可能会比预期的要快。如果您确实发现字符串键不够有效，则可以尝试执行类似的操作，例如为字符串计算哈希码并向其中添加图块ID ...这可能会在实践中起作用，尽管总有可能哈希冲突。但是您可以在启动时运行冲突检查例程，该例程将生成所有可能的filename + 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;
   }
}

关于c++ - 更好地了解LRU算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15463128/