算法复杂度分析:实际使用Knuth的普通操作(oops)和内存操作(mems)方法

Question

在实现大多数算法(排序、搜索、图遍历等)时，常常会在减少内存访问方面进行权衡，而代价是额外的普通操作。

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

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

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

忽略操作系统的影响(因此没有内存中断，等等)，假设目前有一个简单的处理器，

(1)谁能建议普通的如何在Forth中堆栈操作(例如dup、rot、over、swap等)与Forth的内存访问获取(@)或存储(!) ?的成本进行比较

(2)我是否可以用经验法则来决定有多少普通操作可以用来交换以节省内存访问呢？

我要找的是‘内存访问成本高达50个普通操作，或500个普通操作，或5个普通操作’之类的东西

我试着了解获取和存储与rot、交换、dup、dup和rot、dup、dup和rot的相对开销。

Answer 1

内存获取和寄存器操作之间的比较对于汇编程序来说是可以的，就像对c编译器的输出一样，它实际上是一个汇编程序。第四，这个问题很难理解。首先，Forth是一个解释器，在使用第四种语言时，速度是最高的。当然，可以在Forth的基础上添加一个优化器，但是这个问题就更没有意义了，因为c-优化器和第四优化器的输出收敛到--你猜到了--一个最优解。

让我们看一个基本的运算在Forth喜欢和。这是作为

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

因此，我们已经看到了三个内存操作，看起来像是一个基本的计算操作。看来Knuth度量不适用。另外，Forth似乎正在放松大的time.That，但事实并非如此。这些内存操作都放在典型处理器的L1缓存中。这与小c函数中的局部变量一样有效，我们可以使用变量和堆栈来比较堆栈操作和内存操作。答案很简单。变量可能会导致内存失速。堆栈操作几乎肯定是L1缓存命中。这是一个最重要的考虑点。然而，这个问题明确要求不要考虑它！这就是了。

Answer 2

本文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程序员都可以阅读。

Ps。去福斯。