算法现代的硬件？ [英] Algorithms for modern hardware?
问题描述
再一次，我发现自己的一组
Once again, I find myself with a set of broken assumptions. The article itself is about a 10x performance gain by modifying a proven-optimal algorithm to account for virtual memory:
在一个现代的多的问题CPU，运行 在几吉赫的时钟频率，所述 最坏情况下的损失将近1 000万 每个虚拟机缺页的说明。如果你 用旋转盘正在运行，则 数字更像亿 说明。
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.
有什么好处是O（LOG2（n））的算法 如果这些行动导致页面错误 和缓慢的磁盘操作？对于大多数 有关数据集的O（N），甚至是 为O（n ^ 2）算法，避免了页 故障，将运行兜圈子了。
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.
是否有更多这样的算法在吗？我们应该重新审视我们的教育，所有这些基本构建块？还有什么我需要注意写我自己的时候了？
Are there more such algorithms around? Should we re-examine all those fundamental building blocks of our education? What else do I need to watch out for when writing my own?
澄清：
在讨论的算法并不比成熟最优的速度更快，因为大O符号是有缺陷的或无意义的。它的速度更快，因为成熟的最优算法依赖于一个假设，即是不正确的现代硬件/操作系统，即所有内存访问是平等的，可以互换的。
The algorithm in question isn't faster than the proven-optimal one because the Big-O notation is flawed or meaningless. It's faster because the proven-optimal algorithm relies on an assumption that is not true in modern hardware/OSes, namely that all memory access is equal and interchangeable.
推荐答案
您只需要重新审视自己的算法，当你的客户抱怨你的程序的缓慢或缺少关键的最后期限。否则，注重正确性，健壮性，可读性强，易于维护。直到这些项目取得的任何性能优化是在浪费开发时间。
You only need to re-examine your algorithms when your customers complain about the slowness of your program or it is missing critical deadlines. Otherwise focus on correctness, robustness, readability, and ease of maintenance. Until these items are achieved any performance optimization is a waste of development time.
页面错误和磁盘操作可以是平台特定的。总是个人资料您code，看看那里的瓶颈。这些方面花费的时间会产生最大的效益。
Page faults and disk operations may be platform specific. Always profile your code to see where the bottlenecks are. Spending time on these areas will produce the most benefits.
如果你有兴趣，再加上页面错误和缓慢的磁盘操作，你可能想知道的：
If you're interested, along with page faults and slow disk operations, you may want to aware of:
- 在缓存命中 - 面向设计数据
- 在缓存命中率 - 减少不必要的 分支/跳转。
- 缓存prediction - 收缩循环使 他们到合适的处理器的缓存。
- Cache hits -- Data Oriented Design
- Cache hits -- Reducing unnecessary branches / jumps.
- Cache prediction -- Shrink loops so they fit into the processor's cache.
此外，这些项目的质量已经达到后才，客户投诉和分析器分析了您的程序。
Again, these items are only after quality has been achieved, customer complaints and a profiler has analyzed your program.
这篇关于算法现代的硬件？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
