4

在实现大多数算法（排序、搜索、图遍历等）时，通常可以在减少内存访问方面做出权衡，但代价是额外的普通操作。

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

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

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

忽略操作系统的影响（因此没有内存停顿等），并假设目前是一个简单的处理器，

(1) 谁能建议 Forth 中的普通堆栈操作（例如 dup、rot、over、swap 等）与 Forth 的内存访问 fetch (@) 或 store (!) 的成本相比如何？

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

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

我试图了解 fetch 和 store 与 rot、swap、dup、drop、over、正确到一个数量级的相对成本。

4

2 回答 2

3

本文从记忆中提取一个单词需要多少时间？谈论主内存停顿时间，使用一些经验法则类型的数字，但基本上你可以在停顿主内存时执行大量指令。正如其他人所说，系统之间的数字差异很大。

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

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

附言。前进。

于 2013-03-18T01:50:51.370 回答
1

对于汇编程序来说，内存获取和寄存器操作之间的比较是可以的，因为它对于 c 编译器的输出也是如此，它实际上是一个汇编程序。在 Forth 中，这个问题几乎没有意义。首先，Forth 是一个解释器，在使用 Forth 时，人们放弃了最终的速度。当然，可以在 Forth 之上添加一个优化器，但这样问题就更没有意义了，因为 c-optimiser 和 Forth 优化器的输出会收敛到 - 你猜对了 - 一个最佳解决方案。

让我们看一下 Forth 中的一个基本运算，例如 AND。这被实现为

> CODE AND
>     POP AX
>     POP BX
>     AND AX, BX
>     PUSH AX
>     NEXT

所以我们已经看到了三个内存操作，看起来像是一个基本的计算操作。Knuth 指标似乎不适用。此外，Forth 似乎正在失去大量时间。但事实并非如此。这些内存操作都在典型处理器的 L1 高速缓存上。这与小型 c 函数中的局部变量一样有效，我们可以使用 VARIABLE 和堆栈将堆栈操作与内存操作进行比较。答案很简单。VARIABLE 存在内存停滞的风险。堆栈操作几乎肯定会命中 L1 缓存。这是一个最重要的考虑点。但是问题明确要求不要考虑它！所以在那里。

于 2020-10-18T16:29:28.573 回答