Tôi có thể làm cho bộ nhớ cache .NET LRU đơn giản của mình nhanh hơn bằng cách nào?

Question

CẬP NHẬT: Xin cảm ơn các bạn đã trả lời. Đêm qua và tối nay tôi đã thử một vài cách tiếp cận khác nhau và đưa ra một cách tương tự với cách mà Jeff đưa ra dưới đây (tôi thậm chí đã làm những gì anh ta đề xuất trong bản cập nhật của mình, và cùng nhau triển khai thực hiện LL đơn giản để tăng thêm). Đây là đoạn mã, vào thời điểm này nó trông không rõ ràng nữa, nhưng tôi đã trải qua nhiều lần thay đổi bất cứ điều gì tôi có thể để tăng cường hiệu suất.

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

Có một vài phần trông/cảm thấy giống như sử dụng lại nút cũ khi thực hiện thêm - nhưng tôi có thể nhận được sự gia tăng đáng kể về hiệu suất của chúng. Tôi cũng hơi ngạc nhiên trước sự khác biệt mà nó tạo ra để chuyển từ các thuộc tính thực tế trên nút thành các biến công cộng, nhưng tôi đoán đó là cách nó đi với công cụ này. Tại thời điểm này, mã ở trên gần như hoàn toàn bị giới hạn hiệu năng bởi các hoạt động từ điển, vì vậy tôi không chắc chắn tôi sẽ nhận được nhiều hơn từ việc nghiền nó xung quanh. Tôi sẽ tiếp tục suy nghĩ về nó và xem xét một số câu trả lời.

Giải thích từ bài đăng gốc: Xin chào tất cả. Vì vậy, tôi đã viết một triển khai LRU nhẹ đơn giản để sử dụng trong thư viện nén (tôi đang sử dụng nó để tìm các chuỗi byte phù hợp trong đầu vào dựa trên băm, kiểu LZW) và tôi đang tìm cách lam no nhanh hơn.

Answer 1

CẬP NHẬT # 2

Điều này làm giảm nhu cầu về danh sách traversal trên một danh sách Remove liên kết. Nó giới thiệu LruCacheNode có cả khóa và giá trị. Khóa chỉ được sử dụng khi bạn cắt bộ nhớ cache. Bạn có thể nhận được hiệu suất tốt hơn nếu bạn đã viết triển khai danh sách liên kết của riêng mình, trong đó mỗi nút về bản chất là một LruCacheNode cùng với tham chiếu Tiếp theo và Quay lại. Đây là loại LinkedHashMap làm gì (xem thesetwo câu hỏi).

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

Bạn sẽ phải cấu hình mọi thứ để xem đây có phải là cải tiến trong môi trường của bạn hay không.

Cập nhật nhỏ: Tôi đã cập nhật BumpToFront để kiểm tra xem liệu nút đã ở phía trước cho mỗi nhận xét từ Tim Stewart hay chưa.

Answer 2

Với bộ đệm phần cứng, thay vì nói 128 phần tử và duy trì thứ tự của các mục 1-128, bạn có thể có nó là 32 x 4, vì vậy 32 hàng gồm 4 phần tử. 5 bit đầu tiên của một địa chỉ sẽ xác định xem 32 hàng địa chỉ nào sẽ ánh xạ tới, sau đó bạn sẽ chỉ tìm kiếm 4 mục và nếu không tìm thấy thay thế lâu nhất trong số 4.

Điều này nhanh hơn nhiều và là IIRC trong vòng 10% tỷ lệ truy cập của bộ nhớ cache 1 x 128.

Để dịch, bạn sẽ thay vì một danh sách được liên kết, có nhiều danh sách được liên kết, vì vậy việc duyệt qua chúng nhanh hơn nhiều. Bạn sẽ phải có một cách để xác định danh sách một mục cụ thể được ánh xạ tới.

Vấn đề là khi danh sách của bạn tăng kích thước, bạn nhận được lợi nhuận giảm từ việc cố gắng duy trì độ chính xác hoàn hảo theo thứ tự chính xác của từng phần tử trong danh sách. Bạn thậm chí có thể tốt hơn với một danh sách không có thứ tự, và thay thế ngẫu nhiên bất kỳ phần tử nào khi bạn bị thiếu bộ nhớ cache. Phụ thuộc vào kích thước của danh sách của bạn, và hình phạt cho một bỏ lỡ so với chi phí duy trì danh sách.

Answer 3

Không phải là điểm của bộ nhớ cache LRU để cho phép bạn cắt bộ nhớ cache và loại bỏ những thứ ít được sử dụng gần đây nhất? :-) Tôi không thấy bất kỳ mã nào để cắt bộ nhớ cache.Vì bạn rất có thể muốn hiệu năng cao cho trường hợp truy xuất được truy xuất và trường hợp sử dụng cắt bớt ít quan trọng hơn vì sao không dỡ bỏ danh sách bảo trì cho quá trình cắt?

IOW, chỉ cần ném các mục nhập vào bộ nhớ cache, nhưng dấu thời gian chúng trên truy xuất. Không sắp xếp lại các mục nhập, chỉ cần đánh dấu chúng bất cứ khi nào chúng được sử dụng. Có thể là dấu thời gian DateTime thực sự hoặc có thể là một bộ đếm đơn giản trong lớp, số cao nhất được sử dụng gần đây nhất. Sau đó, trong quá trình cắt chỉ cần đi bộ toàn bộ cây và loại bỏ các mục với tem lâu đời nhất.