Възможно ли е да се създаде наистина слаб ключов речник в C#?

Опитвам се да изясня подробностите за истински WeakKeyedDictionary<,> за C#... но срещам трудности.

Осъзнавам, че това е нетривиална задача, но привидната невъзможност да се декларира WeakKeyedKeyValuePair<,> (където GC следва препратката към стойност само ако ключът е достъпен) я прави привидно невъзможна.

Има два основни проблема, които виждам:

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

    Да, добавете/премахнете достатъчно от речника и те в крайна сметка ще бъдат заменени, но какво ще стане, ако не го направите?

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

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

Но проблем 2 ме озадачи. Осъзнавам, че на това лесно се противодейства с, така че не го правете, но това ме кара да се чудя - възможно ли е изобщо да се реши този проблем?


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


Отговори (1)


Разгледайте ConditionalWeakTable‹TKey, TValue› Class.

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

По същество това е речник, където и ключът, и стойността са WeakReference и стойността се поддържа жива, докато ключът е активен.

Забележка! Този клас не използва GetHashCode и Equals за извършване на сравнения на равенство, той използва ReferenceEquals.

person dtb    schedule 09.12.2011
comment
Хубава находка, много интригуващо! Чудя се как се реализира? Без да знаем това, проблемът става дали е възможно да се създаде наистина WeakValuedDictionary‹,›. Ще се разровя до рефлектора и ще видя дали мога да го разбера... - person Mania; 09.12.2011
comment
Какъв срам, изглежда, че зависи от вътрешен .NET-magic 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: Да, това е основно това, което правят ephemerons и DependentHandle, просто създайте екземпляр с X и Y като параметри, но дали това е „хубав“ начин зависи от вашето мнение за отражение в .NET имплементацията. (Разбира се, това не е разрешено в частично надеждни приложения.) - person Zarat; 21.07.2012
comment
@Zarat: Искаш да кажеш, че DependentHandle е родната имплементация на ефемерон, надеждният код може да спечели ефективност, като използва това, но ненадеждният код трябва просто да създаде ConditionalWeakTable с един или два елемента в него (желаната връзка плюс евентуално връзка от горната страна на самата желана таблица за свързване)? Освен това бях любопитен какво е гарантирано по отношение на относителното поведение на обектите ConditionalWeakTable и fReachable? Ще бъдат ли обекти, които могат да се изтрият (но не са много достъпни) от едната страна на ConditionalWeakTable, по същия начин и от другата? - person supercat; 23.07.2012
comment
@supercat: Да това имах предвид. Не съм сигурен какво имате предвид с „fReachable“, за мен ефемероните са просто начин да кажа на GC, че даден обект е условно достижим: АКО A е (силно) достижим, ТОГАВА B също трябва да бъде маркиран (силно) достижим. [Надявам се, че не съм се объркал, отдавна не гледах тези неща.] - person Zarat; 25.07.2012
comment
@Zarat: Един обект е freachable, ако не съществуват силно вкоренени препратки към него, но той или има регистриран финализатор, или е достъпен от обект с регистриран финализатор. Ако даден обект е freachable, тогава в следващия GC цикъл той няма да отговаря на условията за събиране, но ако има финализатор, той ще бъде поставен в freachable опашката, която е силно вкоренен списък от обекти, чиито финализатори трябва да се изпълняват на най-ранно удобство. Един от конструкторите за WeakReference съдържа параметър bool, който показва дали WeakReference трябва да бъде анулиран, когато... - person supercat; 25.07.2012
comment
...целта му става изчезваща или само когато целта му престане да съществува. Като цяло, след като обект стане невалиден, човек трябва да се стреми да го замени, вместо да го използва повторно, така че WeakReference да стане невалиден в този момент е желателно. От друга страна, могат да възникнат ситуации, при които човек трябва да ускори почистването на обект, който може да бъде разрушен (напр. защото желае да създаде нов обект, използвайки същия хардуерен ресурс). За това може да се използва дълго WeakReference. Би било интересно да се знае кои поведения поддържат ефемероните. - person supercat; 25.07.2012
comment
@supercat: А, разбирам, просто не знаех това под термина „freachable“. Бърз тест показва, че 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 Не съм сигурен, че си прав в разсъжденията си. Finalizer се нарича вътре в специална нишка (понякога се нарича FinalizerWorker). Тази нишка не се различава от която и да е друга нишка и не пречи на никоя друга нишка да напредва. Предполагам, че сте объркали нишката FinalizerWorker с нишката Garbage Collector, която спира всички останали нишки. Ако някой би могъл да заключи нещо в нишката на GC, това може да доведе до мъртво заключване. - person Vladimir Nesterovsky; 21.03.2015
comment
@VladimirNesterovsky Ако погледнете ConcurrentDictionary.TryRemove, ще видите, че използва lock. Да приемем, че имате само една нишка в приложението си и се опитвате да премахнете нещо от WeakTable. GC се включва, докато сте вътре в тази TryRemove ключалка. Във вашия деструктор вие блокирате тази ключалка и тъй като основната ви нишка е спряна, тя никога няма да се отключи и блокира завинаги. - person Paya; 21.03.2015
comment
@Paya, моята гледна точка е, че FinilizerWorker и GC са две различни нишки. Нищо не се спира или блокира, докато FinilizerWorker работи. FinilizerWorker е нишка, в която всички финализатори са поставени на опашка за изпълнение от GC нишка. За разлика от това GC thead може да реши да спре света, за да проследи графика на обекти за колекцията. - 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 стигне до реда states.Remove(state.key) състоянието.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