5

我在这里有一个循环，我想让它运行得更快。我正在传递一个大数组。我最近听说达夫的设备可以应用于这个for循环吗？有任何想法吗？

for (i = 0; i < dim; i++) {
    for (j = 0; j < dim; j++) {
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
    }
}
4

13 回答 13

19

请，请不要使用达夫的设备。一千名维护程序员会感谢你的。我曾经在一家培训公司工作，有人认为在他们的 C 编程课程的前十页中介绍该设备很有趣。作为一名讲师，这是不可能处理的，除非（就像编写该课程的那个人显然那样）你相信“kewl”编码。

不用说，我尽快从课程中删除了这个东西。

于 2010-04-30T21:35:15.320 回答
5

为什么要让它跑得更快？

是否存在实际性能问题？

如果是这样，您是否进行了分析并发现它执行得足够频繁，因此值得优化？

如果是这样，您可能希望以两种方式编写它，您现在使用的直接方式和使用 Duff 的设备，或者您喜欢的任何其他方式。

此时，您将测试性能。你可能会感到惊讶。现代优化器相当不错，现代 CPU 真的很复杂，所以源代码级优化往往适得其反。（我曾经在一个花费大量时间的循环中执行此操作，发现收紧循环，即使在引入一些间接性的同时，也可以提高性能。你的里程几乎肯定会有所不同。）

最后，如果 Duff 的设备确实更快，您必须决定性能改进是否值得采用这种直接且可优化的代码，并在下一个编译器版本中替换一个可能根本不会提高性能的维护问题。

于 2010-04-30T21:57:51.937 回答
3

你不应该手动展开循环。如果有的话，它只会给你一个非常特定于平台的优势。所有好的编译器都可以展开循环，但甚至不能保证让代码更快，因为从主内存读取更长的程序会占用更多的内存带宽。

如果您希望循环快速运行，您应该确保 RIDX 计算的任何内容dst都是按顺序访问的，因此您可以最大限度地减少缓存未命中的数量。除此之外，我看不出如何使循环更快。

于 2010-04-30T21:46:00.477 回答
2

Duff's Device 只是一种循环展开的技术。由于可以展开任何循环，因此您可以使用 Duff 的设备。

于 2010-04-30T21:37:04.740 回答
2

如果您能够弄清楚这一点并获得收益，那将是微不足道的，并且绝不会证明复杂性是合理的。

你最好把精力花在一个水平上——重新考虑你的整个解决方案。也许与其复制值，不如创建一个翻译数组，并在需要时花更多时间间接查找答案（构建图像并不是一个好主意——只是试图给你一种不同的方式来看待它）。

或者也许有一些完全不同的方法——看看你的整个问题，尝试完全抛弃你当前的方法和概念，看看是否有一些你没有考虑过的东西，因为你太依赖这个实现了。

你的显卡可以做这些工作吗？

在高层次上重新思考问题比您想象的要频繁得多。

编辑：更多地查看您的样本，看起来您正在获取图像块并将其逐个像素地复制到另一个图像中。如果是这样，几乎可以肯定有一些方法可以摆脱宏并逐字节复制，或者甚至使用块移动汇编函数然后调整结果的边缘以匹配。

或者我可能猜错了，但很有可能在比逐个像素更大的范围内查看它可能比展开循环更有帮助。

于 2010-04-30T21:38:49.400 回答
2

执行语句的指令周期数

dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];

将远远超过循环开销，因此展开循环在百分比基础上的帮助很小。

于 2010-05-01T01:07:08.300 回答
1

我相信这是 Duff 设备的候选者，具体取决于 RIDX() 函数的作用。但我希望您不要指望有人为您编写代码……此外，您可能希望正确地格式化您的代码，以便它实际上是可读的。

于 2010-04-30T21:31:47.673 回答
1

可能，只要 dim 是 2 的幂，或者您的目标系统具有快速模数。今天学到了新东西。我在 5 年前独立发现了这个结构，并将其放入我们的 memCopy() 例程中。谁知道 ：）

于 2010-04-30T21:32:23.067 回答
0

迂腐，没有。Duff 的设备用于写入硬件寄存器（因此副本的目标始终是相同的地址）。

您可以为这样的副本实现非常类似于 Duff 的设备的东西，但会有清晰度和维护成本。我会先进行分析以确保这是一个问题。我还会研究您是否可以简化索引，因为这可能使编译器能够完成展开循环的繁琐工作。

于 2010-04-30T22:20:58.150 回答
0

如果您使用它，请确保您对其进行测量以确定改进对于您的性能要求而言是真实的、重要的和必要的。我怀疑它会是。

对于大循环，由 Duff 的设备处理的余数在操作中将是微不足道的一部分，而对于余数很重要的小循环，只有当你有很多这样的循环（它们自己在一个循环中）时，你才会看到好处，因为小根据定义，循环不会花费那么长时间！即使这样，编译器的优化器也可能会做得更好或更好，而不会使您的代码不可读。Duff 设备的应用也有可能会阻止优化器应用更有效的优化，这就是为什么如果你使用它，你需要测量它。

您可能一直在节省时间（如果有的话），您可能已经浪费了好几次阅读对这个问题的回复。

于 2010-04-30T22:24:16.780 回答
0

Duff 的设备可能不是展开循环中的优化解决方案。

我有一个功能，它向一个端口发送一个位，然后向另一个端口发送一个时钟脉冲。对于每一位，功能是：

  if (bit == 1)
  {
     write to the set port.
  }
  else
  {
     write to the clear port.
  }
  write high clock bit.
  write low clock bit.

这被放入 Duff 的设备循环中，同时进行位移位和位计数递增。

我通过使用半字节值而不是位（半字节为 4 位）提高了循环的效率。switch 语句基于半字节值。这允许在没有任何if语句的情况下处理 4 位，从而改善通过指令缓存（管道）的流程。

有时 Duff 的设备可能不是最佳解决方案；但可以成为更有效解决方案的基础。

于 2010-05-01T01:06:03.677 回答
0

当优化开启时，现代编译器已经为你做循环展开，这使得 Duff 的设备过时了。编译器比您更了解编译目标的最佳展开级别，您无需编写任何额外的代码来执行此操作。这在当时是一种巧妙的 hack，但如今 Duff 的设备只是一种历史奇闻，而不是一种好的编程实践。

于 2010-08-28T12:32:07.437 回答
0

最后，无论是谁调用优化，每个参与的人都需要确保它有良好的文档记录，并以尽可能自我记录的风格编写，为变量、函数等使用正确拼写的有意义的名称。所以很明显，如果评论和代码不同步。

优化的需求永远不会结束。我正在和一个研究生交谈，他破坏了 malloc()/free() 处理有史以来最大的遗传数据文件一次尝试。之后堆变得太碎片化，malloc 无法找到一块连续的 RAM 来分配给调用函数。他不得不切换到一个 malloc 只在 32k 边界上发布内存块的库。旧库占用的内存增加了 160%，运行速度慢了很多，但它完成了工作。

您必须小心使用 Duff 的设备和许多其他优化，以确保编译器不会将您的优化优化为模糊的损坏的目标代码。当我们进入一个使用自动并行化工具的环境时，这将成为一个更大的问题。

我预计优化级别越低，未来的优化就越有可能破坏代码。我可以看到，我在设计为在多个平台上运行的代码中丢弃换行符并将换行符放回到每个平台上的打印和写入函数中的习惯将在该线程中讨论的一些事情中遇到问题。

-gcouger

于 2012-01-12T22:34:39.217 回答