主页 / coding / 问题 / 78689825
Accepted
i like bananas
Asked: 2024-07-01 05:17:25 +0800 CST

如何以缓存友好的方式将项目存储在 LIFO 堆栈中？

  • 772

编辑/免责声明：

看来我对缓存行的理解是错误的，这使得这个问题不相关且具有误导性。我认为每当 CPU 尝试获取特定索引处的内存时，它也会抓取第一个索引之后的索引，但事实并非如此。请参阅 缓存行如何工作？以供参考。

我正要编写一个数据容器，用于存储连续且可调整大小的内存块，其中的项目只能通过推送或弹出从一侧访问 - 基本上是一个 LIFO 堆栈。我读了很多关于 CPU 缓存和内存访问模式的文章，并希望所述容器尽可能地缓存友好。

因此，我查看了互联网上常见的 LIFO 堆栈实现。大多数都建议使用动态数组作为基础，并通过在数组末尾添加或删除项目来访问数据。在这种情况下，空容量间隙以以下方式存储在数据之后：

 stack bottom            stack top
 array begin             V  array end
 V                       V  V
|V          data         V |V     gap     |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|8 |7 |6 |5 |4 |3 |2 |1 |0 |  |  |  |  |  |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
                        |       cache line       |

但是，这对我来说似乎不太适合缓存。每当有人查找堆栈顶部的项目时，CPU 都会从包含垃圾的间隙中获取内存，至少我是这么理解的。

间隙出现在内存块的开头，数据出现在结尾的方法是否更高效？在这种情况下，项目的索引将被反转，底部和顶部也是如此。在这种情况下，缓存行可以命中更多项目，如下所示：

                stack top               stack bottom
                V                       V
|      gap     |V          data         V |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|  |  |  |  |  |0 |1 |2 |3 |4 |5 |6 |7 |8 |
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
               |       cache line      |

我的理解正确吗？哪种方法性能更高且缓存友好？

我的假设可能完全错误。正如我所说，我看到的大多数实现都使用第一种方法，因此一定有某种原因。

干杯!

algorithm

1 个回答

  1. Best Answer

    使用数组的 LIFO 堆栈对于任一增长方向都同样具有缓存友好性，除非您有一个特定的大小模式，恰好有利于奇数大小的分配并向下增长。

    Linux或 C等高效重新分配（不复制数据）的API是围绕在分配末尾而不是开头添加新空间而设计的，因此如果您的堆栈可以超出初始分配，那么这就是支持正常方式的一个观点。至少如果您使用的分配 API 支持这些，而不是像 C++ 的残缺/那样本质上是强迫性的。mremapreallocnewdeletestd::vector

    除此之外，它们是相等的，除非您的高水位通常比 64 字节的倍数多 1 或 2 个元素，就像您在此处展示的那样，以使您的其他版本看起来不错。在该版本中，第一个推送的元素本身位于缓存行中，但堆栈顶部尚未跨入新的缓存行。

    如果您在第二个图中再添加一个元素，它将是其缓存行中唯一正在使用的元素。它看起来不错，只是因为您为当前堆栈状态挑选了一些元素，这些元素恰好与您为第一个元素选择的错位（堆栈的“底部”，位于向下增长堆栈的最高地址）配合良好（相对于缓存行边界）。

    使用向下增长的前端间隙设计，第一个被推送的元素（最高地址）可能与其他一些有用数据位于同一缓存行中，因此保持缓存行热度会很有帮助（如果您的堆栈经常变空，因此您实际上访问该元素）。
    内存分配器通常会将分配舍入为某个较大大小的倍数，例如 16 字节，但一个缓存行中仍可能有其他分配。
    不过，除非您对预期的堆栈大小和/或接下来的内容有特别的了解，否则通常您需要分配一个是缓存行大小倍数的内存块。

    有趣的事实：asm 调用堆栈在主流 ISA 上向下增长（以及不支持一个堆栈增长方向的 ISA 调用约定，如 MIPS）。例如 x86push并call减少堆栈指针寄存器 (RSP)。造成这种情况的原因不是缓存效率，更多的是历史原因，可以追溯到 CPU 拥有缓存之前。不过，它不会给 CPU 缓存带来任何特殊问题。

    CPU/asm 堆栈的分配方式使得最高地址的缓存行得到充分利用，而您的堆栈的分配末尾不是缓存行的末尾。（通常，“堆栈”是页面大小的倍数，因此同一行中不会有其他东西在其旁边。）

    • 1

相关问题