现代硬件的算法？

Question

再一次，我发现自己有一套 broken assumptions .文章本身通过修改经过验证的最佳算法来考虑虚拟内存，将性能提高了大约 10 倍:

On a modern multi-issue CPU, running at some gigahertz clock frequency, the worst-case loss is almost 10 million instructions per VM page fault. If you are running with a rotating disk, the number is more like 100 million instructions.

What good is an O(log2(n)) algorithm if those operations cause page faults and slow disk operations? For most relevant datasets an O(n) or even an O(n^2) algorithm, which avoids page faults, will run circles around it.

周围有更多这样的算法吗？我们是否应该重新审视我们教育的所有这些基本组成部分？自己编写时还需要注意什么？

澄清:

所讨论的算法并不比已证明的最佳算法快，因为 Big-O 表示法有缺陷或毫无意义。它速度更快，因为经过验证的最佳算法依赖于现代硬件/操作系统中不正确的假设，即所有内存访问都是平等且可互换的。

Answer 1

只有当您的客户提示您的程序运行缓慢或错过关键期限时，您才需要重新检查您的算法。否则关注正确性、健壮性、可读性和易维护性。在实现这些项目之前，任何性能优化都是在浪费开发时间。

页面错误和磁盘操作可能是特定于平台的。始终分析您的代码以查看瓶颈所在。花时间在这些方面会产生最大的好处。

如果您对页面错误和磁盘操作缓慢感兴趣，您可能想知道:

• 缓存命中——面向数据的设计
• 缓存命中——减少不必要的 分支/跳跃。
• 缓存预测——收缩循环 它们适合处理器的缓存。

同样，这些项目只有在达到质量、客户投诉和剖析器分析了您的程序之后才会出现。