2

テクスチャ キャッシングのために、3D レンダラーに LRU アルゴリズムを実装する必要があります。Linux の C++ でコードを記述します。

  • 私の場合、テクスチャ キャッシングを使用して、画像データの「タイル」(16x16 ピクセル ブロック) を格納します。ここで、キャッシュ内でルックアップを行い、ヒットを取得したとします (タイルはキャッシュ内にあります)。そのエントリの「キャッシュ」の内容を関数の呼び出し元に返すにはどうすればよいですか? 私は説明する。タイルをキャッシュ メモリにロードするときに、たとえば 16x16 ピクセルを格納するためにメモリを割り当ててから、そのタイルの画像データをロードすることを想像します。キャッシュ エントリの内容を関数の呼び出し元に渡す方法は 2 つあります
    。1) タイル データへのポインタとして (高速でメモリ効率が高い) 

    TileData *tileData = cache->lookup(tileId); // 安全ではありません？

    2) または、関数の呼び出し元によって割り当てられたメモリ空間内のキャッシュからタイル データを再コピーする必要があります (コピーが遅くなる可能性があります)。 

    void Cache::lookup(int tileId, float *&tileData)
{
   // キャッシュ内のタイルを見つけます。ディスクからのキャッシュ ロードでない場合は、キャッシュに追加します ...
   ...
   // タイル データをコピーします。安全ですが、それほど遅くはありませんか?
   memcpy((char*)tileData, tileDataFromCache, sizeof(float) * 3 * 16 * 16);
}
float *tileData = new float[3 * 16 * 16]; // そのタイルにメモリを割り当てる必要があります
// キャッシュからタイル データを取得します。コピーが必要です
cache->lookup(tileId, tileData);

    私は 1) を使用しますが、問題は、ルックアップの直後にタイルがキャッシュから削除され、関数がリターン ポインターを使用してデータにアクセスしようとするとどうなるかということです。これに対する唯一の解決策は、参照カウント (auto_ptr) の形式を使用することです。データは、使用されなくなったときにのみ実際に削除されますか?

  • アプリケーションは複数のテクスチャにアクセスする場合があります。各テクスチャとテクスチャの各タイルに固有のキーを作成する方法が見つからないようです。たとえば、ファイル 1 のタイル 1 とファイル 2 のタイル 1 がキャッシュにある場合、tildId=1 で検索するだけでは十分ではありません...しかし、ファイルを説明するキーを作成する方法が見つからないようです。名前と tileID。ファイル名と tileID (FILENAME_TILEID) を含む文字列を作成できますが、キーとして使用される文字列は整数よりもはるかに遅くなりませんか?

  • 最後に、タイムスタンプについて質問があります。多くの論文では、キャッシュ内のエントリの順序付けにタイム スタンプを使用することを提案しています。タイムスタンプを使用するのに適した関数は何ですか? time() 関数、clock()? タイムスタンプを使用するよりも良い方法はありますか?

申し訳ありませんが、非常に長いメッセージであることは承知していますが、LRU の実装は思ったほど簡単ではないようです。

4

3 に答える 3

4

質問への回答:

1) shared_ptr (または論理的に同等のもの) を返します。その後、「このオブジェクトを削除しても安全な場合」の問題はすべてほぼ解消されます。

2）文字列をキーとして使用することから始め、実際に遅すぎるかどうかを確認します。文字列が長すぎない場合 (たとえば、ファイル名が長すぎない場合)、予想よりも高速であることに気付くかもしれません。文字列キーが十分に効率的でないことがわかった場合は、文字列のハッシュコードを計算してそれにタイル ID を追加するなどの方法を試すことができます。ハッシュ衝突。ただし、起動時に衝突チェック ルーチンを実行して、考えられるすべてのファイル名とタイル 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;
   }
}
于 2013-03-17T17:45:26.297 に答える
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 に答える
0

質問と同じ順序で：

  • テクスチャの日付をコピーすることは、パフォーマンスの観点から合理的ではないようです。実際に安全にコーディングできる限り、参照カウントははるかに優れています。データ メモリは、レンダラーによって使用されなくなるか、キャッシュに参照が格納されるとすぐに解放されます。

  • あなたが説明していることのルックアップ部分に、ある種のハッシュテーブルを使用しようとしていると思います。問題の一般的な解決策には、次の 2 つの部分があります。

    • テクスチャ ファイル名とタイル ID などの複数の値を組み合わせる適切なハッシュ関数を使用します。基本的に、1 つのエンティティとして扱われる複合キーを作成します。ハッシュ関数は、すべての基本コンポーネントのハッシュの XOR 操作、またはより複雑なものである可能性があります。

      適切なハッシュ関数を選択することは、パフォーマンス上の理由から重要です。この関数が十分にランダムでない場合、多くのハッシュ衝突が発生します。

    • 適切な複合等価性チェックを使用して、ハッシュ衝突のケースを処理します。

    このようにして、単一のハッシュ テーブル ルックアップで対象のすべての属性の組み合わせをルックアップできます。

  • これにタイムスタンプを使用してもうまくいきません。キャッシングに関するほとんどの情報源は、通常、ネットワーク リソースのキャッシング (HTTP キャッシュなど) を念頭に置いて問題のアルゴリズムを説明しています。ここでは、次の 3 つの理由で機能しません。

    1. 自然時間を使用することは、10 分後にキャッシュ エントリをドロップするなど、それを考慮したキャッシュ ポリシーを実装する意図がある場合にのみ意味があります。非常に奇妙なことをしていない限り、このようなことは 3D レンダラーでは意味がありません。

    2. 高精度のタイマーを使用している場合でも、タイムスタンプの実際の解像度は比較的低くなります。ほとんどのタイマー ソースの精度は約 1 ミリ秒です。これは、プロセッサにとって非常に長い時間です。この時間内に、レンダラーはいくつかのテクスチャ エントリを処理していたはずです。

    3. タイマー呼び出しがどれだけ高価か知っていますか? このようにそれらを悪用すると、キャッシュがまったくない場合よりもシステムのパフォーマンスが低下する可能性さえあります...

    この問題の通常の解決策は、タイマーをまったく使用しないことです。LRU アルゴリズムに必要なのは、次の 2 つのことだけです。

    1. 許可されるエントリの最大数。

    2. 既存のエントリの順序は、最後のアクセスからのものです。

    項目 (1) はシステムの構成に由来し、通常は使用可能なストレージ スペースに依存します。項目 (2) は一般に、結合されたリンク リスト/ハッシュ テーブル データ構造の使用を意味します。この場合、ハッシュ テーブル部分は高速アクセスを提供し、リンク リストはアクセス順序を保持します。エントリがアクセスされるたびに、リストの最後に配置され、古いエントリは先頭から削除されます。

    2 つの個別のデータ構造ではなく、結合されたデータ構造を使用すると、ルックアップ操作を行うことなく、エントリをハッシュ テーブルから削除できます。これにより、全体的なパフォーマンスが向上しますが、絶対に必要というわけではありません。

于 2013-03-17T17:48:00.787 に答える