Awesome

MemoizationForUnity

日本語

Summary

This library "MemoizationForUnity" provides a powerful memoization function.
Memoization is a function that caches the output of a function using its inputs as keys.
This makes it possible to skip the second and subsequent heavy calculation processes and return the output immediately.
Among the long-established techniques for caching return values using arguments as keys, memoization is a major technique in functional languages.
"MemoizationForUnity" uses SourceGenerator to automatically generate a memoization cache function.

System Requirements

Performance

Measurement code on the editor

Test Code.

Result

CalcPrime uses one argument and GetMethodInfo uses three arguments.
Performance is improved for all items.
It can be seen that the fewer the arguments, the faster the retrieval, and the higher the processing load of Raw, the better the effect.
GetTypes, which has no arguments and a high load, shows a processing speed improvement of about 1,000,000x.

Measurement code on the runtime

private readonly ref struct Measure
{
    private readonly string _label;
    private readonly StringBuilder _builder;
    private readonly float _time;

    public Measure(string label, StringBuilder builder)
    {
        _label = label;
        _builder = builder;
        _time = (Time.realtimeSinceStartup * 1000);
    }

    public void Dispose()
    {
        _builder.AppendLine($"{_label}: {(Time.realtimeSinceStartup * 1000) - _time} ms");
    }
}

:

var log = new StringBuilder();
{
    using (new Measure("CalcPrime_Raw", log))
    {
        for (int i = 0; i < 10000; ++i)
        {
            FindLargestPrimeRaw(1000);
        }
    }

    using (new Measure("CalcPrime_Memoized", log))
    {
        for (int i = 0; i < 10000; ++i)
        {
            FindLargestPrime(1000);
        }
    }
}

 :

Result

Both items show improved performance over the editor.
This validation reveals that cache references perform better with Mono than with IL2CPP.
GetTypes has the fastest performance because it is subject to optimization by Static Type Caching.

How to install

Installing MemoizationForUnity

1. Open [Window > Package Manager].
2. click [+ > Add package from git url...].
3. Type https://github.com/Katsuya100/MemoizationForUnity.git?path=packages and click [Add].

If it doesn't work

The above method may not work well in environments where git is not installed.
Download the appropriate version of com.katuusagi.memoizationforunity.tgz from Releases, and then [Package Manager > + > Add package from tarball...] Use [Package Manager > + > Add package from tarball...] to install the package.

If it still doesn't work

Download the appropriate version of Katuusagi.MemoizationForUnity.unitypackage from Releases and Import it into your project from [Assets > Import Package > Custom Package].

How to Use

Normal usage

Memoization functions are generated by attaching the Memoization attribute to methods in the partial type.

private partial class Class
{
    [Memoization]
    public static int Method(int arg0)
    {
        :
    }
}

The following implementation is then generated.

private static System.Collections.Generic.Dictionary<int, int> __MemoizationCacheValue_980d929936fa49b59a9d533a1c442eca__ = new System.Collections.Generic.Dictionary<int, int>();
public static int MethodWithMemoization(int arg0)
{
    var __key__ = arg0;
    if (__MemoizationCacheValue_980d929936fa49b59a9d533a1c442eca__.TryGetValue(__key__, out var __cache__))
    {
        return __cache__;
    }
    var __result__ = Method(arg0);
    __MemoizationCacheValue_980d929936fa49b59a9d533a1c442eca__.Add(__key__, __result__);
    return __result__;
}

MethodWithMemoization caches the return value, so it returns the return value fast.

Alternatively, you can omit the WithMemoization suffix by adding the Raw suffix as follows

private partial class Class
{
    [Memoization]
    public static int MethodRaw(int arg0)
    {
        :
    }
}

The following implementation is generated by adding the Raw suffix.

private static System.Collections.Generic.Dictionary<int, int> __MemoizationCacheValue_e99db10c9a424507be15cbcd47f085c3__ = new System.Collections.Generic.Dictionary<int, int>();
public static int Method(int arg0)
{
    var __key__ = arg0;
    if (__MemoizationCacheValue_e99db10c9a424507be15cbcd47f085c3__.TryGetValue(__key__, out var __cache__))
    {
        return __cache__;
    }
    var __result__ = MethodRaw(arg0);
    __MemoizationCacheValue_e99db10c9a424507be15cbcd47f085c3__.Add(__key__, __result__);
    return __result__;
}

In this case, Method caches the return value.

Clear cache

If you want to clear the cache, set the IsClearable parameter of the Memoization attribute.

[Memoization(IsClearable = true)]
public static int MethodRaw(int arg0)
{
    :
}

A Clear function will then be generated for method.
If it is an Instance function, ClearInstanceMemoizationCache will be generated.
If it is a Static function, ClearStaticMemoizationCache will be generated.

Custom generated method name

You can use any function name by setting the MethodName parameter.
The following example sets the function name MethodFast.

[Memoization(MethodName = nameof(MethodFast))]
public static int MethodInternal(int arg0)
{
    :
}

The MethodName parameter is referenced and the following implementation is generated.

private static System.Collections.Generic.Dictionary<int, int> __MemoizationCacheValue_c119bf728a8546a282d1fa37ffa9d7e6__ = new System.Collections.Generic.Dictionary<int, int>();
public static int MethodFast(int arg0)
{
    var __key__ = arg0;
    if (__MemoizationCacheValue_c119bf728a8546a282d1fa37ffa9d7e6__.TryGetValue(__key__, out var __cache__))
    {
        return __cache__;
    }
    var __result__ = MethodInternal(arg0);
    __MemoizationCacheValue_c119bf728a8546a282d1fa37ffa9d7e6__.Add(__key__, __result__);
    return __result__;
}

Thread-safe support

Memoization cache is basically not thread-safe.
Functions called from multiple threads should have the ThreadSafeType parameter of the Memoization attribute set.

[Memoization(ThreadSafeType = ThreadSafeType.Concurrent)]
public static int MethodRaw(int arg0)
{
    :
}

Setting the ThreadSafeType parameter makes the hash table in the cache area thread-safe.
The process varies depending on the value you set.

Custom modifiers

The default behavior of Memoization is to inherit the modifiers of the original method.
However, there may be cases where you want to expose only the generated methods, leaving the calculation process as an internal method.
In such cases, use the Modifier parameter.

[Memoization(Modifier = "public static")]
private static int MethodRaw(int arg0)
{
    :
}

The following implementation is then generated.
You can see that the modifier has changed to public.

private static System.Collections.Generic.Dictionary<int, int> __MemoizationCacheValue_9c36aae2f3ed4842919001270b87e3c0__ = new System.Collections.Generic.Dictionary<int, int>();
public static int Method(int arg0)
{
    var __key__ = arg0;
    if (__MemoizationCacheValue_9c36aae2f3ed4842919001270b87e3c0__.TryGetValue(__key__, out var __cache__))
    {
        return __cache__;
    }
    var __result__ = MethodRaw(arg0);
    __MemoizationCacheValue_9c36aae2f3ed4842919001270b87e3c0__.Add(__key__, __result__);
    return __result__;
}

Keying Array Elements

Usually when an array is passed as an argument, it is sometimes inconvenient because the reference is made part of the key. To treat array elements as keys, the following implementation is recommended.

[Memoization(CompareArrayElement = true)]
private static int MethodRaw(int arg0)
{
    :
}

Advanced features

Attaching attributes to generated methods

Generated methods inherit the attributes of the original method.
To attach attributes only to generated methods, implement as follows.

public class TestFunctionAttribute : Attribute
{
}
:
[Memoization(Attributes = new string[] { "TestFunctionAttribute" })]
public static bool HasAttributeRaw()
{
    :
}

Custom cache comparison process

Memoization refers to the cache by its hash table.
It is optimized internally as much as possible, but further speed-up can be achieved by customizing the CacheComparer parameter as follows.

public class CustomComparer : IEqualityComparer<int>
{
  :
}

[Memoization(CacheComparer = "new CustomComparer()")]
private static int MethodRaw(int arg0)
{
    :
}

Then CustomComparer is assigned to the implemented Dictionary.

private static System.Collections.Generic.Dictionary<int, int> __MemoizationCacheValue_eddb945ad3a8410db30f0a8eebf6af87__ = new System.Collections.Generic.Dictionary<int, int>(new CustomComparer());

Set callback to detect cache make

If you want to detect that a cache has been created, set the function name to the OnCachedMethod parameter.

[Memoization(OnCachedMethod = nameof(OnCached))]
private static int MethodRaw(int arg0)
{
    :
}

The partial function will be defined and you can customize your implementation according to the definition.

private partial static void OnCached(int key, int result)
{
    :
}

Interrupt to cache

In some cases, you may want to pre-create a cache or share a cache among the Memoization methods.
In such cases, set the function name to the InterruptCacheMethod parameter.

[Memoization(InterruptCacheMethod = nameof(InterruptCache))]
private static int MethodRaw(int arg0)
{
    :
}

A function is then generated to add or change values in the cache.
However, this operation can cause unexpected behavior since the cache can be manipulated at will.

Prohibited settings

Application to non-partial types

Memoization cannot be applied to non-partial types due to code generation by the SourceGenerator.

Memoization of struct instance methods

Partialing an instance member of struct will result in a non-avoidable warning (CS0282).
Therefore, application of Memoization to struct instance methods is prohibited.

Memoization to methods without return value or out,ref

Memoization cannot be set for methods that have no outputs.

Reasons for high performance

This library uses SourceGenerator to analyze the code and select the optimal cache method on a case-by-case basis.
For example, if a method has arguments, it is converted to a Tuple and an EqualityComparer optimized specifically for Tuple is used.
If a method has no arguments, it only checks if it is cached or not with a flag.
This makes it possible to retrieve values at high speed.
Furthermore, if there is no need to clear the cache, optimization is performed by Static Type Caching.
In this case, the cache can be retrieved at zero cost.
In the case of Generic Static functions, Static Type Caching also switches the referenced table.
If there are only type arguments, Static Type Caching directly holds the value, allowing zero-cost caching.
This eliminates the need to write cumbersome Static Type Caching definitions.
In the case of the Instance function, Static Type Caching is not available, but the type argument is converted to an integer ID, so the cache can be searched faster than with Type as the key.

These techniques allow for fast cache retrieval.

Notes

The theoretical slowest cases of Memoization are Instance functions that are thread-safe and have long variable-length arguments.
Although there are situations where this can contribute to speedup, these conditions should be handled with care.

Also, be careful when taking floating numbers as arguments.
If a linearly varying value is taken as an argument, the cache size tends to increase.
The same is true when taking a value such as the current time as an argument.
Use this function only for cases such as "performing the calculation again using the same value".