Caching Compiled Expression tree

c# expression-trees

Domanda

Come memorizzare in modo efficace i metodi compilati da un albero di espressioni?

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);
}

Sopra, ogni chiamata sta per ricompilare ciascuna espressione, anche se alcune sono identiche. Non riesco ad avere un Dictionary<Expression<Func<T, string>>, Func<T, string>>() cache del metodo compilato dall'espressione perché l' equals fallirà.

Risposta accettata

Ho trovato un po 'di tempo fa questo articolo , che espone pro e contro del caching delle espressioni (con estrazione costante ... che ti permette di compilare .Where(t=>t.prop==3) e .Where(t=>t.prop==5) allo stesso delegato).


Risposta popolare

I problemi con gli alberi di espressione nella cache in una cache centralizzata sono:

  1. Avrai bisogno di algoritmi di confronto e algoritmi di hash completi.
  2. Sarà necessario implementare questi algoritmi autonomamente, poiché i tipi di espressioni standard non li forniscono immediatamente.

Un confronto completo sull'uguaglianza sarà costoso da eseguire, ma il costo può essere alleviato in qualche modo con una funzione hash economica. Inoltre, poiché gli alberi di espressione sono immutabili, è possibile memorizzare nella cache il codice hash dopo averlo calcolato per la prima volta. Ciò potrebbe richiedere un po 'di tempo libero dalle ricerche, ma ogni volta che controlli la cache usando un'espressione appena creata come chiave (che, immagino, sarebbe la maggior parte delle volte) avrai almeno bisogno di cancellare la nuova espressione.

Opzione 1: cache locale / statica

Una soluzione ideale eviterebbe tutto questo sovraccarico. Se è fattibile (cioè, se queste espressioni non sono composte dinamicamente), la soluzione migliore è semplicemente mettere in cache gli alberi di espressione vicino ai loro siti di dichiarazione. Dovresti essere in grado di memorizzare la maggior parte (se non tutte) di questi in campi statici:

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);
}

Lo svantaggio è che potresti finire con espressioni duplicate su vari tipi, ma se non stai generando un numero molto grande di espressioni, questo potrebbe non essere un problema.

Opzione 2: caching centralizzato

Se questa non è un'opzione per te, dovrai implementare una cache centralizzata e gli algoritmi di hashing e di uguaglianza necessari per farlo. L'algoritmo di hashing ti aiuterà a restringere il tuo gruppo di candidati, quindi è importante che funzioni ragionevolmente bene , cioè produca pochissime collisioni nella pratica. Tuttavia, data la natura complessa degli alberi di espressione, si desidera mantenere bassi i costi. Pertanto, ti consiglierei di non mirare ad una perfetta funzione di hashing, ma che sia ragionevolmente economica, ma efficace. Forse qualcosa del genere:

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);
        }
    }
}

Non è perfetto, ma dovrebbe ottenere risultati abbastanza buoni:

  1. Esegue la drill down e include tutte le espressioni nell'albero.
  2. Al minimo, il NodeType di ogni sottoespressione è incluso nell'hash. Un miglioramento ovvio (ma potenzialmente costoso) sarebbe quello di includere anche il Type ; provalo se scopri che stai ricevendo troppe collisioni.
  3. Sono inclusi membri e tipi a cui si fa riferimento nell'espressione.
  4. I valori costanti che appaiono nell'albero sono inclusi.
  5. Non richiede un'allocazione dell'heap per l'esecuzione, a scapito di essere non rientranti (dato che stai analizzando solo un'espressione di livello superiore, va bene). È possibile eseguirlo contemporaneamente su più thread.

Poiché in realtà non si GetHashCode() override di GetHashCode() per nessuno dei tipi di espressione, le imperfezioni della funzione di hashing non si estinguono e influiscono sul codice esterno. Questo ci dà un certo grado di libertà nel piegare le regole delle funzioni di hash.

Il tuo paragone sull'uguaglianza dovrà essere più completo. Mentre la funzione di hashing è effettivamente una "stima" utilizzata per ridurre al minimo il tuo gruppo candidato, il confronto di uguaglianza esegue la corrispondenza effettiva e deve essere perfetto. Potresti certamente usare la mia proposta di soluzione di hashing come modello per come affrontare il problema, ma tieni presente che devi eseguire un confronto esaustivo di tutti gli attributi di una espressione. Una cosa da tenere a mente è che probabilmente non si desidera confrontare i nomi dei nodi ParameterExpression nell'albero, ma si vorrà mantenere una mappatura dei parametri / variabili nei due alberi che si stanno confrontando per assicurarsi rappresentano lo stesso "valore" nel contesto del loro albero di espressione genitore.

Con l'eccezione di ignorare i nomi di parametri / variabili, non preoccupatevi di cercare di risolvere "equivalenza semantica", cioè espressioni che producono gli stessi risultati ed effetti collaterali ma non sono strutturalmente identici. Non può essere fatto in modo efficiente e non vale la pena provarlo.

Infine, potresti essere in grado di velocizzare le cose implementando una ricerca a due livelli: in primo luogo, scegli la cache corretta in base al tipo di parametro, quindi cerca una corrispondenza all'interno di quella cache. Questo approccio sarebbe più efficace se è garantito che ogni espressione lambda avrà esattamente un argomento. I benefici si degraderebbero con più argomenti.



Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow
È legale questo KB? Sì, impara il perché