performance - 算法复杂度分析 : practically using Knuth's Ordinary Operations (oops) and Memory Operations (mems) method

Question

在实现大多数算法(排序、搜索、图形遍历等)时，经常需要权衡以减少内存访问，同时增加普通操作。

Knuth 有一个有用的方法来比较各种算法实现的复杂性，方法是从特定处理器中抽象出来，只区分普通操作 (oops) 和内存操作 (mems)。

在编译程序中，通常让编译器组织低级操作，并希望操作系统能够处理数据是保存在缓存内存(更快)还是虚拟内存(更慢)中的问题。此外，指令的确切数量/成本由编译器封装。

有了 Forth，不再有这样的封装，并且更接近于机器，尽管可能更接近于运行在寄存器处理器之上的堆栈机器。

忽略操作系统的影响(因此没有内存停顿等)，并暂时假设一个简单的处理器，

(1) 任何人都可以建议 Forth 中的普通堆栈操作(例如 dup、rot、over、swap 等)与 Forth 的内存访问 fetch ( @) 或存储 (!)？

(2) 是否有经验法则可以用来决定有多少普通操作与保存内存访问权衡？

我正在寻找的是“内存访问成本高达 50 个普通操作，或 500 个普通操作，或 5 个普通操作”之类的 Ballpark 绝对没问题。

我正在尝试了解获取和存储与循环、交换、复制、删除、结束、更正到一个数量级的相对开销。

Answer 1

本文How much time does it take to fetch one word from memory?谈论主内存停顿时间，有一些经验法则类型的数字，但基本上你可以在主内存停顿时执行很多指令。正如其他人所说，系统之间的数字差异很大。

主内存停顿是一个值得关注的大领域，尤其是当 CPU 具有更多内核时，但内存带宽通常不会快很多。也有一些研究正在围绕压缩主内存中的数据进行，以便 CPU 可以利用“备用”周期和紧凑的缓存行 http://oai.cwi.nl/oai/asset/15564/15564B.pdf

对于那些真正对细节感兴趣的人，大多数 CPU 制造商都发布了关于内存优化等方面的深度指南。主要针对高端和编译器编写者，但所有 2gl 和 3gl 程序员都可以阅读。

附言。前进。