5
\$\begingroup\$

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.

\$\endgroup\$

5 Answers 5

4
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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). enter image description here

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.

\$\endgroup\$
11
  • \$\begingroup\$ Thanks for statistics! It looks like your tests fit to CPU cache, so it is really quick. My math looks very different: I have many megabytes of records with complex calculated properties where each getter invocation can cascade through the whole record set (getter on record #1 invokes getters of many properties on record #2, etc.). Records are wide (hundreds of parameters to be calculated) and only a subset is usually requested, so I need to do it on demand only – code/data separation to calculate everything once will not work. \$\endgroup\$ May 25, 2016 at 7:36
  • \$\begingroup\$ Syntax should be clean, as I would not like to obscure complex math logic with technical details. I wish it would be possible to do Cached<double> Prop2 { get; } = () => Prop1 * 2; but C# doesn’t allow anything of it, which is a real shame. It just looks like that C# is not the best choice here. \$\endgroup\$ May 25, 2016 at 7:36
  • \$\begingroup\$ What about: Cached<double> Prop2 { get; } = Cached.New( () => Prop1 * 2, () => Prop1);? That would work and is still compact. \$\endgroup\$
    – JanDotNet
    May 25, 2016 at 8:02
  • \$\begingroup\$ Yep, it could help a lot, but there is no way to access this or base from the field initializer: Error CS0236 A field initializer cannot reference the non-static field, method, or property... \$\endgroup\$ May 25, 2016 at 8:27
  • \$\begingroup\$ You are right, default property initialization does not work... but you could initialze cached properties in contructor. I've updated the code above. \$\endgroup\$
    – JanDotNet
    May 25, 2016 at 8:46
2
\$\begingroup\$

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>.


\$\endgroup\$
1
  • \$\begingroup\$ 1) Yes, performance is problematic. ConcurrentDictionary is slow plus we have some reference type allocations... 2) Here we check dependency acquisition delegates d, not current dependency values d()... 3) Yes, it makes sense... 4) I think you supposed to mention IEquitable<T> here. It is not recommended to implement it for reference types though (there is no technical meaning in it), so for objects with Value Identity we usually override Object.Equal() which is used by SequenceEquals. \$\endgroup\$ May 23, 2016 at 18:26
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ Oops, sorry. This multiplication was from my syntax verification unit tests. Real applications involve sophisticated logic with megabytes of data to be processed repeatedly. \$\endgroup\$ May 24, 2016 at 14:41
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.