更好地了解LRU算法 [英] Better understanding the LRU algorithm

问题描述

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

I need to implement a LRU algorithm in a 3D renderer for texture caching. I write the code in C++ on Linux.

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

• In my case I will use texture caching to store "tiles" of image data (16x16 pixels block). Now imagine that I do a lookup in the cache, get a hit (tile is in the cache). How do I return the content of the "cache" for that entry to the function caller? I explain. I imagine that when I load a tile in the cache memory, I allocate the memory to store 16x16 pixels for example, then load the image data for that tile. Now there's two solutions to pass the content of the cache entry to the function caller:
  1) either as pointer to the tile data (fast, memory efficient),

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

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

2) or I need to recopy the tile data from the cache within a memory space allocated by the function caller (copy can be slow).

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)，其中实际上仅在不再使用数据时才删除数据?

I would go with 1) but the problem is, what happens if the tile gets deleted from the cache just after the lookup, and that the function tries to access the data using the return pointer? The only solution I see to this, is to use a form of referencing counting (auto_ptr) where the data is actually only deleted when it's not used anymore?

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

the application might access more than 1 texture. I can't seem to find of a way of creating a key which is unique to each texture and each tile of a texture. For example I may have tile 1 from file1 and tile1 from file2 in the cache, so making the search on tildId=1 is not enough... but I can't seem to find a way of creating the key that accounts for the file name and the tileID. I can build a string that would contain the file name and the tileID (FILENAME_TILEID) but wouldn't a string used as a key be much slower than an integer?

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

Finally I have a question regarding time stamp. Many papers suggest to use a time stamp for ordering the entry in the cache. What is a good function to use a time stamp? the time() function, clock()? Is there a better way than using time stamps?

对不起，我意识到这是一条很长的信息，但是LRU的实现似乎并不像听起来那样简单.

Sorry I realise it's a very long message, but LRU doesn't seem as simple to implement than it sounds.

推荐答案

回答您的问题:

1)返回一个shared_ptr(或在逻辑上等效的东西).然后，所有何时可以安全删除该对象"问题都将消失.

1) Return a shared_ptr (or something logically equivalent to it). Then all of the "when-is-it-safe-to-delete-this-object" issues pretty much go away.

2)我将从使用字符串作为键开始，看看它实际上是否太慢.如果字符串不太长(例如，文件名不太长)，则可能会比预期的要快.如果您确实发现字符串键不够高效，则可以尝试执行类似的操作，例如为字符串计算哈希码并向其中添加图块ID ...这可能会在实践中起作用，尽管总有可能哈希冲突.但是您可以在启动时运行一个冲突检查例程，该例程将生成所有可能的filename + tileID组合，并在映射到相同的键值时提醒您，以便至少在测试期间您会立即知道问题，并可能对此采取措施(例如，通过调整文件名和/或哈希码算法).当然，这是假定所有文件名和图块ID都将是预先知道的.

2) I'd start by using a string as a key, and see if it actually is too slow or not. If the strings aren't too long (e.g. your filenames aren't too long) then you may find it's faster than you expect. If you do find out that string-keys aren't efficient enough, you could try something like computing a hashcode for the string and adding the tile ID to it... that would probably work in practice although there would always be the possibility of a hash-collision. But you could have a collision-check routine run at startup that would generate all of the possible filename+tileID combinations and alert you if map to the same key value, so that at least you'd know immediately during your testing when there is a problem and could do something about it (e.g. by adjusting your filenames and/or your hashcode algorithm). This assumes that what all the filenames and tile IDs are going to be known in advance, of course.

3)我不建议您使用时间戳，因为它是不必要且脆弱的.相反，请尝试这样的操作(伪代码):

3) I wouldn't recommend using a timestamp, it's unnecessary and fragile. Instead, try something like this (pseudocode):

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

这篇关于更好地了解LRU算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！