Блог

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

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

 for (int i = 0; i < count;   i) {
    ref Expr expr = ref expressions[i];
    switch (expr.Type) {
        case Op.Addition:
            expr.Value = expressions[expr.Operand1].Value   expressions[expr.Operand2].Value;
            break;
        case ...
    }
}
 

Я также оцениваю производные, используя обратную автоматическую дифференциацию. Это включает в себя итерацию дерева сверху вниз и вычисление сопряженного для каждого выражения. Для каждого типа выражения существуют простые правила:

 ref Expr root = ref expressions[expressions.Length - 1];
root.Adjoint = 1.0;

for (int i = expressions.Length - 1; i >= 0; --i) {
    ref Expr expr = ref expressions[i];
    switch (expr.Type) {
        case Op.Addition:
            ref Expr left = ref expressions[expr.Operand1];
            ref Expr right = ref expressions[expr.Operand2];
            left.Adjoint  = expr.Adjoint;
            right.Adjoint  = expr.Adjoint;
            break;
        case ...
    }
}
 

Чтобы избежать ветвления, я подумал, что скомпилирую это дерево выражений, создав код IL. Для этого я снова повторяю итерацию снизу вверх по дереву и выдаю инструкции для вычисления значений выражений. Аналогично, я повторяю сверху вниз и выдаю инструкции для вычисления сопряжений. Затем я получаю две большие функции, которые вычисляют значения и сопряженные для всех выражений без каких-либо ветвлений.

 var method = new DynamicMethod("Evaluate", typeof(void), new Type[] { typeof(double[]) }, true);
var il = method.GetILGenerator();

for (int i = 0; i < expressions.Length;   i) {
    ref Expr expr = ref expressions[i];
    switch (expr.Type) {
        case Op.Addition:
            il.Emit(OpCodes.Ldarg_0);
            il.Emit(OpCodes.Ldc_I4, expr.Index);
            il.Emit(OpCodes.Ldarg_0);
            il.Emit(OpCodes.Ldc_I4, expr.Operand1);
            il.Emit(OpCodes.Ldelem_R8);
            il.Emit(OpCodes.Ldarg_0);
            il.Emit(OpCodes.Ldc_I4, expr.Operand2);
            il.Emit(OpCodes.Ldelem_R8);
            il.Emit(OpCodes.Add);
            il.Emit(OpCodes.Stelem_R8);
        case ...
    }
}

il.Emit(OpCodes.Ret);
evaluate = method.CreateDelegate<EvaluateFunction>();
 

Для небольших деревьев выражений это оказалось довольно эффективным. Время на оценку дерева было довольно значительно сокращено. Однако для больших деревьев выражений скомпилированная функция оценки фактически становится медленнее.

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