12

我正在查看 Don Knuth 教授的一些代码，这些代码用 CWEB 编写并转换为 C。一个具体的例子是 dlx1.w，可从Knuth 的网站获得

在某一阶段，结构 nd[cc] 的 .len 值会递减，并且以一种笨拙的方式完成：

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

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

我的问题是：为什么 Knuth 会这样写，而不是

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 来说会异常冗长，但也许这是本能的备忘录而不是说教。

对于它的价值，我在CWEB 文档中进行了搜索，但没有找到答案。我的问题可能更多地与 Knuth 的标准做法有关，我正在一点一点地学习。我会对将这些实践作为一个整体进行布局（并且可能受到批评）的任何资源感兴趣——但现在，让我们专注于 Knuth 以这种方式编写它的原因。

4

2 回答 2

4

初步说明：对于 Knuth 风格的文学编程（即在阅读 WEB 或 CWEB 程序时），Knuth 设想的“真实”程序既不是“源”<code>.w 文件，也不是生成的（纠结的）.c文件，但排版（编织）输出。最好将源.w文件视为生成它的一种手段（当然还有.c提供给编译器的源文件）。（如果你手边没有 cweave 和 TeX；我已经在这里排版了其中的一些程序；这个程序DLX1 在这里。）

所以在这种情况下，我将代码中的位置描述为 DLX1 的模块 25，或子程序“cover”：

问题

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

这在第 1.3.1 节（分册 1的一部分）中有详细说明：

定时。[…] 程序的运行时间不仅取决于时钟频率，还取决于可以同时活动的功能单元的数量以及它们的流水线化程度；它取决于用于在执行指令之前预取指令的技术；它取决于用于产生 2 64 个虚拟字节错觉的随机存取存储器的大小；它取决于缓存和其他缓冲区等的大小和分配策略等。

出于实际目的，MMIX通常可以通过为每个操作分配固定成本来令人满意地估计程序的运行时间，该成本基于在具有大量主内存的高性能机器上获得的近似运行时间；所以这就是我们要做的。假设每个操作采用整数 υ，其中 υ（发音为“oops”）是表示流水线实现中的时钟周期时间的单位。尽管 υ 的值随着技术的进步而降低，但我们始终跟上最新的进步，因为我们以 υ 为单位测量时间，而不是以纳秒为单位。我们估计的运行时间也将假定取决于程序使用的内存引用或内存的数量；这是加载和存储指令的数量。例如，我们假设每个LDO(load octa) 指令成本 µ + υ，其中 µ 是内存引用的平均成本。程序的总运行时间可能会报告为 35µ+ 1000υ，意思是“35 mems 加上 1000 oops”。μ/υ比值多年来一直在稳步增加；没有人确切知道这种趋势是否会持续下去，但经验表明 µ 和 υ 值得独立考虑。

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

尽管我们经常使用表 1 的假设来估计运行时间，但我们必须记住，实际运行时间可能对指令的顺序非常敏感。例如，如果我们在发出命令和需要结果之间找到 60 件其他事情要做，那么整数除法可能只需要一个周期。如果多个 LDB（加载字节）指令引用相同的八字节，则它们可能只需要引用一次内存。然而，加载命令的结果通常不能在紧随其后的指令中使用。经验表明，有些算法可以很好地处理高速缓存，而另一些则不行；因此 µ 并不是真正的常数。甚至指令在内存中的位置也会对性能产生重大影响，因为有些指令可以与其他指令一起获取。[…] 只有元模拟器可以提供有关程序在实践中的实际行为的可靠信息；但这样的结果可能难以解释，因为可能有无限多的配置。这就是为什么我们经常求助于表 1 中更简单的估计。

最后，我们可以使用 Godbolt 的Compiler Explorer查看典型编译器为此代码生成的代码。（理想情况下，我们会查看 MMIX 指令，但由于我们无法做到这一点，所以让我们满足于那里的默认设置，这似乎是 x68-64 gcc 8.2。）我删除了所有的os 和oos。

对于代码版本：

  /*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 程序集了解不多）只是前一种情况下生成的代码的串联（除了使用 registeredx而不是r14d），因此在一行中写入减量并没有保存你任何mems。特别是，将其视为单个是不正确的，尤其是cover在这种算法中被称为大量次数的情况（为精确覆盖而跳舞的链接）。

所以 Knuth 写的版本是正确的，因为它的目标是计算 mem 的数量。正如您所观察到的，他也可以写oo,nd[cc].len--;（数两个 mem），但在这种情况下，乍一看它可能看起来像一个错误。（顺便说一句，在您的示例中，oo,nd[k].len--,nd[k].aux=i-1;两个 mem 的问题来自 load 和 store in --；而不是两个商店。）

于 2018-12-30T19:22:48.687 回答
3

这整个实践似乎是基于对 C 如何工作的错误想法/模型，即抽象机器执行的工作与执行的实际程序之间存在某种对应关系（即“C 是可移植汇编程序”的谬误）。我认为我们无法回答更多关于为什么会出现该确切代码片段的问题，除了它碰巧是一个不寻常的习惯用法，用于将抽象机器上的负载和存储分别计数。

于 2018-12-30T17:59:51.007 回答