Using ImmutableSortedSet<T> for a thread safe cache

Question

I have a method that takes a DateTime and returns the date marking the end of that quarter. Because of some complexity involving business days and holiday calendars, I want to cache the result to speed up subsequent calls. I'm using a SortedSet<DateTime> to maintain a cache of data, and I use the GetViewBetween method in order to do cache lookups as follows:

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
}

Now I want to make my cache threadsafe. Rather than use a lock everywhere which would incur a performance hit on every lookup, I'm exploring the new ImmutableSortedSet<T> collection which would allow me to avoid locks entirely. The problem is that ImmutableSortedSet<T> doesn't have the method GetViewBetween. Is there any way to get similar functionality from the ImmutableSortedSet<T>?

[EDIT]

Servy has convinced me just using a lock with a normal SortedSet<T> is the easiest solution. I'll leave the question open though just because I'm interested to know whether the ImmutableSortedSet<T> can handle this scenario efficiently.

Answer 1

Let's divide the question into two parts:

1. How to get a functionality similar to GetViewBetween with ImmutableSortedSet<T>? I'd suggest using the IndexOf method. In the snippet below, I created an extension method GetRangeBetween which should do the job.

2. How to implement lock-free, thread-safe updates with data immutable data structures? Despite this is not the original question, there are some skeptical comments with respect to this issue. The immutables framework implements a method for exactly that purpose: System.Collections.Immutable.Update<T>(ref T location, Func<T, T> transformer) where T : class; The method internally relies on atomic compare/exchange operations. If you want to do this by hand, you'll find an alternative implementation below which should behave the same like Immutable.Update.

So here is the code:

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);
    }
}

Usage:

    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);
    }