2

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

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

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

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

    无效缓存::lookup(int tileId, float *&tileData)
{
   // 在缓存中查找切片，如果不在缓存中，则从磁盘加载到缓存，...
   ...
   // 现在复制平铺数据，安全但不是很慢吗？
   memcpy((char*)tileData, tileDataFromCache, sizeof(float) * 3 * 16 * 16);
}
浮动 *tileData = 新浮动[3 * 16 * 16]; // 需要为该图块分配内存
// 从缓存中获取瓦片数据，需要一个副本
缓存->查找（tileId，tileData）；

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

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

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

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

4

3 回答 3

4

回答您的问题：

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

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

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;
   }
}
于 2013-03-17T17:45:26.297 回答
0

按照与您的问题相同的顺序：

  • 从性能的角度来看，复制纹理日期似乎并不合理。引用计数听起来要好得多，只要您实际上可以安全地对其进行编码。一旦渲染器不使用数据内存或在缓存中存储引用，数据内存就会被释放。

  • 我假设您将使用某种哈希表来查找您所描述的内容。您的问题的常见解决方案有两个部分：

    • 使用组合多个值的合适散列函数，例如纹理文件名和图块 ID。本质上，您创建了一个复合键，它被视为一个实体。散列函数可以是所有基本组件的散列的异或运算，或者更复杂的东西。

      出于性能原因，选择合适的哈希函数至关重要 - 如果所述函数不够随机，您将遇到很多哈希冲突。

    • 使用合适的复合相等检查来处理哈希冲突的情况。

    这样，您可以在单个哈希表查找中查找所有感兴趣属性的组合。

  • 为此使用时间戳是行不通的-期间。大多数关于缓存的资料通常在描述有问题的算法时考虑到网络资源缓存（例如 HTTP 缓存）。这在这里行不通，原因有以下三个：

    1. 使用自然时间仅在您打算实施将其考虑在内的缓存策略时才有意义，例如在 10 分钟后删除缓存条目。除非您正在做一些非常奇怪的事情，否则这样的事情在 3D 渲染器中是没有意义的。

    2. 即使您使用高精度计时器，时间戳的实际分辨率也相对较低。大多数计时器源的精度约为 1 毫秒，这对于处理器来说是一个很长的时间——在那个时候，您的渲染器将处理多个纹理条目。

    3. 你知道定时器调用有多昂贵吗？像这样滥用它们甚至可能使您的系统性能比根本没有任何缓存更糟糕......

    这个问题的通常解决方案是根本不使用计时器。LRU算法只需要知道两件事：

    1. 允许的最大条目数。

    2. 现有条目的顺序是它们的最后一次访问。

    第 (1) 项来自系统配置，通常取决于可用存储空间。第(2)项一般暗示使用组合链表/散列表数据结构，其中散列表部分提供快速访问，链表保留访问顺序。每次访问一个条目时，它都会被放在列表的末尾，而旧条目会从它的开头删除。

    使用组合数据结构，而不是两个单独的数据结构，可以从哈希表中删除条目，而无需进行查找操作。这提高了整体性能，但不是绝对必要的。

于 2013-03-17T17:48:00.787 回答
0

正如承诺的那样，我正在发布我的代码。如果我犯了错误或者我是否可以进一步改进，请告诉我。我现在将研究使其在多线程环境中工作。再次感谢 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;
}
于 2013-03-25T18:18:29.720 回答