C#编译表达式树求值在规模较大时速度变慢的原因是什么？
问题描述
我生成了一个包含简单数学表达式的表达式树，支持的表达式类型仅限常量、变量、加法、减法、乘法、除法、取反、sqrt及少量三角函数。变量和常量性质类似，但值可以修改。
我采用自底向上遍历的方式执行表达式树求值，需要对表达式类型做switch分支判断，示例代码如下：
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 ... } }
同时我使用反向自动微分计算导数，采用自顶向下遍历的方式为每个表达式计算adjoint，不同表达式类型对应不同的计算规则，示例代码如下：
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代码的方式编译表达式树：同样自底向上遍历树生成求值指令，自顶向下遍历生成adjoint计算指令，最终得到两个无分支的大型函数，分别完成所有表达式的求值和adjoint计算任务，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>();
这种方案在处理小型表达式树时效果很好，求值耗时大幅降低，但当表达式树规模较大时，编译后的求值函数运行速度反而更慢，性能表现如下图：
请问导致这一现象的原因是什么？目前我猜测可能和大型函数的指令缓存大小有关，但该函数无任何分支，理论上指令加载效率应该很高，希望得到专业解答。
原因分析
指令缓存失效是核心原因
你的猜测方向正确。无分支不代表指令加载效率高，现代CPU的L1指令缓存（L1 I-cache）容量通常仅为32KB或64KB，你生成的单条表达式操作对应的IL，经过JIT编译为x64原生指令后体积约为15~20字节，当表达式节点规模超过3000时，原生指令总大小就会超过64KB，无法完全放入L1 I-cache。此时CPU需要频繁从L2、L3缓存甚至内存加载指令，指令访问延迟会比L1命中高4~100倍不等。
而原来带switch的循环实现，整个循环的原生指令总大小仅几十字节，可以完全常驻L1 I-cache，每次循环都命中缓存。同时现代CPU的分支预测器对这种固定顺序的switch分支预测准确率接近100%，分支预测失败的开销远低于指令缓存失效的开销。寄存器分配效率低下
你生成的IL代码中，每个操作都重复执行加载数组基址、加载索引、读取元素、回写结果的操作，没有利用寄存器复用中间结果。且超大函数的寄存器分配压力极高，.NET JIT会将大量临时值溢出到栈内存，额外增加了内存访问开销。而循环实现中JIT可以将数组基址、循环变量等高频访问数据缓存在寄存器中，数据访问效率更高。JIT优化降级
.NET的JIT编译器对超大函数会跳过很多优化策略，包括指令重排、常量传播、公共子表达式消除等，生成的原生代码本身执行效率就低于对小循环做过充分优化的代码。
优化建议
- 可以采用分块编译的方案：将表达式树按节点规模拆分为多个大小在100~200节点的子块，每个子块编译为独立的小函数，外层用循环调用这些子函数，既保留了无分支计算的优势，又能让每个子函数的指令完全放入L1 I-cache。
- 优化IL生成逻辑，尽可能复用栈上的临时值，减少重复的数组加载、存储操作，降低最终原生指令的体积。
内容的提问来源于stack exchange，提问作者Homar
