为什么当我将方法移动到基类中时,我的性能会慢到爬行?

注意 -现在这里有一个“干净”的解决方案,所以跳到最后的编辑,如果你只想一个版本,运行速度快,不关心所有的侦探工作。

似乎并不是直接通话和虚拟通话之间的区别导致了经济放缓。这与那些代表有关;我不能很具体地解释它是什么,但是查看一下生成的IL显示了许多缓存的委托,我认为这些委托可能在基类版本中没有得到使用。但是IL本身在两个版本之间似乎没有明显的不同,这让我相信抖动本身是部分原因。

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毫秒多一点。

这违背了所有可能与编译字节码有关的逻辑解释,这就是为什么我怀疑jitter参与了这个阴谋。我认为上面的第一个“优化”可能是( 警告-前方有猜测 )允许插入委托内联-这是一个已知的事实,抖动不能内联虚拟调用-但仍然有一些其他的问题 不 被内联了,这就是我现在被难住的地方。

我的下一步是通过 MethodImplAttribute 看看它对运行时有什么影响-这将有助于证明或反驳这个理论。

编辑:哈,就在我提交这个之后,我偶然发现了另一个优化。如果将此方法添加到基类:

private TreeType CreateNilNode(T value)
{
    return CreateNode(Self(), value, Self());
}

现在这里的运行时间降到了38ms,仅略高于原始版本。这让我大吃一惊,因为 二等兵 Insert<U> 方法仍然与我答案中的第一个代码块相同。我是 去 CreateNilNode 方法,但我没必要。要么jitter看到匿名委托与 可以将程序速度提高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 对于每个递归调用,由于 以及内部代表。

现在将基类的插入方法替换为:

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 方法 非虚拟的 插入器 实例。改变派生类很简单,只要替换重写的 插入

protected override DerivedAvlTree<T> Insert(T value, Inserter inserter)
{
    return base.Insert(value, inserter).Balance();
}

就这样。现在运行这个。所需时间几乎与 AvlTree公司 ,在发布版本中通常要少几毫秒。

这与派生类调用原始实现,然后也调用Balance无关,是吗?

如果调用((TreeType)this).Method()而不是this.Method(),生活可能会好一点,但很可能无法删除多态调用,除非同时声明重写方法为sealed。即使这样,您也可能需要为此实例支付运行时检查的罚款。

将可重用代码放入基类中的通用静态方法可能也会有所帮助,但我认为您仍然需要为多态调用付费。C类泛型只是不优化C++模板。

你在VS IDE下运行,对吗?要花20倍的时间,对吧?

在它周围环绕一个循环以迭代10次,因此长版本需要20秒。然后在它运行时,点击“暂停”按钮,查看调用堆栈。你将以95%的把握准确地看到问题所在。如果你不相信你看到的,再试几次。它为什么起作用? Here's the long explanation ,和 here's the short one