Всем привет.
Подскажите — как можно оптимизировать следующий код?
Класс предоставляет локи для синхронизации операций в других Concurrent-коллекциях. Например, в ConcurrentDictionary для методов с отложенной инициализации AddOrUpdate и GetOrAdd.
Задача — получить объект блокировки (который SyncRoot) для определенного ключа (чтобы не блокировать всю коллекцию). Если больше никто эту блокировку не использует — убрать из коллекции. Идеально было бы вовсе отдать работу по подсчёту ссылок GC.
public sealed class ConcurrentLockProvider<TKey>
{
private readonly Dictionary<TKey, Lock> _locks;
public ConcurrentLockProvider()
: this(EqualityComparer<TKey>.Default)
{
}
public ConcurrentLockProvider(IEqualityComparer<TKey> comparer)
{
_locks = new Dictionary<TKey, Lock>(comparer);
}
public IDisposable Acquire(TKey key)
{
lock(_locks)
{
Lock item;
if(!_locks.TryGetValue(key, out item))
{
item = new Lock(key, _locks);
_locks[key] = item;
}
Interlocked.Increment(ref item.Counter);
return item;
}
}
private sealed class Lock : IDisposable
{
private readonly TKey _key;
private readonly Dictionary<TKey, Lock> _dic;
public long Counter;
public Lock(TKey key, Dictionary<TKey, Lock> locks)
{
_key = key;
_dic = locks;
}
#region Implementation of IDisposable
public void Dispose()
{
lock(_dic)
{
if(Interlocked.Decrement(ref Counter) < 1)
_dic.Remove(_key);
}
}
#endregion
}
}
Здравствуйте, LWhisper, Вы писали:
LW>Если больше никто эту блокировку не использует — убрать из коллекции. Идеально было бы вовсе отдать работу по подсчёту ссылок GC.
Используйте вместо Dictionary<TKey, Lock> System.Runtime.CompilerServices.ConditionalWeakTable<TKey, Lock>
Re[2]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, vorona, Вы писали:
V>Используйте вместо Dictionary<TKey, Lock> System.Runtime.CompilerServices.ConditionalWeakTable<TKey, Lock>
Замечательное решение, но увы — не подходит, так как сравнивает объекты по ссылкам, а в моём случае проверка должна выполняться средствами IEqualityComparer. :c
Re: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, LWhisper, Вы писали:
LW>Класс предоставляет локи для синхронизации операций в других Concurrent-коллекциях. Например, в ConcurrentDictionary для методов с отложенной инициализации AddOrUpdate и GetOrAdd.
Ускользает мысль, зачем в ConcurrentDictionary синхронизировать операции, да еще и блокирующим образом? Он же Concurrent!
Re[2]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, samius, Вы писали:
S>Ускользает мысль, зачем в ConcurrentDictionary синхронизировать операции, да еще и блокирующим образом? Он же Concurrent!
В ConcurrentDictionary есть методы GetOrAdd и AddOrUpdate, которые принимают функции, возвращающие значения, которые необходимо добавить в словарь, если их там ещё нет.
Проблема в том, что вызов этих функций не синхронизирован. Одновременный вызов из 10 потоков 10 раз вызовет переданный делегат и создаст 10 объектов, но лишь один из них окажется в словаре. Поэтому таким образом нельзя создавать IDisposable объекты, так как для них никогда не будет вызван Dispose, да и просто создавать объекты, которые как-либо влияют на внутреннюю экосистему продукта или внешние ресурсы. Такие вот они Concurrent.
Re: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, LWhisper, Вы писали:
LW>Задача — получить объект блокировки (который SyncRoot) для определенного ключа (чтобы не блокировать всю коллекцию). Если больше никто эту блокировку не использует — убрать из коллекции. Идеально было бы вовсе отдать работу по подсчёту ссылок GC.
. Симптомы: вы где-то сделали ошибку в цепочке рассуждений, в итоге получили проблему которую нельзя решить простыми средствами и ваша попытка решения по факту только создаёт новые. Ну и в итоге вместо того, чтобы лечить первопричину, вы пытаетесь перекинуть проблемы на рантайм (подсчёт ссылок в GC, угу).
Начните с задачи, для которой вам потребовалась комбинация из ConcurrentDictionary и локов, дальше видно будет.
Re[3]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, LWhisper, Вы писали:
LW>Здравствуйте, samius, Вы писали:
S>>Ускользает мысль, зачем в ConcurrentDictionary синхронизировать операции, да еще и блокирующим образом? Он же Concurrent! LW>В ConcurrentDictionary есть методы GetOrAdd и AddOrUpdate, которые принимают функции, возвращающие значения, которые необходимо добавить в словарь, если их там ещё нет. LW>Проблема в том, что вызов этих функций не синхронизирован. Одновременный вызов из 10 потоков 10 раз вызовет переданный делегат и создаст 10 объектов, но лишь один из них окажется в словаре.
Т.е. проблема не в коллекции и синхронизировать надо не операции ConcurrentDictionary. LW>Поэтому таким образом нельзя создавать IDisposable объекты, так как для них никогда не будет вызван Dispose, да и просто создавать объекты, которые как-либо влияют на внутреннюю экосистему продукта или внешние ресурсы. Такие вот они Concurrent.
Никогда? Прямо никогда нельзя и никогда не будет вызыван Dispose? Я предлагаю трезво оценить вероятность вызова из 10и потоков метода GetOrAdd с одним ключем. Сколько тысячных процента?
Кроме как через Lazy<T> вашу задачу можно решить гораздо проще, не создавая динамически syncRoot-ы, а используюя таблицу однажды созданных. Хэш от ключа делите на длину таблицы, что бы выбрать syncRoot. Длину таблицы выбирать от вероятности коллизии с разными ключами.
Re[4]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, Sinix, Вы писали:
S>P.S. В CodeJam кстати этот момент тоже не поправлен.
А это вот фик знает, что важнее — изредка, на коллизии словить повторный вызов конструктора значения, или на каждое создание генерить инстанс Lazy<T>. Можно, конечно, добавить в фабрику третью реализацию, но не замусорит ли это публичный API — вопрос.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, samius, Вы писали:
S>Я предлагаю трезво оценить вероятность вызова из 10и потоков метода GetOrAdd с одним ключем. Сколько тысячных процента?
Это зависит от количества коллизий, когда одновременно столкнутся два потока с запросом к одному ключу и цикл CompareExchange прокрутится больше одного раза. В общем случае такое оценить практически невозможно.
S>Кроме как через Lazy<T> вашу задачу можно решить гораздо проще, не создавая динамически syncRoot-ы, а используюя таблицу однажды созданных.
+1
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>А это вот фик знает, что важнее — изредка, на коллизии словить повторный вызов конструктора значения, или на каждое создание генерить инстанс Lazy<T>.
Ага. Но нам ничего не мешает вообще отдельную коллекцию сделать и в фабрику её не выставлять. Тем более что основной сценарий очень специфический, словарь для кэша всяких вещей, которые гарантированно не устареют за время жизни процесса / долгоживущего сервиса.
Для всего остального смысл, имхо, теряется. Обычного ConcurrentDictionary хватит.
Re[6]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, Sinix, Вы писали:
S>Ага. Но нам ничего не мешает вообще отдельную коллекцию сделать и в фабрику её не выставлять.
Это еще хуже, потому что неконсистентно. Лучше уж как в самом Lazy — три варианта. Можно даже штатный LazyThreadSafetyMode использовать вместо своего енума.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
S>>Я предлагаю трезво оценить вероятность вызова из 10и потоков метода GetOrAdd с одним ключем. Сколько тысячных процента?
AVK>Это зависит от количества коллизий, когда одновременно столкнутся два потока с запросом к одному ключу и цикл CompareExchange прокрутится больше одного раза. В общем случае такое оценить практически невозможно.
А в общем и не надо.
Re[4]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, mDmitriy, Вы писали:
D>не факт, что с Lazy сработает всегда и объект будет создан только один...
Факт вообще-то, смотрим на LazyThreadSafetyMode.
D>мне вот пришлось городить что-то типа ConcurrentDictionary<TKey, Lazy<Task<TValue>>>, и внутри перед созданием еще проверять TryGetValue
Ну так вы неправильно ConcurrentDictionary используете, документацию надо читать Доппроверка из TryGetValue вам никак не поможет.
Вообще, ошибки при попытке смочь в многопоточные коллекции — регулярное дело. Вот тут товарищ доказывает, что ConcurrentDictionary поломан, попробуйте найти баг в доказательстве:
class Program
{
static void DoTest()
{
var random = new Random();
var start = new ManualResetEvent(false);
var dict = new ConcurrentDictionary<string, int>();
var results = new int[100];
var threads = Enumerable.Range(0, 100).Select(i => new Thread(() =>
{
start.WaitOne(Timeout.Infinite, false);
lock (results) results[i] = dict.GetOrAdd("key", x => i);
}));
threads.ToList().ForEach(x => x.Start());
Thread.Sleep(100);
start.Set();
Thread.Sleep(100);
var uniqueValues = results.Distinct().Select(x => x.ToString());
Console.WriteLine("Unique values ({0}): {1}", uniqueValues.Count(), string.Join("/", uniqueValues));
}
static void Main(string[] args)
{
while (!Console.KeyAvailable)
{
DoTest();
}
Console.ReadKey();
}
}
Each time you see two values, it means that 2 threads received a different value for "key".
D>потому что просто Lazy пробивало на дубликаты при многопоточном обращении
Эва как! А можно пруф? Для текущего кода такое возможно или при косяке где-то в equality comparer, или при серьёзом баге в кишках ConcurrentDictionary. Такое однозначно надо воспроизводить и репортить.
Re[6]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, Sinix, Вы писали: D>>не факт, что с Lazy сработает всегда и объект будет создан только один... S>Факт вообще-то, смотрим на LazyThreadSafetyMode.
используется, естественно
D>>мне вот пришлось городить что-то типа ConcurrentDictionary<TKey, Lazy<Task<TValue>>>, и внутри перед созданием еще проверять TryGetValue S>Ну так вы неправильно ConcurrentDictionary используете, документацию надо читать Доппроверка из TryGetValue вам никак не поможет.
возможно, но на каком-то этапе разработки сработала, убирать не стал пока
S>Вообще, ошибки при попытке смочь в многопоточные коллекции — регулярное дело. Вот тут товарищ доказывает, что ConcurrentDictionary поломан, попробуйте найти баг в доказательстве:
чуть позже гляну
D>>потому что просто Lazy пробивало на дубликаты при многопоточном обращении S>Эва как! А можно пруф? Для текущего кода такое возможно или при косяке где-то в equality comparer, или при серьёзом баге в кишках ConcurrentDictionary. Такое однозначно надо воспроизводить и репортить.
за текущий код не скажу, я в собственном наблюдал
компарер самописный был, да
и он точно глючил, потому что в результате мне пришлось везде прийти к простым строковым ключам
почему глючил — непонятно, там всего-то 2 метода реализовать
Re[3]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, LWhisper, Вы писали:
LW> Поэтому таким образом нельзя создавать IDisposable объекты, так как для них никогда не будет вызван Dispose,
Это с чего вдруг?
LW>да и просто создавать объекты, которые как-либо влияют на внутреннюю экосистему продукта или внешние ресурсы. Такие вот они Concurrent.
Значит проектировать надо соотв. образом. Т.е. влиять на среду, если убедился, что сущ. в ед. экземпляре.
Кодом людям нужно помогать!
Re[4]: Неблокирующая коллекция локов с функцией самоочистки
Здравствуйте, samius, Вы писали:
S>Никогда? Прямо никогда нельзя и никогда не будет вызыван Dispose? Я предлагаю трезво оценить вероятность вызова из 10и потоков метода GetOrAdd с одним ключем. Сколько тысячных процента?
Да, никогда. В моём случае вероятность — 100%. В остальных случаях, при использовании по назначению (то есть в многопоточной среде) на длительном отрезке времени она стремится к 100%.
S>Кроме как через Lazy<T> вашу задачу можно решить гораздо проще, не создавая динамически syncRoot-ы, а используюя таблицу однажды созданных. Хэш от ключа делите на длину таблицы, что бы выбрать syncRoot. Длину таблицы выбирать от вероятности коллизии с разными ключами.
Интересное решение. Насколько я понимаю, нечто подобное как раз используется в ConcurrentDictionary.
Re[2]: Неблокирующая коллекция локов с функцией самоочистки
. Симптомы: вы где-то сделали ошибку в цепочке рассуждений, в итоге получили проблему которую нельзя решить простыми средствами и ваша попытка решения по факту только создаёт новые. Ну и в итоге вместо того, чтобы лечить первопричину, вы пытаетесь перекинуть проблемы на рантайм (подсчёт ссылок в GC, угу).
S>Начните с задачи, для которой вам потребовалась комбинация из ConcurrentDictionary и локов, дальше видно будет.
Цепочка из нескольких кэшей, в процессе инициализации которых возможны задержки. Сейчас стреляет на общем локе на весь кэш. Думаю, спустя несколько версий, начнёт стрелять и на индивидуальных локах.