ضغط قاموس ضعيف

Question

لدي فصل فور مع الممتلكات هوية شخصية. وبعد هدفي هو أنه لا توجد حالتين من فور مع نفس الشيء هوية شخصية في نفس الوقت.

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

static Foo CreateFoo(int id) {
    Foo foo;
    if (!cache.TryGetValue(id, out foo)) {
        foo = new Foo(id);
        foo.Initialize(...);
        cache.Put(id, foo);
    }
    return foo;
}

يتم تطبيق ذاكرة التخزين المؤقت كشركةu003CTKey,WeakReference> ، مرتكز على jaredpar.'س بناء الضعف hashtable:

class WeakDictionary<TKey, TValue> where TValue : class {
    private readonly Dictionary<TKey, WeakReference> items;
    public WeakDictionary() {
        this.items = new Dictionary<TKey, WeakReference>();
    }
    public void Put(TKey key, TValue value) {
        this.items[key] = new WeakReference(value);
    }
    public bool TryGetValue(TKey key, out TValue value) {
        WeakReference weakRef;
        if (!this.items.TryGetValue(key, out weakRef)) {
            value = null;
            return false;
        } else {
            value = (TValue)weakRef.Target;
            return (value != null);
        }
    }
}

المشكلة هي أن الضعف لا تزال في القاموس بعد أن تم جمع أهدافهم من القمامة. هذا يعني الحاجة إلى بعض الاستراتيجيات كيفية "جمع القمامة" يدويا الضعف الميت، كما هو موضح Bascal cuoq. في ماذا يحدث لضعف بعد GC من الضعف..

---

سؤالي هو: ما هي أفضل استراتيجية لمفعول قاموس ضعيف؟

الخيارات التي أراها هي:

1. لا تقم بإزالة الضعف من القاموس. IMO هذا سيء، لأن ذاكرة التخزين المؤقت تستخدم في العمر الكامل للتطبيق الخاص بي، و كثير من الضعف الميت سوف تتراكم مع مرور الوقت.

2. المشي في القاموس بأكمله على كل وضع و tirgetvalue., وإزالة الضعف الميت. هذا يهزم الغرض إلى حد ما من القاموس لأن كلا العمليات تصبح تشغيل).

3. المشي في القاموس بأكمله بشكل دوري في خيط الخلفية. ما سيكون فاصل زمني جيد، بالنظر إلى أنني لا أعرف نمط استخدام createfoo.?

4. إلحاق كل KeyValuepair المدرجة إلى قائمة مرتبطة مزدوجة النهاية. كل مكالمة إلى وضع و tirgetvalue. يفحص رأس القائمة. إذا كان الضعف على قيد الحياة، فقم بنقل الزوج إلى نهاية القائمة. إذا كان ميتا، فقم بإزالة الزوج من القائمة والضعيف من القاموس.

5. قم بتنفيذ جدول تجزئة مخصصة مع اختلاف بسيط، عند إزالته دلو ممتلئا، تتم إزالة الضعف الميت من الجرافة قبل المتابعة كالمعتاد.

هل هناك استراتيجيات أخرى؟

ربما تكون أفضل استراتيجية ربما خوارزمية مع تعقيد الوقت المطفأ. هل هذه الاستراتيجية موجودة؟

Answer 1

الخيار الخاص بك 3 (مؤشر الترابط) لديه العيب الكبير لجعل التزامن ضروري على جميع إجراءات وضع / teregetvalue. إذا كنت تستخدم هذا، فستكون الفاصل الزمني الخاص بك ليس في milliseconds ولكن كل إجراءات تحرف n n.

الخيار 2، مسح القاموس، سوف يتحمل النفقات العامة الخطيرة. يمكنك تحسين المسح الضوئي فقط 1 في 1000 إجراءات و / أو عن طريق مشاهدة عدد المرات التي يعمل فيها GC.

لكنني سأنظر بجدية الخيار 1: لا تفعل شيئا. قد يكون لديك "الكثير" من الإدخالات الميتة ولكن من ناحية أخرى أنها صغيرة جدا (واحصل على إعادة تدويرها). ربما لا يوجد خيار لتطبيق الخادم، ولكن للحصول على تطبيق عميل، سأحاول الحصول على قياس حول عدد الإدخالات (KBYTE) في الساعة التي نتحدث عنها.

بعد بعض النقاش:

هل هذه الاستراتيجية [n المطفأة] موجودة؟

أعتقد أن لا. مشكلتك هي نسخة مصغرة من GC. سيكون لديك لمسح الشيء كله مرة واحدة في حين. فقط الخيارات 2) و 3) تقديم حل حقيقي. وهي باهظة الثمن ولكن يمكن أن تكون (بشدة) محسنة مع بعض الاستدلال. الخيار 2) سوف تظل تعطيك الأسوأ في بعض الأحيان على الرغم من.

Answer 2

إذا كنت تستطيع تبديل الكائن المدار لتكون مفتاح القاموس، فيمكنك استخدام .NET 4.0's Conditionalweaktable (Namespace System.Runtime.compilerservices).

وفقا للسيد ريختر، يتم إخطار ConvertalWeaktable من جمع الكائنات من قبل جامع القمامة بدلا من استخدام خيط الاقتراع.

    static ConditionalWeakTable<TabItem, TIDExec> tidByTab = new ConditionalWeakTable<TabItem, TIDExec>();

    void Window_Loaded(object sender, RoutedEventArgs e)
    {
        ...
        dataGrid.SelectionChanged += (_sender, _e) =>
        {
            var cs = dataGrid.SelectedItem as ClientSession;

            this.tabControl.Items.Clear();

            foreach (var tid in cs.GetThreadIDs())
            {
                tid.tabItem = new TabItem() { Header = ... };
                tid.tabItem.AddHandler(UIElement.MouseDownEvent,
                    new MouseButtonEventHandler((__sender, __e) =>
                    {
                        tabControl_SelectionChanged(tid.tabItem);
                    }), true);
                tidByTab.Add(tid.tabItem, tid);
                this.tabControl.Items.Add(tid.tabItem);
            }
        };
    }

    void tabControl_SelectionChanged(TabItem tabItem)
    {
        this.tabControl.SelectedItem = tabItem;
        if (tidByTab.TryGetValue(tabControl.SelectedItem as TabItem, out tidExec))
        {
            tidExec.EnsureBlocksLoaded();
            ShowStmt(tidExec.CurrentStmt);
        }
        else
            throw new Exception("huh?");
    }

ما هو مهم هنا هو أن الشيء الوحيد الذي يشير إلى كائن Tabitem هو مجموعة TabControls.Items، ومفتاح الشروط القابلة للتلف. مفتاح الشروط لا يحسب. لذلك عندما نقوم بمسح جميع العناصر من TabControl، يمكن جمع تلك Tabitems (لأن لا شيء يشير إليها لفترة أطول، مرة أخرى لم يعد مفتاح OfficeTableTable). عندما يتم جمع المباريات التي تم جمعها، يتم إعلام الضيوف وقابلة للإزالة مع إزالة القيمة الرئيسية هذه. لذلك فإن كائنات TidExec الضخمة هي أيضا جمع القمامة في تلك المرحلة (لا شيء يشير إليها، باستثناء قيمة OptionalWeTable).

Answer 3

النهج رقم 5 مثيرة للاهتمام، ولكن لديه عيوب أنه قد يكون من الصعب معرفة المستوى الحقيقي لاستخدام جدول التجزئة، وبالتالي متى ينبغي توسيع جدول التجزئة. قد يتم التغلب على تلك الصعوبة إذا كان يبدو أنه "يبدو" مثل جدول التجزئة، أولا يقوم أولا بفحص الجدول بالكامل لإزالة الإدخالات الميتة. إذا كانت أكثر من نصف الإدخالات في الطاولة ميتة، فلا تهتم بتوسيعها. يجب أن يؤدي هذا النهج إلى إطفاء السلوك O (1) المطفأة، لأن المرء لن يقوم بمسح الجدول بأكمله حتى يتم إضافة المرء إلى الوراء ككثير من الإدخالات التي تم حذفها.

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

Answer 4

كان لدي هذه المشكلة نفسها، وحلها مثل هذا (الضعيف هو الطبقة التي كنت أحاول تنظيفها):

internal class CleanerRef
{
    ~CleanerRef()
    {
        if (handle.IsAllocated)
            handle.Free();
    }

    public CleanerRef(WeakDictionaryCleaner cleaner, WeakDictionary dictionary)
    {
        handle = GCHandle.Alloc(cleaner, GCHandleType.WeakTrackResurrection);
        Dictionary = dictionary;
    }

    public bool IsAlive
    {
        get {return handle.IsAllocated && handle.Target != null;}
    }

    public object Target
    {
        get {return IsAlive ? handle.Target : null;}
    }

    GCHandle handle;
    public WeakDictionary Dictionary;
}


internal class WeakDictionaryCleaner
{
    public WeakDictionaryCleaner(WeakDictionary dict)
    {
        refs.Add(new CleanerRef(this, dict));
    }

    ~WeakDictionaryCleaner()
    {
        foreach(var cleanerRef in refs)
        {
            if (cleanerRef.Target == this)
            {
                cleanerRef.Dictionary.ClearGcedEntries();
                refs.Remove(cleanerRef);
                break;
            }
        }
    }
    private static readonly List<CleanerRef> refs = new List<CleanerRef>();
}

ما يحاول هذا الفصل الدراسي تحقيقه هو "ربط" GC. تقوم بتنشيط هذه الآلية عن طريق إنشاء مثيل ضعيف في مجال بناء المجموعة الضعيفة:

new WeakDictionaryCleaner(weakDictionary);

لاحظ أنني لا أقوم بإنشاء أي إشارة إلى المثيل الجديد، بحيث يقوم GC بالتخلص منه أثناء الدورة التالية. في طريقة CleargcedentRies () الطريقة التي أقوم بإنشاء مثيل جديد مرة أخرى، بحيث يكون لكل دورة GC منظف تنهي ذلك بدوره سيقوم بتنفيذ ضغط المجموعة. يمكنك جعل Cleanerref.dictionary أيضا مرجع ضعيف بحيث لن يحمل القاموس في الذاكرة.

أتمنى أن يساعدك هذا

Answer 5

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

static IdentityMap<int, Entity> Cache = new IdentityMap<int, Entity>(e => e.ID);
...
var entity = Cache.Get(id, () => LoadEntity(id));

فئة تعرض طريقة عامة واحدة فقط Get مع key واختياري value المعلمة التي يتم تحميلها على المكدس وتخزين كيان إذا لم يكن في ذاكرة التخزين المؤقت.

using System;
class IdentityMap<TKey, TValue>
    where TKey : IEquatable<TKey>
    where TValue : class
{
    Func<TValue, TKey> key_selector;
    WeakReference<TValue>[] references;
    int[] buckets;
    int[] bucket_indexes;
    int tail_index;
    int entries_count;
    int capacity;

    public IdentityMap(Func<TValue, TKey> key_selector, int capacity = 10) {
        this.key_selector = key_selector;
        Init(capacity);
    }
    void Init(int capacity) {
        this.bucket_indexes = new int[capacity];
        this.buckets = new int[capacity];
        this.references = new WeakReference<TValue>[capacity];
        for (int i = 0; i < capacity; i++) {
            bucket_indexes[i] = -1;
            buckets[i] = i - 1;
        }
        this.tail_index = capacity - 1;
        this.entries_count = 0;
        this.capacity = capacity;
    }

    public TValue Get(TKey key, Func<TValue> value = null) {
        int bucket_index = Math.Abs(key.GetHashCode() % this.capacity);
        var ret = WalkBucket(bucket_index, true, key);
        if (ret == null && value != null) Add(bucket_index, ret = value());
        return ret;
    }

    void Add(int bucket_index, TValue value) {
        if (this.entries_count == this.capacity) {
            for (int i = 0; i < capacity; i++) WalkBucket(i, false, default(TKey));
            if (this.entries_count * 2 > this.capacity) {
                var old_references = references;
                Init(this.capacity * 2);
                foreach (var old_reference in old_references) {
                    TValue old_value;
                    if (old_reference.TryGetTarget(out old_value)) {
                        int hash = key_selector(value).GetHashCode();
                        Add(Math.Abs(hash % this.capacity), old_value);
                    }
                }
            }
        }
        int new_index = this.tail_index;
        this.tail_index = buckets[this.tail_index];
        this.entries_count += 1;
        buckets[new_index] = bucket_indexes[bucket_index];
        if (references[new_index] != null) references[new_index].SetTarget(value);
        else references[new_index] = new WeakReference<TValue>(value);
        bucket_indexes[bucket_index] = new_index;
    }

    TValue WalkBucket(int bucket_index, bool is_searching, TKey key) {
        int curr_index = bucket_indexes[bucket_index];
        int prev_index = -1;
        while (curr_index != -1) {
            TValue value;
            int next_index = buckets[curr_index];
            if (references[curr_index].TryGetTarget(out value)) {
                if (is_searching && key_selector(value).Equals(key)) return value;
                prev_index = curr_index;
            } else {
                if (prev_index != -1) buckets[prev_index] = next_index;
                else bucket_indexes[bucket_index] = next_index;

                buckets[curr_index] = this.tail_index;
                this.tail_index = curr_index;
                this.entries_count -= 1;
            }
            curr_index = next_index;
        }
        return null;
    }
}

Answer 6

يمكنك إزالة "غير صالح" WeakReference داخل TryGetValue:

تعديل خطأي، هذه الحلول فعلا لا تفعل شيئا أكثر مما اقترحته، منذ Put سوف تبادل الطريقة الكائن القديم مع الجديد على أي حال. فقط تجاهله.

public bool TryGetValue(TKey key, out TValue value) {
    WeakReference weakRef;
    if (!this.items.TryGetValue(key, out weakRef)) {
        value = null;
        return false;
    } else {
        value = (TValue)weakRef.Target;
        if (value == null)
            this.items.Remove(key);
        return (value != null);
    }
}

أو، يمكنك إنشاء مثيل جديد فورا داخل قاموسك، كلما حاجة إلى ذلك:

public TValue GetOrCreate(TKey key, Func<Tkey, TValue> ctor) {

    WeakReference weakRef;
    if (!this.items.TryGetValue(key, out weakRef) {
        Tvalue result = ctor(key);
        this.Put(key, result);
        return result;
    } 

    value = (TValue)weakRef.Target;
    if (value == null)
    {
        Tvalue result = ctor(key);
        this.Put(key, result);
        return result;
    }

    return value;
}

يمكنك بعد ذلك استخدامه مثل هذا:

static Foo CreateFoo(int id)
{
    return cache.GetOrCreate(id, id => new Foo(id));
}

تعديل

وفقا ل WINDBG، WeakReference المثال وحده يحتل 16 بايت. بالنسبة إلى 100000 كائنات تم جمعها، لن يكون هذا عبئا خطيرا، لذلك يمكنك السماح لهم بسهولة بالعيش.

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

Answer 7

القليل من التخصص: عندما تعرف الفصول المستهدفة مرجع القاموس الضعيف TKey القيمة، يمكنك إزالة دخولها من دعوة Finalyzer.

public class Entry<TKey>
{
    TKey key;
    Dictionary<TKey, WeakReference> weakDictionary;

    public Entry(Dictionary<TKey, WeakReference> weakDictionary, TKey key)
    {
        this.key = key;
        this.weakDictionary = weakDictionary;
    }

    ~Entry()
    {
        weakDictionary.Remove(key);
    }
}

عندما تكون الكائنات المخزنة مؤقتا هي فرعية من Entry<TKey>, ، لا فارغ WeakReference يطلق على التسريبات منذ Finalyzer بعد أن تم جمع مثالها للقمامة.