Jul*_*iet 18 c# performance inheritance
我在C#中编写不可变二进制树的不同实现,我希望我的树从基类继承一些常用方法.
不幸的是,它从基类派生类是一败涂地缓慢.非派生类可以充分发挥作用.以下是两个几乎相同的AVL树实现,用于演示:
这两棵树具有完全相同的代码,但我在基类中移动了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<int, int> f)
{
var seeds = new int[] { 314159265, 271828183, 231406926, 141421356, 161803399, 266514414, 15485867, 122949829, 198491329, 42 };
var times = new List<double>();
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<double>.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<double>.Create((x, y) => x.CompareTo(y));
for (int i = 0; i < VALUE_COUNT; i++)
{
avlTree2 = avlTree2.Insert(rnd.NextDouble());
}
return avlTree2.Count;
}
}
}
我的探查器表明该程序花费了过多的时间BaseBinaryTree.Insert.任何有兴趣的人都可以看到我用上面的代码创建的EQATEC日志文件(你需要EQATEC分析器才能理解文件).
我真的想为所有二叉树使用一个公共基类,但如果性能受损,我不能这样做.
是什么导致我的DerivedAvlTree表现如此糟糕,我该怎么做才能解决它？
Aar*_*ght 17
注意 - 这里现在有一个"干净"的解决方案,所以如果您只想要一个运行速度快且不关心所有侦探工作的版本,请跳到最终编辑.
它似乎不是导致速度减慢的直接和虚拟呼叫之间的区别.这与那些代表有关; 我不能完全解释它是什么,但是看看生成的IL会显示很多缓存的委托,我认为它们可能不会在基类版本中使用.但是IL本身在两个版本之间似乎并没有显着差异,这使我相信抖动本身是部分责任.
看看这个重构,它将运行时间减少了大约60%:
public virtual TreeType Insert(T value)
{
Func<TreeType, T, TreeType, TreeType> 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<TreeType>(value, nodeFunc);
}
private TreeType Insert<U>(T value,
Func<TreeType, T, TreeType, TreeType> nodeFunc)
{
return this.Match<TreeType>(
() => CreateNode(Self(), value, Self()),
nodeFunc);
}
这应该(并且显然确实)确保插入委托仅在每次插入时创建一次 - 它不会在每次递归时创建.在我的机器上,它将运行时间从350毫秒减少到120毫秒(相比之下,单级版本在大约30毫秒内运行,所以这仍然远不及它应该的位置).
但在这里它变得更加奇怪 - 在尝试上述重构之后,我想,嗯,也许它仍然很慢,因为我只完成了一半的工作.所以我也尝试了实现第一个代理:
public virtual TreeType Insert(T value)
{
Func<TreeType> nilFunc = () => CreateNode(Self(), value, Self());
Func<TreeType, T, TreeType, TreeType> 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<TreeType>(value, nilFunc, nodeFunc);
}
private TreeType Insert<U>(T value, Func<TreeType> nilFunc,
Func<TreeType, T, TreeType, TreeType> nodeFunc)
{
return this.Match<TreeType>(nilFunc, nodeFunc);
}
猜猜是什么......这让它再次变慢了!有了这个版本,在我的机器上,这次运行花费了超过250毫秒.
这违背了可能将问题与编译的字节码相关联的所有逻辑解释,这就是为什么我怀疑抖动是在这个阴谋中.我认为上面的第一个"优化"可能是(警告 - 前面的猜测)允许插入委托内联 - 这是一个众所周知的事实,即抖动不能内联虚拟调用 - 但仍有其他内容没有内联,这就是我现在很难过.
我的下一步是通过选择性地禁用对某些方法的内联,MethodImplAttribute并查看它对运行时的影响 - 这将有助于证明或反驳这一理论.
我知道这不是一个完整的答案,但希望它至少可以为您提供一些工作,并且可能对此分解进行一些进一步的实验可以产生与原始版本性能接近的结果.
编辑:哈,在我提交之后,我偶然发现了另一个优化.如果将此方法添加到基类:
private TreeType CreateNilNode(T value)
{
return CreateNode(Self(), value, Self());
}
现在运行时间下降到38毫秒,仅略高于原始版本.这让我大吃一惊,因为实际上并没有提到这种方法! 私有Insert<U>方法仍然与我的答案中的第一个代码块相同.我打算改变第一个参数来引用该CreateNilNode方法,但我没有必要.抖动是看到匿名代表与CreateNilNode方法相同并共享正文(可能再次内联),或者......或者,我不知道.这是我见过的第一个实例,其中添加私有方法并且从不调用它可以将程序加速4倍.
你必须检查这一点,以确保我没有意外地引入任何逻辑错误 - 非常确定我没有,代码几乎相同 - 但如果它全部检出,那么你在这里,这几乎像快速为非衍生AvlTree.
进一步更新
我能够提出一个基本/派生组合的版本,实际上运行速度比单一版本略快.采取了一些哄骗,但它的工作原理!
我们需要做的是创建一个专用的插件,只需创建一次所有委托,无需进行任何变量捕获.相反,所有状态都存储在成员字段中.把它放在BaseBinaryTree课堂里:
protected class Inserter
{
private TreeType tree;
private Func<TreeType> nilFunc;
private Func<TreeType, T, TreeType, TreeType> 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<TreeType>(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<T> Insert(T value, Inserter inserter)
{
return base.Insert(value, inserter).Balance();
}
而已.现在运行它.它将花费几乎完全相同的时间AvlTree,通常在发布版本中减少几毫秒.
减速显然是由于虚拟方法,匿名方法和变量捕获的某些特定组合,它以某种方式阻止抖动进行重要优化.我不太确定它是否已经内联,它可能只是在缓存代表,但我认为唯一可以真正详细说明的人就是抖动的人.