Можно ли создать на С# действительно словарь со слабыми ключами?

Я пытаюсь вычленить детали настоящего WeakKeyedDictionary<,> для C#... но у меня возникают трудности.

Я понимаю, что это нетривиальная задача, но кажущаяся невозможность объявить WeakKeyedKeyValuePair<,> (где сборщик мусора следует за ссылкой на значение только в том случае, если ключ достижим) делает ее, по-видимому, невозможной.

Я вижу две основные проблемы:

  1. Каждая реализация, которую я до сих пор видел, не обрезает значения после того, как ключи собраны. Подумайте об этом - одна из основных причин использования такого Словаря состоит в том, чтобы предотвратить хранение этих значений (не только ключей!), Поскольку они недоступны, но здесь на них указывают сильные ссылки.

    Да, достаточно добавить/удалить из словаря, и они в конечном итоге будут заменены, но что, если вы этого не сделаете?

  2. Без гипотетического WeakKeyedKeyValuePair<,> (или другого средства указания сборщику мусора помечать значение только в том случае, если ключ достижим) любое значение, которое ссылается на его ключ, никогда не будет собрано. Это проблема при хранении произвольных значений.

Проблема 1 может быть решена довольно неидеальным/хакерским способом: используйте уведомления GC, чтобы дождаться завершения полного GC, а затем продолжить и обрезать словарь в другом потоке. С этим я наполовину согласен.

Но проблема 2 поставила меня в тупик. Я понимаю, что этому легко противостоять, поэтому не делайте этого, но мне интересно, возможно ли решить эту проблему?


person Mania    schedule 09.12.2011    source источник


Ответы (1)


Взгляните на класс ConditionalWeakTable‹TKey, TValue›.

Позволяет компиляторам динамически присоединять поля объектов к управляемым объектам.

По сути, это словарь, в котором и ключ, и значение являются WeakReference, и значение сохраняется до тех пор, пока жив ключ.

Примечание! Этот класс не использует GetHashCode и Equals для сравнения на равенство, он использует ReferenceEquals.

person dtb    schedule 09.12.2011
comment
Хорошая находка, самая интригующая! Как это реализовано интересно? Не зная этого, возникает проблема, возможно ли создать действительно WeakValuedDictionary‹,›. Я покопаюсь в отражателе и посмотрю, смогу ли я понять это... - person Mania; 09.12.2011
comment
Какой позор, похоже, что это зависит от внутреннего .NET-магического DependentHandle для его реализации. Кроме того, он игнорирует .GetHashCode и .Equals, что делает его в лучшем случае нестандартным словарем :(. Кроме того, без доступа к DependentHandle проблема теперь перешел к определению WeakValuedDictionary‹,›. Я полагаю, что это может быть настолько близко, насколько мы можем получить.. - person Mania; 09.12.2011
comment
@Mania DependentHandle — это реализация CLR эфемеронов, которую невозможно реализовать без сотрудничества с GC. Это должно было быть обнародовано, как GCHandle. Если вы не возражаете против трюков с отражением, вы можете превратить статические методы CLR в делегаты и реализовать свои собственные DependentHandle и WeakValuedDictionary. Будьте осторожны при изучении справочного источника .NET (который является общедоступным) или используйте какой-нибудь декомпилятор, потому что он имеет сложные условия гонки. - person Zarat; 09.04.2012
comment
@Zarat: Если кто-то хочет создать единую связь жизненной зависимости между двумя объектами X и Y (такую, что ссылка будет рассматриваться как сильная ссылка на X только до тех пор, пока существует сильная ссылка на Y), существует ли лучший способ сделать это, чем создание отдельного элемента ConditionalWeakTable? - person supercat; 09.07.2012
comment
@supercat: Да, это в основном то, что делают эфемероны и DependentHandle, просто создайте экземпляр с X и Y в качестве параметров, однако, является ли это «хорошим» способом, зависит от вашего мнения об отражении в реализации .NET. (Конечно, это не разрешено в частично доверенных приложениях.) - person Zarat; 21.07.2012
comment
@Zarat: Вы говорите, что DependentHandle является собственной реализацией эфемерона, доверенный код может повысить эффективность за счет его использования, но ненадежный код должен просто создать ConditionalWeakTable с одним или двумя элементами в нем (желаемая связь, а также, возможно, связь из восходящая сторона самой желаемой таблицы компоновки)? Кроме того, мне было любопытно, что гарантируется в отношении относительного поведения объектов ConditionalWeakTable и fReachable? Будут ли объекты, достижимые (но не сильно достижимые) на одной стороне ConditionalWeakTable, такими же и на другой? - person supercat; 23.07.2012
comment
@supercat: Да, это то, что я имел в виду. Не уверен, что вы имеете в виду под «fReachable», для меня эфемероны - это просто способ сообщить сборщику мусора, что объект условно достижим: ЕСЛИ A (сильно) достижим, ТО B также должен быть помечен (сильно) достижим. [Надеюсь, я не ошибся, я давно не смотрел на этот материал.] - person Zarat; 25.07.2012
comment
@Zarat: объект доступен, если на него не существует сильно укоренившихся ссылок, но он либо имеет зарегистрированный финализатор, либо доступен из объекта с зарегистрированным финализатором. Если объект является freachable, то в следующем цикле GC он не будет допущен к сбору, но если у него есть финализатор, он будет помещен в очередь freachable, которая представляет собой сильно укоренившийся список объектов, финализаторы которых должны запускаться в самое раннее удобство. Один из конструкторов для WeakReference содержит параметр bool, который указывает, следует ли сделать WeakReference недействительным, когда... - person supercat; 25.07.2012
comment
... его цель становится доступной или только тогда, когда ее цель перестает существовать. Как правило, когда объект становится доступным, следует стремиться заменить его, а не использовать повторно, поэтому желательно, чтобы WeakReference в этот момент стал недействительным. С другой стороны, могут возникнуть ситуации, когда необходимо ускорить очистку доступного для доступа объекта (например, если требуется создать новый объект, используя тот же аппаратный ресурс). Для этого можно было бы использовать длинный WeakReference. Было бы интересно узнать, какое поведение поддерживают эфемероны. - person supercat; 25.07.2012
comment
@supercat: А, понятно, просто не знал об этом термине «доступный». Беглый тест показывает, что DependentHandle и ConditionalWeakTable реализованы в виде длинных слабых ссылок, они не сбрасываются при первом проходе сбора. (Мой тест: воскресить объект из финализатора, он по-прежнему доступен в ConditionalWeakTable и длинных слабых ссылках, но короткая слабая ссылка была очищена.) - person Zarat; 26.07.2012
comment
@Zarat: Какой объект вы воскрешали - «исходную» или «целевую» сторону ссылки? Кроме того, какая ссылка существовала на сам ConditionalWeakTable? Крайние случаи, которые меня интересуют, это то, что произойдет, если таблица Tab содержит ссылки с A на Tab и с B на C (и других ссылок на таблицу нет). Если A становится недоступным, но B сильно достижимым, каков статус C? Если WeakReference становится недоступным, его цель будет признана недействительной независимо от того, длинная это ссылка или короткая, но я не знаю о CWT. - person supercat; 26.07.2012
comment
@Zarat: Кстати, одна вещь, которую я хотел бы видеть в качестве класса фреймворка, была бы InternTable<T>IEqualityComparer<T> в качестве параметра построения). Учитывая экземпляр T, определите, содержит ли уже таблица запись, которая будет сравниваться равной. Если да, сравните этот экземпляр; в противном случае сохраните предоставленный экземпляр в таблице и верните его. Такая таблица, если она реализована правильно, могла бы значительно улучшить производительность вложенных неизменяемых типов, где хеш-коды могут довольно надежно различать неравные экземпляры, но где сравнение одинаковых экземпляров обходится дорого. - person supercat; 26.07.2012
comment
@Zarat: использование InternTable<T> гарантирует, что ссылки на экземпляры с одинаковым содержимым будут заменены ссылками на те же экземпляры. Если кто-то хочет выполнить много сравнений таких вещей, как деревья и поддеревья, которые построены отдельно, но будут иметь много равных частей, такие замены могут привести к значительному повышению эффективности. Обратите внимание, что нет смысла сохранять объект интернированным после того, как все другие ссылки исчезли, даже если существуют эквивалентные объекты. - person supercat; 26.07.2012
comment
@supercat: (1) Я воскресил ключ. (2) Доступность таблицы не имеет значения, за исключением случаев, когда она завершается, она очищается, в противном случае она просто действует как список. (3) Слабая ссылка очищается, когда она становится доступной, потому что запущен ее финализатор. Здесь финализатор находится на столе, поэтому он не влияет на эфемероны, пока таблица не будет собрана и очищена. (4) InternTable, вероятно, можно реализовать с помощью CWT, но более эффективно, если вы напрямую используете отражение и эфемероны. - person Zarat; 03.08.2012
comment
@supercat: Думаю, мы немного отклонились от темы :) Если вы хотите продолжить обсуждение, вы можете сделать это по почте или в моем блоге. я опубликовал свой трюк с отражением в повторно реализовать DependentHandle и новый класс Ephemeron, аналог того, что WeakReference представляет собой GCHandle. - person Zarat; 03.08.2012
comment
Некоторое время назад я разместил вопрос о стажерской таблице по адресу stackoverflow.com/questions/10923682/, поэтому, если вы хотите обсудить что-либо там, я хотел бы получить больше мыслей по этому вопросу. Я думаю, что коллекция со слабым интернированием может значительно повысить ценность многих неизменяемых типов. Например, сравнение двух деревьев, содержащих одни и те же элементы, но построенных отдельно, занимает время O(n) каждый раз, когда они сравниваются. Однако, если деревья реализуют хорошую функцию GetHashCode(), и если код, который строит деревья, интернирует их... - person supercat; 03.08.2012
comment
... (включая поддеревья), тогда время для сравнения будет O(1) [поскольку каждое дерево будет содержать не только идентичные поддеревья, но и одинаковые поддеревья]. Однако я не уверен, каким будет наиболее эффективный способ создания класса WeakInterning, и поэтому буду рад вашим мыслям в другом посте. - person supercat; 03.08.2012
comment
Может быть, мы могли бы поговорить о таких вещах? - person supercat; 03.08.2012
comment
Я с интересом слежу за этой дискуссией. Я предлагаю вам продолжить обсуждение где-нибудь в другом месте и опубликовать вопрос с ответом на ваш вопрос с вашими выводами. Пожалуйста, дайте ссылку здесь, чтобы я мог продолжить следить за этой темой. Спасибо! - person dtb; 03.08.2012
comment
Если сравнение удостоверений нельзя использовать, то ConditionalWeakTable не подходит. В этом случае я бы предложил нашу реализацию WeakTable.cs и наше описание в блог WeakTable. - person Vladimir Nesterovsky; 09.01.2014
comment
@VladimirNesterovsky Я проверил ваш код, и вы получаете доступ к параллельному словарю в финализаторе. Это подвергает вас редкому состоянию гонки, которое может привести к взаимоблокировке. - person Paya; 19.03.2015
comment
@Paya, я не уверен, что ты прав в своих рассуждениях. Финализатор вызывается внутри выделенного потока (иногда его называют FinalizerWorker). Этот поток ничем не отличается от любого другого потока и не препятствует развитию любого другого потока. Я предполагаю, что вы перепутали поток FinalizerWorker с потоком сборщика мусора, который останавливает все остальные потоки. Если бы можно было что-то заблокировать в потоке GC, это могло бы привести к тупиковой блокировке. - person Vladimir Nesterovsky; 21.03.2015
comment
@VladimirNesterovsky Если вы посмотрите на ConcurrentDictionary.TryRemove, вы увидите, что он использует lock. Допустим, у вас есть только один поток в вашем приложении, и вы пытаетесь удалить что-то из WeakTable. Сборщик мусора срабатывает, пока вы находитесь внутри блокировки TryRemove. В вашем деструкторе вы блокируете эту блокировку, и, поскольку ваш основной поток приостановлен, он никогда не разблокируется и не заблокируется навсегда. - person Paya; 21.03.2015
comment
@Paya Я хочу сказать, что FinalizerWorker и GC - это два разных потока. Ничего не останавливается и не блокируется во время работы FinalizerWorker. FinalizerWorker — это поток, в котором все Finalizers ставятся в очередь для выполнения потоком GC. Напротив, GC руководитель может решить остановить мир, чтобы отследить граф объектов для коллекции. - person Vladimir Nesterovsky; 21.03.2015
comment
@VladimirNesterovsky Кажется, вы правы, хотя в Интернете полно людей, кричащих никогда не lock в финализаторе. Я думаю, вы не можете заблокировать что-либо, чтобы вызвать взаимоблокировку потока GC (не потока финализатора), не так ли? - person Paya; 21.03.2015
comment
@Paya Я так понимаю. Поток GC реализуется средой выполнения, и в его контексте не запускается пользовательский код. На самом деле вполне возможно, что выделенного потока GC вообще не существует, так как среда выполнения может заглянуть к любому и остановить всех остальных. - person Vladimir Nesterovsky; 21.03.2015
comment
@VladimirNesterovsky Мне кажется, я обнаружил еще одно состояние гонки - пожалуйста, дайте мне знать, что вы думаете: я вызываю Remove("asdf") в потоке 1, и поток попадает непосредственно перед строкой states.Remove(state.key);, где он участвует в гонке потоком 2, который вызывает GetOrAdd("asdf"). Поскольку поток 1 еще не удалил ключ из ConditionalWeakTable, а поток 2 попытается связать другой объект с тем же ключом, используя ConditionalWeakTable, вы получите исключение. - person Paya; 21.03.2015
comment
@Paya, состояние гонки - это не зло, единственная проблема - сохранить инварианты. Когда поток 1 попадает в строку state.Remove(state.key) state.initialized == 2 (припаркован). Поток 2 в GetOrAdd либо а) найдет и вернет старое значение; б) вернуть новое значение. Если новое состояние не инициализировано (state.initialized == 0), то оно помечается как инициализированное (state.initialized == 1) и добавляется к состояниям. Если наблюдается, что состояние было припарковано (state.initialized == 2) после States.Add(key, state), то состояние удаляется из состояний. В вашем случае GetOrAdd вернет старое значение. - person Vladimir Nesterovsky; 21.03.2015
comment
Давайте продолжим обсуждение в чате. - person Vladimir Nesterovsky; 22.03.2015