كيف يمكنني أن أجعل ذاكرة التخزين المؤقت البسيطة لـ .NET LRU أسرع؟

Question

تحديث:أهلا شباب، شكرا على الردود.لقد جربت الليلة الماضية والليلة عدة طرق مختلفة وتوصلت إلى طريقة مشابهة لتلك الموضحة أدناه بواسطة 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)، وأنا أبحث عن طرق لجعل بشكل أسرع.

Answer 1

التحديث رقم 2

يؤدي هذا إلى تقليل الحاجة إلى اجتياز القائمة في إزالة القائمة المرتبطة.يقدم LruCacheNode الذي يحتوي على المفتاح والقيمة.يتم استخدام المفتاح فقط عند قطع ذاكرة التخزين المؤقت.يمكنك الحصول على أداء أفضل إذا قمت بكتابة تنفيذ القائمة المرتبطة الخاصة بك حيث تكون كل عقدة بشكل أساسي LruCacheNode بالإضافة إلى مرجع التالي والخلفي.هذا نوع ما يفعله LinkedHashMap (انظر هؤلاء اثنين أسئلة).

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.

Answer 2

وأليس وجهة مخبأ LRU للسماح لك لخفض ذاكرة التخزين المؤقت والتخلص من الاشياء الأقل المستخدمة مؤخرا؟ :-) أنا لا أرى أي رمز لخفض ذاكرة التخزين المؤقت. منذ كنت على الارجح تريد الأداء العالي لاسترداد حالة الاستخدام، وخفض استخدام الحالة هو أقل أهمية لماذا لا افراغ الصيانة القائمة إلى عملية تقليم؟

وIOW، مجرد رمي الإدخالات في ذاكرة التخزين المؤقت، ولكن طابع زمني لهم على استرجاعها. لا إعادة ترتيب الإدخالات، فقط وضع علامة عليها كلما كنت تستخدم. يمكن أن يكون التاريخ والوقت الزمني الحقيقي، أو يمكن أن يكون عداد بسيطة في الصف، كانت تستخدم أكبر عدد مؤخرا. ثم في عملية تقليم مجرد المشي الشجرة كلها وإزالة إدخالات مع أقدم الطوابع.

Answer 3

ومع مخابئ الأجهزة، بدلا من القول 128 عناصر، والحفاظ على ترتيب العناصر 1-128، قد يكون لديك أنها 32 × 4، لذلك 32 صفوف من 4 عناصر لكل منها. ان بت 5 الأولى من عنوان تحديد أي من 32 صفوف من شأنها أن الخريطة عنوان ل، ثم هل البحث فقط 4 بنود، وإذا لم يتم العثور يحل محل أقدم من 4.

وهذا هو أسرع بكثير، وغير IIRC في حدود 10٪ من معدل ضرب من مخبأ 1 × 128.

لترجمة، وكنت بدلا من قائمة مرتبطة واحدة، لديك العديد منها، بحيث يجتاز منهم كان أسرع بكثير. أن يكون لديك وسيلة لتحديد أي قائمة عنصر معين إلى معين.

والنقطة الوجود، كما ينمو قائمتك في الحجم، والحصول على عوائد متناقصة من محاولة الحفاظ بدقة مثالية الترتيب الدقيق من كل عنصر في القائمة. حتى أنك قد تكون أفضل حالا مع قائمة غير مرتبة، واستبدال عشوائيا أي عنصر عندما يكون لديك ملكة جمال ذاكرة التخزين المؤقت. يعتمد على حجم القائمة الخاصة بك، وعقوبة لملكة جمال في مقابل تكاليف الإبقاء على القائمة.