はかせのラボ

私の頭の中を書いていく雑記ブログです

IL 自動メモ化の実装をあれこれ考えたけど結局ネタ被りしたから速度勝負に切り替えた話

あいさつ

どうも、はかせです。
今回は前回やったメモ化の自動化をやってみたいと思います。

やり方

自動化の前にメモ化の復習。
メモ化ってのはメソッドの引数と戻り値をペアでキャッシュして
同じ引数で呼ばれた時にキャッシュを返すことで
プログラムの高速化を行う技法のことでした。

理屈は単純ですね。
そしてこんだけ単純なら自動化できそう。
つかWikipediaの項目にもあるくらいなんでおそらく
自動化するのがメジャーなんでしょう。

ということでやってみます。

今回私が考えた自動化の方法はこの三つです。
・Dictionaryの拡張メソッドを作る
アスペクト指向で処理の間にキャッシュを挟み込む
・IL生成でメソッドをオーバーライドする

さて一個ずつやっていきましょう。

まずはメモ化なしのを置いておく

高速化ってのは元からどれだけ早くなったかが大切です。
なのでメモ化せずにやった場合のを載せておきます。

protected virtual int NotMemoFibonacci(int index)
{
    if (index < 0) throw new ArgumentException();
    return index < 2 ? index : NotMemoFibonacci(index - 1) + NotMemoFibonacci(index - 2);
}

f:id:hakase0274:20190920223351p:plain
約4.5秒
これがどれだけ早くなるのでしょうか。

Dictionaryの拡張メソッドを作る

メモ化はキャッシュの応用で、
キャッシュってことはそれはつまりDictionaryを使うわけでして、
だったらそいつを拡張したらええんでないの?
という発想です。

/// <summary>
/// 拡張メソッドによるメモ化
/// </summary>
public static class Extensions
{
    public static TValue ExecuteMemoization<TKey, TValue>(this Dictionary<TKey, TValue> dictionary, TKey key, Func<TKey, TValue> func)
    {
        TValue result;

        if (!dictionary.TryGetValue(key, out result))
        {
            result = func(key);
            dictionary.Add(key, result);
        }

        return result;
    }
}

private int MemoFibonacciDictionaryExtensions(int index)
{
    if (index < 0) throw new ArgumentException();
    //こんな感じでキーとマッチしなかった場合のデリゲートを渡す
    return index < 2 ? index : memoDic.ExecuteMemoization(index, i => MemoFibonacciDictionaryExtensions(i - 1) + MemoFibonacciDictionaryExtensions(i - 2));
}

さて実行結果Done
f:id:hakase0274:20190920223148p:plain
いきなり2ミリ秒来ましたー!

と言ってもまぁこんくらい早くなるのは前の記事でも
検証済みなのでそこまでって感じですね。

アスペクト指向で処理の間にキャッシュを挟み込む

まずアスペクト指向とは何ぞやってとこからですね。
平たく言えば処理を行う前に別の処理(ログとか)を行う感じです。
要はこれが
f:id:hakase0274:20190920224243p:plain
こんな感じ
f:id:hakase0274:20190920224246p:plain
そしてコード

public class MemoizationProxy<TInstance, TArgs, TResult> : RealProxy where TInstance : new()
{
    private readonly TInstance _decorated;
    private Dictionary<TArgs, TResult> memoDic;

    private MemoizationProxy(TInstance decorated) : base(typeof(TInstance))
    {
        _decorated = decorated;
        memoDic = new Dictionary<TArgs, TResult>();
    }

    public static TInstance Create()
    {
        return (TInstance)new MemoizationProxy<TInstance, TArgs, TResult>(new TInstance()).GetTransparentProxy();
    }

    public override IMessage Invoke(IMessage msg)
    {
        var methodCall = msg as IMethodCallMessage;
        var methodInfo = methodCall.MethodBase as MethodInfo;
        if (methodCall.InArgs.Length != 1) throw new System.IO.InvalidDataException("引数が誤ってます");
        var key = (TArgs)methodCall.InArgs[0];
        if (!memoDic.TryGetValue(key, out TResult memoResult))
        {
            memoResult = (TResult)methodInfo.Invoke(_decorated, methodCall.InArgs);
            memoDic.Add(key, memoResult);
        }
        return new ReturnMessage(memoResult, null, 0, methodCall.LogicalCallContext, methodCall);
    }
}

public class TestAOP : MarshalByRefObject
{
    public int Fibonacci(int index)
    {
        if (index < 0) throw new ArgumentException();
        return index < 2 ? index : Fibonacci(index - 1) + Fibonacci(index - 2);
    }
}

アスペクト指向についてはぶっちゃけ概要くらいしか知りません。
何やらRealProxyを継承してInvokeをぶんどればいいってのは
ググって知りました。

さて結果は
f:id:hakase0274:20190920224648p:plain
約5秒!?

むしろ遅くなってもうた・・・
こらあかん・・・あかんでぇ・・・・

※追記 2019/09/22
この記事のやり方ではメモ化が機能していないことが発覚しました
正しいやり方はこちらの記事であげています

hakase0274.hatenablog.com

IL生成でメソッドをオーバーライドする

これは単純でメモ化対象をvirtualメソッドにして
オーバーライドの仕組みを使って
実行前にキャッシュをごにょごにょするやり方です。

じゃコードです。
と言いたいところなんですが、
さすがに長すぎるのでGitHubに上げました。
github.com

このコード実行するとこんな感じのC#コードが出来ます。

using Hakase;
using System.Collections.Generic;

internal class HakaseMemoizationebcd0e6a-bb80-4025-95d3-2964f222856f : HakaseMemo
{
	private Dictionary<Memoization.Param, HakaseMemo> Field_e4a818a50118467f8002cadab4da868c;

	public HakaseMemoizationebcd0e6a-bb80-4025-95d3-2964f222856f()
	{
		Field_e4a818a50118467f8002cadab4da868c = new Dictionary<Memoization.Param, HakaseMemo>();
	}

	public new unsafe virtual int Fibonacci(int P_0)
	{
		Memoization.Param key = new Memoization.Param(P_0);
		int value;
		if (!Field_e4a818a50118467f8002cadab4da868c.TryGetValue(key, out *(HakaseMemo*)(&value)))
		{
			value = base.Fibonacci(P_0);
			Field_e4a818a50118467f8002cadab4da868c[key] = (HakaseMemo)value;
		}
		return value;
	}
}

キャッシュ用のDictionaryをメンバに持っていて
メモ化対象のメソッドをオーバーライドし、
キャッシュ周りの処理をやってメソッド実行の必要がある場合のみ
親のメソッド、つまりメモ化対象のメソッドを呼び出します。

引数は何がどれだけ来るか分かったものじゃないので
それ用のクラスを作ってそこに押し込みました。

さて気になる実行結果はというと
f:id:hakase0274:20190920232803p:plain
1ミリ秒!!!

4.5秒から始めて1ミリ秒・・がんばったなぁ(´;ω;`)

ちなみに

このメソッドオーバーライド式は私が最初にメモ化を知った参考記事と同じやり方です。
(引数を押し込めるってのも参考記事同様)
その記事はこちら
qiita.com

参考元の実装はLINQを使ったりnullチェックを行ったりと
わかりやすい&堅牢な作りで、
どんな状況でもエラー出ないような作りを目指してる感じでした。

対して私の実装はそういったものを省いて
(LINQはfor文に置き換えたり、
nullがあり得ないような作りにしてnullチェックを省いたり)

今の私の実力で出せる最高速を目指しました。
(そのため参考元と比べると少し挙動が不安)

参考元の実装と私の実装の比較です。
f:id:hakase0274:20190920233703p:plain
参考元が9ミリ秒で私が1ミリ秒です。

速度と安全性はトレードオフって感じですかね。

あとがき

今回は自動メモ化の実装を速度意識でやってみました。
私は高速化初心者なので、
あくまで参考元の実装で省けるとこ省いてって感じでやりました。
(0からできるほどの実力はありません)

ただなんでしょうね。
別にできることが変わったわけでも何でもないのに
謎の達成感があります。

これもIL書きの魅力の一つ・・・なんでしょうかね?

それでは今回はこの辺でノシ