単純な.NET LRUキャッシュを高速化するにはどうすればよいですか？
https://stackoverflow.com/questions/615648
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
更新： 皆さん、返信ありがとう。昨夜と今夜、私はいくつかの異なるアプローチを試し、Jeffが下に示したものに似たアプローチを思いつきました（彼がアップデートで提案したことをすでに実行し、追加の利益のために自分のシンプルなLL実装をまとめました）。コードは次のとおりです。この時点では特にきれいに見えませんが、パフォーマンスを強化するためにできることを何回も変更してきました。
public class NewLRU2<K, V> where V : class
{
int m_iMaxItems;
Dictionary<K, LRUNode<K, V>> m_oMainDict;
private LRUNode<K,V> m_oHead;
private LRUNode<K,V> m_oTail;
private LRUNode<K,V> m_oCurrent;
public NewLRU2(int iSize)
{
m_iMaxItems = iSize;
m_oMainDict = new Dictionary<K, LRUNode<K,V>>();
m_oHead = null;
m_oTail = null;
}
public V this[K key]
{
get
{
m_oCurrent = m_oMainDict[key];
if (m_oCurrent == m_oHead)
{
//do nothing
}
else if (m_oCurrent == m_oTail)
{
m_oTail = m_oCurrent.Next;
m_oTail.Prev = null;
m_oHead.Next = m_oCurrent;
m_oCurrent.Prev = m_oHead;
m_oCurrent.Next = null;
m_oHead = m_oCurrent;
}
else
{
m_oCurrent.Prev.Next = m_oCurrent.Next;
m_oCurrent.Next.Prev = m_oCurrent.Prev;
m_oHead.Next = m_oCurrent;
m_oCurrent.Prev = m_oHead;
m_oCurrent.Next = null;
m_oHead = m_oCurrent;
}
return m_oCurrent.Value;
}
}
public void Add(K key, V value)
{
if (m_oMainDict.Count >= m_iMaxItems)
{
//remove old
m_oMainDict.Remove(m_oTail.Key);
//reuse old
LRUNode<K, V> oNewNode = m_oTail;
oNewNode.Key = key;
oNewNode.Value = value;
m_oTail = m_oTail.Next;
m_oTail.Prev = null;
//add new
m_oHead.Next = oNewNode;
oNewNode.Prev = m_oHead;
oNewNode.Next = null;
m_oHead = oNewNode;
m_oMainDict.Add(key, oNewNode);
}
else
{
LRUNode<K, V> oNewNode = new LRUNode<K, V>(key, value);
if (m_oHead == null)
{
m_oHead = oNewNode;
m_oTail = oNewNode;
}
else
{
m_oHead.Next = oNewNode;
oNewNode.Prev = m_oHead;
m_oHead = oNewNode;
}
m_oMainDict.Add(key, oNewNode);
}
}
public bool Contains(K key)
{
return m_oMainDict.ContainsKey(key);
}
}
internal class LRUNode<K,V>
{
public LRUNode(K key, V val)
{
Key = key;
Value = val;
}
public K Key;
public V Value;
public LRUNode<K, V> Next;
public LRUNode<K, V> Prev;
}
追加を行うときに古いノードを再利用するなど、奇妙に見える/感じるいくつかの部分がありますが、それらからかなりのパフォーマンスの向上を得ることができました。ノードの実際のプロパティから単なるパブリック変数に切り替えることで生じた違いにも少し驚きましたが、それがこのようなものに当てはまると思います。この時点で、上記のコードは辞書操作によってほぼ完全にパフォーマンスが制限されているため、それをマッシュアップすることでさらに多くのことが得られるかどうかはわかりません。引き続き考えて、いくつかの回答を検討します。
元の投稿からの説明： こんにちは皆さん。 そこで、圧縮ライブラリで使用するための単純な軽量LRU実装を作成しました（ハッシュ、LZWスタイルに基づいて入力で一致するバイト文字列を見つけるために使用しています）。より速く。
解決
更新＃2
これにより、リンクされたリストでのリストのトラバースの必要性が減ります。キーと値の両方を持つLruCacheNodeを導入します。キーは、キャッシュをトリムするときにのみ使用されます。各ノードが基本的にLruCacheNodeであり、NextおよびBack参照を含む独自のリンクリスト実装を記述した場合、パフォーマンスが向上する可能性があります。これは、LinkedHashMapが行うことの一種です（これら 2つのの質問） 。
public class LruCache<K, V>
{
private readonly int m_iMaxItems;
private readonly Dictionary<K, LinkedListNode<LruCacheNode<K, V>>> m_oMainDict;
private readonly LinkedList<LruCacheNode<K, V>> m_oMainList;
public LruCache(int iSize)
{
m_iMaxItems = iSize;
m_oMainDict = new Dictionary<K, LinkedListNode<LruCacheNode<K, V>>>();
m_oMainList = new LinkedList<LruCacheNode<K, V>>();
}
public V this[K key]
{
get
{
return BumpToFront(key).Value;
}
set
{
BumpToFront(key).Value = value;
}
}
public void Add(K key, V value)
{
LinkedListNode<LruCacheNode<K, V>> newNode = m_oMainList.AddFirst(new LruCacheNode<K, V>(key, value));
m_oMainDict.Add(key, newNode);
if (m_oMainList.Count > m_iMaxItems)
{
m_oMainDict.Remove(m_oMainList.Last.Value.Key);
m_oMainList.RemoveLast();
}
}
private LruCacheNode<K, V> BumpToFront(K key)
{
LinkedListNode<LruCacheNode<K, V>> node = m_oMainDict[key];
if (m_oMainList.First != node)
{
m_oMainList.Remove(node);
m_oMainList.AddFirst(node);
}
return node.Value;
}
public bool Contains(K key)
{
return m_oMainDict.ContainsKey(key);
}
}
internal sealed class LruCacheNode<K, V>
{
private readonly K m_Key;
private V m_Value;
public LruCacheNode(K key, V value)
{
m_Key = key;
m_Value = value;
}
public K Key
{
get { return m_Key; }
}
public V Value
{
get { return m_Value; }
set { m_Value = value; }
}
}
環境の改善であるかどうかを確認するには、プロファイルを作成する必要があります。
マイナーアップデート： BumpToFrontを更新して、Tim Stewartからのコメントごとにノードが既に先頭にあるかどうかを確認しました。
他のヒント
LRUキャッシュのポイントは、キャッシュをトリムして、最も最近使用されていないものを捨てることができるのではないでしょうか？ :-)キャッシュをトリミングするコードが表示されません。おそらく、ユースケースの取得に高いパフォーマンスが必要で、トリムのユースケースはそれほど重要ではないので、なぜリストのメンテナンスをトリムプロセスにオフロードしないのですか？
IOW、エントリをキャッシュにスローするだけですが、取得時にタイムスタンプを付けます。エントリを並べ替えるのではなく、使用するたびにマークするだけです。真のDateTimeタイムスタンプ、またはクラス内の単純なカウンターである可能性があり、最も大きい数値が最後に使用されました。次に、トリムプロセスでツリー全体をたどって、最も古いスタンプを持つエントリを削除します。
ハードウェアキャッシュでは、128個の要素を持ち、アイテム1〜128の順序を維持する代わりに、32 x 4として各4要素の32行がある場合があります。アドレスの最初の5ビットは、アドレスが32行のうちどの行にマップされるかを決定し、4つの項目のみを検索し、見つからない場合は4つの最も古いものを置き換えます。
これは非常に高速で、IIRCは1 x 128キャッシュのヒット率の10％以内です。
翻訳するには、1つのリンクリストの代わりに複数のリストを作成します。そのため、リストをたどるのははるかに高速でした。特定のアイテムがどのリストにマップされているかを判断する方法が必要になります。
重要なのは、リストのサイズが大きくなると、リスト内の各要素の正確な順序を完全な精度で維持しようとすることから得られる利益が減少することです。順序付けられていないリストを使用して、キャッシュミスが発生したときに任意の要素をランダムに置換することをお勧めします。リストのサイズ、およびミスに対するペナルティとリストの維持コストに依存します。
