在.NET中手动实现高性能算法

Question

作为一种学习经历,我最近尝试使用 C#中的3路分区实现Quicksort.

除了需要在递归调用之前在左/右变量上添加额外的范围检查之外,它似乎工作得很好.

我事先知道框架在List <>中提供了内置的Quicksort实现.排序(通过Array.Sort).所以我尝试了一些基本的分析来比较性能.结果:内置的List <>.Sort方法在同一个列表上运行,比我自己的手动实现快10倍.

使用反射器,我发现List <>中的实际排序.排序是在外部代码中实现的,而不是IL(在名为tryszsort()的函数中).

看看我自己的Quicksort实现,我希望用迭代替换递归调用可能会有所改进.此外,禁用数组边界检查(如果可能)也可以带来一些好处.也许这会更接近内置实现,但我不自信.

所以我的问题是:期望在优化算法(用.NET IL编写,与本机代码相匹配)中的性能是否可以与外部实现的算法的性能竞争？

再一次,我意识到Quicksort是框架的一部分,这对我来说只是一次学习经历.然而,还有许多算法(CRC32可以想到)未提供,但仍然可能对许多应用程序有很大价值.这是关于在.NET中实现CRC32和性能问题的相关问题.

因此,如果您需要在.NET中实现这样的算法,需要了解哪些主要的性能注意事项,以便您的算法至少可以接近外部代码的性能？

[更新]

通过更改算法以在Int的简单数组上操作而不是List,我将执行速度提高到内置Array.Sort的大约10%以内.在Reflector中,我可以看到这避免了对列表中的每个get或set上的Callvirt()操作.我认为这可能会改善一些事情,但我对此感到惊讶.

Answer 1

通过使用非递归代码,特别是使用"不安全"块和指针算法(如果适用),您实际上可以通过使用C#编写的算法看到x5或x10性能增益.与性能一样(在处理托管环境时更是如此),在您尝试并对其进行基准测试之前,您永远不会知道.

现在,一般来说,你应该主要用C#写东西,然后优化它,再多一点优化它,如果它仍然不够好,找出确切的关键代码并将其移植到C++(同时注意限制数量)托管/本地呼叫边界).