Сжатие словаря слабых ссылок - PullRequest
16 голосов
/ 12 января 2010

У меня есть класс Foo со свойством Id . Моя цель состоит в том, чтобы не было двух экземпляров Foo с одинаковым Id одновременно.

Итак, я создал фабричный метод CreateFoo , который использует кэш для возврата того же экземпляра для того же Id .

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

Кэш реализован в виде словаря , основанного на @ JaredPar * Построении хэш-таблицы WeakReference :

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

Проблема в том, что WeakReferences остаются в словаре после сбора мусора. Это подразумевает необходимость некоторой стратегии, как вручную «собрать мусор» мертвых WeakReferences, как объяснено @ Pascal Cuoq в Что происходит с WeakReference после GC WeakReference.Target .


Мой вопрос: Какова наилучшая стратегия сжатия словаря WeakReference?

Опции, которые я вижу:

  1. Не удаляйте WeakReferences из словаря. IMO, это плохо, потому что кэш используется в течение всего времени жизни моего приложения, и много мертвых WeakReferences со временем накапливается.

  2. Пройдите по всему словарю на каждом Поставьте и TryGetValue и удалите мертвые WeakReferences. Это несколько противоречит цели словаря, потому что обе операции становятся O (n) .

  3. Периодически проходить весь словарь в фоновом потоке. Какой будет хороший интервал, учитывая, что я не знаю шаблон использования CreateFoo ?

  4. Добавить каждую вставленную KeyValuePair в двусторонний связанный список. Каждый вызов Put и TryGetValue проверяет заголовок списка. Если WeakReference жив, переместите пару в конец списка. Если он мертв, удалите пару из списка и WeakReference из словаря.

  5. Реализация пользовательской хеш-таблицы с небольшим отличием, что, когда корзина заполнена, мертвые WeakReferences сначала удаляются из корзины, а затем продолжают обычную работу.

Есть ли другие стратегии?

Лучшей стратегией, вероятно, является алгоритм с амортизированной временной сложностью. Существует ли такая стратегия?

Ответы [ 7 ]

10 голосов
/ 31 августа 2011

Если вы можете переключить управляемый объект как ключ словаря, то вы можете использовать ConditionalWeakTable в .Net 4.0 (пространство имен System.Runtime.CompilerServices).

По словам г-на Рихтера, ConditionalWeakTable уведомляется о сборе объектов сборщиком мусора, а не с помощью потока опроса.

    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 и ключ ConditionalWeakTable. Ключ ConditionalWeakTable не считается. Поэтому, когда мы удаляем все элементы из tabControl, эти TabItems можно собирать мусором (поскольку ничто больше не ссылается на них, опять же ключ ConditionalWeakTable не учитывается). Когда они собирают мусор, ConditionalWeakTable уведомляется, и запись с этим значением ключа удаляется. Поэтому мои громоздкие объекты TIDExec также собираются в этот момент сборщиком мусора (на них ничего не ссылается, кроме значения ConditionalWeakTable).

5 голосов
/ 12 января 2010

Ваш вариант 3 (поток) имеет большой недостаток, заключающийся в необходимости синхронизации для всех действий Put / TryGetvalue. Если вы используете это, ваш интервал будет не в миллисекундах, а через каждое действие N TryGet.

Вариант 2, сканирование словаря, может повлечь за собой серьезные накладные расходы. Вы можете улучшить, только просканировав 1 на 1000 действий и / или наблюдая, как часто запускается сборщик мусора.

Но я бы серьезно рассмотрел вариант 1: ничего не делать. У вас может быть «много» мертвых записей, но, с другой стороны, они довольно маленькие (и перерабатываются). Вероятно, не вариант для серверного приложения, но для клиентского приложения я бы попытался определить, сколько записей (кБайт) в час мы говорим.

После некоторого обсуждения:

Есть ли такая [n амортизированная] стратегия? есть

Я бы догадался, нет. Ваша проблема - миниатюрная версия GC. Вам придется сканировать все это время от времени. Так что только варианты 2) и 3) дают реальное решение. И оба они дороги, но их можно (сильно) оптимизировать с помощью некоторой эвристики. Вариант 2) все равно даст вам случайный наихудший случай.

4 голосов
/ 12 июня 2012

Подход №5 интересен, но имеет недостаток в том, что может быть трудно узнать, каков реальный уровень использования хеш-таблицы и, следовательно, когда хеш-таблицу следует расширить. Эта трудность может быть преодолена, если всякий раз, когда «кажется», что хеш-таблица должна быть расширена, сначала выполняется сканирование всей таблицы, чтобы удалить мертвые записи. Если более половины записей в таблице были мертвыми, не беспокойтесь о расширении. Такой подход должен привести к амортизированному поведению O (1), так как никто не будет выполнять сканирование всей таблицы, пока не добавит столько записей, сколько было удалено.

Более простой подход, который также давал бы O (1) амортизированное время и O (1) пространство на недавно использованный элемент, состоял бы в том, чтобы вести подсчет количества элементов, которые были живы после последней очистки таблицы, и сколько элементов было добавлено с тех пор. Всякий раз, когда последнее число превышает первое, выполните сканирование и очистку всей таблицы. Время, необходимое для сканирования и продувки, будет пропорционально количеству элементов, добавленных между продувками, таким образом, сохраняется время амортизации O (1), а общее количество элементов в сборе не будет превышать вдвое количество недавно наблюдавшихся элементов. чтобы быть живым, поэтому количество мертвых элементов не может превышать вдвое количество недавно живых элементов.

3 голосов
/ 09 марта 2010

У меня была такая же проблема, и я решил ее следующим образом (WeakDictionary - класс, который я пытался очистить):

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. Этот механизм активируется путем создания экземпляра WeakDictionaryCleaner во время создания слабой коллекции:

new WeakDictionaryCleaner(weakDictionary);

Обратите внимание, что я не создаю никаких ссылок на новый экземпляр, так что GC будет распоряжаться им во время следующего цикла. В методе ClearGcedEntries () я снова создаю новый экземпляр, так что каждый цикл GC будет иметь очиститель для завершения, который, в свою очередь, будет выполнять сжатие коллекции. Вы можете сделать CleanerRef.Dictionary также слабой ссылкой, чтобы он не содержал словарь в памяти.

Надеюсь, это поможет

2 голосов
/ 27 мая 2013

Полагаю, это правильное место, хотя это может выглядеть как некромантия. На всякий случай, если кто-то наткнется на этот вопрос, как я. Отсутствие выделенной Identity Map в .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;
    }
}
1 голос
/ 12 января 2010

Вы можете удалить «недействительный» WeakReference внутри TryGetValue:

[Edit] Моя ошибка, эти решения на самом деле не делают ничего, кроме того, что вы предложили, так как метод 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 байтов. Для 100 000 собранных предметов это не будет таким серьезным бременем, так что вы можете легко позволить им жить.

Если это серверное приложение, и вы полагаете, что вы могли бы выиграть от сбора, я бы подумал о переходе на фоновый поток, а также о реализации простого алгоритма для увеличения времени ожидания всякий раз, когда вы собираете относительно небольшое число объектов.

0 голосов
/ 19 декабря 2018

Небольшая специализация: когда целевые классы знают слабую ссылку на словарь и ее значение TKey, вы можете удалить его запись из вызова финализатора.

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 утечек, поскольку финализатор вызывается после того, как его экземпляр был собран сборщиком мусора.

...