Property caching

Question

Trying to figure out how to efficiently cache property calculations with dependency tracking to invalidate the cache. Here is the syntax I have at the moment (one Cache instance supports multiple object properties):

class Multiplication
{
    public int Arg1 { get; set; }
    public int Arg2 { get; set; }
    public int Result => Cache
        .Lazy(() => Arg1 * Arg2)
        .From(() => Arg1, () => Arg2);

    Cache Cache { get; } = new Cache();
}

Here Result is recalculated on Arg* change. Implementation classes:

public class Cache
{
    public LazyProperty<T> Lazy<T>(
        Func<T> factory, 
        [CallerMemberName] string memberName = "") =>
        new LazyProperty<T>(
             value => (Cached<T>)Store.GetOrAdd(memberName, value), 
             new Cached<T>(factory));

    ConcurrentDictionary<string, object> Store { get; } = 
        new ConcurrentDictionary<string, object>();
}

This one helps with flow API:

public class LazyProperty<T>
{
    public static implicit operator T(LazyProperty<T> property) => property.Resolve();

    internal LazyProperty(Func<Cached<T>, Cached<T>> getOrAdd, Cached<T> value)
    {
        GetOrAdd = getOrAdd;
        Value = value;
    }

    public LazyProperty<T> From(params Func<object>[] dependencies) =>
        new LazyProperty<T>(GetOrAdd, Value.Depending(dependencies));

    Func<Cached<T>, Cached<T>> GetOrAdd { get; }
    Cached<T> Value { get; }
    Cached<T> Resolve() => GetOrAdd(Value);
}

Dependency tracking done by:

public class Cached<T>
{
    public static implicit operator T(Cached<T> cache) => cache.Value;

    public Cached(Func<T> factory, params Func<object>[] dependencies)
    {
        if (factory == null)
            throw new ArgumentNullException("factory");

        if(dependencies == null || dependencies.Any(d => d == null))
            throw new ArgumentNullException("dependancies");

        _factory = factory;
        _dependencies = dependencies;
    }

    public Cached<T> Depending(params Func<object>[] dependencies) => 
        new Cached<T>(_factory, _dependencies.Concat(dependencies).ToArray());

    readonly Func<T> _factory;
    readonly Func<object>[] _dependencies;
    object[] _context = null;
    T _value = default(T);

    T Value
    {
        get
        {
            var context = _dependencies
                .Select(d => d())
                .ToArray();

            if (_context?.SequenceEqual(context) == true)
                return _value;

            lock (this)
            {
                if (_context?.SequenceEqual(context) == true)
                    return _value;

                _context = context;
                _value = _factory();                    
                return _value;
            }
        }
    }        
}

Any ideas how to simplify/speed it up? Thanks.

Answer 1

You could potentially use incremental computation (think Excel cells that cache values).

Some details (in F#) here: https://fsprojects.github.io/FSharp.Data.Adaptive/

The above is ported from the Incremental portion of the Aardvark project: https://github.com/aardvark-platform/aardvark.base

The documentation is all F# since this model works well in a functional style, but it works similarly well in imperative (and is interoperable with C#) https://rawgit.com/wiki/aardvark-platform/aardvark.docs/docs/base/adaptive-functional-programming.html

These do pretty much exactly what you want, with automatic dependency tracking and lazy value updating (on read).

There are some utility classes for interop with C# as well, and they work decently - but you still end up having to do some manual messy F# interop on occasion.

Unfortunately, the documentation is also a bit lacking, so reading code is often also necessary if you want to do more than the basics, but it's a quite powerful model.

Answer 2

Based on your code, I created a class for getting cached values (without dictionaries). The usage is syntactically not so elegant as your approach, but for time-consuming operations and frequently access it may improve performance.

For testing performance, 2 methods (that differ in execution time) are compared with it's cached versions:

MathOperation

public double MathOperation()
{
    return Math.Sin(Math.Sqrt(Val1 * Val2) * Math.Sqrt(Val1 * Val2));
}

StringOperation

public double StringOperation()
{
    double value = 0;
    for (int i = 0; i < 50; i++)
        value = double.Parse((Val1 * Val2).ToString());
    return value;
}

The table below displays the ellapsed time in milli seconds for each method depending on the number of calls.

• Column "XXXCached" displays the ellapsed time for constant Val1 and Val2 (full caching effect).
• Column "XXXCached (changed values)" displays the ellapsed time if Val1 changes before each call (no caching effect).

Cached class:

public class Cached
{
    public static Cached<TVal> Create<TVal>(Func<TVal> getter, params Func<object>[] dependencies)
    {
        return new Cached<TVal>(getter, dependencies);
    }
}

public class Cached<T>
{
    public static implicit operator T(Cached<T> property) => property.GetValue();

    private T _currentValue;
    private object[] _context;
    private readonly Func<object>[] _dependencies;
    private readonly Func<T> _getter;
    public Cached(Func<T> getter, params Func<object>[] dependencies)
    {
        _getter = getter;
        _dependencies = dependencies;
    }

    public T GetValue()
    {
        lock(this)
        {
            var context = _dependencies.Select(d => d()).ToArray();
            if (_context?.SequenceEqual(context) != true)
            {
                _context = context;
                _currentValue = _getter();
            }
            return _currentValue;
        }
    }
}

Usage:

public class Container
{
    public Container()
    {
        MathOperationCached = Cached.Create(() => MathOperation, () => Val1, () => Val2);
        StringOperationCached = Cached.Create(() => StringOperation(), () => Val1, () => Val2);
    }
    public double Val1 { get; set; }
    public double Val2 { get; set; }

    public Cached<double> MathOperationCached { get; private set; }
    public Cached<double> StringOperationCached { get; private set; }

    public double MathOperation => Math.Sin(Math.Sqrt(Val1 * Val2) * Math.Sqrt(Val1 * Val2));
    public double StringOperation() 
    {
        double value = 0;
        for (int i = 0; i < 50; i++)
            value = double.Parse((Val1 * Val2).ToString());
        return value;
    }
}

Conclusion:

For most mathematical operations, it is faster to recalculate the result each time. For other time-consuming operations that are frequently accessed, it may may be faster to cache the result. However, such cases are so rare (IMHO), that there is no need for a special class. The availability of such a class misleads to use it also for operations that are faster without such kind of caching. In addition, implementing custom caching (for instance by setting a flag in the setter of the depending properties) is even faster.

Answer 3

Nice pice of code!

Did you run performance tests? It would be interesting to know if the cached version is more performant as a non-cached version depending on complexity of the dependend objects.

---

However, some notes:

if(dependencies == null || dependencies.Any(d => d == null))
        throw new ArgumentNullException("dependancies");

Is it desired, that properties that are null are not allowed? If so, it is also possible that dependent properties become null after the LazyProperty was created - so IMHO that restriction can be removed.

---

The naming of you API is very compact. Actally, I didn't understand what exactly the code does just by looking on the Multiplication class. Conside to use a more descriptive naming like:

public int Result => PropertyRepository
    .AddLazy(() => Arg1 * Arg2)
    .WithDependencies(() => Arg1, () => Arg2);

---

You change tracking does not indicate changes in complex objects. But maybe that is not the main use case... However, to avoid accidentally misusage, you could restrict the types of dependent properties to types that implement IComparable<T>.

---

Answer 4

This may go against the intent of the OP question but I need to take into account what is being trying to get cached.

What you are trying to cache here is just a multiplication. This is equivalent to two Mov and a arithmetic operation (Mul) in assembly.

Even the processor's from the 90's wouldn't have trouble doing 3 assembly operations and all what you are doing is waste memory, nothing else.

My point is: don't cache the values at all.

Answer 5

Original approach works too slow and syntactically inefficient – it is also quicker to recalculate everything than track dependencies. Now I defined a Lazy.tt template to create class with overrides, so if attribute named Lazy marks property or class like here:

class Calculator
{
    public int Arg1 { get; set; }
    public int Arg2 { get; set; }
    [Lazy] public virtual int Mul => Arg1 * Arg2;
    [Lazy] public virtual int Sum => Arg1 + Arg2;
}

The following Lazy class is generated by tt:

class LazyCalculator : Calculator
{
    public LazyCalculator() // Delegate all ctors
        : base()
    {
        Init();
    }

    void Init()
    {
        LazyMul = new Lazy<int>(() => base.Mul);
        LazySum = new Lazy<int>(() => base.Sum);
    }

    Lazy<int> LazyMul;
    public override int Mul => LazyMul.Value;

    Lazy<int> LazySum;
    public override int Sum => LazySum.Value;
}

It is not perfect, as EnvDTE (to browse code structure) is slow and not available for MSBuild, but I just could not come to the better solution at the moment.