Чередование обновлений словаря .net в узком цикле

Question

Я работаю над приложением, которое выполняет обработку с тем, что я бы назвал довольно высокой пропускной способностью (текущие пики в диапазоне 400 Мбит / с, цель проекта - 10 Гбит / с).

Я запускаю несколько экземпляров цикла, который в основном просто циклически просматривает и обрабатывает информацию, и использует словарь для хранения состояния. Тем не менее, мне также нужно периодически сканировать весь словарь, чтобы проверить время ожидания, и я хотел бы получить некоторые идеи о том, что делать, если это сканирование становится горячей точкой производительности. По сути, я ищу, есть ли какие-либо стандартные методы чередования проверок времени ожидания в словаре с основным кодом обработки в цикле, так что, скажем, в цикле 1 я проверяю первый элемент словаря, цикл 2, второй, и т. д. Кроме того, ключи словаря изменяются и будут удалены и добавлены в основной код обработки, так что это не так просто, как взять копию всех ключей словаря и затем проверить их одну за другой в основном цикле .

Повторюсь, это не проблема с текущей производительностью. Поэтому, пожалуйста, не комментируйте преждевременную оптимизацию, я понимаю, что это преждевременно, я сознательно делаю выбор, чтобы считать это потенциальной проблемой.

Редактировать для ясности : Мне любопытно, что я думаю об этом на выходных, и какой подход передовой практики может быть для чего-то подобного. Это не единственная проблема, которую я имею, и не единственная область производительности, на которую я смотрю. Тем не менее, это одна из областей, где мне не совсем понятен четкий и краткий подход к этому.

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

Какой-то псевдокод логики, если он помогает:

Dictionary hashdb;
while(true) {
  grab_record_from_buffer(); // There is a buffer in place, so some delays are tolerable
  process(record);  //do the main processing
  update_hashdb();  //Add,remove,update entries in the dictionary
  if(last_scan > 15 seconds)
    foreach(entry in hashdb)
      periodic_check(entry);  //check for timeouts or any other periodic checks on every db entry
}

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

Спасибо,

Answer 1

Можете ли вы использовать .NET 4.0 (или хотя бы планируете это сделать)? Если это так, ConcurrentDictionary может помочь вам - он позволяет перебирать словарь, в то же время изменяя его (либо в том же потоке, либо в другом).

Вы должны знать, что результаты могут быть удивительными - вы можете увидеть некоторые изменения, но не другие, например - но если это приемлемо, это может быть полезным подходом.

Затем можно было бы, чтобы один поток периодически проверял все остальные словари. Я знаю, что вы ранее исключали это из-за требований к синхронизации, но прелесть ConcurrentDictionary в том, что он не требует синхронизации ¹ . Изменит ли это возможность использования отдельного потока проверки?

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

---

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

С Стивен Тауб пост на ConcurrentDictionary:

Для модификации / записи в словарь, ConcurrentDictionary использует мелкозернистую блокировку для обеспечения потокобезопасность (читает в словаре выполняются без блокировки)

Другим большим уменьшением блокировки является упомянутая выше возможность: вы можете перебирать словарь в одном потоке, изменяя его в другом, при условии, что вы можете увидеть, что некоторые изменения были применены с момента создания итератора, но не другие. Сравните это с обычным Dictionary<,>, где для безопасного одновременного доступа вам придется блокировать словарь на все время его итерации.

Answer 2

Одной из идей здесь может быть добавление уровня косвенности (какой-то объект прокси / оболочки). Это позволит вам обновить объекты и удалить объекты (установив для него значение null) без прерывания итераторов (хотя Add все еще остается проблемой).

Очевидно, что вы захотите добавить случайное «правильное» удаление, которое распространяется на null, но это может очень хорошо работать с ReaderWriterLockSlim - поскольку «get», iterate »,« update »и« remove via set-to-null «теперь требуется только блокировка чтения, а только« добавить »и« очистить удаленные ключи »- блокировка записи.

Примечание. Я здесь использую : class, чтобы избежать необходимости добавлять собственный код для обеспечения атомарности:

static void Main()
{
    try
    {
        var direct = new Dictionary<string, string>();
        direct.Add("abc", "abc");
        direct.Add("def", "def");
        using (var iter = direct.GetEnumerator())
        {
            iter.MoveNext();
            Console.WriteLine(iter.Current.Value);
            direct["def"] = "DEF";
            iter.MoveNext();
            Console.WriteLine(iter.Current.Value);
        }
    }
    catch { Console.WriteLine("direct: BOOM"); }
    try
    {
        var indirect = new Dictionary<string, Wrapper<string>>();
        indirect.Add("abc", "abc");
        indirect.Add("def", "def");
        using (var iter = indirect.GetEnumerator())
        {
            iter.MoveNext();
            Console.WriteLine(iter.Current.Value);
            indirect["def"].Value = "DEF";
            iter.MoveNext();
            Console.WriteLine(iter.Current.Value);
        }
    } catch { Console.WriteLine("indirect: BOOM"); }
}
class Wrapper<T> where T : class {
    public T Value { get; set; }
    public static implicit operator Wrapper<T>(T value) {
        return new Wrapper<T> { Value = value};
    }
    public static implicit operator T (Wrapper<T> value) {
        return value.Value;
    }
    public override string ToString() {
        return Convert.ToString(Value);
    }
}