Walt D
Walt D

Reputation: 4731

What is the most performant way to make the results of a cached computation thread-safe?

(Apologies if this was answered elsewhere; it seems like it would be a common problem, but it turns out to be hard to search for since terms like "threading" and "cache" produce overwhelming results.)

I have an expensive computation whose result is accessed frequently but changes infrequently. Thus, I cache the resulting value. Here's some c# pseudocode of what I mean:

int? _cachedResult = null;

int GetComputationResult()
{
    if(_cachedResult == null)
    {
        // Do the expensive computation.
        _cachedResult = /* Result of expensive computation. */;
    }
    return _cachedResult.Value;
}

Elsewhere in my code, I will occasionally set _cachedResult back to null because the input to the computation has changed and thus the cached result is no longer valid and needs to be re-computed. (Which means I can't use Lazy<T> since Lazy<T> doesn't support being reset.)

This works fine for single-threaded scenarios, but of course it's not at all thread-safe. So my question is: What is the most performant way to make GetComputationResult thread-safe?

Obviously I could just put the whole thing in a lock() block, but I suspect there might be a better way? (Something that would do an atomic check to see if the result needs to be recomputed and only lock if it does?)

Thanks a lot!

Upvotes: 4

Views: 179

Answers (3)

Ian Mercer
Ian Mercer

Reputation: 39317

You could simply reassign the Lazy<T> to achieve a reset:

Lazy<int> lazyResult = new Lazy<int>(GetComputationResult);

public int Result { get { return lazyResult.Value; } }

public void Reset()
{
   lazyResult = new Lazy<int>(GetComputationResult);
}

Upvotes: 0

ipavlu
ipavlu

Reputation: 1659

perhaps this will provide some food for thought:).

  1. Generic class.
  2. The class can compute data asynchronously or synchronously.
  3. Allows fast reads thanks to the spinlock.
  4. Does not perform heavy stuff inside the spinlock, just returning Task and if necessary, creating and starting Task on default TaskScheduler, to avoid inlining.

Task with Spinlock is pretty powerful combination, that can solve some problems in lock-free way.

    using System;
    using System.Threading;
    using System.Threading.Tasks;

    namespace Example
    {
        class OftenReadSometimesUpdate<T>
        {
            private Task<T> result_task = null;
            private SpinLock spin_lock = new SpinLock(false);
            private TResult LockedFunc<TResult>(Func<TResult> locked_func)
            {
                TResult t_result = default(TResult);
                bool gotLock = false;
                if (locked_func == null) return t_result;

                try
                {
                    spin_lock.Enter(ref gotLock);
                    t_result = locked_func();
                }
                finally
                {
                    if (gotLock) spin_lock.Exit();
                    gotLock = false;
                }
                return t_result;
            }


            public Task<T> GetComputationAsync()
            {
                return
                LockedFunc(GetComputationTaskLocked)
                ;
            }
            public T GetComputationResult()
            {
                return
                LockedFunc(GetComputationTaskLocked)
                .Result
                ;
            }
            public OftenReadSometimesUpdate<T> InvalidateComputationResult()
            {
                return
                this
                .LockedFunc(InvalidateComputationResultLocked)
                ;
            }
            public OftenReadSometimesUpdate<T> InvalidateComputationResultLocked()
            {
                result_task = null;
                return this;
            }

            private Task<T> GetComputationTaskLocked()
            {
                if (result_task == null)
                {
                    result_task = new Task<T>(HeavyComputation);
                    result_task.Start(TaskScheduler.Default);
                }
                return result_task;
            }
            protected virtual T HeavyComputation()
            {
                //a heavy computation
                return default(T);//return some result of computation
            }
        }
    }

Upvotes: 0

Cameron
Cameron

Reputation: 98886

You can use the double-checked locking pattern:

// Thread-safe (uses double-checked locking pattern for performance)
public class Memoized<T>
{
    Func<T> _compute;
    volatile bool _cached;
    volatile bool _startedCaching;
    volatile StrongBox<T> _cachedResult;  // Need reference type
    object _cacheSyncRoot = new object();

    public Memoized(Func<T> compute)
    {
        _compute = compute;
    }

    public T Value {
        get {
            if (_cached)    // Fast path
                return _cachedResult.Value;
            lock (_cacheSyncRoot)
            {
                if (!_cached)
                {
                    _startedCaching = true;
                    _cachedResult = new StrongBox<T>(_compute());
                    _cached = true;
                }
            }
            return _cachedResult.Value;
        }
    }

    public void Invalidate()
    {
        if (!_startedCaching)
        {
            // Fast path: already invalidated
            Thread.MemoryBarrier();  // need to release
            if (!_startedCaching)
                return;
        }
        lock (_cacheSyncRoot)
            _cached = _startedCaching = false;
    }
}

This particular implementation matches your description of what it should do in corner cases: If the cache has been invalidated, the value should only be computed once, by a single thread, and other threads should wait. However, if the cache is invalidated concurrently with the cached value being accessed, the stale cached value may be returned.

Upvotes: 4

Related Questions