c - 为什么 Knuth 使用这种笨拙的减量？

Question

我正在查看 Don Knuth 教授的一些代码，这些代码是用 CWEB 编写并转换为 C 语言的。具体示例是 dlx1.w，可从 Knuth's website 获取。

在某个阶段，struct nd[cc] 的 .len 值会递减，并且是以一种笨拙的方式完成的:

  o,t=nd[cc].len-1;
  o,nd[cc].len=t;

(这是一个特定于 Knuth 的问题，所以也许您已经知道“o”是一个用于递增“mems”的预处理器宏，“mems”是通过访问 64 位字来衡量的运行总工作量.)“t”中剩余的值绝对不会用于其他任何用途。 (此处的示例位于 dlx1.w 的第 665 行，或 ctangle 之后的 dlx1.c 的第 193 行。)

我的问题是:为什么高德纳这样写，而不是

nd[cc].len--;

他确实在其他地方使用过(dlx1.w 的第 551 行):

oo,nd[k].len--,nd[k].aux=i-1;

(“oo”是一个类似的宏，用于将“mems”递增两次 - 但这里有一些微妙之处，因为 .len 和 .aux 存储在同一个 64 位字中。为 S.len 赋值和 S.aux，通常只计算 mems 的一个增量。)

我唯一的理论是减量由两次内存访问组成:首先查找，然后分配。 (对吗？)而这样的写法是为了提醒两个步骤。对于 Knuth 来说，这可能是异常冗长的，但也许这是本能的备忘录，而不是说教。

对于它的值(value)，我在 CWEB documentation 中进行了搜索没有找到答案。我的问题可能更多地与高德纳的标准实践有关，我正在一点一点地学习。我会对将这些实践作为一个 block 进行布局(并且可能受到批评)的任何资源感兴趣 - 但现在，让我们关注 Knuth 为什么这样写。

Answer 1

初步评论:对于 Knuth 风格的文学编程(即，当阅读 WEB 或 CWEB 程序时)，Knuth 所设想的“真实”程序既不是“源” .w文件也不是生成的(纠结).c文件，而是排版(编织)输出。来源.w文件最好被认为是生成它的一种方法(当然还有提供给编译器的 .c 源代码)。 (如果你没有方便的 cweave 和 TeX；我已经排版了其中一些程序 here ；这个程序 DLX1 is here 。)

因此，在这种情况下，我将代码中的位置描述为 DLX1 的模块 25，或子例程“cover”:

无论如何，回到实际问题:请注意，这个(DLX1)是为计算机编程艺术编写的程序之一。由于报告程序所花费的时间“秒”或“分钟”逐年变得毫无意义，因此他用“mems”加上“oops”来报告程序花费的时间，这由“mems”主导，即对 64 位字的内存访问次数(通常)。因此，书中包含诸如“该程序在 3.5 gigamems 的运行时间内找到该问题的答案”之类的陈述。此外，这些陈述基本上是关于程序/算法本身，而不是针对某些硬件的特定版本的编译器生成的特定代码。 (理想情况下，当细节非常重要时，他会在 MMIX 或 MMIXAL 中编写程序，并在 MMIX 硬件上分析其操作，但这种情况很少见。)对 mems 进行计数(如上报告)是插入 o 的目的。和oo指令到程序中。请注意，对于多次执行的“内循环”指令(例如子例程 cover 中的所有内容)，正确执行此操作更为重要。在这种情况下。

第 1.3.1′ 节对此进行了详细说明(Fascicle 1 的一部分):

Timing. […] The running time of a program depends not only on the clock rate but also on the number of functional units that can be active simultaneously and the degree to which they are pipelined; it depends on the techniques used to prefetch instructions before they are executed; it depends on the size of the random-access memory that is used to give the illusion of 2⁶⁴ virtual bytes; and it depends on the sizes and allocation strategies of caches and other buffers, etc., etc.

For practical purposes, the running time of an MMIX program can often be estimated satisfactorily by assigning a fixed cost to each operation, based on the approximate running time that would be obtained on a high-performance machine with lots of main memory; so that’s what we will do. Each operation will be assumed to take an integer number of υ, where υ (pronounced “oops”) is a unit that represents the clock cycle time in a pipelined implementation. Although the value of υ decreases as technology improves, we always keep up with the latest advances because we measure time in units of υ, not in nanoseconds. The running time in our estimates will also be assumed to depend on the number of memory references or mems that a program uses; this is the number of load and store instructions. For example, we will assume that each LDO (load octa) instruction costs µ + υ, where µ is the average cost of a memory reference. The total running time of a program might be reported as, say, 35µ+ 1000υ, meaning “35 mems plus 1000 oops.” The ratio µ/υ has been increasing steadily for many years; nobody knows for sure whether this trend will continue, but experience has shown that µ and υ deserve to be considered independently.

他当然明白与现实的区别:

Even though we will often use the assumptions of Table 1 for seat-of-the-pants estimates of running time, we must remember that the actual running time might be quite sensitive to the ordering of instructions. For example, integer division might cost only one cycle if we can find 60 other things to do between the time we issue the command and the time we need the result. Several LDB (load byte) instructions might need to reference memory only once, if they refer to the same octabyte. Yet the result of a load command is usually not ready for use in the immediately following instruction. Experience has shown that some algorithms work well with cache memory, and others do not; therefore µ is not really constant. Even the location of instructions in memory can have a significant effect on performance, because some instructions can be fetched together with others. […] Only the meta-simulator can be trusted to give reliable information about a program’s actual behavior in practice; but such results can be difficult to interpret, because infinitely many configurations are possible. That’s why we often resort to the much simpler estimates of Table 1.

最后，我们可以使用Godbolt的Compiler Explorer查看典型编译器为此代码生成的代码。 (理想情况下，我们会查看 MMIX 指令，但由于我们无法做到这一点，所以让我们采用默认值，这似乎是 x68-64 gcc 8.2。)我删除了所有 o和 oo s。

对于代码版本:

  /*o*/ t = nd[cc].len - 1;
  /*o*/ nd[cc].len = t;

第一行生成的代码是:

  movsx rax, r13d
  sal rax, 4
  add rax, OFFSET FLAT:nd+8
  mov eax, DWORD PTR [rax]
  lea r14d, [rax-1]

第二行是:

  movsx rax, r13d
  sal rax, 4
  add rax, OFFSET FLAT:nd+8
  mov DWORD PTR [rax], r14d

对于代码版本:

  /*o ?*/ nd[cc].len --;

生成的代码是:

  movsx rax, r13d
  sal rax, 4
  add rax, OFFSET FLAT:nd+8
  mov eax, DWORD PTR [rax]
  lea edx, [rax-1]
  movsx rax, r13d
  sal rax, 4
  add rax, OFFSET FLAT:nd+8
  mov DWORD PTR [rax], edx

正如你所看到的(即使对 x86-64 汇编不太了解)只是前一种情况中生成的代码的串联(除了使用寄存器 edx 而不是 r14d )，所以它并不像如果将减量写在一行中可以节省您的内存。特别是，将其算作单个是不正确的，尤其是像 cover 这样的东西。这在该算法中被调用了很多次(通过跳舞链接来实现精确覆盖)。

因此 Knuth 编写的版本是正确的，因为它的目标是计算内存数量。他还可以写oo,nd[cc].len--; (数两个内存)正如您所观察到的，但在这种情况下乍一看可能看起来像是一个错误。 (顺便说一句，在您的问题 oo,nd[k].len--,nd[k].aux=i-1; 的示例中，两个 mems 来自 -- 中的负载和存储；而不是两个存储。)