Использование ImmutableSortedSet <T> для кеша потоковой безопасности

Question

У меня есть метод, который принимает DateTime и возвращает дату, обозначающую конец этой четверти. Из-за некоторой сложности, связанной с деловыми днями и праздничными календарями, я хочу кэшировать результат, чтобы ускорить последующие вызовы. Я использую SortedSet<DateTime> поддерживать кэш данных, и я использую метод GetViewBetween для того, чтобы сделать поиск в кэше следующим образом:

private static SortedSet<DateTime> quarterEndCache = new SortedSet<DateTime>(); 

public static DateTime GetNextQuarterEndDate(DateTime date) 
{ 
    var oneDayLater = date.AddDays(1.0); 
    var fiveMonthsLater = date.AddMonths(5); 
    var range = quarterEndCache.GetViewBetween(oneDayLater, fiveMonthsLater); 
    if (range.Count > 0) 
    { 
     return range.Min; 
    } 

    // Perform expensive calc here 
} 

Теперь я хочу, чтобы мой кэш поточно. Вместо того, чтобы использовать блокировку повсюду, которая повлечет за собой удар производительности при каждом поиске, я изучаю новую коллекцию ImmutableSortedSet<T>, которая позволит мне полностью избежать блокировок. Проблема в том, что ImmutableSortedSet<T> не имеет метода GetViewBetween. Есть ли способ получить аналогичную функциональность от ImmutableSortedSet<T>?

[EDIT]

Servy убедил меня только с помощью замка с нормальным SortedSet<T> является самым простым решением. Я оставлю вопрос открытым, хотя только потому, что мне интересно узнать, может ли ImmutableSortedSet<T> эффективно обрабатывать этот сценарий.

Answer 1

Давайте разделим вопрос на две части:

1. Как получить функциональность, аналогичную GetViewBetween с ImmutableSortedSet<T>? Я бы предложил использовать метод IndexOf. В приведенном ниже фрагменте я создал метод расширения GetRangeBetween, который должен выполнять эту работу.

2. Как реализовать незакрепленные, потокобезопасные обновления с неизменяемыми структурами данных? Несмотря на то, что это не оригинальный вопрос, есть некоторые скептические комментарии по этому вопросу. Рамка неизменяемости реализует метод для этой цели: System.Collections.Immutable.Update<T>(ref T location, Func<T, T> transformer) where T : class; Метод внутренне полагается на операции атомного сравнения/обмена. Если вы хотите сделать это вручную, вы найдете альтернативную реализацию ниже, которая должна вести себя так же, как Immutable.Update.

Так вот код:

public static class ImmutableExtensions 
{ 
    public static IEnumerable<T> GetRangeBetween<T>(
     this ImmutableSortedSet<T> set, T min, T max) 
    { 
     int i = set.IndexOf(min); 
     if (i < 0) i = ~i; 
     while (i < set.Count) 
     { 
      T x = set[i++]; 

      if (set.KeyComparer.Compare(x, min) >= 0 && 
       set.KeyComparer.Compare(x, max) <= 0) 
      { 
       yield return x; 
      } 
      else 
      { 
       break; 
      } 
     } 
    } 

    public static void LockfreeUpdate<T>(ref T item, Func<T, T> fn) 
     where T: class 
    { 
     T x, y; 

     do 
     { 
      x = item; 
      y = fn(x); 

     } while (Interlocked.CompareExchange(ref item, y, x) != x); 
    } 
} 

Использование:

private static volatile ImmutableSortedSet<DateTime> quarterEndCache = 
     ImmutableSortedSet<DateTime>.Empty; 
    private static volatile int counter; // test/verification purpose only 

    public static DateTime GetNextQuarterEndDate(DateTime date) 
    { 
     var oneDayLater = date.AddDays(1.0); 
     var fiveMonthsLater = date.AddMonths(5); 
     var range = quarterEndCache.GetRangeBetween(oneDayLater, fiveMonthsLater); 
     if (range.Any()) 
     { 
      return range.First(); 
     } 

     // Perform expensive calc here 
     // -> Meaningless dummy computation for verification purpose only 
     long x = Interlocked.Increment(ref counter); 
     DateTime test = DateTime.FromFileTime(x); 
     ImmutableExtensions.LockfreeUpdate(
      ref quarterEndCache, 
      c => c.Add(test)); 

     return test; 
    } 

    [TestMethod] 
    public void TestIt() 
    { 
     var tasks = Enumerable 
      .Range(0, 100000) 
      .Select(x => Task.Factory.StartNew(
       () => GetNextQuarterEndDate(DateTime.Now))) 
      .ToArray(); 

     Task.WaitAll(tasks); 

     Assert.AreEqual(100000, counter); 
    }