c# - data - drupal 8 cache
Caching compilado árbol de expresiones (6)
El problema que describe es grave en el sentido de que evaluar dos expresiones para determinar la igualdad semántica es al menos tan costoso como compilar la expresión. Para ilustrar esto, here hay un enlace a una implementación para la igualdad de expresión. Esta implementación no es perfecta, por ejemplo:
MethodA() { MethodB(); }
MethodB() { ... }
En el ejemplo anterior, MethodA y MethodB son equivalentes en el sentido de que hacen lo mismo, y lo más probable es que quieras considerarlos como equivalentes. Por ejemplo, construir esto en C # con la optimización del compilador habilitada reemplazará la llamada a MethodA con MethodA llamadas a MethodA . Hay una gran cantidad de problemas al comparar el código y es un tema de investigación en curso.
Debe considerar un diseño en el que las expresiones estén referenciadas por algún tipo de clave que lo identifique si descubre que compilar las expresiones es el cuello de botella en su aplicación. Para cuando hayas determinado la igualdad, ya podrías haberla compilado.
Para comentar sobre la respuesta de J0HN, compara el código hash del cuerpo y los parámetros, esto no es una solución confiable, ya que no hace una evaluación profunda del árbol de expresiones.
Además, eche un vistazo a esta pregunta como se publicó en los comentarios.
¿Cómo cachear eficientemente los métodos compilados desde un árbol de expresiones?
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);
}
Arriba, cada llamada recompilará cada expresión, incluso si algunas son idénticas. No puedo tener un Dictionary<Expression<Func<T, string>>, Func<T, string>>() almacena en caché el método compilado de la expresión porque los equals fallarán.
Encontré hace bastante tiempo este artículo , que expone los pros y los contras del almacenamiento en caché de expresiones (con extracción constante ... que le permite compilar .Where(t=>t.prop==3) y .Where(t=>t.prop==5) al mismo delegado).
La razón por la que no puede usar Dictionary<Expression<Func<T, string>>, Func<T, string>> es que Expression<T> GetHashCode no es lo suficientemente inteligente como para detectar expresiones "iguales". No estoy seguro, pero es muy probable que la Expression<T>.GetHashCode devuelva la dirección de memoria de la expresión.
Para resolver este problema, podría introducir un cálculo de hash más "inteligente". Consideremos expresiones iguales que tienen cuerpos iguales. Es un camino bastante resbaladizo, pero si está dispuesto a asumir la responsabilidad de garantizar que:
- No hay dos expresiones diferentes que tengan el mismo código hash
- Dos expresiones con el mismo cuerpo tienen el mismo código hash
Podrías lograr lo que quieras.
Aquí hay una simple prueba de código de concepto que he reunido para usted en pastebin. No es la fuerza industrial (algunos consejos en los comentarios para mejorarla), sin embargo, demuestra claramente la viabilidad del enfoque.
Un par de cosas a considerar antes de seguir elaborando: la función de hash incorrecta puede dar lugar a errores bastante complicados. Entonces, piénsalo dos veces, escribe muchas pruebas unitarias y presa :)
Llámeme simplista, pero esto parece 4 veces más rápido en un escenario simple que probé:
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);
}
Los problemas con el almacenamiento en caché de los árboles de expresión en un caché centralizado son:
- Necesitará una comparación de igualdad completa y algoritmos de hashing.
- Deberá implementar estos algoritmos usted mismo, ya que los tipos de expresión estándar no los proporcionan de forma inmediata.
Una comparación de igualdad completa será costosa de realizar, pero el costo puede aliviarse de alguna manera con una función hash barata. Además, dado que los árboles de expresiones son inmutables, puede almacenar en caché el código hash después de haberlo calculado por primera vez. Esto puede reducir el tiempo de las búsquedas, pero cada vez que revise el caché utilizando una expresión recién creada como la clave (que, me imagino, sería la mayor parte del tiempo), al menos tendrá que marcar la nueva expresión.
Opción 1: almacenamiento en caché local / estático
Una solución ideal evitaría todos estos gastos generales. Si es factible (es decir, si estas expresiones no están compuestas dinámicamente), su mejor opción es simplemente almacenar en caché los árboles de expresión cerca de sus sitios de declaración. Debería poder almacenar la mayoría (si no todos) de estos en campos estáticos:
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);
}
El inconveniente es que puede terminar con expresiones duplicadas en varios tipos, pero si no está generando una gran cantidad de expresiones, esto puede no ser un problema.
Opción 2: almacenamiento en caché centralizado
Si esa no es una opción para usted, deberá implementar un caché centralizado y los algoritmos de hashing e igualdad requeridos para hacerlo. El algoritmo de hash le ayudará a reducir su conjunto de candidatos, por lo que es importante que funcione razonablemente bien , es decir, que produzca muy pocas colisiones en la práctica. Sin embargo, dada la naturaleza compleja de los árboles de expresión, usted quiere mantener los costos bajos. Por lo tanto, le aconsejaría que no apunte a una función de hash perfecta, sino que sea razonablemente barata pero efectiva. Quizás algo como esto:
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);
}
}
}
No es perfecto, pero debería obtener buenos resultados:
- Profundiza e incluye cada expresión en el árbol.
- Como mínimo, el
NodeTypedeNodeTypede cadaNodeTypese incluye en el hash. Una mejora obvia (pero potencialmente costosa) sería incluir también elType; Pruébalo si encuentras que estás recibiendo demasiadas colisiones. - Se incluyen los miembros y tipos referidos en la expresión.
- Se incluyen los valores constantes que aparecen en el árbol.
- No requiere una asignación de montón para ejecutarse, a costa de no ser reentrante (ya que solo está analizando una expresión de nivel superior, esto está bien). Puede ejecutarlo simultáneamente en varios subprocesos.
Dado que en realidad no está anulando GetHashCode() para ninguno de los tipos de expresión, las imperfecciones de la función de hash no se filtrarán y afectarán al código externo. Esto nos da un grado de libertad al doblar las reglas de las funciones hash.
Tu comparación de igualdad tendrá que ser más completa. Mientras que la función de hash es efectivamente una ''estimación'' utilizada para minimizar su conjunto de candidatos, la comparación de igualdad realiza la coincidencia real, y debe ser perfecta. Ciertamente, podría usar mi solución de hashing propuesta como una plantilla para abordar el problema, pero tenga en cuenta que debe realizar una comparación exhaustiva de todos los atributos de una expresión. Una cosa a tener en cuenta es que probablemente no desee comparar los nombres de los nodos de ParameterExpression en el árbol, pero querrá mantener una asignación de los parámetros / variables en los dos árboles que está comparando para asegurarse representan el "mismo" valor en el contexto de su árbol de expresión principal.
Con la excepción de ignorar los nombres de parámetros / variables, no se moleste en intentar resolver la "equivalencia semántica", es decir, las expresiones que producen los mismos resultados y efectos secundarios pero que no son estructuralmente idénticos. No se puede hacer de manera eficiente, y no vale la pena intentarlo.
Por último, puede acelerar las cosas implementando una búsqueda de dos niveles: primero, elija la memoria caché correcta en función del tipo de parámetro y luego busque una coincidencia dentro de esa memoria caché. Este enfoque sería más efectivo si se garantiza que cada expresión lambda tendrá exactamente un argumento. Los beneficios se degradarían con más argumentos.
Si su objetivo es compilar + invocar para "extraer valor" de la expresión, puede que busque en otra forma.
Intento extraer valor del árbol de expresiones sin compilar a través de la reflexión.
Mi solución no es totalmente compatible con todas las expresiones, al principio se escribió para invocar el método de almacenamiento en caché sin lambda y aritmética, pero con algunas mejoras puede ayudar.
Aquí está:
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;
}
Con uso:
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;
}
Creo que, con algunas mejoras y tipos de expresiones adicionales, esta solución podría ser una alternativa más rápida para Compile (). DynamicInvoke ()