Уплотнение словаря WeakReference

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

Таким образом, я создал метод фабрики 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;
}

Кэш реализован как Словарь , на основе Здания @JaredPar Хеш-таблица WeakReference:

class WeakDictionary where TValue : class {
    private readonly Dictionary items;
    public WeakDictionary() {
        this.items = new Dictionary();
    }
    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. Цель.


Мой вопрос: что лучшая стратегия состоит в том, чтобы уплотнить Словарь WeakReference?

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

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

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

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

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

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

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

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

16
задан Community 23 May 2017 в 12:34
поделиться

3 ответа

Ваш вариант 3 (нить) обладает большим недостатком изготовления синхронизации, необходимых на всех действиях поставок / TRYGGETVALUE. Если вы используете это, ваш интервал не находится в миллисекундах, но каждый N Tryget действий.

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

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

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

имеет такую ​​стратегию [N амортизированной] существуют?

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

5
ответ дан 30 November 2019 в 21:46
поделиться

Если вы хотите исправить это Джеймс определенно имеет правильный ответ, но в случае, если вы хотите просто отключить предупреждения об устаревании, вы можете запустить python так:

$ python -Wignore::DeprecationWarning 
Python 2.6.2 (r262:71600, Sep 20 2009, 20:47:22) 
[GCC 4.2.1 (Apple Inc. build 5646)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import sets
>>> 

(От: http://puzzling.org/logs/thoughts/2009/May/3/python26-deprecation-warning )

Вы также можете игнорировать его программно:

import warnings
warnings.simplefilter("ignore", DeprecationWarning)
-121--1439064-

Смотрите R-FAQ :

Два проекта используют PHP для предоставления веб-интерфейса R. R _ PHP _ Online по Стиву R-php активно разрабатывается Альфредо Понтильо и Анджело Минео и обеспечивает как веб-интерфейс для R, так и набор предварительно определенных анализов, которые не требуют ввода R-кода.

и эта статья: Использование R через PHP в учебных целях: R-php

-121--2789799-

Вы можете удалить «недопустимый» 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));
}

[Edit]

В соответствии с windbg, один экземпляр WeakReference занимает 16 байт. Для 100 000 собранных объектов это не было бы таким серьезным бременем, поэтому можно было бы легко дать им жить.

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

1
ответ дан 30 November 2019 в 21:46
поделиться

У меня была такая же проблема, и я решил ее следующим образом (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>();
}

Эти два класса пытаются добиться того, чтобы «зацепить» сборщик мусора. Вы активируете этот механизм, создавая экземпляр WeakDictionaryCleaner во время создания слабой коллекции:

new WeakDictionaryCleaner(weakDictionary);

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

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

3
ответ дан 30 November 2019 в 21:46
поделиться
Другие вопросы по тегам:

Похожие вопросы: