Подтвердить что ты не робот

Кэширование Скомпилированное дерево выражений

Как эффективно кэшировать методы, скомпилированные из дерева выражений?

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 завершится с ошибкой.

4b9b3361

ОТВЕТЫ

Ответ 1

Я нашел довольно давно в этой статье, в которой раскрываются все преимущества и недостатки кеширования экспрессии (с постоянным извлечением... который позволяет вы должны скомпилировать .Where(t=>t.prop==3) и .Where(t=>t.prop==5) одному и тому же делегату).

Ответ 2

Проблемы с кэшированием деревьев выражений в централизованном кеше:

  • Вам потребуются всесторонние алгоритмы сравнения и хэширования.
  • Вам нужно будет реализовать эти алгоритмы самостоятельно, поскольку стандартные типы выражений не предоставляют их из коробки.

Полное сравнение сравнений будет дорогостоящим, но стоимость может быть уменьшена с помощью дешевой хэш-функции. Кроме того, поскольку деревья выражений неизменяемы, вы можете кэшировать хеш-код после того, как вы рассчитали его в первый раз. Это может сэкономить время на поиск, но каждый раз, когда вы проверяете кеш с помощью только что созданного выражения в качестве ключа (который, я думаю, будет в большинстве случаев), вам, по крайней мере, нужно будет хешировать новое выражение.

Вариант 1: локальное/статическое кэширование

Идеальное решение позволило бы избежать всех этих накладных расходов. Если это возможно (т.е. Если эти выражения не составлены динамически), лучше всего просто кешировать деревья выражений рядом с сайтами объявлений. Вы должны уметь хранить большинство (если не все) из них в статических полях:

private static readonly Expression<Func<int, string>> _addOne =
    i => (i + 1).ToString();
private static readonly Expression<Func<int, string>> _addTwo =
    i => (i + 2).ToString();

public void SomeToStringCalls()
{
    ToString(_addOne, 1);
    ToString(_addOne, 2);
    ToString(_addTwo, 3);
    ToString(_addTwo, 4);
}

Недостатком является то, что в конечном итоге вы можете использовать повторяющиеся выражения для разных типов, но если вы не генерируете очень большое количество выражений, это может не быть проблемой.

Вариант 2: Централизованное кэширование

Если это не вариант для вас, вам потребуется реализовать централизованный кэш и алгоритмы хэширования и равенства, необходимые для этого. Алгоритм хеширования поможет вам сузить набор кандидатов, поэтому важно, чтобы он работал достаточно хорошо, т.е. Производил очень мало коллизий на практике. Однако, учитывая сложный характер деревьев выражений, вы хотите снизить издержки. Поэтому я бы посоветовал вам не стремиться к идеальной хэширующей функции, но достаточно дешевой, но эффективной. Возможно, что-то вроде этого:

internal static class ExpressionHasher
{
    private const int NullHashCode = 0x61E04917;

    [ThreadStatic]
    private static HashVisitor _visitor;

    private static HashVisitor Visitor
    {
        get
        {
            if (_visitor == null)
                _visitor = new HashVisitor();
            return _visitor;
        }
    }

    public static int GetHashCode(Expression e)
    {
        if (e == null)
            return NullHashCode;

        var visitor = Visitor;

        visitor.Reset();
        visitor.Visit(e);

        return visitor.Hash;
    }

    private sealed class HashVisitor : ExpressionVisitor
    {
        private int _hash;

        internal int Hash
        {
            get { return _hash; }
        }

        internal void Reset()
        {
            _hash = 0;
        }

        private void UpdateHash(int value)
        {
            _hash = (_hash * 397) ^ value;
        }

        private void UpdateHash(object component)
        {
            int componentHash;

            if (component == null)
            {
                componentHash = NullHashCode;
            }
            else
            {
                var member = component as MemberInfo;
                if (member != null)
                {
                    componentHash = member.Name.GetHashCode();

                    var declaringType = member.DeclaringType;
                    if (declaringType != null && declaringType.AssemblyQualifiedName != null)
                        componentHash = (componentHash * 397) ^ declaringType.AssemblyQualifiedName.GetHashCode();
                }
                else
                {
                    componentHash = component.GetHashCode();
                }
            }

            _hash = (_hash * 397) ^ componentHash;
        }

        public override Expression Visit(Expression node)
        {
            UpdateHash((int)node.NodeType);
            return base.Visit(node);
        }

        protected override Expression VisitConstant(ConstantExpression node)
        {
            UpdateHash(node.Value);
            return base.VisitConstant(node);
        }

        protected override Expression VisitMember(MemberExpression node)
        {
            UpdateHash(node.Member);
            return base.VisitMember(node);
        }

        protected override MemberAssignment VisitMemberAssignment(MemberAssignment node)
        {
            UpdateHash(node.Member);
            return base.VisitMemberAssignment(node);
        }

        protected override MemberBinding VisitMemberBinding(MemberBinding node)
        {
            UpdateHash((int)node.BindingType);
            UpdateHash(node.Member);
            return base.VisitMemberBinding(node);
        }

        protected override MemberListBinding VisitMemberListBinding(MemberListBinding node)
        {
            UpdateHash((int)node.BindingType);
            UpdateHash(node.Member);
            return base.VisitMemberListBinding(node);
        }

        protected override MemberMemberBinding VisitMemberMemberBinding(MemberMemberBinding node)
        {
            UpdateHash((int)node.BindingType);
            UpdateHash(node.Member);
            return base.VisitMemberMemberBinding(node);
        }

        protected override Expression VisitMethodCall(MethodCallExpression node)
        {
            UpdateHash(node.Method);
            return base.VisitMethodCall(node);
        }

        protected override Expression VisitNew(NewExpression node)
        {
            UpdateHash(node.Constructor);
            return base.VisitNew(node);
        }

        protected override Expression VisitNewArray(NewArrayExpression node)
        {
            UpdateHash(node.Type);
            return base.VisitNewArray(node);
        }

        protected override Expression VisitParameter(ParameterExpression node)
        {
            UpdateHash(node.Type);
            return base.VisitParameter(node);
        }

        protected override Expression VisitTypeBinary(TypeBinaryExpression node)
        {
            UpdateHash(node.Type);
            return base.VisitTypeBinary(node);
        }
    }
}

Это не идеально, но он должен получить хорошие результаты:

  • Он сверлит и включает в себя каждое выражение в дереве.
  • Как минимум, NodeType каждого подвыражения включается в хэш. Одним из очевидных (но потенциально дорогостоящих) улучшений будет также включение Type; попробуйте, если вы обнаружите, что получаете слишком много конфликтов.
  • Включены члены и типы, на которые ссылается выражение.
  • Включены постоянные значения, отображаемые в дереве.
  • Это не требует выполнения кучи, за счет того, что он не является реентерабельным (поскольку вы анализируете только выражение верхнего уровня, это прекрасно). Вы можете запускать его одновременно на нескольких потоках.

Поскольку вы фактически не переопределяете GetHashCode() для любого из типов выражений, несовершенства хеширующей функции не будут просачиваться и влиять на внешний код. Это дает нам определенную свободу в изгибе правил хэш-функций.

Ваше сравнение равенства должно быть более полным. В то время как функция хэширования является фактически "оценкой", используемой для минимизации вашего набора кандидатов, сравнение равенства выполняет фактическое сопоставление, и оно должно быть совершенным. Вы могли бы использовать мое предложенное решение хеширования как шаблон для того, как подойти к проблеме, но помните, что вы должны выполнить исчерпывающее сравнение всех атрибутов выражения. Следует иметь в виду, что вы, вероятно, не хотите сравнивать имена узлов ParameterExpression в дереве, но вам нужно поддерживать отображение параметров/переменных в двух деревьях, которые вы сравниваете с убедитесь, что они представляют "то же" значение в контексте своего родительского дерева выражений.

За исключением игнорирования имен параметров/переменных, не пытайтесь решить "семантическую эквивалентность", т.е. выражения, которые дают одинаковые результаты и побочные эффекты, но не являются структурно идентичными. Это невозможно сделать эффективно, и не стоит этого пытаться.

Наконец, вы можете ускорить процесс путем реализации двухуровневого поиска: во-первых, выберите правильный кеш на основе типов параметров, затем найдите соответствие в этом кеше. Такой подход был бы наиболее эффективным, если бы гарантировано, что каждое лямбда-выражение будет иметь ровно один аргумент. Преимущества будут деградировать с большим количеством аргументов.

Ответ 3

Причина, по которой вы не можете использовать Dictionary<Expression<Func<T, string>>, Func<T, string>>, состоит в том, что Expression<T> GetHashCode недостаточно умен, чтобы обнаружить "равные" выражения. Я не уверен, но вполне вероятно, что Expression<T>.GetHashCode возвращает адрес памяти выражения.

Чтобы решить эту проблему, вы можете ввести более "умный" хэш-расчет. Пусть рассмотрим равные выражения, имеющие равные тела. Это довольно скользкий путь, но если вы готовы взять на себя ответственность за то, чтобы:

  • Нет двух разных выражений, имеющих один и тот же хэш-код
  • Два выражения с одним и тем же телом имеют одинаковый хэш-код

вы могли бы достичь того, чего хотите.

Здесь просто доказательство кода концепции Я собрал для вас в pastebin. Это не промышленная сила (некоторые намеки на комментарии для ее улучшения), однако она наглядно демонстрирует осуществимость подхода.

Несколько вещей, которые следует рассмотреть, прежде чем разрабатывать: неправильная хеш-функция может привести к довольно сложным ошибкам. Итак, подумайте дважды, напишите много модульных тестов и жертву:)

Ответ 4

Проблема, которую вы описываете, является серьезной в том смысле, что оценка двух выражений для семантического равенства по крайней мере так же дорого, как компиляция выражения. Чтобы проиллюстрировать это, здесь является ссылкой на реализацию для выражения равенства. Эта реализация не идеальна, например:

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

В приведенном выше примере MethodA и MethodB эквивалентны в том смысле, что они делают то же самое, и вы, скорее всего, захотите считать их эквивалентными. Например, построение этого в С# с включенной оптимизацией компилятора заменит вызов MethodB на вызовы MethodA. При сравнении кода существует множество проблем, и это тема текущих исследований.

Вы должны рассмотреть дизайн, в котором выражения ссылаются на какой-то ключ, который идентифицирует его, если вы обнаружите, что компиляция выражений является узким местом в вашем приложении. К тому времени, когда вы определили равенство, вы могли бы скомпилировать его.

Чтобы прокомментировать ответ J0HN, он сравнивает хэш-код тела и параметров, это отнюдь не надежное решение, так как оно не делает глубокую оценку дерева выражений.

Кроме того, посмотрите этот вопрос, как опубликовано в комментариях.

Ответ 5

Если ваша цель состоит в том, чтобы скомпилировать + invoke для выражения "extract value" из выражения, возможно, вы смотрите другим способом.

Я пытаюсь извлечь значение из дерева выражений без компиляции через отражение.

Мое решение не полностью поддерживает все выражения, сначала оно было написано для активации метода кэширования без лямбда и арифметики, но с некоторыми улучшениями он может помочь.

Вот он:

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()

Ответ 6

Назовите меня упрощенным, но это кажется примерно в 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);
    }