2

这可能与语言无关，但我是从 C++ 背景问的。

我正在为嵌入式系统（AVR，8 位）编写一个环形缓冲区。让我们假设：

const uint8_t size = /* something > 0 */;
uint8_t buffer[size];
uint8_t write_pointer;

如果缓冲区是 2 的幂，那么有一个巧妙的技巧可以&对写入和读取指针size-1进行有效的无分支翻转，如下所示：size

// value = buffer[write_pointer];
write_pointer = (write_pointer+1) & (size-1);

但是，如果大小不是 2 的幂，则回退可能是将指针（即索引）与大小进行比较并进行条件重置：

// value = buffer[write_pointer];
if (++write_pointer == size) write_pointer ^= write_pointer;

由于重置很少发生，因此对于任何分支预测都应该很容易。

虽然这假设指针需要在内存中向前推进。虽然这很直观，但它需要size在每次迭代中加载。我假设在常规情况下颠倒顺序（向后推进）会产生更好的 CPU 指令（即），因为仅在重置期间才需要。jump if not zerosize

// value = buffer[--write_pointer];
if (write_pointer == 0) write_pointer = size;

所以

TL; DR：我的问题是：由于缓存未命中（因为不能简单地向前读取内存），通过内存向后行进是否会对执行时间产生负面影响，或者这是一个有效的优化？

4

4 回答 4

3

你有一个带缓存的 8 位 avr？和分支预测？

就缓存而言，向前或向后有什么关系？高速缓存的命中或未命中是高速缓存行内的任何位置，开始、中间、结束、随机、连续，无关紧要。您可以从缓存行的后到前或从前到后工作，这是相同的成本（假设所有其他事情保持不变）第一个雾导致填充，然后该行在缓存中，您可以访问任何以较低的延迟以任何模式的项目，直到被驱逐。

在像这样的微控制器上，即使以丢弃一些内存为代价，您也要努力对齐循环缓冲区，以便您可以屏蔽。没有缓存指令获取很痛苦，因为它们可能来自可能比处理器时钟速率慢的闪存，因此您确实希望减少执行的指令，或者使执行更具确定性（每个循环的指令数量相同直到该任务完成）。可能有一个管道会欣赏掩蔽而不是 if-then-else。

TL; DR：我的问题是：由于缓存未命中（因为不能简单地向前读取内存），通过内存向后行进是否会对执行时间产生负面影响，或者这是一个有效的优化？

缓存不在乎，行中任何项目的未命中都会导致填充，一旦进入缓存，任何访问模式，随机，顺序向前或向后，或者只是在同一地址上敲击，在更快的内存中花费的时间更少。直到被驱逐。驱逐不会来自相邻的缓存线，它们将来自缓存线的 2 次幂，因此无论您拉出的下一个缓存线是在更高的地址还是更低的地址，成本都是相同的。

于 2013-06-16T03:51:44.793 回答
0

由于缓存未命中，在内存中向后行进是否会对执行时间产生负面影响（因为不能简单地向前读取内存）

为什么你认为你会有缓存未命中？如果您尝试访问缓存之外（向前或向后），您将遇到缓存未命中。

于 2013-06-15T22:29:31.403 回答
0

有几点需要澄清：

  1. 每次都需要加载该大小（它是常量，因此应该是不可变的）
  2. 你的代码是正确的。例如，在基于 0 的索引中（如在 C/C++ 中用于数组访问），值0' is a valid pointer into the buffer, and the valuesize' 不是。xor同样，当您可以简单地分配时，同样不需要0模运算符（writer_pointer = (write_pointer +1) % size）。
  3. 在虚拟内存的一般情况下会发生什么（即逻辑上相邻的地址可能遍布真实内存映射中的所有位置）、分页（内容很可能逐页缓存）和其他因素（来自外部进程、中断）

简而言之：这种优化会导致更多与足部相关的伤害，而不是真正的性能提升。此外，几乎可以肯定的是，使用矢量化代码 (SIMD) 可以获得更多更好的收益。

编辑：在解释语言或 JIT 语言中，假设您完全可以依赖使用和JNZ其他人可能有点乐观。在这一点上，问题是，loading size和比较与比较之间有多大的差异0。

于 2013-06-15T22:43:23.280 回答
0

像往常一样，在执行任何形式的手动代码优化时，您必须对特定硬件有广泛深入的了解。如果你没有那个，那么你不应该尝试手动优化，故事结束。

因此，您的问题充满了各种奇怪的假设：

  • 首先，您假设这write_pointer = (write_pointer+1) & (size-1)比其他方法更有效，例如您发布的 XOR 示例。您只是在这里猜测，您将不得不反汇编代码并查看哪个产生的 CPU 指令更少。

    因为，在为微型、原始的 8 位 MCU 编写代码时，内核中并没有太多的事情来加速您的代码。我不知道 AVR8，但您似乎有一个小的指令管道，仅此而已。您似乎不太可能在分支预测方面遇到很多问题。您似乎不太可能拥有数据和/或指令缓存。阅读友好的 CPU 内核手册。

  • 至于通过内存向后行进，它不太可能对您的程序性能产生任何影响。在旧的、糟糕的编译器上，如果循环条件是与零的比较而不是值，那么您将获得更高效的代码。在现代编译器上，这应该不是问题。至于缓存内存问题，我怀疑您是否需要担心缓存内存。

在 8 位 MCU 上编写高效代码的最佳方法是尽可能坚持使用 8 位算法，并避免像瘟疫一样使用 32 位算法。忘记你曾经听说过一种叫做浮点的东西。这将使您的程序高效，您不太可能找到任何更好的方法来手动优化代码。

于 2013-06-17T06:51:03.060 回答