为什么我的表现慢慢爬行我将方法移动到基类？
我在C＃中编写了不可变二进制树的不同实现，我希望我的树从基类inheritance一些常用方法。
不幸的是，从基类派生的类非常慢。 非派生类可以充分发挥作用。 以下是两个几乎相同的AVL树实现，用于演示：
- AvlTree： http ：//pastebin.com/V4WWUAyT
- DerivedAvlTree： http ：//pastebin.com/PussQDmN
这两棵树的代码完全相同 ，但我在基类中移动了DerivedAvlTree.Insert方法。 这是一个测试应用程序：
using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using Juliet.Collections.Immutable; namespace ConsoleApplication1 { class Program { const int VALUE_COUNT = 5000; static void Main(string[] args) { var avlTreeTimes = TimeIt(TestAvlTree); var derivedAvlTreeTimes = TimeIt(TestDerivedAvlTree); Console.WriteLine("avlTreeTimes: {0}, derivedAvlTreeTimes: {1}", avlTreeTimes, derivedAvlTreeTimes); } static double TimeIt(Func f) { var seeds = new int[] { 314159265, 271828183, 231406926, 141421356, 161803399, 266514414, 15485867, 122949829, 198491329, 42 }; var times = new List(); foreach (int seed in seeds) { var sw = Stopwatch.StartNew(); f(seed); sw.Stop(); times.Add(sw.Elapsed.TotalMilliseconds); } // throwing away top and bottom results times.Sort(); times.RemoveAt(0); times.RemoveAt(times.Count - 1); return times.Average(); } static int TestAvlTree(int seed) { var rnd = new System.Random(seed); var avlTree = AvlTree.Create((x, y) => x.CompareTo(y)); for (int i = 0; i < VALUE_COUNT; i++) { avlTree = avlTree.Insert(rnd.NextDouble()); } return avlTree.Count; } static int TestDerivedAvlTree(int seed) { var rnd = new System.Random(seed); var avlTree2 = DerivedAvlTree.Create((x, y) => x.CompareTo(y)); for (int i = 0; i < VALUE_COUNT; i++) { avlTree2 = avlTree2.Insert(rnd.NextDouble()); } return avlTree2.Count; } } } - AvlTree：在121毫秒内插入5000个项目
- DerivedAvlTree：在2182毫秒内插入5000个项目
我的探查器表明该程序在BaseBinaryTree.Insert花费了过多的时间。 任何有兴趣的人都可以看到我用上面的代码创建的EQATEC日志文件 （你需要EQATEC分析器才能理解文件）。
我真的想为所有二叉树使用一个公共基类，但如果性能受到影响，我就不能这样做。
是什么导致我的DerivedAvlTree表现如此糟糕，我该怎么做才能解决它？
注意 – 这里现在有一个“干净”的解决方案，所以如果你只想要一个运行速度快且不关心所有侦探工作的版本，请跳到最终编辑。
它似乎并没有导致速度减慢的直接和虚拟呼叫之间的区别。 这与那些代表有关; 我不能完全解释它是什么，但是看一下生成的IL会显示很多缓存的委托，我认为这些委托可能不会在基类版本中使用。 但是IL本身在两个版本之间似乎并没有显着差异，这让我相信抖动本身是部分责任。
看看这个重构，它将运行时间减少了大约60％：
public virtual TreeType Insert(T value) { Func nodeFunc = (l, x, r) => { int compare = this.Comparer(value, x); if (compare < 0) { return CreateNode(l.Insert(value), x, r); } else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); } return Self(); }; return Insert(value, nodeFunc); } private TreeType Insert(T value, Func nodeFunc) { return this.Match( () => CreateNode(Self(), value, Self()), nodeFunc); }
这应该（并且显然确实）确保插入委托仅在每次插入时创建一次 – 它不会在每次递归时创建。 在我的机器上，它将运行时间从350毫秒减少到120毫秒（相比之下，单级版本在大约30毫秒内运行，所以这仍然远不及它应该的位置）。
但是在这里它变得更加奇怪 – 在尝试上述重构之后，我想，嗯，也许它仍然很慢，因为我只完成了一半的工作。 所以我也尝试了实现第一个代理：
public virtual TreeType Insert(T value) { Func nilFunc = () => CreateNode(Self(), value, Self()); Func nodeFunc = (l, x, r) => { int compare = this.Comparer(value, x); if (compare < 0) { return CreateNode(l.Insert(value), x, r); } else if (compare > 0) { return CreateNode(l, x, r.Insert(value)); } return Self(); }; return Insert (value, nilFunc, nodeFunc); } private TreeType Insert(T value, Func nilFunc, Func nodeFunc) { return this.Match (nilFunc, nodeFunc); }
猜猜是什么……这让它再次变慢了！ 有了这个版本，在我的机器上，这次运行花费了超过250毫秒。
这违背了可能将问题与编译的字节码相关联的所有逻辑解释，这就是为什么我怀疑抖动是在这个阴谋中。 我认为上面的第一个“优化”可能是（ 警告 – 前面的猜测 ）允许插入委托内联 – 这是一个众所周知的事实，即抖动不能内联虚拟调用 – 但仍有其他内容没有内联，这就是我现在很难过。
我的下一步是通过MethodImplAttribute选择性地禁用对某些方法的内联，并查看它对运行时的影响 – 这将有助于certificate或反驳这一理论。
我知道这不是一个完整的答案，但希望它至少可以为你提供一些工作，也许这种分解的一些进一步实验可以产生与原始版本性能接近的结果。
编辑：哈，在我提交之后，我偶然发现了另一个优化。 如果将此方法添加到基类：
private TreeType CreateNilNode(T value) { return CreateNode(Self(), value, Self()); }
现在运行时间下降到38毫秒，仅略高于原始版本。 这让我大吃一惊，因为实际上并没有提到这种方法！ 私有的Insert方法仍然与我的答案中的第一个代码块相同。 我打算更改第一个参数来引用CreateNilNode方法，但我没有必要。 抖动是看到匿名委托与CreateNilNode方法相同并共享正文（可能再次内联），或者……或者，我不知道。 这是我见过的第一个实例，其中添加私有方法并且从不调用它可以将程序加速4倍。
你必须检查这一点，以确保我没有意外地引入任何逻辑错误 – 非常确定我没有，代码几乎相同 – 但如果它全部检查出来，那么你在这里，这几乎像快速作为非衍生的AvlTree 。
进一步更新
我能够提出一个基本/派生组合的版本，实际上运行速度比单一版本略快 。 采取了一些哄骗，但它的工作原理！
我们需要做的是创建一个专用的插件，只需创建一次所有委托，无需进行任何变量捕获。 相反，所有状态都存储在成员字段中。 把它放在BaseBinaryTree类中：
protected class Inserter { private TreeType tree; private Func nilFunc; private Func nodeFunc; private T value; public Inserter(T value) { this.nilFunc = () => CreateNode(); this.nodeFunc = (l, x, r) => PerformMatch(l, x, r); this.value = value; } public TreeType Insert(TreeType parent) { this.tree = parent; return tree.Match (nilFunc, nodeFunc); } private TreeType CreateNode() { return tree.CreateNode(tree, value, tree); } private TreeType PerformMatch(TreeType l, T x, TreeType r) { int compare = tree.Comparer(value, x); if (compare < 0) { return tree.CreateNode(l.Insert(value, this), x, r); } else if (compare > 0) { return tree.CreateNode(l, x, r.Insert(value, this)); } return tree; } }
是的，是的，我知道，使用这个可变的内部tree状态是非常不起作用的，但请记住，这不是树本身，它只是一个一次性的“可运行”实例。 没有人说perf-opt很漂亮！ 这是避免为每个递归调用创建一个新的Inserter的唯一方法，否则会因为Inserter及其内部委托的所有新分配而降低这一速度。
现在将基类的插入方法替换为：
public TreeType Insert(T value) { return Insert(value, null); } protected virtual TreeType Insert(T value, Inserter inserter) { if (inserter == null) { inserter = new Inserter(value); } return inserter.Insert(Self()); }
我已将公共Insert方法设为非虚拟 ; 所有实际工作都委托给一个受保护的方法，该方法接受（或创建自己的） Inserter实例。 更改派生类很简单，只需用以下代码替换重写的Insert方法：
protected override DerivedAvlTree Insert(T value, Inserter inserter) { return base.Insert(value, inserter).Balance(); }
而已。 现在运行它。 它将花费几乎与AvlTree相同的时间，通常在发布版本中减少几毫秒。
减速显然是由于虚拟方法，匿名方法和变量捕获的某些特定组合，它以某种方式阻止抖动进行重要优化。 我不太确定它是否已经内联，它可能只是在缓存代表，但我认为唯一可以真正详细说明的人就是抖动的人。
它与调用原始实现的派生类没有任何关系，然后调用Balance，是吗？
我想你可能需要查看生成的机器代码，看看有什么不同。 我从源代码中可以看到，你已经将很多静态方法转换为多态的虚方法…在第一种情况下，JIT确切地知道将调用什么方法并且可以执行直接调用指令，甚至可能排队。 但是通过多态调用，它别无选择，只能进行v表查找和间接调用。 该查找代表了正在完成的工作的很大一部分。
如果你调用（（TreeType）this）.Method（）而不是this.Method（），生活可能会好一点。但是你可能无法删除多态调用，除非你还将覆盖方法声明为密封。 即使这样，您也可以在此实例上支付运行时检查的代价。
将可重用代码放入基类中的通用静态方法也可能有所帮助，但我认为您仍然需要为多态调用付费。 C＃generics只是不像C ++模板那样进行优化。
你在VS IDE下运行，对吧？ 它花了大约20倍，对吧？
绕一圈循环迭代10次，所以长版需要20秒。 然后在它运行时，点击“暂停”按钮，然后查看调用堆栈。 你会看到95％确定性的确切问题。 如果你不相信你所看到的，那就试试几次吧。 它为什么有效？ 这是一个很长的解释 ， 这里是简短的 解释 。