27

式ツリーからコンパイルされたメソッドを効率的にキャッシュする方法は?

public void SomeToStringCalls()
{
    ToString(i => (i + 1).ToString(), 1);
    ToString(i => (i + 1).ToString(), 2);
    ToString(i => (i + 2).ToString(), 3);
    ToString(i => (i + 2).ToString(), 4);
}

private string ToString<T>(Expression<Func<T, string>> expression, T input)
{
    var method = expression.Compile();
    return method.Invoke(input);
}

上記では、一部が同一であっても、すべての呼び出しで各式が再コンパイルされます。Dictionary<Expression<Func<T, string>>, Func<T, string>>()意志が失敗するため、コンパイルされたメソッドを式からキャッシュすることはできませequalsん。

4

7 に答える 7

2

使用できない理由は、 「等しい」式を検出するほどスマートDictionary<Expression<Func<T, string>>, Func<T, string>>ではないためです。Expression<T> GetHashCodeよくわかりませんがExpression<T>.GetHashCode、式のメモリアドレスを返す可能性が非常に高いです。

この問題に対処するには、より「スマートな」ハッシュ計算を導入できます。本体が等しい等式を考えてみましょう。それは非常に滑りやすい道ですが、責任を持って次のことを保証する意思がある場合:

  1. 2 つの異なる式が同じハッシュ コードを持つことはありません
  2. 本体が同じ 2 つの式のハッシュ コードは同じです

あなたが望むものを達成することができます。

これは、pastebin で作成した概念コードの簡単な証明です。これは工業的な強みではありませんが (コメントに改善のヒントがあります)、アプローチの実現可能性を明確に示しています。

さらに詳しく説明する前に考慮すべき点がいくつかあります。ハッシュ関数が不適切であると、非常に厄介なバグが発生する可能性があります。だから、よく考えて、たくさんの単体テストと獲物を書いてください:)

于 2013-11-06T15:15:18.733 に答える
1

あなたが説明する問題は、2 つの式を意味論的に同等に評価することは、少なくとも式をコンパイルするのと同じくらい高価であるという意味で深刻です。これを説明するために、式の等価性の実装へのリンクを次に示します。この実装は完全ではありません。たとえば、次のようになります。

MethodA() { MethodB(); }
MethodB() { ... }

上記の例では、MethodAとMethodBは同じことを行うという意味で同等であり、ほとんどの場合、それらを同等と見なしたいと考えています。たとえば、コンパイラの最適化を有効にしてこれを C# でビルドすると、MethodB呼び出しがMethodA呼び出しに置き換えられます。コードを比較する際には無数の問題があり、進行中の研究のトピックです。

式のコンパイルがアプリケーションのボトルネックであることがわかった場合は、式を識別する何らかのキーによって式が参照される設計を検討する必要があります。同等性を決定するまでには、すでにコンパイルされている可能性があります。

J0HNの答えにコメントするには、本体のハッシュコードとパラメーターを比較します。これは、式ツリーの詳細な評価を行わないため、決して信頼できるソリューションではありません。

また、コメントに投稿されたこの質問を見てください。

于 2013-11-06T15:33:46.077 に答える
0

あなたの目標が式から「値を抽出する」ためにコンパイル+呼び出すことである場合、別の方法を検討することができます。

リフレクションによってコンパイルせずに式ツリーから値を抽出しようとしています。

私の解決策は、すべての式を完全にサポートしているわけではありません。最初は、ラムダと算術演算を使用せずにメソッド呼び出しをキャッシュするために作成されましたが、いくつかの改善により役立ちます。

ここにあります：

private static object ExtractValue(Expression expression, object[] input, ReadOnlyCollection<ParameterExpression> parameters)
{
    if (expression == null)
    {
        return null;
    }

    var ce = expression as ConstantExpression;
    if (ce != null)
    {
        return ce.Value;
    }

    var pe = expression as ParameterExpression;
    if (pe != null)
    {
        return input[parameters.IndexOf(pe)];
    }

    var ma = expression as MemberExpression;
    if (ma != null)
    {
        var se = ma.Expression;
        object val = null;
        if (se != null)
        {
            val = ExtractValue(se, input, parameters);
        }

        var fi = ma.Member as FieldInfo;
        if (fi != null)
        {
            return fi.GetValue(val);
        }
        else
        {
            var pi = ma.Member as PropertyInfo;
            if (pi != null)
            {
                return pi.GetValue(val);
            }
        }
    }

    var mce = expression as MethodCallExpression;
    if (mce != null)
    {
        return mce.Method.Invoke(ExtractValue(mce.Object, input, parameters), mce.Arguments.Select(a => ExtractValue(a, input, parameters)).ToArray());
    }

    var sbe = expression as BinaryExpression;
    if (sbe != null)
    {
        var left = ExtractValue(sbe.Left, input, parameters);
        var right = ExtractValue(sbe.Right, input, parameters);

        // TODO: check for other types and operands

        if (sbe.NodeType == ExpressionType.Add)
        {
            if (left is int && right is int)
            {
                return (int) left + (int) right;
            }
        }

        throw new NotImplementedException();
    }

    var le = expression as LambdaExpression;
    if (le != null)
    {
        return ExtractValue(le.Body, input, le.Parameters);
    }

    // TODO: Check for other expression types

    var dynamicInvoke = Expression.Lambda(expression).Compile().DynamicInvoke();
    return dynamicInvoke;
}

使用法:

private static string ToString<T>(Expression<Func<T, string>> expression, T input)
{
    var sw = Stopwatch.StartNew();
    var method = expression.Compile();
    var invoke = method.Invoke(input);
    sw.Stop();
    Console.WriteLine("Compile + Invoke: {0}, {1} ms", invoke, sw.Elapsed.TotalMilliseconds);
    sw.Restart();
    var r2 = ExtractValue(expression, new object[] {input}, null);
    sw.Stop();
    Console.WriteLine("ExtractValue: {0}, {1} ms", r2, sw.Elapsed.TotalMilliseconds);
    return invoke;
}

いくつかの改善と追加の式タイプにより、このソリューションは Compile().DynamicInvoke() のより高速な代替手段になる可能性があると思います

于 2013-11-06T18:09:01.770 に答える
-1

単純すぎると思いますが、私がテストした 1 つの単純なシナリオでは、これは約 4 倍高速に見えます。

    public static Dictionary<string, object> cache
        = new Dictionary<string, object>();
    public static string ToString<T>(
            Expression<Func<T, string>> expression,
            T input)
    {
        string key = typeof(T).FullName + ":" + expression.ToString();
        object o;  cache.TryGetValue(key, out o);
        Func<T, string> method = (Func<T, string>)o;
        if (method == null)
        {
            method = expression.Compile();
            cache[key] = method;
        }
        return method.Invoke(input);
    }
于 2013-11-06T18:32:18.477 に答える